Leetcode0037--Sudoku Solver 数独游戏
【轉載請注明】http://www.cnblogs.com/igoslly/p/8719622.html
?
來看一下題目：
| ?????? Write a program to solve a Sudoku puzzle by filling the empty cells. Empty cells are indicated by the character '.'. ?????? You may assume that there will be only one unique solution. | 題目意思： 完成數獨游戲的計算 |
在做這題的前兩天，樓主正在摸索華為筆試題的時候，已經寫了一個非常直白的實現，具體鏈接如下：
http://www.cnblogs.com/igoslly/p/8708960.html
不過和原題有些區別：① 所有數據均以字符串形式保存? ②? 需要填寫的位置以 “.” 代替 0
我們稍稍修改下代碼，就可以得到實現方法1：
bool check(int n,char key,vector<vector<char>> num){for(int i=0;i<9;i++){int j=n/9;if(num[j][i]==key){return false;}} for(int i=0;i<9;i++){int j=n%9;if(num[i][j]==key){return false;}}int x=n/9/3*3;int y=n%9/3*3;for(int i=x;i<x+3;i++){for(int j=y;j<y+3;j++){if(num[i][j]==key){return false;}}}return true; } void dfs(int n,vector<vector<char>> &num,bool *sign){if(n>80){*sign=true;return;}if(num[n/9][n%9]!='.'){ dfs(n+1,num,sign);}else{for(char i='1';i<='9';i++){if(check(n,i,num)==true){num[n/9][n%9]=i;dfs(n+1,num,sign);if(*sign==true) return;}}num[n/9][n%9]='.';} } class Solution { public:void solveSudoku(vector<vector<char>>& board) {bool sign=false;dfs(0,board,&sign);} };實現方法2：
??????? 優化check函數，將原先逐行、逐列遍歷進行判斷的方法 → 記錄每行、每列、每九宮格是否含有當前數字
??????? 具體實施（較原先冗長的代碼簡短太多）：
// line[i][j],column[i][j],subcube[i][j] 分別代表數獨每行、每列、每個子單元是否含有數字j（對應1-9）bool line[9][9],column[9][9],subcube[9][9];??????? 進行dfs前，首先要對原題給出的數字進行記錄
// 將所有數組置為falsememset(line,false,sizeof(line));memset(column,false,sizeof(column));memset(subcube,false,sizeof(subcube));// 根據題意，設定初始數組的值for(int i=0;i<9;i++){for(int j=0;j<9;j++){if(board[i][j]=='.')continue;int num=board[i][j]-'1';// 給定題目存在問題，無解，直接返回int cube=i/3*3 + j/3;if(line[i][num] || column[j][num] || subcube[cube][num]) return ;line[i][num] = column[j][num] = subcube[cube][num] = true;}}實現方法3：
????? 在實現方法1中，我們使用 n = 0~80 來記錄當前填充空格，根據 n 是否越界判斷數獨填充是否完成。
????? 當然我們也可以采用 i & j / row & col 對位置進行記錄，更為直觀；
????? 逐行進行填充時，需要對 j > 8 （初始 0）進行換行操作：
// 當j>8時，i++，否則 i 值不變 // 當j>8時，及時取余，重新從0~8計算 (i,j) -> (i+(j+1)/9,(j+1)%9)?????? 具體遞歸代碼：
bool step(vector<vector<char>>&board,int i,int j){if(i==9)return true;if(board[i][j]!='.'){if(i==8&&j==8){return true;}else{return step(board,i+(j+1)/9,(j+1)%9); // step里值表示i,j換行 }}int cube=i/3*3 + j/3;for(int k=0;k<9;k++){if(line[i][k] || column[j][k] || subcube[cube][k])continue;line[i][k] = column[j][k] = subcube[cube][k] = true;board[i][j] = '1'+k;if(step(board,i+(j+1)/9,(j+1)%9)) // 若數獨已完成，直接返回truereturn true;line[i][k] = column[j][k] = subcube[cube][k] = false;board[i][j] = '.';}return false;} G M T| Detect languageAfrikaansAlbanianArabicArmenianAzerbaijaniBasqueBelarusianBengaliBosnianBulgarianCatalanCebuanoChichewaChinese (Simplified)Chinese (Traditional)CroatianCzechDanishDutchEnglishEsperantoEstonianFilipinoFinnishFrenchGalicianGeorgianGermanGreekGujaratiHaitian CreoleHausaHebrewHindiHmongHungarianIcelandicIgboIndonesianIrishItalianJapaneseJavaneseKannadaKazakhKhmerKoreanLaoLatinLatvianLithuanianMacedonianMalagasyMalayMalayalamMalteseMaoriMarathiMongolianMyanmar (Burmese)NepaliNorwegianPersianPolishPortuguesePunjabiRomanianRussianSerbianSesothoSinhalaSlovakSlovenianSomaliSpanishSundaneseSwahiliSwedishTajikTamilTeluguThaiTurkishUkrainianUrduUzbekVietnameseWelshYiddishYorubaZulu | ? | AfrikaansAlbanianArabicArmenianAzerbaijaniBasqueBelarusianBengaliBosnianBulgarianCatalanCebuanoChichewaChinese (Simplified)Chinese (Traditional)CroatianCzechDanishDutchEnglishEsperantoEstonianFilipinoFinnishFrenchGalicianGeorgianGermanGreekGujaratiHaitian CreoleHausaHebrewHindiHmongHungarianIcelandicIgboIndonesianIrishItalianJapaneseJavaneseKannadaKazakhKhmerKoreanLaoLatinLatvianLithuanianMacedonianMalagasyMalayMalayalamMalteseMaoriMarathiMongolianMyanmar (Burmese)NepaliNorwegianPersianPolishPortuguesePunjabiRomanianRussianSerbianSesothoSinhalaSlovakSlovenianSomaliSpanishSundaneseSwahiliSwedishTajikTamilTeluguThaiTurkishUkrainianUrduUzbekVietnameseWelshYiddishYorubaZulu | ? | ? | ? | ? | ? |
| ? | Options : History : Feedback : Donate | Close |
轉載于:https://www.cnblogs.com/igoslly/p/8719622.html
總結
以上是生活随笔為你收集整理的Leetcode0037--Sudoku Solver 数独游戏的全部內容，希望文章能夠幫你解決所遇到的問題。
