教你怎么用Java回溯算法解數獨
更新時間：2021年06月02日 15:38:46 作者：趨向_quxiang
一直不太會數獨問題,這次下決定搞明白,所以整理了本篇文章,文中有非常詳細的代碼示例,對不會算法的小伙伴們很有幫助,需要的朋友可以參考下
一、題干
輸入一個9*9二維數組表示數獨，已經填入的數字用1-9表示，待填入的數字用0表示，試寫一個算法解出數獨并輸出。
二、思路
容易想到回溯法，即以人的思維的解數獨，遍歷數組，如果是空白就從1-9依次選一個數判斷本行、列、3*3宮格內是否有重復，如果有就進行下一個數字的選擇；如果該數暫時滿足條件，那么進行下一個格子的選擇，遞歸的終止條件是遍歷完所有格子。
三、代碼分段演示
輸入數組
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判斷這個格子是否還沒有填數，如果沒有，就從1-9依次選取一個數，先判斷選的這個數是否合法，如果合法就做選擇，并開始下一個格子的判斷，決定完下一個格子之后就撤銷選擇(這是回溯法基本框架)；如果該格子已填數，直接開始下一個格子的判斷。終止條件就是r==9，也就是二維數組遍歷完。
public static void dfs(int[][] board, int r, int c) {
// 所有數填完了，輸出
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;
}
// 空白填數
if (board[r][c] == 0) {
// 從 1-9 中依次選數
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);
}
在二維數組中，下一個格子有兩種可能：一是就在本行只需列+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);
}
判斷是否滿足條件
行和列的判斷就不必細說了，關鍵是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);
}
// 回溯填數
public static void dfs(int[][] board, int r, int c) {
// 所有數填完了，輸出
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;
}
// 空白填數
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
到此這篇關于教你怎么用Java回溯算法解數獨的文章就介紹到這了,更多相關Java回溯法解數獨內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
這篇文章主要為大家詳細介紹了java實現(xiàn)在線聊天系統(tǒng)，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-09-09
synchronized作為Java程序員最常用同步工具，很多人卻對它的用法和實現(xiàn)原理一知半解，以至于還有不少人認為synchronized是重量級鎖，性能較差，盡量少用。但不可否認的是synchronized依然是并發(fā)首選工具，本文就來詳細講講2023-02-02
動態(tài)代理是基于接口實現(xiàn)的代理,mybatis就是用這個技術實現(xiàn)的,下面這篇文章主要給大家介紹了關于java中動態(tài)代理如何實現(xiàn)的相關資料,需要的朋友可以參考下2024-01-01
Java swing實現(xiàn)酒店管理系統(tǒng)
這篇文章主要為大家詳細介紹了Java swing實現(xiàn)酒店管理系統(tǒng)，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-02-02
本篇文章主要介紹了spring 5 webclient使用指南詳解，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2018-01-01
這篇文章主要介紹了idea如何快速查找一個類或類中方法名和變量問題,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2023-11-11
相對于FillLayout來說，RowLayout比較靈活，功能也比較強。用戶可以設置布局中子元素的大小、邊距、換行及間距等屬性。2009-06-06
Java 8 Stream Api 中的 map和 flatMap 操作方法
Java 8提供了非常好用的 Stream API ,可以很方便的操作集合。今天通過這篇文章給大家分享Java 8 Stream Api 中的 map和 flatMap 操作方法,需要的朋友可以參考下2019-11-11
最近工作中遇到需要計算時間差,這里給大家總結下,下面這篇文章主要給大家介紹了關于Java計算Date類時間差的相關資料,文中通過代碼介紹的非常詳細,需要的朋友可以參考下2023-12-12
這篇文章主要介紹了springboot枚舉類型傳遞的步驟，幫助大家更好的理解和學習使用springboot，感興趣的朋友可以了解下，希望能給你帶來幫助2021-08-08