棋盘推理是什么,棋盘合集

N皇后问题是一个比较经典的问题其主要目标是在N×N的棋盘上放置N个皇后要求所有皇后之间不能互相攻击即任意两个皇后不能处在同一行、同一列或同一对角线上。解决该问题可以采用递归的方式基于(N-1)×棋盘的解的情况推出N×N棋盘的解的情况。

解决N皇后问题的关键在于如何放置皇后。可以用一个二维数组board表示棋盘其中board[i][j]表示第i行第j列是否放置了皇后。对于每一行i遍历该行的每一列j判断该位置是否可以放置皇后。如果可以放置将board[i][j]置为1继续判断下一行。如果不能放置继续遍历该行的下一列。如果遍历完该行的所有列都不能放置皇后则返回上一行重新遍历该行的下一列。

对于基于(N-1)×棋盘的解的情况推出N×N棋盘的解的情况可以分为两个步骤

1.复制(N-1)×棋盘的解到N×N棋盘 2.在N×N棋盘上填充第N个皇后

具体实现方式如下

复制(N-1)×棋盘的解到N×N棋盘 对于(N-1)×棋盘的解可以直接复制到N×N棋盘的前N-1行第N行先不填充皇后之后再填充。

在N×N棋盘上填充第N个皇后 对于第N行遍历该行的每一列j判断该位置是否可以放置皇后。如果可以放置将board[N][j]置为1继续填充下一行。如果不能放置继续遍历该行的下一列。如果遍历完该行的所有列都不能放置皇后则返回上一行重新遍历该行的下一列。

最终得到的解就是N×N棋盘上所有皇后都不互相攻击的放置方案。