好久沒寫演算法了，淺解個數獨
本篇代碼以偽代碼為主，主要講解解題思路
規則介紹：
首先數獨的游戲規則，每個九宮格 每一行 每一列 每個數字只能出現一次(1-9)
開局時會生成一些不能改變數字的格子
按規則填滿所有格子為過關
圖下所示為前幾天朋友卡關了的狀態：
例如第二行第一列有一個固定的5，在它的九宮格里就不能再出現另一個5
第二行也不能再出現5，第一列也不能再出現5
回溯思路：
我需要一個方法能夠解這道題，我稱呼他為方法A
需要呼叫方法A就能自動解開這道題，但是按斬訓溯演算法的解題思路，方法A中的核心代碼只需要解開一個格子的值，然后在下一個格子的位置再呼叫方法A
就有了如下偽代碼：
布爾 方法A(int x,int y){
//此處先省略解開當前格子的代碼 傳入的引數為格子的坐標
回傳 方法A(x,y+1);
}
這樣的話，只需要呼叫方法A(0,0) 在解開一個格子后，他會自動去解下一個坐標的格子
最侄訓傳true表示解開了這道數獨，否則沒解開
但是一行只有9個格子，一共9列，所以添加如下代碼自動換行(添加到方法頂端，先判斷是否越界再運行核心代碼)：
if (x > 8) {
return true;
}
if (y > 8) {
return 方法A(x + 1, 0);
}
現在這個方法已經會自動尋找下一個格子了
但是如果這個格子里的數值是不能修改的，就應該跳過這個格子
我的方法是開始運行前就遍歷一遍格子，如果值不為0(開始求解前就有值)，就把這個格子標記為不可變
if(此格子的數值不可變){
return 方法A(x,y+1);
}
即使這里的y+1超過了下標上限，運行到下一個格子的時候也會自動修正
以上是部分回溯，當然后續還會根據情況修改
解題思路：
說明：我將開始解題前就有值的格子稱為不可變格子，因為里面的值是固定的，不能改變
1、首先找到這個格子能填入的所有數值
以圖中(0,0)為例，第0下標列中有5,4,1,7 第0下標行中有6,3,2 所在的九宮格中有5,1,7 所以這個格子只能填入8,9
提醒：
這個格子所在的九宮格里所有格子的特征：格子的行號除以3相等 格子的列號除以3相等
（左上角這個九宮格里的任何格子 行號除以3都為0 列號除以3都為0 而下面的九宮格行號除以3為1 列號除以3為0）
2、依次嘗試能填的所有數字
先填入8，然后進行下一個格子，運行中如果發現下一個格子怎么填都不正確，說明前面的格子有存在錯誤的，則值清0，回傳前面的格子，接著試下一個答案
例如：
(0,0)格子填入8，進入下一個格子 即呼叫了方法A(0,1) (0,1)格子中只能填入4,9 結果發現填哪個都不行，只能把自己重新賦值0 回傳false
(0,0)接收到false 繼續嘗試下一個 嘗試填入9 繼續呼叫方法A(0,1)
以此類推，直到得到正確答案 如果所有值都試完了 都沒有正確答案 則回傳false
所以回溯部分的代碼也需要一些修改
for(可填入的數字的集合){
格子(x,y)=可填入的數字
if(方法A(x,y+1)){
return true;
}
}
格子(x,y)=0
return false;
運行起來大概是這個樣子
如果得到正確的解，會從最后一個格子回傳 true
而前面的格子都是使用if(方法A(x,y+1))呼叫的后面的格子
接收到true后也會回傳true 直到最初的方法A(0,0)也回傳true
如果所有的方案都無法得到解 嘗試完所有方案后 也會依次回傳false
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/531823.html
標籤：其他