教你怎么用Java回溯算法解數(shù)獨
一、題干
輸入一個9*9二維數(shù)組表示數(shù)獨,已經(jīng)填入的數(shù)字用1-9表示,待填入的數(shù)字用0表示,試寫一個算法解出數(shù)獨并輸出。
二、思路
容易想到回溯法,即以人的思維的解數(shù)獨,遍歷數(shù)組,如果是空白就從1-9依次選一個數(shù)判斷本行、列、3*3宮格內(nèi)是否有重復,如果有就進行下一個數(shù)字的選擇;如果該數(shù)暫時滿足條件,那么進行下一個格子的選擇,遞歸的終止條件是遍歷完所有格子。
三、代碼分段演示
輸入數(shù)組
Scanner sc = new Scanner(System.in); int[][] board = new int[9][9]; // 輸入 for (int i = 0; i < 9; i++) { for (int j = 0; j < 9; j++) { board[i][j] = sc.nextInt(); } }
dfs回溯
(r, c)
是當前正在判斷的格子坐標,board[r][c] == 0
判斷這個格子是否還沒有填數(shù),如果沒有,就從1-9依次選取一個數(shù),先判斷選的這個數(shù)是否合法,如果合法就做選擇,并開始下一個格子的判斷,決定完下一個格子之后就撤銷選擇(這是回溯法基本框架);如果該格子已填數(shù),直接開始下一個格子的判斷。終止條件就是r==9
,也就是二維數(shù)組遍歷完。
public static void dfs(int[][] board, int r, int c) { // 所有數(shù)填完了,輸出 if (r == 9) { for (int i = 0; i < 9; i++) { for (int j = 0; j < 9; j++) { System.out.print(board[i][j] + " "); } System.out.println(); } return; } // 空白填數(shù) if (board[r][c] == 0) { // 從 1-9 中依次選數(shù) for (int k = 1; k <= 9; k++) { // 先判斷放進去是否滿足條件再選擇 if (isValid(board, r, c, k)) { // 做選擇 board[r][c] = k; // 決定下一個格子 next(board, r, c); // 撤銷選擇 board[r][c] = 0; } } } // 非空白直接決定下一個格子 else next(board, r, c); }
在二維數(shù)組中,下一個格子有兩種可能:一是就在本行只需列+1即可,二是當前格子是本行最后一個,那么下一個格子就是下一行第一個。
// 遞歸下一個格子 public static void next(int[][] board, int r, int c) { if (c + 1 == 9) dfs(board, r + 1, 0); else dfs(board, r, c + 1); }
判斷是否滿足條件
行和列的判斷就不必細說了,關(guān)鍵是3*3宮格的判斷,行 / 3 * 3 和 列 / 3 * 3 就是所在的3*3宮格左上角格子的坐標,其中 / 是地板除法
// 判斷是否合法 public static boolean isValid(int[][] board, int r, int c, int val) { // 列 for (int i = 0; i < 9; i++) { if (board[i][c] == val) return false; } // 行 for (int j = 0; j < 9; j++) { if (board[r][j] == val) return false; } // 3 * 3 for (int x = r / 3 * 3, i = x; i < x + 3; i++) { for (int y = c / 3 * 3, j = y; j < y + 3; j++) { if (board[i][j] == val) return false; } } return true; }
四、完整代碼
public static void main(String[] args) { solveSudoku(); } public static void solveSudoku() { Scanner sc = new Scanner(System.in); int[][] board = new int[9][9]; // 輸入 for (int i = 0; i < 9; i++) { for (int j = 0; j < 9; j++) { board[i][j] = sc.nextInt(); } } dfs(board, 0, 0); } // 回溯填數(shù) public static void dfs(int[][] board, int r, int c) { // 所有數(shù)填完了,輸出 if (r == 9) { for (int i = 0; i < 9; i++) { for (int j = 0; j < 9; j++) { System.out.print(board[i][j] + " "); } System.out.println(); } return; } // 空白填數(shù) if (board[r][c] == 0) { for (int k = 1; k <= 9; k++) { if (isValid(board, r, c, k)) { // 做選擇 board[r][c] = k; // 決定下一個格子 next(board, r, c); // 撤銷選擇 board[r][c] = 0; } } } // 非空白直接決定下一個格子 else next(board, r, c); } // 遞歸下一個格子 public static void next(int[][] board, int r, int c) { if (c + 1 == 9) dfs(board, r + 1, 0); else dfs(board, r, c + 1); } // 判斷是否合法 public static boolean isValid(int[][] board, int r, int c, int val) { // 列 for (int i = 0; i < 9; i++) { if (board[i][c] == val) return false; } // 行 for (int j = 0; j < 9; j++) { if (board[r][j] == val) return false; } // 3 * 3 for (int x = r / 3 * 3, i = x; i < x + 3; i++) { for (int y = c / 3 * 3, j = y; j < y + 3; j++) { if (board[i][j] == val) return false; } } return true; }
順便提供幾個示例輸入輸出
輸入: 5 3 0 0 7 0 0 0 0 6 0 0 1 9 5 0 0 0 0 9 8 0 0 0 0 6 0 8 0 0 0 6 0 0 0 3 4 0 0 8 0 3 0 0 1 7 0 0 0 2 0 0 0 6 0 6 0 0 0 0 2 8 0 0 0 0 4 1 9 0 0 5 0 0 0 0 8 0 0 7 9 輸出: 5 3 4 6 7 8 9 1 2 6 7 2 1 9 5 3 4 8 1 9 8 3 4 2 5 6 7 8 5 9 7 6 1 4 2 3 4 2 6 8 5 3 7 9 1 7 1 3 9 2 4 8 5 6 9 6 1 5 3 7 2 8 4 2 8 7 4 1 9 6 3 5 3 4 5 2 8 6 1 7 9
輸入: 0 0 0 5 0 0 9 0 0 6 0 4 2 0 3 0 0 0 5 0 0 0 6 0 0 3 2 0 0 0 0 9 0 4 0 0 4 2 0 1 0 5 0 7 9 0 0 9 7 0 0 1 0 0 9 0 0 0 0 6 0 1 8 2 0 0 0 4 0 0 0 5 0 0 0 0 0 0 6 0 0 輸出: 7 3 2 5 8 1 9 6 4 6 9 4 2 7 3 5 8 1 5 1 8 4 6 9 7 3 2 1 7 5 6 9 8 4 2 3 4 2 6 1 3 5 8 7 9 3 8 9 7 2 4 1 5 6 9 4 7 3 5 6 2 1 8 2 6 1 8 4 7 3 9 5 8 5 3 9 1 2 6 4 7
輸入: 0 0 9 7 4 8 0 0 0 7 0 0 0 0 0 0 0 0 0 2 0 1 0 9 0 0 0 0 0 7 0 0 0 2 4 0 0 6 4 0 1 0 5 9 0 0 9 8 0 0 0 3 0 0 0 0 0 8 0 3 0 2 0 0 0 0 0 0 0 0 0 6 0 0 0 2 7 5 9 0 0 輸出: 5 1 9 7 4 8 6 3 2 7 8 3 6 5 2 4 1 9 4 2 6 1 3 9 8 7 5 3 5 7 9 8 6 2 4 1 2 6 4 3 1 7 5 9 8 1 9 8 5 2 4 3 6 7 9 7 5 8 6 3 1 2 4 8 3 2 4 9 1 7 5 6 6 4 1 2 7 5 9 8 3
到此這篇關(guān)于教你怎么用Java回溯算法解數(shù)獨的文章就介紹到這了,更多相關(guān)Java回溯法解數(shù)獨內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
SpringBoot集成Hutool防止XSS攻擊的兩種解決方法
XSS漏洞是生產(chǎn)上比較常見的問題,本文主要介紹了SpringBoot集成Hutool防止XSS攻擊的兩種解決方法,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧2024-04-04解決springboot服務啟動報錯:Unable?to?start?embedded?contain
這篇文章主要介紹了解決springboot服務啟動報錯:Unable?to?start?embedded?contain的問題,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教2022-08-08