從迷宮到八皇后問(wèn)題認(rèn)識(shí)遞歸與回溯
迷宮問(wèn)題
迷宮大家都很熟悉蔫磨，給定一個(gè)起點(diǎn)己肮，一個(gè)終點(diǎn)，中間有各種復(fù)雜的通路剪廉，從起點(diǎn)走到終點(diǎn)就算是走出了迷宮娃循。
那么如何使用計(jì)算機(jī)機(jī)算出一條迷宮的走法呢？
首先需要先在計(jì)算機(jī)中模擬出一個(gè)迷宮的樣子斗蒋，之前我們提到過(guò)的二維數(shù)組可以用來(lái)表示一個(gè)平面捌斧，用作迷宮的地圖是非常合適的。
我們可以創(chuàng)建一個(gè)二維數(shù)組泉沾，用0表示路捞蚂，1表示墻，即可表示任意方形的迷宮跷究，下面是我在Java中隨便創(chuàng)建的一個(gè)小迷宮姓迅，接下來(lái)我們將用他來(lái)完成對(duì)迷宮問(wèn)題的解決
/**
* 創(chuàng)建迷宮，用二維數(shù)組存放返回
* @return 迷宮
*/
public static int[][] createMaze(){
//創(chuàng)建八行七列的地圖
int[][] map = new int[8][7];
//用1表示墻,將四周?chē)饋?lái)
for (int i = 0; i < 7; i++) {
map[0][i] = 1;
map[7][i] = 1;
}
for (int i = 0; i < 8; i++) {
map[i][0] = 1;
map[i][6] = 1;
}
//設(shè)置中間的墻
map[2][1] = 1;
map[2][3] = 1;
map[2][4] = 1;
map[3][4] = 1;
map[4][2] = 1;
map[4][3] = 1;
map[5][3] = 1;
map[5][5] = 1;
map[6][2] = 1;
return map;
}
打印一下迷宮看看效果
/**
* 打印迷宮（打印二維數(shù)組）
* @param map 二維數(shù)組
*/
public static void printMaze(int[][] map){
for (int[] row : map) {
for (int data : row) {
System.out.print(data+"\t");
}
System.out.println();
}
}
1是墻俊马，0是路丁存，沒(méi)有什么問(wèn)題，接下來(lái)開(kāi)始分析如何用Java計(jì)算出一條通路柴我。
我們可以讓計(jì)算機(jī)嘗試按照一種策略去窮舉解寝，也就是把能走的路全部走一遍。
我們發(fā)現(xiàn)每一個(gè)點(diǎn)嘗試?yán)^續(xù)往下走艘儒，可以選擇四個(gè)方向上聋伦、下、左界睁、右
那么就要選定一種嘗試的順序策略觉增，比如規(guī)定按照下、右翻斟、上逾礁、左的順序
也就是說(shuō)，走下一步的時(shí)候先嘗試向下走访惜，走不通再?lài)L試向右走敞斋，走不通再?lài)L試向上走，走不通再?lài)L試向左走疾牲，都走不通說(shuō)明只要來(lái)到這個(gè)點(diǎn)就已經(jīng)是死路了植捎，我們要回到上一個(gè)點(diǎn)再去嘗試下一種方式
策略定下了，我們來(lái)分析什么樣的路是走不通的路：
- 首先如果那個(gè)位置的數(shù)據(jù)為1也就是墻阳柔，走不通
- 如果這個(gè)位置是我們來(lái)時(shí)的位置焰枢，再走就成回頭路了，也應(yīng)該走不通
- 如果這個(gè)位置是以前嘗試過(guò)的死路舌剂，也不必再走
綜上我們發(fā)現(xiàn)济锄，需要對(duì)走過(guò)的路也做一個(gè)記錄，我們規(guī)定將走過(guò)的路標(biāo)記為2霍转，走過(guò)已經(jīng)確定是死路的點(diǎn)標(biāo)記為3
這時(shí)候荐绝，重點(diǎn)來(lái)了，體會(huì)用遞歸的方式來(lái)完成這種回溯避消，我們?cè)O(shè)計(jì)一個(gè)方法低滩，讓這個(gè)方法的功能是從當(dāng)前點(diǎn)位開(kāi)始召夹，嘗試找到一條通向重點(diǎn)的路，那么思路應(yīng)該是先嘗試向下走恕沫，走到下一個(gè)點(diǎn)监憎，從下一個(gè)點(diǎn)再?lài)L試走到再下一個(gè)點(diǎn)直到走通（到達(dá)終點(diǎn)）返回true，或者走不通（將走不通的點(diǎn)標(biāo)記為3）返回false
可以這樣想婶溯，我們用一個(gè)固定的走迷宮的方式（按順序嘗試）鲸阔，從一個(gè)點(diǎn)移動(dòng)到了下一個(gè)點(diǎn)，還要再向下一個(gè)點(diǎn)移動(dòng)迄委，那么我們先不管我們是從哪里走過(guò)來(lái)的褐筛，就將當(dāng)前所在這個(gè)點(diǎn)看成是一個(gè)新的起點(diǎn)再去按固定的走迷宮方式嘗試下去。
解釋起來(lái)有點(diǎn)抽象叙身，看到這里應(yīng)該是有點(diǎn)云里霧里渔扎，不知道如何去做，此時(shí)應(yīng)該上代碼了曲梗，結(jié)合上面的話已經(jīng)代碼注釋來(lái)讀一下代碼赞警，應(yīng)該就能夠理解了
我們就使用剛剛創(chuàng)建的那個(gè)迷宮，將[1,1]點(diǎn)作為總起點(diǎn)虏两，[6,5]點(diǎn)作為終點(diǎn)來(lái)實(shí)現(xiàn)
/**
* 走迷宮
* 結(jié)束點(diǎn)寫(xiě)死愧旦，map[6][5]
* 約定，當(dāng)?shù)貓D[i][j]為0表示路沒(méi)有走過(guò)定罢，為1時(shí)表示墻笤虫，為2時(shí)表示通路可以走，3表示該位置已經(jīng)走過(guò)但是不通
* 策略——>走迷宮時(shí)祖凫，下-右-上-左琼蚯，走不通再回溯
*
* @param map 迷宮地圖
* @param i 從哪里開(kāi)始（起點(diǎn)的行索引）
* @param j 從哪里開(kāi)始（起點(diǎn)的列索引）
* @return 是否能夠找到通路
*/
public static boolean setWay(int[][] map,int i,int j){
//進(jìn)入方法先判斷當(dāng)前點(diǎn)是不是終點(diǎn)，如果當(dāng)前點(diǎn)就是終點(diǎn)惠况，說(shuō)明已經(jīng)走通了遭庶，返回true
if (i == 6 && j == 5){
//已經(jīng)是終點(diǎn)了，設(shè)置這個(gè)點(diǎn)走過(guò)了稠屠，返回true
map[i][j] = 2;
return true;
}
//沒(méi)返回說(shuō)明當(dāng)前點(diǎn)不是終點(diǎn)峦睡，需要繼續(xù)走
//再判斷，當(dāng)前點(diǎn)能不能走权埠，如果當(dāng)前點(diǎn)為0（1是墻榨了，2是回頭路，3是死路）攘蔽，表示這個(gè)點(diǎn)可以走
if (map[i][j] == 0) {
//路能走龙屉，就先將當(dāng)前點(diǎn)設(shè)置為走過(guò)
map[i][j] = 2;
//然后按策略走一遍迷宮——>下->右->上->左
//先嘗試向下走
// 把向下走的那個(gè)點(diǎn)再作為起點(diǎn)，調(diào)用自己這個(gè)走迷宮的方法
// 如果走通了就返回true（一層一層返回true最終返回到最外層）
// 如果走不通返回了false满俗，會(huì)回到這里转捕，接著去嘗試向右走
// （false也是下面的很多個(gè)點(diǎn)一層一層返回到這里）
if (setWay2(map,i+1,j)){
return true;
}
//直到向下走不了作岖，改向右走
else if (setWay2(map,i, j+1)){
return true;
}
//向右也走不通，改向上走
else if (setWay2(map,i-1,j)){
return true;
}
//向上也走不通瓜富，改向左走
else if (setWay2(map,i,j-1)){
return true;
}else {
//全都走不通鳍咱，是死路降盹，將當(dāng)前點(diǎn)標(biāo)記為3
map[i][j] = 3;
return false;
}
}
//如果當(dāng)前點(diǎn)不為0与柑，返回false
else {
return false;
}
}
由于傳入方法的二維數(shù)組是引用類(lèi)型，傳來(lái)的是地址蓄坏，所以方法中對(duì)這個(gè)數(shù)組的操作都會(huì)實(shí)際作用在數(shù)組上价捧，方法結(jié)束后打印數(shù)據(jù)看看效果
public static void main(String[] args) {
//創(chuàng)建迷宮
int[][] maze = createMaze();
//使用遞歸回溯走迷宮
setWay(maze,1,1);
//輸出嘗試走過(guò)的地圖
printMaze(maze);
}
我們看到算法是正確的，找到了一條標(biāo)記為2的通路涡戳，從[1,1]走到[6,5]结蟋，還有一些標(biāo)記為3的也都確實(shí)是走不通的死路。
八皇后問(wèn)題
八皇后問(wèn)題表述為：在8×8格的國(guó)際象棋上擺放8個(gè)皇后渔彰，使其不能互相攻擊嵌屎，即任意兩個(gè)皇后都不能處于同一行、同一列或同一斜線上恍涂，問(wèn)有多少種擺法宝惰。
高斯認(rèn)為有76種方案。1854年在柏林的象棋雜志上不同的作者發(fā)表了40種不同的解再沧，后來(lái)有人用圖論的方法解出92種結(jié)果尼夺。如果經(jīng)過(guò)±90度、±180度旋轉(zhuǎn)炒瘸，和對(duì)角線對(duì)稱(chēng)變換的擺法看成一類(lèi)淤堵，共有42類(lèi)。
但我們這里暫時(shí)先不討論旋轉(zhuǎn)和對(duì)稱(chēng)變換顷扩。
如圖所示就是一種八皇后的擺放方式
如何使用計(jì)算機(jī)算出一共有多少擺放方式拐邪，并且將所有擺放方式列舉出來(lái)呢？
這里依然是采用一種遞歸+回溯的思路隘截，先分析一下：
首先分析可以按行考慮或按列考慮扎阶，比如按行考慮，就是說(shuō)第一行放了皇后技俐，下一個(gè)皇后就只能放第二行乘陪，再下一個(gè)就只能放第三行，每一行都去嘗試皇后可以放在那一列來(lái)進(jìn)行遞歸
一個(gè)棋盤(pán)按說(shuō)可以存進(jìn)一個(gè)二維數(shù)組雕擂，但是皇后的擺放有每一行只能有一個(gè)的限制啡邑，所以可以用一個(gè)一位數(shù)組即可，數(shù)組下標(biāo)表示第幾行井赌，具體數(shù)據(jù)記錄在那一列
那么就可以先將第一個(gè)皇后放在第一行第一列谤逼，然后去考慮第二行皇后可以放在哪里贵扰、第三行...一直到第八行
我們的方法可以設(shè)計(jì)為當(dāng)前正在放第幾個(gè)皇后，但是要記錄好之前的皇后都怎么擺的
假設(shè)我們正在放第n個(gè)皇后
首先需要一個(gè)數(shù)組arr[]來(lái)保存八個(gè)皇后的擺放位置流部，一個(gè)變量count記錄一共有多少種擺法戚绕。
然后進(jìn)行如下步驟：
- 在第n行循環(huán)將皇后嘗試擺放在第1到第8列
- 嘗試第i列時(shí)，將皇后放進(jìn)去（arr[n]=i）,再循環(huán)去分析和前n-1行的皇后是否有沖突
- 如果沒(méi)有沖突說(shuō)明前n行擺的是可以的枝冀，接著去調(diào)用我們自己舞丛，擺第n+1個(gè)皇后，無(wú)論后面的皇后擺的怎么樣果漾，到方法執(zhí)行完球切，還是要接著去嘗試第i+1列
- 如果沖突直接繼續(xù)去嘗試第i+1列
- 直到八列都嘗試完，說(shuō)明第n個(gè)皇后后續(xù)所有情況已經(jīng)窮盡了绒障，也就是對(duì)我們的上一層來(lái)說(shuō)吨凑，步驟c擺放第n+1個(gè)皇后方法執(zhí)行完畢了，如果我們就是最外層户辱，說(shuō)明所有情況都窮盡了
- 而擺第n個(gè)皇后的時(shí)候鸵钝，要進(jìn)行邊界判斷，如果n變成8了庐镐，說(shuō)明arr[0]到arr[7]八個(gè)皇后都放好了恩商，此時(shí)數(shù)組arr中完整的保存了一種皇后的擺法，將它打印或記錄下來(lái)焚鹊，讓解法總數(shù)+1
- 還有一個(gè)重點(diǎn)痕届，就是如何判斷沖突，行沖突不用判斷因?yàn)榉椒ň褪菑男谐霭l(fā)末患，每行一定只有一個(gè)跛锌，還需判斷列沖突和對(duì)角線沖突亿傅，列沖突非常簡(jiǎn)單演怎，判斷數(shù)組中第n個(gè)和前n-1個(gè)有沒(méi)有相同即可十厢，判斷對(duì)角看似非常復(fù)雜，但只要借助一個(gè)叫做斜率的概念即可簡(jiǎn)單解決探橱，觀察可發(fā)現(xiàn)申屹，如果是在一個(gè)對(duì)角線，這個(gè)對(duì)角線一定屬于一個(gè)正方形隧膏，正方形對(duì)角線斜率為1哗讥，也就是第n個(gè)皇后和前面第i個(gè)皇后，如果在一個(gè)對(duì)角線胞枕，那么n-i == arr[n]-arr[i]杆煞。
八皇后比起剛剛迷宮只找一條通路應(yīng)該是要難理解一些的，這種遞歸+回溯的方式，確實(shí)需要一定的想象力决乎，下面在結(jié)合注釋閱讀一下代碼队询，慢慢體會(huì)這種算法
package com.zwx.recursion;
import java.util.Arrays;
/**
* 八皇后問(wèn)題（遞歸回溯）
*
* @author coderZWX
* @date 2022-05-31 15:41
*/
public class EightQueens {
//定義一個(gè)max表示共有多少個(gè)皇后
private int maxQueensCount = 8;
//定義一個(gè)數(shù)組，保存皇后放置位置的結(jié)果构诚，比如arr={0,4,7,5,2,6,1,3}
private int[] array = new int[maxQueensCount];
//解法總數(shù)
private int count;
public static void main(String[] args) {
long startTime = System.currentTimeMillis();
EightQueens queens = new EightQueens();
queens.check(0);
System.out.println(queens.count);
System.out.println("用時(shí)（毫秒）："+(System.currentTimeMillis()-startTime));
}
/**
* 放置第n個(gè)皇后
* @param n n表示數(shù)組下標(biāo)蚌斩，第一個(gè)皇后其實(shí)n為0
*/
private void check(int n){
//判斷n是否越界，如果越界到第九個(gè)范嘱，說(shuō)明已經(jīng)八個(gè)皇后已經(jīng)放好了
if (n == maxQueensCount){
//打印一個(gè)結(jié)果
System.out.println(Arrays.toString(array));
//記錄結(jié)果數(shù)量加一
count++;
return;
}
//依次放入皇后并判斷是否沖突
for (int i = 0; i < maxQueensCount; i++) {
//先把當(dāng)前皇后n送膳，放到該行的第i列
array[n] = i;
//判斷是否沖突
// 不論是否沖突，都會(huì)最終i++接著執(zhí)行下一次循環(huán)
// 如果沖突就直接進(jìn)下一次循環(huán)接著嘗試下一列
// 不沖突在放完后面皇后之后也會(huì)進(jìn)下一次循環(huán)嘗試下一列
if (judge(n)){
//不沖突接著放n+1個(gè)皇后
check(n+1);
}
}
//如果出了這個(gè)大循環(huán)
// 說(shuō)明第n個(gè)皇后在第n行放哪里都不行彤侍，也就是前面的擺法都是錯(cuò)的
// 方法到這里就結(jié)束了肠缨，如果是內(nèi)層逆趋，它的外層還會(huì)在外層的for接著循環(huán)
}
/**
* 查看當(dāng)放置第n個(gè)皇后時(shí)盏阶，是否沖突
*
* @param n 第n個(gè)皇后
* @return 是否沖突
*/
private boolean judge(int n){
for (int i = 0; i < n; i++) {
//1.array[i] == array[n] 同一列沖突
//2.Math.abs(n-i) == Math.abs(array[n]-array[i]) 同一斜線沖突（相當(dāng)于判斷了兩點(diǎn)間斜率為1）
if (array[i] == array[n] || Math.abs(n-i) == Math.abs(array[n]-array[i])){
return false;
}
}
return true;
}
}
根據(jù)上面代碼，最終打印出了所有情況闻书，count也就是92名斟，沒(méi)有問(wèn)題
小練習(xí)——迷宮問(wèn)題的最短路徑
我們的迷宮問(wèn)題，為了循序漸進(jìn)魄眉，在前面的算法中只是找到了其中一條通路就結(jié)束了砰盐，所以理解起來(lái)比八皇后這個(gè)簡(jiǎn)單了不少，相當(dāng)于八皇后問(wèn)題只找到一種擺放方式坑律。
那么現(xiàn)在經(jīng)過(guò)了這兩個(gè)算法的學(xué)習(xí)岩梳，結(jié)合迷宮問(wèn)題找一條通路的方法、以及八皇后問(wèn)題的思路晃择，是否可以自行嘗試寫(xiě)一個(gè)算法冀值，窮舉一下迷宮的所有通路，記錄通路數(shù)量宫屠，并找到其中的最短路徑
可評(píng)論留言獲得小練習(xí)的實(shí)現(xiàn)（附詳細(xì)的注釋講解）
