N皇后放置算法
我正在解决N皇后问题，我们需要在NXN棋盘上放置N个皇后，这样两个皇后就不会互相攻击。
#include #include #include int size=8; char arr[8][8]; int i,j; void initializeBoard() { for(i=0;i<size;i++) { for(j=0;j<size;j++) { arr[i][j]='.'; } } } void printArray() { for(i=0;i<size;i++) { for(j=0;j<size;j++) { printf("%c\t",arr[i][j]); } printf("\n"); } printf("\n\n"); } void placeQueen(int i,int j) { arr[i][j]='Q'; } int isAvailable(int i,int j) { int m,n,flag; for(m=0;m<i;m++) { for(n=0;n<size;n++) { int k=abs(im); int l=abs(jn); if(arr[m][j]!='Q' && arr[k][l]!='Q') { flag=1; } else { flag=0; break; } } } return flag; } int main(void) { initializeBoard(); for(i=0;i<size;i++) { for(j=0;j<size;j++) { if(isAvailable(i,j)==1) { // means that particular position is available // and so we place the queen there placeQueen(i,j); break; } } } printArray(); return 0; } 我认为问题在于isAvailable（）方法。 但是，我无法找到错误。 请帮我识别一下。
我采取的方法是否涉及回溯？ 如果没有，请提供相同的解释
你的方法没有回溯。 它迭代了一些可能性，而不是全部。 这个问题最好以递归的方式解决，所以我不会像你那样做。 你必须为女王受其他人攻击的规则定义。 您可以使用ifs和递归来再次应用规则并进行迭代。 大多数回溯算法都是递归写入的。 我会给你一个答案，所以你可以把你的答案放在我的身上。
#include #include int count = 0; void solve(int n, int col, int *hist) { int i, j; if (col == n) { printf("\nNo. %d\n-----\n", ++count); for (i = 0; i < n; i++, putchar('\n')) for (j = 0; j < n; j++) putchar(j == hist[i] ? 'Q' : ((i + j) & 1) ? ' ' : '.'); return; } # define attack(i, j) (hist[j] == i || abs(hist[j] - i) == col - j) for (int i = 0, j = 0; i < n; i++) { for (j = 0; j < col && !attack(i, j); j++); if (j < col) continue; hist[col] = i; solve(n, col + 1, hist); } } int main(int n, char **argv) { if (n <= 1 || (n = atoi(argv[1])) <= 0) n = 8; int hist[n]; solve(n, 0, hist); }
回溯的方式如下：
- 创建约束（规则）以检查条件是否满足。
- 将问题视为搜索树 。 搜索此树所花费的时间基于
n，即电路板的大小。 搜索的最佳方式是递归，因此请记住，解决的智能方法是使用递归。 - 在该代码中，第一组
for循环只打印出板，并检查是否找到Q -
# define attack(i, j) (hist[j] == i || abs(hist[j] - i) == col - j)是我的规则，断言2个皇后不互相攻击。 - 第二组
for循环在约束规则中找到可以插入另一个后置的条件。 - 然后我再次调用find函数。 这就是回溯的方式。
- 我的基本情况是2个皇后可以在板上，然后我将递归检查是否可以添加另一个女王直到8。因此，2 + 1 =（1 + 1）+ 1 = 1（1 + 1）。 再次应用规则，我们有3 + 1 =（2）+ 1 + 1 =（2）+（1 + 1），再次4 =（3）+ 1 + 1 =（3）+（1 + 1） 。
- 递归为你做到了。 让我们一遍又一遍地应用规则。 那么
f(n+1) = f(n) + 1对于那种情况而f(2) = 2是我的基本情况。 - 回溯的基础是，如果其中一个分支无法运行，您可以向上一级并搜索另一个分支，依此类推，直到所有树都被搜索出来。 再次，递归是要走的路。
之前完成此问题，并非所有展示位置都允许有效解决问题。
你的解决方案包括总是将一个女王放在位置（0,0），这将始终可用。
无论何时你经历一切都无法找到任何东西，你将需要进行回溯，或者你需要依赖一个解决方案，将所有女王随机放置并检查解决方案（这种方法实际上比你想象的要快得多） ，但同时，随机因此在一般情况下非常低效）
潜在的伪解决方案：
while(!AllQueensPlaced){ for(going through the array ){ if(isAvailable()) { placeQueen(); lastQueenPlaced = some logical location of last queen; } } if(!AllQueensPlaced) { backtrack(lastQueenPlaced); } }
您的回溯方法应将lastQueenPlaced标记为脏并再次遍历数组以查找新位置，然后再次执行while循环。 不要忘记在backtrack（）中更改lastQueenPlaced，以防它也是lastQueenPlaced。
使用单维数组来跟踪可以在每行中放置女王的列。
女王可以受到威胁的条件可以表示为1）ColumnForRow [i] == ColumnForRow [j] – 它们将在同一列2）（ColumnForRow [i] – ColumnForRow [j]）==（i- j）或（ColumnForRow [j] – ColumnForRow [i]）==（i – j） – 它们将在同一对角线上。
公共课NQueenSolver {
static int BOARD_SIZE = 15; static int count = 0; static int columnForRow[] = new int[BOARD_SIZE]; public static void main(String[] args) { PlaceQueen(0); System.out.println(count); } static boolean check(int row) { for (int i = 0; i < row; i++) { int diff = Math.abs(columnForRow[i] - columnForRow[row]); if (diff == 0 || diff == row - i) return false; } return true; } static void PlaceQueen(int row) { if (row == BOARD_SIZE) { printBoard(); ++count; return; } for (int i = 0; i < BOARD_SIZE; i++) { columnForRow[row] = i; if (check(row)) { PlaceQueen(row + 1); } } } private static void printBoard() { //System.out.println(Arrays.toString(columnForRow)); for (int i = 0; i < BOARD_SIZE; i++) { for (int j = 0; j < BOARD_SIZE; j++) { if (columnForRow[i] == j) System.out.print("Q "); else System.out.print("* "); } System.out.println(); } System.out.println(); }
}
你的代码没有递归方法，这是设计回溯算法时应该首先考虑的问题。 因此，您没有在此处实施任何回溯策略。
你的函数isAvailable（）在很多方面都是不完整的。
要检查已放置的皇后是否有单元格（行，列）受到攻击，您可以使用以下策略。
注意事项：
-
逐行放置皇后
-
为了将女王放在第i行，我们需要检查与放置在0到第（i-1）行的皇后的冲突。
-
女王水平，垂直和对角地攻击。
代码（参考：Tushar Roy的讲座/代码）
boolean isSafe = true; for(int queen = 0; queen
希望这可以帮助。