前几天关注的CSDN公众号推送了一篇文章是讲八皇后问题的,作为经典DFS算法,当时看到文章的时候就点开回顾了一下。
我这里贴 链接 算是在帮公众号做推广吗...好吧不废话了。我觉得文章里画的图解真的很详细易懂,本来想截图,然后一张张地用Java语言再解释一遍,但是担心涉及到知识产权和版权问题,出于尊重的原因。还是只贴链接吧。建议大家可以先看一下链接里的思路解释,对于理解下面的代码实现就会容易很多了。
我们先以8*8的棋盘为例,进行八皇后问题的实现:
一、如果只对总方案数进行计算:
public class Main { static int[] queens = new int[8]; // 记录每一行的皇后位置 static int count = 0;// 记录方案总数 static void dfs(int row) { if (row == 8) { count++; return; } for (int column = 0; column < 8; column++) { queens[row] = column; // 在该行的第column列上放置皇后 if (conflict(row) == false) dfs(row + 1); } } static boolean conflict(int row) { for (int x = 0; x < row; x++) { // 第row行上的皇后与前面row-1个皇后比较 if (queens[x] == queens[row]) // 两个皇后在同一行上 return true; if (Math.abs(queens[x] - queens[row]) == (row - x)) // 两个皇后在同一对角线上 return true; } return false; } public static void main(String[] args) { dfs(0); System.out.println(count); } } 输出:92
二、如果需要打印出各个方案:
public class Main { static int[] queens = new int[8]; static int count = 0; static void dfs(int row) { if (row == 8) { count++; System.out.println("方案" + count + ":"); //打印方案 print(); return; } for (int column = 0; column < 8; column++) { queens[row] = column; if (conflict(row) == false) dfs(row + 1); } } static boolean conflict(int row) { for (int x = 0; x < row; x++) { if (queens[x] == queens[row]) return true; if (Math.abs(queens[x] - queens[row]) == (row - x)) return true; } return false; } static void print() { //打印方案的函数 for (int i = 0; i < 8; i++) { for (int j = 0; j < 8; j++) { if (queens[i] == j) System.out.print("1 "); //表示皇后位置 else System.out.print("0 "); } System.out.println(); } } public static void main(String[] args) { dfs(0); System.out.println(count); } } 输出: 方案1: 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 方案2: 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 方案3: 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 ...... 以下省略
那么如果推广到n*n的棋盘呢?
情况大同小异。为了能够解释清楚,我这里用一道题目来具体化。
其实n*n的棋盘,并不需要改动任何核心的DFS算法,只需要按照题意改动一下输出方式即可,本题只要求输出前三个解。
下面附代码:
import java.util.Scanner; public class Main { static int[] queens; static int count = 0; static int n; static void dfs(int row) { if (row == n) { count++; if (count <= 3) { //按照题意输出 for (int i = 0; i <= n - 2; i++) { System.out.print((queens[i] + 1) + " "); //注意+1 } System.out.println(queens[n - 1] + 1); } return; } for (int column = 0; column < n; column++) { queens[row] = column; if (conflict(row) == false) { dfs(row + 1); } queens[row] = 0; } } static boolean conflict(int row) { for (int x = 0; x < row; x++) { if (queens[x] == queens[row]) return true; if (Math.abs(queens[x] - queens[row]) == (row - x)) return true; } return false; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nextInt(); queens = new int[n]; dfs(0); System.out.println(count); } } 输入:6 输出: 2 4 6 1 3 5 3 6 2 5 1 4 4 1 5 2 6 3 4