說到數獨，或者九宮格，我想大家一定都不陌生，初中高中看的各種雜志上都有這種益智游戲，現在的智能手機上也有人寫出了這種游戲，閑暇時候玩玩也能活躍一下腦子。還有看《模仿游戲》這部電影里面，圖靈在選拔隊友的時候好像出的也是數獨的題目。

我本來對數獨不是太感興趣，但是一個偶然的機會看到朋友在玩這個游戲，就想寫出一個破解算法，來在朋友面前炫耀一下，也可以順便復習一下最近學習的C語言。

數獨事實上就是一個9*9的一個方陣，之所以又叫九宮格，是因為其中每3*3的方陣為一宮，整個大方陣有九個這樣的宮。規則是在每一行每一列填上1~9九個數字，使得各行各列填滿且不重復，并且每一宮中的數字也是1~9不重復。

對于算法來講，主要使用遞歸，對于數據結構來講，用二維數組來表示9*9的方陣，然而每一個位置都有兩個屬性，即數值和所在的宮，所以一開始我先聲明了一個結構體來包含這兩個屬性。然后用一個分配算法來分配各個位置的數字所在的宮。具體的破解算法其實就是讓程序去測試每一個位置該填什么數字，需要判斷每一行，每一列，每一宮是否有重復，都沒有重復則表示成功。如果成功則保留，不成功則退回重新測試。通過輸入原始數據來讓程序運行，程序執行后如果有解則輸出方陣，如果沒有則輸出無解。具體程序如下（C語言）：

#include<stdio.h> #include<stdlib.h> #define _CRT_SECURE_NO_DEPRECATE #pragma warning(disable:4996) #define N 9struct theNums{int num;//數字int pala;//所在的宮 }; struct theNums tn[N][N];int result = 0; //結果數void sharePal(struct theNums shnum[N][N]){//分配宮格int row, col;for (row = 1; row <= N; row++){for (col = 1; col <= N; col++){if (row >= 1 && row <= 3){if(col >= 1 && col <= 3)shnum[row - 1][col - 1].pala = 1;else if (col >= 4&& col <= 6)shnum[row - 1][col - 1].pala = 2;elseshnum[row - 1][col - 1].pala = 3;}else if (row >= 4 && row <= 6){if (col >= 1 && col <= 3)shnum[row - 1][col - 1].pala = 4;else if (col >= 4 && col <= 6)shnum[row - 1][col - 1].pala = 5;elseshnum[row - 1][col - 1].pala = 6;}else{if (col >= 1 && col <= 3)shnum[row - 1][col - 1].pala = 7;else if (col >= 4 && col <= 6)shnum[row - 1][col - 1].pala = 8;elseshnum[row - 1][col - 1].pala = 9;}}} }bool check(struct theNums chenum[N][N], int row, int col, int key){int i, j;//判斷行for (i = 0; i < N; i++){if (chenum[row][i].num == key)return false;}//判斷列for (j = 0; j<N; j++){if (chenum[j][col].num == key)return false;}//判斷所在的宮for (i = 0; i < N; i++){for (j = 0; j < N; j++){if (chenum[i][j].pala == chenum[row][col].pala){if (chenum[i][j].num == key)return false;}}}//可行return true; }int printNum(struct theNums num[N][N]){//輸出九宮格result++;printf("第%d個填法為：\n", result);int i, j;for (i = 0; i < N; i++){for (j = 0; j < N; j++){printf("%3d", num[i][j].num);if (j == 2 || j == 5)printf("\t");}printf("\n");if (i == 2 || i == 5)printf("\n");}return 0; }void CrossWords(struct theNums CWnum[N][N], int n) {//九宮格破解算法struct theNums temp[N][N];int i, j;for (i = 0; i<9; i++){for (j = 0; j < 9; j++){temp[i][j].num = CWnum[i][j].num;temp[i][j].pala = CWnum[i][j].pala;}}i = n / 9; j = n % 9; //求出第n個數的行數和列數if (CWnum[i][j].num != 0) //已經有原始數據{if (n == 80) //是最后一個格子，輸出可行解printNum(temp);else //不是最后一個格子，求下一個格子CrossWords(temp, n + 1);}else //沒有數據{for (int k = 1; k <= 9; k++){bool flag = check(temp, i, j, k);if (flag) //第i行、第j列可以是k{temp[i][j].num = k; //設為kif (n == 80)printNum(temp);elseCrossWords(temp, n + 1);temp[i][j].num = 0; //恢復為0，判斷下一個k}}} }void main(){printf("請輸入數獨中的原始數據，沒有數據的用0代替。\n");for (int i = 0; i<N; i++){printf("Please Input第%d行Numbers：", i + 1);for (int j = 0; j<N; j++)scanf("%d", &tn[i][j].num);}sharePal(tn);printf("數獨的解為：\n\n");CrossWords(tn, 0);if (result == 0)printf("Bad Input,無解!"); // printNum(tn);//輸出九宮格system("pause"); }
舉個例子，芬蘭數學家因卡拉花費3個月設計出了世界上迄今難度最大的九宮格游戲，而且它只有一個答案（皮埃斯：人家花3個月才搞出來的程序一跑幾秒就跑出來了，是對先人的不敬還是時代發展的必然），如下圖：

總結

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

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