問題描述

八皇后問題是十九世紀著名的數學家高斯于1850年提出的。

問題是：在8×8的棋盤上擺放八個皇后，使其不能互相攻擊，即任意兩個皇后都不能處于同一行、同一列或同一斜線上。可以把八皇后問題擴展到n皇后問題，即在n×n的棋盤上擺放n個皇后，使任意兩個皇后都不能處于同一行、同一列或同一斜線上。

顯然，棋盤的每一行上可以而且必須擺放一個皇后，所以，n皇后問題的可能解用一個n元向量X=(x1, x2, …, xn)表示，其中，1≤i≤n并且1≤xi≤n，即第i個皇后放在第i行第xi列上。

由于兩個皇后不能位于同一列上，所以，解向量X必須滿足約束條件：

?????????????xi≠xj ???????????????????（式8.1）

若兩個皇后擺放的位置分別是(i, xi)和(j, xj)，在棋盤上斜率為-1的斜線上，滿足條件i－j= xi－xj，在棋盤上斜率為1的斜線上，滿足條件i＋j= xi＋xj，綜合兩種情況，由于兩個皇后不能位于同一斜線上，所以，解向量X必須滿足約束條件：

????????????|i－xi|≠|j－xj| ??????????（式8.2）

四皇后問題示例

?

實驗目的

(1)掌握回溯算法的設計思想；

(2)掌握解空間樹的動態生成過程。

實驗要求

(1)設計解空間樹的動態生成算法，并設計剪枝函數加快搜索速度；

(2)將上面圖例(四皇后問題)按回溯算法搜索并輸出全部的解。

核心思路：

使用遞歸+回溯

1.初始化棋盤全部為“.”

2.從第一行開始，遍歷該行的每一個位置，符合的填為“Q”，不符合的跳過，再遞歸下一行，遍歷完下一行后，將該行當前位置又重置為“.”，這一過程就是回溯的過程。依次 遍歷進行判斷每一行。

判斷位置是否可以放“Q”：

算法實現：

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;public class S51 {List<List<String>> res = new LinkedList<>();public List<List<String>> solveNQueens(int n) {char[][] borad = new char[n][n];//初始化棋盤for (int i = 0; i < borad.length; i++) {Arrays.fill(borad[i], '.');}backtrack(0, borad);return res;}/*** 第row行的填充結果* @param row 到第row行* @param borad 棋盤*/private void backtrack(int row, char[][] borad) {if (row < 0 || row > borad.length) {return;}if (row == borad.length) {List<String> item = new LinkedList<>();for (int i = 0; i < borad.length; i++) {StringBuffer sb = new StringBuffer();for (int j = 0; j < borad[0].length; j++) {//方便打印結果一目了然添加“\t”sb.append(borad[i][j]+"\t");//改為sb.append(borad[i][j]),即可解決力扣51題}item.add(sb.toString());}res.add(item);return;}int n = borad[row].length;//對row行的每個位置進行判斷是否符合放皇后的位置for (int col = 0; col < n; col++) {if (!isfang(row, col, borad)) {//已放過，即不符合continue;}borad[row][col] = 'Q';//進入下層決策backtrack(row + 1, borad);//回溯borad[row][col] = '.';}}/*** 判斷【row，col】位置是否可以放皇后* @param row 行* @param col 列* @param borad 棋盤* @return true 可放*/private boolean isfang(int row, int col, char[][] borad) {int n = borad.length;//豎直上方for (int k = 0; k <= row; k++) {if (borad[k][col] == 'Q') {return false;}}//右上方for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {if (borad[i][j] == 'Q') {return false;}}//左上方for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {if (borad[i][j] == 'Q') {return false;}}return true;}public static void main(String[] args) {S51 s51 = new S51();int n = 4;List<List<String>> lists = s51.solveNQueens(n);System.out.println(n+" 皇后的解法如下：");for (int i = 0; i < lists.size(); i++) {List<String> res = lists.get(i);System.out.println("結果"+(i+1)+":");for (int j = 0; j < res.size(); j++) {System.out.println(res.get(j));}System.out.println();}}
}

?輸出結果：

將以上代碼中‘sb.append(borad[i][j]+"\t")’改為sb.append(borad[i][j])，就可以提交通過力扣51題?

51. N 皇后

?

快去提交吧~~~?