亚洲乱码中文字幕综合,中国熟女仑乱hd,亚洲精品乱拍国产一区二区三区,一本大道卡一卡二卡三乱码全集资源,又粗又黄又硬又爽的免费视频

教你怎么用Java回溯算法解數(shù)獨

 更新時間:2021年06月02日 15:38:46   作者:趨向_quxiang  
一直不太會數(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)文章

  • Java 如何獲取url地址文件流

    Java 如何獲取url地址文件流

    這篇文章主要介紹了Java 如何獲取url地址文件流,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教
    2022-07-07
  • 關(guān)于Springboot中JSCH的使用及說明

    關(guān)于Springboot中JSCH的使用及說明

    這篇文章主要介紹了關(guān)于Springboot中JSCH的使用及說明,具有很好的參考價值,希望對大家有所幫助。
    2022-09-09
  • Java方法重載和重寫原理區(qū)別解析

    Java方法重載和重寫原理區(qū)別解析

    這篇文章主要介紹了Java方法重載和重寫原理區(qū)別解析,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下
    2020-03-03
  • Java中的移位運算符使用及原理詳解

    Java中的移位運算符使用及原理詳解

    在 Java 中,移位運算符用于對二進制數(shù)進行位移操作,它們可以將一個數(shù)的所有位向左或向右移動指定的位數(shù),本文小編將給大家詳細的介紹一下Java移位運算符,需要的朋友可以參考下
    2023-09-09
  • 如何在java中使用Jython

    如何在java中使用Jython

    這篇文章主要介紹了如何在java中使用Jython,由于項目中需要用到Java調(diào)用Python的腳本,來實現(xiàn)一些功能,就對jython做了一些了解,通過jython可以實現(xiàn)java對python腳本的調(diào)用,需要的朋友可以參考一下
    2022-03-03
  • SpringBoot集成Hutool防止XSS攻擊的兩種解決方法

    SpringBoot集成Hutool防止XSS攻擊的兩種解決方法

    XSS漏洞是生產(chǎn)上比較常見的問題,本文主要介紹了SpringBoot集成Hutool防止XSS攻擊的兩種解決方法,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧
    2024-04-04
  • java操作xml的方法匯總及解析

    java操作xml的方法匯總及解析

    這篇文章主要介紹了java操作xml的方法匯總及解析,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下
    2019-11-11
  • java調(diào)用通義千問API的詳細完整步驟

    java調(diào)用通義千問API的詳細完整步驟

    通義千問是阿里云自主研發(fā)的大語言模型,能夠在用戶自然語言輸入的基礎(chǔ)上,通過自然語言理解和語義分析,理解用戶意圖,在不同領(lǐng)域、任務內(nèi)為用戶提供服務和幫助,下面這篇文章主要給大家介紹了關(guān)于java調(diào)用通義千問API的詳細完整步驟,需要的朋友可以參考下
    2024-02-02
  • 解決springboot服務啟動報錯:Unable?to?start?embedded?contain

    解決springboot服務啟動報錯:Unable?to?start?embedded?contain

    這篇文章主要介紹了解決springboot服務啟動報錯:Unable?to?start?embedded?contain的問題,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教
    2022-08-08
  • Java編寫簡單猜數(shù)游戲

    Java編寫簡單猜數(shù)游戲

    這篇文章主要為大家詳細介紹了Java編寫簡單猜數(shù)游戲,文中示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2021-01-01

最新評論