java回溯算法解數(shù)獨問題
本文實例為大家分享了java回溯算法解數(shù)獨問題，供大家參考，具體內(nèi)容如下
下面來詳細講一下如何用回溯算法來解數(shù)獨問題。
下圖是一個數(shù)獨題，也是號稱世界上最難的數(shù)獨。當然了，對于計算機程序來說，只要算法是對的，難不難就不知道了，反正計算機又不累?；厮菟惴ɑ旧暇褪歉F舉，解這種數(shù)獨類的問題邏輯比較簡單。
不管算法懂不懂，先把類建出來，變量定義好，那放大學(xué)試卷上就是可以拿兩分了。
package shudu;
/**
* Created by wolf on 2016/3/17.
*/
public class Sudoku {
private int[][] matrix;
public Sudoku(int[][] matrix) {
this.matrix = matrix;
}
public static void main(String[] args) {
// 號稱世界上最難數(shù)獨
int[][] sudoku = {
{8, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 3, 6, 0, 0, 0, 0, 0},
{0, 7, 0, 0, 9, 0, 2, 0, 0},
{0, 5, 0, 0, 0, 7, 0, 0, 0},
{0, 0, 0, 0, 4, 5, 7, 0, 0},
{0, 0, 0, 1, 0, 0, 0, 3, 0},
{0, 0, 1, 0, 0, 0, 0, 6, 8},
{0, 0, 8, 5, 0, 0, 0, 1, 0},
{0, 9, 0, 0, 0, 0, 4, 0, 0}};
Sudoku s = new Sudoku(sudoku);
s.backTrace(0, 0);
}
/**
* 數(shù)獨算法
* @param i
* 行號
* @param j
* 列號
*/
private void backTrace(int i, int j) {
}
}
用一個二維數(shù)組來存儲這個矩陣，然后定義一個方法來計算。方法里有兩個屬性——行號和列號。
我們的原理就是從第0行0列開始，依次往里面填入1-9之間的數(shù)字，然后判斷填入的這個數(shù)字是否能放進去（該行該列和它所在的小九宮格是否有重復(fù)數(shù)字）。如果能放進去，那么就繼續(xù)用1-9去試該行的下一列。一直到該行的最后一列，然后換行繼續(xù)重復(fù)上面的步驟（也就是執(zhí)行backTrace方法）。一直執(zhí)行到最后一個空格，也就是i=8,j=8的時候，且最后這個空格所放的值也完全符合規(guī)則，那么此時就算完成，不用再繼續(xù)調(diào)用backTrace方法了，輸出正確解即可。
所以回溯法樣子看起來是這樣的。給第一個空格填1-9中任何一個，開始判斷，如果OK，然后進入下一層，如果不OK，就斷掉了。下一層還是從1-9開始試，然后OK，不OK……當最終目標達到時，空格已填滿又滿足條件，那么中斷該分支，輸出結(jié)果。
繼續(xù)我們的程序。
由于有些位置已經(jīng)有數(shù)字了，所以我們需要判斷，如果該坑已經(jīng)有人蹲了，那么就把列號j加1，進入下一列。如果到第8列了，就換行。
修改程序如下：
package shudu;
/**
* Created by wolf on 2016/3/17.
*/
public class Sudoku {
private int[][] matrix;
public Sudoku(int[][] matrix) {
this.matrix = matrix;
}
public static void main(String[] args) {
// 號稱世界上最難數(shù)獨
int[][] sudoku = {
{8, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 3, 6, 0, 0, 0, 0, 0},
{0, 7, 0, 0, 9, 0, 2, 0, 0},
{0, 5, 0, 0, 0, 7, 0, 0, 0},
{0, 0, 0, 0, 4, 5, 7, 0, 0},
{0, 0, 0, 1, 0, 0, 0, 3, 0},
{0, 0, 1, 0, 0, 0, 0, 6, 8},
{0, 0, 8, 5, 0, 0, 0, 1, 0},
{0, 9, 0, 0, 0, 0, 4, 0, 0}};
Sudoku s = new Sudoku(sudoku);
s.backTrace(0, 0);
}
/**
* 數(shù)獨算法
*
* @param i 行號
* @param j 列號
*/
private void backTrace(int i, int j) {
//如果i行j列是空格，那么才進入給空格填值的邏輯
if (matrix[i][j] == 0) {
for (int k = 1; k <= 9; k++) {
//判斷給i行j列放1-9中的任意一個數(shù)是否能滿足規(guī)則
if (check(i, j, k)) {
//將該值賦給該空格，然后進入下一個空格
matrix[i][j] = k;
backTrace(i, j + 1);
}
}
} else {
//如果該位置已經(jīng)有值了，就進入下一個空格進行計算
backTrace(i, j + 1);
}
}
/**
* 判斷給某行某列賦值是否符合規(guī)則
*
* @param row 被賦值的行號
* @param line 被賦值的列號
* @param number 賦的值
* @return
*/
private boolean check(int row, int line, int number) {
//判斷該行該列是否有重復(fù)數(shù)字
for (int i = 0; i < 9; i++) {
if (matrix[row][i] == number || matrix[i][line] == number) {
return false;
}
}
//判斷小九宮格是否有重復(fù)
int tempRow = row / 3;
int tempLine = line / 3;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (matrix[tempRow * 3 + i][tempLine * 3 + j] == number) {
return false;
}
}
}
return true;
}
}
此時已經(jīng)寫好了判斷某行某列賦某個值是否ok的方法，通過該方法就能校驗出數(shù)字是否能放到該位置。
還缺少的是邊界值的判斷，就是當已經(jīng)到最后一列了，還沒到最后一行時，需要對行號加1，然后恢復(fù)列號為0。
修改一下backTrace方法，增加邊界值判斷。
package shudu;
/**
* Created by wolf on 2016/3/17.
*/
public class Sudoku {
private int[][] matrix;
public Sudoku(int[][] matrix) {
this.matrix = matrix;
}
public static void main(String[] args) {
// 號稱世界上最難數(shù)獨
int[][] sudoku = {
{8, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 3, 6, 0, 0, 0, 0, 0},
{0, 7, 0, 0, 9, 0, 2, 0, 0},
{0, 5, 0, 0, 0, 7, 0, 0, 0},
{0, 0, 0, 0, 4, 5, 7, 0, 0},
{0, 0, 0, 1, 0, 0, 0, 3, 0},
{0, 0, 1, 0, 0, 0, 0, 6, 8},
{0, 0, 8, 5, 0, 0, 0, 1, 0},
{0, 9, 0, 0, 0, 0, 4, 0, 0}};
Sudoku s = new Sudoku(sudoku);
s.backTrace(0, 0);
}
/**
* 數(shù)獨算法
*
* @param i 行號
* @param j 列號
*/
private void backTrace(int i, int j) {
if (i == 8 && j == 9) {
//已經(jīng)成功了，打印數(shù)組即可
System.out.println("獲取正確解");
printArray();
return;
}
//已經(jīng)到了列末尾了，還沒到行尾，就換行
if (j == 9) {
i++;
j = 0;
}
//如果i行j列是空格，那么才進入給空格填值的邏輯
if (matrix[i][j] == 0) {
for (int k = 1; k <= 9; k++) {
//判斷給i行j列放1-9中的任意一個數(shù)是否能滿足規(guī)則
if (check(i, j, k)) {
//將該值賦給該空格，然后進入下一個空格
matrix[i][j] = k;
backTrace(i, j + 1);
}
}
} else {
//如果該位置已經(jīng)有值了，就進入下一個空格進行計算
backTrace(i, j + 1);
}
}
/**
* 判斷給某行某列賦值是否符合規(guī)則
*
* @param row 被賦值的行號
* @param line 被賦值的列號
* @param number 賦的值
* @return
*/
private boolean check(int row, int line, int number) {
//判斷該行該列是否有重復(fù)數(shù)字
for (int i = 0; i < 9; i++) {
if (matrix[row][i] == number || matrix[i][line] == number) {
return false;
}
}
//判斷小九宮格是否有重復(fù)
int tempRow = row / 3;
int tempLine = line / 3;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (matrix[tempRow * 3 + i][tempLine * 3 + j] == number) {
return false;
}
}
}
return true;
}
/**
* 打印矩陣
*/
public void printArray() {
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
System.out.print(matrix[i][j] + " ");
}
System.out.println();
}
System.out.println();
}
}
可以看到，判斷成功的標志是行號為8，且列號為9時，認為找到了正確解。為什么是9呢，因為在check(i,j,k)那一步，通過了的話，將值K賦給最后一個空格，此時并沒有中斷程序，而且進入了下一層循環(huán)backTrace（i，j + 1），所以i為8j為9時才是終解。程序到這里，運行一下看看，發(fā)現(xiàn)并沒有任何輸出值，并沒有找到正確解，why？
下面要講的就是該程序最關(guān)鍵的地方，也是比較難以理解的地方，就是對根節(jié)點的初始化?；厮菟惴ㄖv究的是一條道走到黑，不撞南墻不回頭，并且把所有的道都走完。
我們把問題簡單化，譬如一共只有兩個空格，只能放0和1，正確答案是00和11.我們給第一個空格放了0，此時我們不知道是否放了0之后，后面是否能完全正確的走完全程。就像走迷宮一樣，你選擇了第一個岔道，此時有可能第一個岔道就是錯的，后面無論怎么走都對了不了，也有可能有多條道可以走。那么我們的做法是先第一步放0，發(fā)現(xiàn)沒問題（符合只能放0和1的規(guī)則），然后走第二步，第二步如果走對了，那就直接走出去了，獲得了一次正確的解（00）。如果第二步是個死胡同（01），那就要回頭了，就是要回到原點，把第一步初始化一下，然后第一步走1，然后再繼續(xù)后面的步驟。所以無論怎么樣，你都需要在第二步走完之后，把第一步走的值給清掉，回歸到原點。這樣才能找到所有的正確路線。
問題放大一下，有N步（N未知），第一步有1-9共9種情況，第一步放了1，后面還有未知的步，那無論后面成功與否，你肯定都要去試第一步放2-9之間的數(shù)字。
看第51行for循環(huán)那里，第一次將數(shù)字1賦給第一個空格。然后判斷是否OK，如果OK了，就進入第二個空格去了，后面具體走多少步我們就不管了，我們只需要在后面的走完之后，初始化第一個空格就行了。那要是不OK呢，不OK當然就不用管他了，這一層走完就沒下文了，等于該分支就斷了。所以我們要在第55行后面加一句初始化的操作matrix[i][j]=0.
完整代碼如下：
package shudu;
/**
* Created by wolf on 2016/3/17.
*/
public class Sudoku {
private int[][] matrix;
public Sudoku(int[][] matrix) {
this.matrix = matrix;
}
public static void main(String[] args) {
// 號稱世界上最難數(shù)獨
int[][] sudoku = {
{8, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 3, 6, 0, 0, 0, 0, 0},
{0, 7, 0, 0, 9, 0, 2, 0, 0},
{0, 5, 0, 0, 0, 7, 0, 0, 0},
{0, 0, 0, 0, 4, 5, 7, 0, 0},
{0, 0, 0, 1, 0, 0, 0, 3, 0},
{0, 0, 1, 0, 0, 0, 0, 6, 8},
{0, 0, 8, 5, 0, 0, 0, 1, 0},
{0, 9, 0, 0, 0, 0, 4, 0, 0}};
Sudoku s = new Sudoku(sudoku);
s.backTrace(0, 0);
}
/**
* 數(shù)獨算法
*
* @param i 行號
* @param j 列號
*/
private void backTrace(int i, int j) {
if (i == 8 && j == 9) {
//已經(jīng)成功了，打印數(shù)組即可
System.out.println("獲取正確解");
printArray();
return;
}
//已經(jīng)到了列末尾了，還沒到行尾，就換行
if (j == 9) {
i++;
j = 0;
}
//如果i行j列是空格，那么才進入給空格填值的邏輯
if (matrix[i][j] == 0) {
for (int k = 1; k <= 9; k++) {
//判斷給i行j列放1-9中的任意一個數(shù)是否能滿足規(guī)則
if (check(i, j, k)) {
//將該值賦給該空格，然后進入下一個空格
matrix[i][j] = k;
backTrace(i, j + 1);
//初始化該空格
matrix[i][j] = 0;
}
}
} else {
//如果該位置已經(jīng)有值了，就進入下一個空格進行計算
backTrace(i, j + 1);
}
}
/**
* 判斷給某行某列賦值是否符合規(guī)則
*
* @param row 被賦值的行號
* @param line 被賦值的列號
* @param number 賦的值
* @return
*/
private boolean check(int row, int line, int number) {
//判斷該行該列是否有重復(fù)數(shù)字
for (int i = 0; i < 9; i++) {
if (matrix[row][i] == number || matrix[i][line] == number) {
return false;
}
}
//判斷小九宮格是否有重復(fù)
int tempRow = row / 3;
int tempLine = line / 3;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (matrix[tempRow * 3 + i][tempLine * 3 + j] == number) {
return false;
}
}
}
return true;
}
/**
* 打印矩陣
*/
public void printArray() {
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
System.out.print(matrix[i][j] + " ");
}
System.out.println();
}
System.out.println();
}
}
以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。
相關(guān)文章
參數(shù)映射準確來說是springmvc來幫我們干的活,但是由于springboot太過火爆,簡化了springmvc相關(guān)配置文件,以至于很多人會誤認為是springboot的功能,本文將給大家介紹SpringBoot接收各種各樣參數(shù),文中有詳細的代碼講解,需要的朋友可以參考下2024-04-04
SpringBoot + openFeign實現(xiàn)遠程接口調(diào)用的過程
現(xiàn)在的微服務(wù)項目不少都使用的是springboot+spring cloud構(gòu)建的項目，微服務(wù)之間的調(diào)用都離不開feign來進行遠程調(diào)用，這篇文章主要介紹了SpringBoot + openFeign實現(xiàn)遠程接口調(diào)用,需要的朋友可以參考下2022-11-11
Java FtpClient 實現(xiàn)文件上傳服務(wù)
本文主要對Java FtpClient實現(xiàn)簡單的圖片上傳到服務(wù)器的方法進行介紹，并且展示的小demo中，對配置過程中主要碰到的問題：關(guān)于文件權(quán)限的問題也進行了說明，下面跟著小編一起來看下吧2016-12-12
本篇文章主要介紹了ssm框架上傳圖片保存到本地和數(shù)據(jù)庫示例，主要使用了Spring+SpringMVC+MyBatis框架集合，有興趣的可以了解一下。2017-03-03
今天給大家?guī)淼氖顷P(guān)于Java的相關(guān)知識,文章圍繞著Java常見的排序算法展開,文中有非常詳細的介紹及代碼示例,需要的朋友可以參考下2021-06-06
本文介紹了在Springboot中配置Hikari連接池的具體參數(shù)和設(shè)置,涵蓋了autoCommit, connectionTimeout, idleTimeout, maxLifetime, minimumIdle, maximumPoolSize等關(guān)鍵配置項,并提供了它們的默認值、描述和條件下的重置規(guī)則2024-09-09
使用SpringBoot的CommandLineRunner遇到的坑及解決
這篇文章主要介紹了使用SpringBoot的CommandLineRunner遇到的坑及解決方案，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2023-02-02
解決SpringCloud Feign傳對象參數(shù)調(diào)用失敗的問題
這篇文章主要介紹了解決SpringCloud Feign傳對象參數(shù)調(diào)用失敗的問題，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-06-06
這篇文章主要介紹了java中g(shù)eneric實例詳解，具有一定參考價值，需要的朋友可以了解下。2017-11-11
Java中過濾器 (Filter) 和 攔截器 (Interceptor)的使用
這篇文章主要介紹了Java中過濾器 (Filter) 和 攔截器 (Interceptor)的使用，文中通過示例代碼介紹的非常詳細，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-05-05