數獨DFS求解

• 簡單數獨的DFS求解
• • 1. 問題
  • 2.求解
  • • 2.1 數據結構設計
    • 2.2 算法設計
    • 2.3 主要代碼
    • • 1.數獨遞歸處理函數 sudoku_try
      • 2.檢測函數 test
  • 3.完整代碼

簡單數獨的DFS求解

1. 問題

給出9×9的標準數獨，使用C語言編程完成這個數獨的求解。

數獨數獨（shù dú）是源自18世紀瑞士的一種數學游戲。是一種運用紙、筆進行演算的邏輯游戲。玩家需要根據9×9盤面上的已知數字，推理出所有剩余空格的數字，并滿足每一行、每一列、每一個粗線宮（3*3）內的數字均含1-9，不重復 [1] 。

數獨盤面是個九宮，每一宮又分為九個小格。在這八十一格中給出一定的已知數字和解題條件，利用邏輯和推理，在其他的空格上填入1-9的數字。使1-9每個數字在每一行、每一列和每一宮中都只出現一次，所以又稱“九宮格”。

2.求解

2.1 數據結構設計

數獨的定義決定了在C語言中使用一個二維數組就能完美的解決問題，所以這里使用9×9的二維數組存儲數獨，其中使用0表示需要填入數字的空格。

例如以上數獨可以使用如下數組數據表示：

0 6 3 0 0 7 8 0 00 1 2 3 0 0 5 0 00 0 5 0 0 0 0 1 00 5 0 4 0 0 0 0 00 3 7 0 0 0 4 9 00 0 0 0 0 2 0 6 00 8 0 0 0 0 6 0 00 0 4 0 0 6 7 8 00 0 6 2 0 0 9 3 0

以上0表示數獨中需要填入數組的空格

考慮到程序的可擴展性，比如解決超級數獨的情況，代碼中使用#define N 9這樣的預定義表示數獨大小。

2.2 算法設計

本案中可以暴力1-9從最左上角開始逐個嘗試，但是關鍵問題是如何使用代碼控制當發現嘗試的數字不符合要求，回退到上一個數字的分析狀態，然后嘗試上一個數字的其他情況。其實這種情況是典型的DFS應用場景。

也就是說在每一個需要填寫數字的位置，可以1-9逐個嘗試 ，而每一個嘗試又是可以遞歸成為對下一個位置1-9數字的嘗試。

梳理一下算法如下：

判斷是否已經將所有空格填滿，如果填滿輸出數獨然后直接退出程序。

判斷當前需要處理的數獨格子中，是否為0。

• 如果為0，表示當前格子是一個需要填入數字的空格，那么可以1-9嘗試填入一個數字，并驗證是否滿足要求。
  • 如果滿足要求，那么暫時使用這個結果，并對下一個格子使用本算法遞歸分析。
  • 如果所有1-9都不能滿足，那么表明上一次填入的數字是錯誤的，所以要回溯到上一次分析狀態中（這里實際上是可以通過遞歸函數的返回實現）。注意：由于前面的嘗試過程中，已經在數獨中嘗試填寫了各種數字，這時候回退上一層調用前，必須先恢復原來狀態，也就是將單元格設置為0。
• 如果為1，表示當前單元格中原來就有數字，不需要我們處理，那么可以跳過這一個，處理下面一個格子。

2.3 主要代碼

1.數獨遞歸處理函數 sudoku_try

void sudoku_try(int s[N][N], int x, int y){int i;if ( x == N ){ /* 當前處理到N行了，也就是0~N-1都填完了，結束！*/printf("\n");print(s); /* 輸出數獨 */exit(0); /* 退出程序 */}if ( s[x][y] == 0 ) {for ( i=1; i <= N; i++ ) {if ( test(s, x, y, i) ) {s[x][y] = i;sudoku_try(s, (y+1) / N + x, (y+1) % N);}}s[x][y] = 0; /* 回退到上一層遞歸調用前，消除前面嘗試遺留的數據。*/}else{sudoku_try(s, (y+1) / N + x, (y+1) % N);} }

請注意以上代碼中第5，15和18行代碼含義，有助于理解。

2.檢測函數 test

int test(int s[N][N], int x, int y, int k){int i, j;for (i = 0; i< N; i++) { /* 分別行列檢測是否有k已經存在 */if ( s[x][i] == k || s[i][y] == k ) return 0;}/* 檢測各自所在小9宮格 */for ( i = x / 3 * 3; i < x / 3 * 3 + 3; i++ )for ( j = y / 3 * 3; j < y / 3 * 3 + 3; j++ )if ( s[i][j] == k ) return 0;return 1; }

3.完整代碼

#include <stdio.h> #include <stdlib.h>#define N 9int test (int s[N][N], int x, int y, int k); void print(int s[N][N]); void sudoku_try(int s[N][N], int x, int y);int main (int argc, char *argv[]) {int sudoku[][N] = {{0, 6, 3, 0, 0, 7, 8, 0, 0},{0, 1, 2, 3, 0, 0, 5, 0, 0},{0, 0, 5, 0, 0, 0, 0, 1, 0},{0, 5, 0, 4, 0, 0, 0, 0, 0},{0, 3, 7, 0, 0, 0, 4, 9, 0},{0, 0, 0, 0, 0, 2, 0, 6, 0},{0, 8, 0, 0, 0, 0, 6, 0, 0},{0, 0, 4, 0, 0, 6, 7, 8, 0},{0, 0, 6, 2, 0, 0, 9, 3, 0},};print(sudoku);sudoku_try(sudoku, 0, 0);return 0; }void sudoku_try(int s[N][N], int x, int y){int i;if ( x == N ){printf("\n");print(s); /* 求一個解后退出，如果需 */exit(0); /* 要求出所有解，怎么修改?*/}if ( s[x][y] == 0 ) {for ( i=1; i <= N; i++ ) {if ( test(s, x, y, i) ) {s[x][y] = i;sudoku_try(s, (y+1) / N + x, (y+1) % N);}}s[x][y] = 0; /* 請解釋語句作用? */}else{sudoku_try(s, (y+1) / N + x, (y+1) % N);} }int test(int s[N][N], int x, int y, int k){int i, j;for (i = 0; i< N; i++) {if ( s[x][i] == k || s[i][y] == k ) return 0;}for ( i = x / 3 * 3; i < x / 3 * 3 + 3; i++ )for ( j = y / 3 * 3; j < y / 3 * 3 + 3; j++ )if ( s[i][j] == k ) return 0;return 1; }void print(int s[N][N]){int i, j;for ( i = 0; i < N; i++ ) {for ( j = 0; j < N; j++)printf("%3d", s[i][j]);printf("\n");} }

本例中代碼運行結果如下：

可以使用以上代碼，試試 https://www.sudoku.name/index-cn.php 網站上的數獨，算一下吧 😃

總結

以上是生活随笔為你收集整理的简单数独的DFS求解的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。