回溯法
對于回溯法，網上有很多種解釋，這裡我依照自己的（死宅）觀點做了以下三種通俗易懂的解釋：
回溯算法：是類似于枚舉的搜索嘗試過程，主要是在搜索嘗試過程中尋找問題的解，當發現已不滿足求解條件時，就“回溯”返回，嘗試别的路徑。
它是一種選優搜索法，按選優條件向前搜索，以達到目标。但當探索到某一步時，發現原先選擇并不優或達不到目标，就退回一步重新選擇，這種走不通就退回再走的技術稱為 回溯法 ，而滿足回溯條件的某個狀态的點稱為 “回溯點” （你也可以理解為 存檔點 ）。
上圖為八皇後的解空間樹， 如果當前點不符合要求就退回再走 。
許多複雜的，規模較大的問題都可以使用回溯法，有“通用解題方法”的美稱。
在包含問題的所有解的解空間樹中，按照 深度優先搜索 的策略，從根結點出發深度探索解空間樹。
當探索到某一結點時，要先判斷該結點是否包含問題的解：
雖然我覺得網上的一般步驟太抽象了，但是還是擺在這裡供大家參考吧。。
問題框架：
設問題的 解 是一個 n維向量(a1,a2,………,an) ， 約束條件 是 ai(i=1,2,3,…..,n)之間 滿足某種條件，記為 f(ai) 。
其中， a[n] 為解空間， i 為搜索的深度，框架如下：
int a[n],i; //a[n]為解空間，i為深度
初始化數組 a[];
i = 1;
while (i>0(有路可走) and (未達到目标)) { //還未回溯到頭
if(i > n) { //搜索到葉結點
搜索到一個解，輸出；
} else { //處理第 i 個元素
a[i]第一個可能的值；
while(a[i]在不滿足約束條件且在搜索空間内) {
a[i]下一個可能的值；
}//while
if(a[i]在搜索空間内) {
标識占用的資源；
i = i 1; //擴展下一個結點
} else {
清理所占的狀态空間； //回溯
i = i – 1;
}//else
}//else
}//while
回溯法是對解空間的 深度優先搜索 ，在一般情況下使用 遞歸函數 來實現回溯法比較簡單。
其中， a[n] 為解空間， i 為搜索的深度，框架如下：
int a[n]; //a[n]為解空間
BackTrace(int i) { //嘗試函數，i為深度
if(i>n) {
輸出結果;
} else {
for(j = 下界; j <= 上界; j=j 1) { //枚舉 i 所有可能的路徑
if(check(j)) { //檢查滿足限界函數和約束條件
a[i] = j;
... //其他操作
BackTrace(i 1);
回溯前的清理工作（如 a[i]置空值等）;
}//if
}//for
}//else
}//BackTrace
由于上述網上的步驟太抽象了，所以在這裡我自己總結了回溯四步走：
第一步，寫出檢測函數，來檢測這個路徑是否滿足條件，是否能通過。
這個函數依據題目要求來編寫，當然，如果要求不止一個，可能需要編寫多個檢測函數。
例如：湊算式
這個算式中A~I代表1~9的數字，不同的字母代表不同的數字。
比如：
6 8/3 952/714 就是一種解法，
5 3/1 972/486 是另一種解法。
這個算式一共有多少種解法？
要做出這個題，
第一步，要寫出檢測函數
public static int sum = 0; // 用來存放總共的解法數
public static double[] a = new double[10];
// 判斷數組裡前j個元素是否與t相同
/**
* @param a 傳入一個數組a
* @param j 判斷前j個元素
* @param t 是否與t相同
* @return
*/
public static boolean same(double[] a, int j, int t) {
for (int i = 1; i < j; i ) {
if (a[i] == t) {
return true;
}
}
return false;
}
/**
* @param a 判斷a數組是否滿足表達式
* @return 如果滿足就true，不滿足就false
*/
public static boolean expression(double[] a) {
if ((a[1] a[2] / a[3] (a[4] * 100 a[5] * 10 a[6]) / (a[7] * 100 a[8] * 10 a[9]) == 10))
return true;
else
return false;
}
由于此題要填數字，所以我們定義choose(i)的含義為：在算式中自動填入數字 i 。
第二步，要尋找遞歸出口，當1~9均已填入後，判斷表達式是否成立，若成立，則輸出。
// 如果選擇的數字大于9，則代表1~9均已選完，判斷是否滿足表達式，輸出選擇的表達式
if (i > 9) {
if (expression(a)) {
for (int x = 1; x < 10; x ) {
System.out.print(a[x] " ");
}
System.out.println();
sum ;
}
return;
}
第三步，要知道這個遞歸是幾個選擇，即 幾叉樹。
此題為1~9九個選擇，九條路，九叉樹。
for (int j = 1; j <= 9; j ) {
// 如果将要填入的數與前面不沖突，則填入
if (!same(a, i, j)) {
a[i] = j;
choose(i 1);
}
}
第四步，若該節點沒有找到出口，則将當前位置回溯，還原現場，重新選擇
在本題中， 還原現場 即 重置為0（表示還未填入1~9的數字）
for (int j = 1; j <= 9; j ) {
// 如果将要填入的數與前面不沖突，則填入
if (!same(a, i, j)) {
a[i] = j;
choose(i 1);
//若沒有找到出口，則将當前位置重置為0，回溯，還原現場
a[i] = 0;
}
}
這個算式中A~I代表1~9的數字，不同的字母代表不同的數字。
比如：
6 8/3 952/714 就是一種解法，
5 3/1 972/486 是另一種解法。
這個算式一共有多少種解法？
// 湊算式
public class Sy1 {
public static void main(String[] args) {
// TODO Auto-generated method stub
choose(1);
System.out.println("一共" sum "種解法");
}
public static int sum = 0; // 用來存放總共的解法數
public static double[] a = new double[10];
// 判斷數組裡前j個元素是否與t相同
/**
* @param a 傳入一個數組a
* @param j 判斷前j個元素
* @param t 是否與t相同
* @return
*/
public static boolean same(double[] a, int j, int t) {
for (int i = 1; i < j; i ) {
if (a[i] == t) {
return true;
}
}
return false;
}
/**
* @param a 判斷a數組是否滿足表達式
* @return 如果滿足就true，不滿足就false
*/
public static boolean expression(double[] a) {
if ((a[1] a[2] / a[3] (a[4] * 100 a[5] * 10 a[6]) / (a[7] * 100 a[8] * 10 a[9]) == 10))
return true;
else
return false;
}
/**
* @param i 選擇第i個數字 遞歸
*/
public static void choose(int i) {
// 如果選擇的數字大于9，則代表1~9均已選完，輸出選擇的表達式
if (i > 9) {
if (expression(a)) {
for (int x = 1; x < 10; x ) {
System.out.print(a[x] " ");
}
System.out.println();
sum ;
}
return;
}
for (int j = 1; j <= 9; j ) {
// 如果将要填入的數與前面不沖突，則填入
if (!same(a, i, j)) {
a[i] = j;
choose(i 1);
//若沒有找到出口，則将當前位置重置為0，回溯，還原現場
a[i] = 0;
}
}
}
}
3.0 5.0 1.0 9.0 7.0 2.0 4.0 8.0 6.0
4.0 9.0 3.0 5.0 2.0 8.0 1.0 7.0 6.0
5.0 3.0 1.0 9.0 7.0 2.0 4.0 8.0 6.0
5.0 4.0 3.0 7.0 2.0 6.0 1.0 9.0 8.0
5.0 4.0 9.0 7.0 3.0 8.0 1.0 6.0 2.0
5.0 8.0 6.0 4.0 7.0 3.0 1.0 2.0 9.0
6.0 4.0 2.0 3.0 5.0 8.0 1.0 7.0 9.0
6.0 4.0 2.0 7.0 1.0 8.0 3.0 5.0 9.0
6.0 7.0 3.0 4.0 8.0 5.0 2.0 9.0 1.0
6.0 8.0 3.0 9.0 5.0 2.0 7.0 1.0 4.0
6.0 9.0 8.0 4.0 3.0 7.0 1.0 5.0 2.0
7.0 1.0 4.0 9.0 6.0 8.0 3.0 5.0 2.0
7.0 3.0 2.0 8.0 1.0 9.0 5.0 4.0 6.0
7.0 3.0 2.0 9.0 8.0 1.0 6.0 5.0 4.0
7.0 5.0 3.0 2.0 6.0 4.0 1.0 9.0 8.0
7.0 5.0 3.0 9.0 1.0 2.0 6.0 8.0 4.0
7.0 9.0 6.0 3.0 8.0 1.0 2.0 5.0 4.0
7.0 9.0 6.0 8.0 1.0 3.0 5.0 4.0 2.0
8.0 1.0 3.0 4.0 6.0 5.0 2.0 7.0 9.0
8.0 6.0 9.0 7.0 1.0 2.0 5.0 3.0 4.0
8.0 7.0 6.0 1.0 9.0 5.0 2.0 3.0 4.0
9.0 1.0 3.0 4.0 5.0 2.0 6.0 7.0 8.0
9.0 1.0 3.0 5.0 2.0 4.0 7.0 8.0 6.0
9.0 2.0 4.0 1.0 7.0 8.0 3.0 5.0 6.0
9.0 2.0 4.0 3.0 5.0 8.0 7.0 1.0 6.0
9.0 3.0 4.0 1.0 5.0 7.0 6.0 2.0 8.0
9.0 4.0 8.0 1.0 7.0 6.0 3.0 5.0 2.0
9.0 4.0 8.0 3.0 5.0 6.0 7.0 1.0 2.0
9.0 6.0 8.0 1.0 4.0 3.0 5.0 7.0 2.0
一共29種解法
如下的10個格子填入0~9的數字。
一共有多少種可能的填數方案？
// 方格填數
public class Sy2 {
public static void main(String[] args) {
// TODO Auto-generated method stub
Block bk = new Block();
bk.init();
bk.addNum(0);// , 0, 0);
System.out.println("一共" Block.sum "種方案");
}
}
class Block {
public int[][] b = new int[3][4];
public static int sum;
/**
* 初始化整個數組
*/
public void init() {
for (int i = 0; i < 3; i ) {
for (int j = 0; j < 4; j ) {
b[i][j] = -2;
}
}
}
/**
* @param y y行
* @param x x列
* @param n 填數n
* @return 返回此方格是否能填數
*/
public boolean isAble(int y, int x, int n) {
// y行 x列 填數n
if (b[y][x] != -2)
return false;
for (int j = y - 1; j <= y 1; j ) {
for (int i = x - 1; i <= x 1; i ) {
if (j < 3 && j >= 0 && i < 4 && i >= 0) {
if (b[j][i] == n - 1 || b[j][i] == n 1) {
return false;
}
}
}
}
return true;
}
/**
* @param n 填入數字n
*/
public void addNum(int n) {
if (n > 9) {
sum ;
return;
}
for (int i = 0; i < 3; i ) {
for (int j = 0; j < 4; j ) {
if ((i == 0 && j == 0) || (i == 2 && j == 3))
continue;
// 如果此方格能填數，則填入數字
if (this.isAble(i, j, n)) {
b[i][j] = n;
this.addNum(n 1);// , y, x 1);
b[i][j] = -2; // 當加入下一個不行返回後，還原現在方塊，繼續循環
}
}
}
}
}
一共1580種方案
在一個 5*5 的地圖上，一隻蛙欲從起點跳到目的地。中間有一條河（如圖），但這隻蛙不會遊泳，并且每次跳隻能橫着跳一格或者豎着跳一格。（聰明的蛙不會跳已經跳過的路）
//青蛙跳
public class Sy1 {
static int count = 0; // 跳法種類計數
static int x = 4, y = 4; // 目的坐标
static int step = 0; // 記錄步數
// 地圖，0代表沒有走過，1 代表已經走過
static int[][] map = { { 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0 }, { 1, 1, 0, 1, 1 }, { 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0 } };
static int min = 25; // 用來記錄最小步數
static int sx[] = new int[25], sy[] = new int[25]; // 記錄坐标
// 求解總共跳法，并求出最短步數，方便下面列出路徑
static void jump(int m, int n) {
if (m < 0 || m >= 5 || n < 0 || n >= 5 || map[m][n] != 0) { // 該點在地圖邊界之内并且未走過
return;
}
map[m][n] = 1; // 走到此節點
step ;
if (m == x && n == y) { // 如果到達目的地
if (step < min)// 更新最短步數
min = step;
count ;
}
// 所有路徑
jump(m 1, n); // 右跳
jump(m - 1, n); // 左跳
jump(m, n 1); // 下跳
jump(m, n - 1); // 上跳
step--; // 回溯法關鍵步驟
map[m][n] = 0;
}
// 列出最短步數的路徑
static void find(int m, int n) {
if (m < 0 || m >= 5 || n < 0 || n >= 5 || map[m][n] != 0) { // 該點在地圖邊界之内并且未走過
return;
}
// 記錄坐标
sx[step] = m;
sy[step] = n;
// 走到此節點
map[m][n] = 1;
step ;
if (m == x && n == y && step == min) { // 到達目的且為最短路徑
int p = min - 1;
System.out.print("最短 path:" p "步");
for (int i = 0; i < min; i )
System.out.print("(" sx[i] "," sy[i] ")");
System.out.println();
}
find(m 1, n);
find(m - 1, n);
find(m, n 1);
find(m, n - 1);
step--;
map[m][n] = 0;
}
public static void main(String[] args) {
jump(0, 0);
step = 0;
System.out.println("總共" count "種解法");
find(0, 0);
}
}
程序運行結果：
以一個 M×N 的長方陣表示迷宮， 0 和 1 分别表示迷宮中的 通路 和 障礙 。
設計一個程序，對任意輸入的迷宮，輸出一條從入口到出口的通路，或得出沒有通路的結論。
例：
輸入：
請輸入迷宮的行數 9
請輸入迷宮的列數 8
請輸入 9 行 8 列的迷宮
0 0 1 0 0 0 1 0
0 0 1 0 0 0 1 0
0 0 1 0 1 1 0 1
0 1 1 1 0 0 1 0
0 0 0 1 0 0 0 0
0 1 0 0 0 1 0 1
0 1 1 1 1 0 0 1
1 1 0 0 0 1 0 1
1 1 0 0 0 0 0 0
為了方便大家觀看，我換成了矩陣：
001000100010001000101101011100100001000001000101011110011100010111000000001000100010001000101101011100100001000001000101011110011100010111000000
輸出：
有路徑
路徑如下：
# # 1 0 0 0 1 0
0 # 1 0 0 0 1 0
# # 1 0 1 1 0 1
# 1 1 1 0 0 1 0
# # # 1 # # # 0
0 1 # # # 1 # 1
0 1 1 1 1 0 # 1
1 1 0 0 0 1 # 1
1 1 0 0 0 0 # #
為了方便大家觀看，我換成了矩陣：
##1000100#100010##101101#1110010###1###001###1#1011110#1110001#1110000####1000100#100010##101101#1110010###1###001###1#1011110#1110001#1110000##
答案：這裡用棧來實現的遞歸，算是一個新思路。
//迷宮
/*位置類*/
class Position {
int row;
int col;
public Position() {
}
public Position(int row, int col) {
this.col = col;
this.row = row;
}
public String toString() {
return "(" row " ," col ")";
}
}
/*地圖類*/
class Maze {
int maze[][];
private int row = 9;
private int col = 8;
Stack<Position> stack;
boolean p[][] = null;
public Maze() {
maze = new int[15][15];
stack = new Stack<Position>();
p = new boolean[15][15];
}
/*
* 構造迷宮
*/
public void init() {
Scanner scanner = new Scanner(System.in);
System.out.println("請輸入迷宮的行數");
row = scanner.nextInt();
System.out.println("請輸入迷宮的列數");
col = scanner.nextInt();
System.out.println("請輸入" row "行" col "列的迷宮");
int temp = 0;
for(int i = 0; i < row; i) {
for(int j = 0; j < col; j) {
temp = scanner.nextInt();
maze[i][j] = temp;
p[i][j] = false;
}
}
}
/*
* 回溯迷宮，查看是否有出路
*/
public void findPath() {
// 給原始迷宮的周圍加一圈圍牆
int temp[][] = new int[row 2][col 2];
for(int i = 0; i < row 2; i) {
for(int j = 0; j < col 2; j) {
temp[0][j] = 1;
temp[row 1][j] = 1;
temp[i][0] = temp[i][col 1] = 1;
}
}
// 将原始迷宮複制到新的迷宮中
for(int i = 0; i < row; i) {
for(int j = 0; j < col; j) {
temp[i 1][j 1] = maze[i][j];
}
}
// 從左上角開始按照順時針開始查詢
int i = 1;
int j = 1;
p[i][j] = true;
stack.push(new Position(i, j));
while (!stack.empty() && (!(i == (row) && (j == col)))) {
if ((temp[i][j 1] == 0) && (p[i][j 1] == false)) {
p[i][j 1] = true;
stack.push(new Position(i, j 1));
j ;
} else if ((temp[i 1][j] == 0) && (p[i 1][j] == false)) {
p[i 1][j] = true;
stack.push(new Position(i 1, j));
i ;
} else if ((temp[i][j - 1] == 0) && (p[i][j - 1] == false)) {
p[i][j - 1] = true;
stack.push(new Position(i, j - 1));
j--;
} else if ((temp[i - 1][j] == 0) && (p[i - 1][j] == false)) {
p[i - 1][j] = true;
stack.push(new Position(i - 1, j));
i--;
} else {
stack.pop();
if(stack.empty()) {
break;
}
i = stack.peek().row;
j = stack.peek().col;
}
}
Stack<Position> newPos = new Stack<Position>();
if (stack.empty()) {
System.out.println("沒有路徑");
} else {
System.out.println("有路徑");
System.out.println("路徑如下：");
while (!stack.empty()) {
Position pos = new Position();
pos = stack.pop();
newPos.push(pos);
}
}
/*
* 圖形化輸出路徑
* */
String resault[][]=new String[row 1][col 1];
for(int k=0; k<row; k) {
for(int t=0; t<col; t) {
resault[k][t]=(maze[k][t]) "";
}
}
while (!newPos.empty()) {
Position p1=newPos.pop();
resault[p1.row-1][p1.col-1]="#";
}
for(int k=0; k<row; k) {
for(int t=0; t<col; t) {
System.out.print(resault[k][t] "\t");
}
System.out.println();
}
}
}
/*主類*/
class Sy4 {
public static void main(String[] args) {
Maze demo = new Maze();
demo.init();
demo.findPath();
}
}
程序運行結果：
嘿嘿，上面的那種用棧來實現遞歸的方法是不是看完了呢！把它放在第一個就是為了讓大家以為沒有遞歸回溯的答案，好認認真真的看完。。。（别打我）
貼心的我當然準備了用 遞歸回溯 方法的代碼：
// 迷宮
class Sy4 {
public static void main(String[] args) {
Demo demo = new Demo();
demo.init();
demo.find(0, 0);
}
}
class Demo {
int m, n;
// 類在實例化時分配空間，但是隻是邏輯上連續的空間，而不一定是物理上，畢竟有靜态變量，不可能完全連續。
String[][] maze; //不能用char，掃描器Scanner不能掃描。
//這裡隻是聲明，後面輸入m、n時才能确定分配空間的大小
//初始化迷宮
public void init() {
Scanner scanner = new Scanner(System.in);
System.out.println("請輸入迷宮的行數");
m = scanner.nextInt();
System.out.println("請輸入迷宮的列數");
n = scanner.nextInt();
maze = new String[m][n];
System.out.println("請輸入" m "行" n "列的迷宮");
for (int i = 0; i < m; i) {
for (int j = 0; j < n; j) {
maze[i][j] = scanner.next();
}
}
System.out.println("--------------------------------------------------------");
System.out.println("迷宮如下：");
for (int i = 0; i < m; i) {
for (int j = 0; j < n; j) {
System.out.print(maze[i][j] " ");
}
System.out.println();
}
System.out.println("--------------------------------------------------------");
}
//走到(x, y)點，找找路徑
public void find(int x, int y) {
if (x < 0 || y < 0 || x >= m || y >= n || !maze[x][y].equals("0")) { // 注意字符串要用equals
return;
}
maze[x][y] = "#"; // 走到此節點
if (x == m - 1 && y == n - 1) {
for (int i = 0; i < m; i) {
for (int j = 0; j < n; j) {
System.out.print(maze[i][j] " ");
}
System.out.println();
}
System.out.println("--------------------------------------------------------");
}
find(x 1, y); //下移
find(x - 1, y); //上移
find(x, y 1); //右移
find(x, y - 1); //左移
maze[x][y] = "0";
}
}
--------------------------------------------------------
迷宮如下：
0 0 1 0 0 0 1 0
0 0 1 0 0 0 1 0
0 0 1 0 1 1 0 1
0 1 1 1 0 0 1 0
0 0 0 1 0 0 0 0
0 1 0 0 0 1 0 1
0 1 1 1 1 0 0 1
1 1 0 0 0 1 0 1
1 1 0 0 0 0 0 0
--------------------------------------------------------
# 0 1 0 0 0 1 0
# 0 1 0 0 0 1 0
# 0 1 0 1 1 0 1
# 1 1 1 # # 1 0
# # # 1 # # # 0
0 1 # # # 1 # 1
0 1 1 1 1 0 # 1
1 1 0 0 0 1 # 1
1 1 0 0 0 0 # #
--------------------------------------------------------
# 0 1 0 0 0 1 0
# 0 1 0 0 0 1 0
# 0 1 0 1 1 0 1
# 1 1 1 0 0 1 0
# # # 1 # # # 0
0 1 # # # 1 # 1
0 1 1 1 1 0 # 1
1 1 0 0 0 1 # 1
1 1 0 0 0 0 # #
--------------------------------------------------------
# 0 1 0 0 0 1 0
# # 1 0 0 0 1 0
# # 1 0 1 1 0 1
# 1 1 1 # # 1 0
# # # 1 # # # 0
0 1 # # # 1 # 1
0 1 1 1 1 0 # 1
1 1 0 0 0 1 # 1
1 1 0 0 0 0 # #
--------------------------------------------------------
# 0 1 0 0 0 1 0
# # 1 0 0 0 1 0
# # 1 0 1 1 0 1
# 1 1 1 0 0 1 0
# # # 1 # # # 0
0 1 # # # 1 # 1
0 1 1 1 1 0 # 1
1 1 0 0 0 1 # 1
1 1 0 0 0 0 # #
--------------------------------------------------------
# # 1 0 0 0 1 0
0 # 1 0 0 0 1 0
# # 1 0 1 1 0 1
# 1 1 1 # # 1 0
# # # 1 # # # 0
0 1 # # # 1 # 1
0 1 1 1 1 0 # 1
1 1 0 0 0 1 # 1
1 1 0 0 0 0 # #
--------------------------------------------------------
# # 1 0 0 0 1 0
0 # 1 0 0 0 1 0
# # 1 0 1 1 0 1
# 1 1 1 0 0 1 0
# # # 1 # # # 0
0 1 # # # 1 # 1
0 1 1 1 1 0 # 1
1 1 0 0 0 1 # 1
1 1 0 0 0 0 # #
--------------------------------------------------------
# # 1 0 0 0 1 0
# # 1 0 0 0 1 0
# 0 1 0 1 1 0 1
# 1 1 1 # # 1 0
# # # 1 # # # 0
0 1 # # # 1 # 1
0 1 1 1 1 0 # 1
1 1 0 0 0 1 # 1
1 1 0 0 0 0 # #
--------------------------------------------------------
# # 1 0 0 0 1 0
# # 1 0 0 0 1 0
# 0 1 0 1 1 0 1
# 1 1 1 0 0 1 0
# # # 1 # # # 0
0 1 # # # 1 # 1
0 1 1 1 1 0 # 1
1 1 0 0 0 1 # 1
1 1 0 0 0 0 # #
--------------------------------------------------------
假設國際象棋棋盤有 5*5 共 25 個格子。
設計一個程序，使棋子從初始位置（棋盤編号為 1 的位）開始跳馬，能夠把棋盤的格子全部都走一遍，每個格子隻允許走一次。
PS：國際象棋的棋子是在格子中間的。國際象棋中的“馬走日”，如下圖所示，第一步為[1,1],
第二步為[2,8]或[2,12]，第三步可以是[3,5]或[3,21]等，以此類推。
//馬走日
class Sy2 {
private static int[][] next = { { 1, 2 }, { 1, -2 }, { -1, 2 }, { -1, -2 }, { 2, 1 }, { 2, -1 }, { -2, 1 }, { -2, -1 } }; // 馬的跳躍路徑（技巧）
private static int[][] map; // 地圖
private static int m, n;
private static int count = 0;// 統計有多少種走法
private static int step = 0;
public static void main(String[] args) {
m = 5;
n = 5;
int x = 0;
int y = 0;
map = new int[m][n];
jump(x, y);
System.out.println("---------");
System.out.println(count);
}
private static void jump(int x, int y) {
// 如果超出界限，那就繼續下一輪
if (x < 0 || x >= m || y < 0 || y >= n || map[x][y] != 0) {
return;
}
// 立足此節點
step ;
map[x][y] = step;
if (step == m * n) {
if (count == 0) // 如果是第一次，那就輸出一個
show(map);
count ;
}
// 寫出所有路徑（技巧）
int tx = 0, ty = 0;
for (int i = 0; i < 8; i ) {
tx = x next[i][0]; // 技巧
ty = y next[i][1];
jump(tx, ty);
}
// 還原
step--;
map[x][y] = 0;
}
// 顯示數組
private static void show(int[][] arr) {
for (int i = 0; i < m; i ) {
for (int j = 0; j < n; j ) {
System.out.print(arr[i][j] " \t");
}
System.out.println();
}
}
}
程序運行結果：
編程解決“八皇後問題”：即 在一個 8*8 的矩形格子中排放 8 個皇後。
要滿足的條件包括：任意兩個皇後不能在同一行，同一列，也不能在同一條對角線上。
要求編程給出解的個數。
答案：
算法原理：回溯法
首先，可歸納問題的條件為，8 皇後之間需滿足：
這為我們提供一種遍曆的思路，我們可以 逐行 或者 逐列 來進行可行擺放方案的遍曆，每一行（列）遍曆出一個符合條件的位置，接着就到下一行（列）遍曆下一個棋子的合适位置，這種遍曆思路可以保證我們遍曆過程中有一個條件是絕對符合的——就是下一個棋子的擺放位置與前面的棋子 不在同一行 （列）。
這裡我們 逐列擺放 ， 數組下标代表列号，用數組元素存放行号。
把當前列 N 的前面的某一列設為 m,則 m 的所有取值為｛m>=0,m<N｝的集合,故又可在上面式子的基礎，歸納為如下：
從這個圖可以看出， m和N若在同一斜線上 ，那麼 行差Am 和 列差AN 應該 相等 。
所以， 在點m存在的情況下，與點m列差為d的點，若行差也為±d，那麼就在一條斜線上，不合法。
我們規定當 row[i]=true 時，表示該列第 i 行不能放棋子。
這樣我們就能寫成下列程序段了：
// 八皇後
class Sy6 {
public static int num = 0; // 累計方案總數
public static final int MAXQUEEN = 8;// 皇後個數，同時也是棋盤行列總數
public static int[] cols = new int[MAXQUEEN]; // 定義cols數組，表示8列棋子擺放情況，數組元素存放行号
public Sy6() {
// 核心函數
put(0);
System.out.println(MAXQUEEN "皇後問題有" num "種擺放方法。");
}
// 擺第n個皇後
public void put(int n) {
// 遍曆該列所有不合法的行，并用 rows 數組記錄，不合法即 rows[i]=true
boolean[] rows = new boolean[MAXQUEEN]; // boolean默認false
for (int i = 0; i < n; i ) {
rows[cols[i]] = true; // 同行，不合法
int d = n - i; // 列差
if (cols[i] - d >= 0) // 判斷是否超界
// 行差為-d的斜線點，不合法
rows[cols[i] - d] = true;
if (cols[i] d <= MAXQUEEN - 1)// 判斷是否超界
// 行差為d的斜線點，不合法
rows[cols[i] d] = true;
}
// 所有路徑：八行都能擺
for (int i = 0; i < MAXQUEEN; i ) {
// 判斷該行是否合法，如果不合法，那就繼續下一輪
// 遞歸出口
if (rows[i])
continue;
// 設置當前列合法棋子所在行數
cols[n] = i;
// 當前列不為最後一列時
if (n < MAXQUEEN - 1) {
// 擺放下一個
put(n 1);
} else {
// 累計方案個數
num ;
}
}
}
public static void main(String args[]) {
Sy6 queen = new Sy6();
}
}
程序運行結果：
更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!
zpostcode 
Recruit 
weather 
mreligion 
Yellowpages 
sport 
constellation 
shopping 
name 
game 
directory 
literature 
Word 
tour 
furnish 
Lottery 
tftnews 
lyrics 
News 
digital 
car 
dir 
Edu 
Finance 
