37. Sudoku Solver

題目

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.



A sudoku puzzle...


...and its solution numbers marked in red.

分析

一開始想通過推理得到,希望通過數(shù)獨(dú)的規(guī)則得到每個(gè)空白格子可能的取值梗醇,然后往只有一種可能取值的格子填入該值。但是發(fā)現(xiàn)這樣不能得到最終結(jié)果温鸽。因?yàn)橥评淼倪^程實(shí)際上要使用三種方法手负。這就使得算法變得很復(fù)雜涤垫。
另一個(gè)思路是使用搜索蝠猬,但是直接搜索恐怕需要花費(fèi)高昂的代價(jià)统捶。
不過看題解是通過填入一個(gè)數(shù)字敦姻,然后使用第36題中的方法來判斷是否合法來確定是否繼續(xù)歧杏。這樣其實(shí)不需要搜索完整個(gè)空間犬绒,可以不超時(shí)完成。

實(shí)現(xiàn)一

class Solution {
public:
    bool solveSudoku(vector<vector<char>>& board) {
        for(int i=0; i<9; i++){
            for(int j=0; j<9; j++){
                if(board[i][j]!='.')
                    continue;
                for(int num=0; num<9; num++){
                    board[i][j] = num + '0' + 1;
                    if(isValidSudoku(board) && solveSudoku(board))
                        return true;
                    board[i][j] = '.';
                }
                return false;
            }
        }
        return true;
    }
private:
    bool isValidSudoku(vector<vector<char>>& board) {
        for(int i=0; i<9; i++){
            int trow[9]={0}, tcol[9]={0}, tblk[9]={0};
            for(int j=0; j<9; j++){
                if(board[i][j]!='.'){
                    int nrow = board[i][j] - '0' - 1;
                    if(trow[nrow]) return false;
                    trow[nrow]++;
                }
                if(board[j][i]!='.'){
                    int ncol = board[j][i] - '0' - 1;
                    if(tcol[ncol]) return false;
                    tcol[ncol]++;
                }
                int x = i / 3 * 3 + j / 3;
                int y = i % 3 * 3 + j % 3;
                if(board[x][y]!='.'){
                    int nblk = board[x][y] - '0' - 1;
                    if(tblk[nblk]) return false;
                    tblk[nblk]++;
                }
            }
        }
        return true;
    }
};

思考一

這種方法雖然可行,而且簡單礼华,但是實(shí)在是太暴力了。所以想到把搜索和推理結(jié)合圣絮,以此來進(jìn)行剪枝的方法。具體就是記錄每一行捧请、每一列以及每一個(gè)方塊中未出現(xiàn)的數(shù)字棒搜,搜索時(shí)只搜索其允許的取值。另外還可以使用二進(jìn)制中的每一位來表示每一個(gè)數(shù)字是否被使用可款。

實(shí)現(xiàn)二

class Solution {
public:
    int row[9], col[9], blo[9];
    void solveSudoku(vector<vector<char>>& board) {
        for(int i=0; i<9; i++){
            row[i] = (1<<9) - 1;
            col[i] = (1<<9) - 1;
            blo[i] = (1<<9) - 1;
        }
        for(int i=0; i<9; i++){
            for(int j=0; j<9; j++){
                if(board[i][j]!='.'){
                    int num = board[i][j] - '1';
                    row[i] -= 1<<num;
                    col[j] -= 1<<num;
                    blo[i/3*3 + j/3] -= 1<<num;
                }
            }
        }
        dfs(0, 0, board);
    }

private:
    bool dfs(int x, int y, vector<vector<char>>& board){
        if(y>8){
            if(x<8){
                y = 0;
                x++;
            }
            else
                return true;
        }
        if(board[x][y]!='.')
            return dfs(x, y+1, board);

        int tmp = row[x] & col[y] & blo[x/3*3 + y/3];
        if(tmp==0)
            return false;
        for(int i=0; i<9; i++){
            if(!(tmp & (1<<i)))
                continue;
            board[x][y] = i + '1';
            row[x] -= 1<<i;
            col[y] -= 1<<i;
            blo[x/3*3 + y/3] -= 1<<i;
            if(dfs(x, y+1, board))
                return true;
            board[x][y] = '.';
            row[x] += 1<<i;
            col[y] += 1<<i;
            blo[x/3*3 + y/3] += 1<<i;
            tmp -= 1<<i;
        }
        return false;
    }
};

