n皇后(Java)(dfs+回溯)

问题描述:
八皇后问题&＃xff0c;是一个古老而著名的问题&＃xff0c;是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出&＃xff1a;

在8X8格的国际象棋上摆放八个皇后&＃xff0c;使其不能互相攻击&＃xff0c;即任意两个皇后都不能处于同一行、同一列或同一斜线上&＃xff08;斜率为1&＃xff09;&＃xff0c;问有多少种摆法。高斯认为有76种方案。

让我们来举个栗子&＃xff0c;下图的绿色格子是一个皇后在棋盘上的“封锁范围”&＃xff0c;其他皇后不得放置在这些格子&＃xff1a;

题解:

public class Practice_n皇后问题 {static int n;//表示列数,行数static int[] rec;static int cnt;public static void main(String[] args) {n &＃61; 4;rec &＃61; new int[4];dfs(0);System.out.println(cnt);}private static void dfs(int row) {if (row &＃61;&＃61; n) {cnt&＃43;&＃43;;return;}//依次尝试在某一列上放皇后for (int col &＃61; 0; col < n; col&＃43;&＃43;) {boolean ok &＃61; true;//检验这个皇后是否和之前放的皇后有冲突for (int i &＃61; 0; i < row; i&＃43;&＃43;) {if (rec[i] &＃61;&＃61; col || (i - rec[i]) &＃61;&＃61; (row - col) || (i &＃43; rec[i]) &＃61;&＃61; (row &＃43; col)) {ok &＃61; false;break;}}//这下面一步可以认为是剪枝操作if (ok) {rec[row] &＃61; col;//标记dfs(row &＃43; 1);//继续寻找下一行rec[row] &＃61; 0;//恢复原状}}}
}