什么是回溯？

回溯是找到问题的解决方案，其中解决方案取决于先前采取的步骤。例如，在迷宫问题中，解决方案取决于您逐个采取的所有步骤。如果这些步骤中的任何一个是错误的，那么它将不会引导我们解决问题。在迷宫问题中，我们首先选择一条路径并继续沿着它移动。但是一旦我们理解了特定的路径是不正确的，那么我们就回过头来改变它。这就是回溯基本上是什么。

在回溯中，我们先迈出一步，然后我们看看这一步采取的是否正确，即它是否会给出正确答案。如果没有，那么我们就回过头来改变我们的第一步。通常，这是通过递归来完成的。因此，在回溯中，我们首先从问题的部分子解决方案（可能会或可能不会引导我们解决方案）开始，然后检查我们是否可以继续进行此子解决方案。如果没有，那么我们就回来改变它。

因此，回溯的一般步骤是：

从子解决方案开始检查此子解决方案是否会导致解决方案如果没有，则返回并更改子解决方案并再次继续NxN棋盘上的N个女王

回溯最常见的例子之一是在NxN棋盘上安排N个皇后，这样任何女王都不会击倒任何其他女王。女王可以水平，垂直或对角攻击。也以类似的方式尝试解决该问题。我们首先任意放置第一个女王，然后将下一个女王放在任何安全的地方。我们继续此过程，直到未放置的皇后数变为零（找到解决方案）或没有安全的地方。如果没有安全的地方，那么我们改变先前放置的女王的位置。

上图显示了NxN棋盘，我们必须在其上放置N个皇后。所以，我们将从第一位女王开始。

现在，第二步是将第二个女王置于安全位置，然后是第三个女王。

现在，你可以看到我们可以把最后一位女王放在一个安全的地方。所以，我们只会改变前任女王的位置。这是回溯。

此外，没有其他位置我们可以放置第三个女王，所以我们将再回去一步并改变第二个女王的位置。

现在我们将再次将第三位女王置于安全位置，直到我们找到解决方案。

我们将继续这个过程，最后，我们将得到如下所示的解决方案。

现在你已经了解了回溯，让我们现在编码上面使用回溯方法将N个皇后放置在NxN棋盘上的问题。

import java.util.*;class Queen{ //number of queens private static int N; //chessboard private static int[][] board = new int[100][100]; //function to check if the cell is attacked or not private static boolean isAttack(int i,int j) { int k,l; //checking if there is a queen in row or column for(k=0;k<N;k++) { if((board[i][k] == 1) || (board[k][j] == 1)) return true; } //checking for diagonals for(k=0;k<N;k++) { for(l=0;l<N;l++) { if(((k+l) == (i+j)) || ((k-l) == (i-j))) { if(board[k][l] == 1) return true; } } } return false; } private static boolean nQueen(int n) { int i,j; //if n is 0, solution found if(n==0) return true; for(i=0;i<N;i++) { for(j=0;j<N;j++) { //checking if we can place a queen here or not //queen will not be placed if the place is being attacked //or already occupied if((!isAttack(i,j)) && (board[i][j]!=1)) { board[i][j] = 1; //recursion //wether we can put the next queen with this arrangment or not if(nQueen(n-1)==true) { return true; } board[i][j] = 0; } } } return false; } public static void main(String[] args) { Scanner s = new Scanner(System.in); //taking the value of N System.out.println("Enter the value of N for NxN chessboard"); N = s.nextInt(); int i,j; //calling the function nQueen(N); //printing the matix for(i=0;i<N;i++) { for(j=0;j<N;j++) System.out.print(board[i][j]+"\t"); System.out.print("\n"); }  }}

整理不易，请大家收藏，关注，接下来将会给大家提供更多的笔记资料。