思考二

這個(gè)算法與上一個(gè)相比闺鲸,大大縮短了運(yùn)行時(shí)間陨舱。很值得參考。
需要注意的是游盲,使用位運(yùn)算時(shí)要注意運(yùn)算優(yōu)先級,位移操作的優(yōu)先級是很低的益缎,記得加括號。我才不會說我因?yàn)橥浖永ㄌ杁ebug了好久呢欣范。

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末恼琼,一起剝皮案震驚了整個(gè)濱河市,隨后出現(xiàn)的幾起案子蛙卤,更是在濱河造成了極大的恐慌,老刑警劉巖颤难,帶你破解...
    沈念sama閱讀 222,807評論 6 518
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件行嗤,死亡現(xiàn)場離奇詭異,居然都是意外死亡栅屏,警方通過查閱死者的電腦和手機(jī)堂鲜,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,284評論 3 399
  • 文/潘曉璐 我一進(jìn)店門,熙熙樓的掌柜王于貴愁眉苦臉地迎上來甫恩,“玉大人酌予,你說我怎么就攤上這事∷擅遥” “怎么了?”我有些...
    開封第一講書人閱讀 169,589評論 0 363
  • 文/不壞的土叔 我叫張陵雕欺,是天一觀的道長棉姐。 經(jīng)常有香客問我,道長笛洛,這世上最難降的妖魔是什么乃坤? 我笑而不...
    開封第一講書人閱讀 60,188評論 1 300
  • 正文 為了忘掉前任沟蔑,我火速辦了婚禮狱杰,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘宇色。我一直安慰自己颁湖,他們只是感情好例隆,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,185評論 6 398
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著镰禾,像睡著了一般。 火紅的嫁衣襯著肌膚如雪吴侦。 梳的紋絲不亂的頭發(fā)上,一...
    開封第一講書人閱讀 52,785評論 1 314
  • 那天备韧,我揣著相機(jī)與錄音织堂,去河邊找鬼奶陈。 笑死,一個(gè)胖子當(dāng)著我的面吹牛吃粒,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播事示,決...
    沈念sama閱讀 41,220評論 3 423
  • 文/蒼蘭香墨 我猛地睜開眼很魂,長吁一口氣:“原來是場噩夢啊……” “哼!你這毒婦竟也來了遏匆?” 一聲冷哼從身側(cè)響起法挨,我...
    開封第一講書人閱讀 40,167評論 0 277
  • 序言:老撾萬榮一對情侶失蹤凡纳,失蹤者是張志新(化名)和其女友劉穎荐糜,沒想到半個(gè)月后葛超,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 46,698評論 1 320
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡答渔,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,767評論 3 343
  • 正文 我和宋清朗相戀三年沼撕,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片务豺。...
    茶點(diǎn)故事閱讀 40,912評論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡笼沥,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出敬拓,到底是詐尸還是另有隱情裙戏,我是刑警寧澤,帶...
    沈念sama閱讀 36,572評論 5 351
  • 正文 年R本政府宣布累榜,位于F島的核電站营勤,受9級特大地震影響葛作,放射性物質(zhì)發(fā)生泄漏猖凛。R本人自食惡果不足惜赂蠢,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,254評論 3 336
  • 文/蒙蒙 一虱岂、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧第岖,春花似錦、人聲如沸蔑滓。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,746評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至褐健,卻和暖如春比藻,著一層夾襖步出監(jiān)牢的瞬間倘屹,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 33,859評論 1 274
  • 我被黑心中介騙來泰國打工纽匙, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留,地道東北人馏段。 一個(gè)月前我還...
    沈念sama閱讀 49,359評論 3 379
  • 正文 我出身青樓,卻偏偏與公主長得像践瓷,于是被迫代替她去往敵國和親院喜。 傳聞我的和親對象是個(gè)殘疾皇子,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,922評論 2 361

推薦閱讀更多精彩內(nèi)容