數獨演算法c
Ⅰ 基於SAT的數獨游戲求解程序,求C語言代碼
用0代表要填的數
#include <stdio.h>
#include <stdlib.h>
#define SIZE 9
#define get_low_bit(x) ((~x&(x-1))+1)
struct{
int left;
char num;
char try;
}board[SIZE][SIZE];
int bit2num(int bit)
{
switch(bit){
case 16:
case 256:
return 9;
基礎解法
排除法(摒除法)
摒除法:用數字去找單元內唯一可填空格,稱為摒除法,數字可填唯一空格稱為排除法 (Hidden Single)。
根據不同的作用范圍,摒余解可分為下述三種:
數字可填唯一空格在「宮」單元稱為宮排除(Hidden Single in Box),也稱宮摒除法。
數字可填唯一空格在「行」單元稱為行排除法(Hidden Single in Row),也稱行摒除法。
Ⅱ 計算數獨有什麼方法
數獨(すうどく,Sūdoku)是一種運用紙、筆進行演算的邏輯游戲。玩家需要根據9×9盤面上的已知數字,推理出所有剩餘空格的數字,並滿足每一行、每一列、每一個粗線宮內的數字均含1-9,不重復。
數獨盤面是個九宮,每一宮又分為九個小格。在這八十一格中給出一定的已知數字和解題條件,利用邏輯和推理,在其他的空格上填入1-9的數字。使1-9每個數字在每一行、每一列和每一宮中都只出現一次,所以又稱「九宮格」。
【基本方法】
解題的本質有二:隱性唯一解(Hidden Single)及顯性唯一解(Naked Single),他們的名稱是在候選數法的基礎上命名的。
解題必須以邏輯為依歸,猜測的方法被稱為「暴力型」解法(Brute Force),這不是提倡數獨的本意。
根據解題本質發展出來的基本解題方法有二種:
摒除法
摒除法:用數字去找單元內唯一可填空格,稱為摒除法,數字可填唯一空格稱為摒余解(隱性唯一解)。
根據不同的作用范圍,摒余解可分為下述三種:
數字可填唯一空格在「宮」單元稱為宮摒余解(Hidden Single in Box),這種解法稱宮摒除法。
數字可填唯一空格在「行」單元稱為行摒余解(Hidden Single in Row),這種解法稱行摒除法。
數字可填唯一空格在「列」單元稱為列摒余解(Hidden Single in Column),這種解法稱列摒除法。
行摒余解和列摒余解合稱行列摒余解(Hidden Single in Line)。
得到行列摒余解的方法稱為行列摒除法。
余數法
Peer等位群格位
余數法:用格位去找唯一可填數字,稱為余數法,格位唯一可填數字稱為唯余解(Naked Single)。
余數法是刪減等位群格位(Peer)已出現的數字的方法,每一格位的等位群格位有 20 個。
依解題填制的過程可區分為直觀法與候選數法。
直觀法
直觀法就是不做任何記號,直接從數獨的盤勢觀察線索,推論答案的方法。
候選數法
候選數法就是刪減等位群格位已出現的數字,將剩餘可填數字填入空格做為解題線索的參考,可填數字稱為候選數(Candidates,或稱備選數)。
直觀法和候選數法只是填制時候是否有注記的區別,依照個人習慣而定,並非鑒定題目難度或技巧難度的標准,無論是難題或是簡單題都可上述方法填制,一般程序解題以候選數法較多。
【進階解法】
上述方法稱為基礎解法(Basic Techniques),其他所有的解法稱為進階解法(Advanced Techniques),是在補基本解法之不足,所以又稱輔助解法。
進階解法包括:區塊摒除法(Locked Candidates)、數組法(Subset)、四角對角線(X-Wing)、唯一矩形(Unique Rectangle)、全雙值墳墓(Bivalue Universal Grave)、單數鏈(X-Chain)、異數鏈(XY-Chain)及其他數鏈的高級技巧等等。已發展出來的方法有近百種之多。
其中前兩種加上基礎解法為一般數獨書中介紹並使用的方法,同時也是大部分人可以理解並掌握的數獨解題技法。
通過基礎解法出數只需一種解法,摒除法或唯余法,超出此范圍而需要施加進階解法時,解題點需要進階解法協助基礎解法來滿足隱性唯一或顯性唯一才能出數,該解題點的解法需要多個步驟協力完成,因此稱做組合解法。
相對概率
相對概率不是真實的概率,而是用於同一格中的幾個數字之間相互比較出現的可能。
相對概率 = 九宮格出現的概率 × 行出現的概率 × 列出現的概率
九宮格出現的概率:如果九宮格中有2個格可能出現1,目標格可能的數字為1、2、3,另一個格可能出現的數字為1、4,那麼:目標格中的1在九宮格出現的概率 = 目標格中出現1的概率 × (1 - 另一個格中出現1的概率),得1/3 × (1-1/2) = 1/6。
注意:1-1/2表示另一個格不出現1的概率,1/3 × (1-1/2) 的意思就是在另一個格不出現1的情況下,目標格出現1的概率。
如果九宮格中有三個格可能出現1,目標格可能的數字為1、5、6,另一個格可能出現的數字為1、7,還有一個格可能出現的數字為1、8、9,得1/3 × (1-1/2) × (1-1/3) = 1/9。依此類推。
行出現的概率和列出現的概率與九宮格出現的概率的演算法原理相同。最後,把三個概率相乘,得到相對概率,把目標格中3個數字的相對概率進行對比,相對概率越大,出現的可能性越大。
區塊摒除法
區塊摒除法包括宮區塊摒除法(Pointing)與行列區塊摒除法(Claiming)。
在基礎題里,利用區塊摒除可以替代一些基礎解法的觀察,或輔助基礎解法尋找焦點。
在非基礎題里,區塊可以隱藏任何其他結構,簡單的可以把基礎解法隱藏起來,難的可以隱藏數對等等其他進階技巧。
例如:
區塊摒除法
首先數字6對第五宮摒除,得到第五宮的6在R4C5或者R6C5。
不論是在R4C5或者R6C5,C5的其他格都不能再有數字6。(R4C5與R6C5就是數字6的區塊,這也是區塊摒除作用的觀點)
數字6對第二宮摒除,得解R1C4=6。
Ⅲ 數獨萬能解法數獨口訣是什麼
九宮格數獨口訣是戴九履一,左三右七,二四有肩,八六為足,五居中央。還有口訣:「一居上行正中央,依次斜填切莫忘;上出框時向下放,右出框時向左放;排重便在下格填,右上排重一個樣。」 這口訣不僅適用於九宮,也適用於推廣的奇數九宮,如五五圖,七七圖等。
余數法:用格位去找唯一可填數字,稱為余數法,格位唯一可填數字稱為唯余解 。余數法是刪減等位群格位(Peer)已出現的數字的方法,每一格位的等位群格位有 20 個。
直觀法:直觀法就是不做任何記號,直接從數獨的盤勢觀察線索,推論答案的方法。
摒除法:用數字去找單元內唯一可填空格,稱為摒除法,數字可填唯一空格稱為摒余解 。數字可填唯一空格在「宮」單元稱為宮摒余解,這種解法稱宮摒除法。
如果這些數字的每一個區域、每一行、每一列都是1到9之間的數字,那麼玩家需要使用一些排除、鏈刪除等演算法來填充整個9*9的地圖,那麼在游戲開始的時候,會有一些數字,而且這些數字是不能移動和刪除的哦,這是游戲的難度等級,如果難度越大就意味著有更多的固定數字。
Ⅳ 數獨高級解法有哪些
具體如下:
1、聯除法:在兩行三個隔膜中查找相同的數字,然後用它們查找另一行中的位數。該方法適用於中、高級數獨。
2、巡格法:找出每個橫膈膜數字的頻率,找出它的位置。
3、排它法:這種方法是解決問題的關鍵,容易被普通老百姓所忽視。觀察隊列或橫膈膜,如果有一個位置不能被其他數字填補,填補剩下的數字。
4、待定法:這種方法不常使用,但很有效。在區域中臨時定位一個數字,並將其用於排除。
5、行列法:該方法用於提高破階求解問題的效率。
6、假設法:作為專家,我並不主張這種做法。
7 、頻率法:這種方法比以前的方法更有效。列出行中或框中的所有情況,然後選擇一個高頻率的數字。
8、用候選方法解決數獨問題的候選演算法首先,必須建立一個候選列表。在不同的條件下,每個宮格不可能的候選人可以逐步和安全地被清除。
候選數方法可以用來解決復雜的數獨問題,但是候選數方法的使用不像直覺方法那樣直接,需要建立候選人名單的准備過程,所以實際使用可以先用可視化方法解決問題,而不能用候選人的方法來解決問題。
候選人數方法的解決方法是逐步排除不合適候選數的過程,所以在刪除候選數時一定要小心,要確定刪除的候選人是否安全,否則,多次都要重做的問題。在電腦軟體的幫助下,使得候選數表的維護變得輕鬆起來。
常規解題手法:
依解題填制的過程可區分為直觀法與候選數法。
直觀法就是不做任何記號,直接從數獨的盤勢觀察線索,推論答案的方法。
候選數法就是刪減等位群格位已出現的數字,將剩餘可填數字填入空格做為解題線索的參考,可填數字稱為候選數(Candidates,或稱備選數)。
直觀法和候選數法只是填制時候是否有注記的區別,依照個人習慣而定,並非鑒定題目難度或技巧難度的標准,無論是難題或是簡單題都可上述方法填制,一般程序解題以候選數法較多。
Ⅳ 數獨的計算公式是什麼
1、聯除法。
在並排的三個九宮格中的兩排尋找相同數字,再利用九宮格得出另一排中該數字位置,該方法適用於中高級數獨.
2、巡格法
找出在每個九宮格中出現頻率較高的數字,得出該數字在其餘九宮格內位置,該方法應用於方法一之後。
3、排除法
這個方法是解決問題的關鍵,易被常人所忽略。在各行列或九宮格中觀察,若有個位置其它數字都不能填,就填餘下的數字
4、待定法
此方法不常用卻很有效。暫時確定某個數字在某個區域,再利用其來進行排除
5、行列法
此方法用於收官階段,利用先從行列突破來提高解題效率。
6、假設法
即在某個位置隨機的填上一個數字,再進行推演,並有可能最終產生矛盾而否定結論。
7、頻率法
這種方法相比於上一種方法更能提高效率。在某一行列或九宮格列舉出所有情況,再選擇某位置中出現頻率高的數字
8、候選數法
使用候選數法解數獨題目需先建立候選數列表,根據各種條件,逐步安全的清除每個宮格候選數的不可能取值的候選數,從而達到解題的目的。
(5)數獨演算法c擴展閱讀:
數獨的出題方法:
1、挖洞法
從有到無的出題方法。先生成一個終盤,然後挖去部分數字形成一道題目。
2、填數法
從無到有的出題方法。在一個空盤面上填上部分數字形成一道題目。2007年日本NPGenerator軟體的網站提出了一種邊推理邊出題的出題法,可以手工打造出漂亮圖案的數獨題目。
Ⅵ 用C語言如何隨機生成一個數獨
數獨生成演算法?這個還真不好搞,不過我當初寫數獨游戲的時候隨便搗鼓出來過一個,你自己去改改吧,至於這個演算法能不能生成所有的數獨,我還真沒論證過。
原理:對一個給出的數獨棋盤的所有行或列交換給出的兩個數X、Y,數組仍滿足數獨規則。如給出1、2,則對所有列交換1、2的位置,數組仍滿足數獨規則。
由於對棋盤的演進是隨機的,所以相當於隨機生成數獨棋盤啦。每次演進的次數最好大一點,10次以上吧,以保證每個數都被換過位置。
具體代碼就不用我寫了吧,嘎嘎……
Ⅶ 求解數獨題,用C語言實現
回溯法(探索與回溯法)是一種選優搜索法,按選優條件向前搜索,以達到目標。但當探索到某一步時,發現原先選擇並不優或達不到目標,就退回一步重新選擇,這種走不通就退回再走的技術為回溯法,而滿足回溯條件的某個狀態的點稱為「回溯點」。
#include<stdio.h>
intmap[9][9];
boolisPlace(intcount){
introw=count/9;
intcol=count%9;
intj;
//同一行
for(j=0;j<9;++j){
if(map[row][j]==map[row][col]&&j!=col){
returnfalse;
}
}
//同一列
for(j=0;j<9;++j){
if(map[j][col]==map[row][col]&&j!=row){
returnfalse;
}
}
//同一小格
inttempRow=row/3*3;
inttempCol=col/3*3;
for(j=tempRow;j<tempRow+3;++j){
for(intk=tempCol;k<tempCol+3;++k){
if(map[j][k]==map[row][col]&&j!=row&&k!=col){
returnfalse;
}
}
}
returntrue;
}
voidbacktrace(intcount){
if(count==81){
for(inti=0;i<9;++i){
for(intj=0;j<9;++j){
printf("%d",map[i][j]);
}
printf("\n");
}
return;
}
introw=count/9;
intcol=count%9;
if(map[row][col]==0){
for(inti=1;i<=9;++i){
map[row][col]=i;//賦值
if(isPlace(count)){//可以放
backtrace(count+1);//進入下一層
}
}
map[row][col]=0;//回溯
}else{
backtrace(count+1);
}
}
intmain()
{
charc;
for(inti=0;i<9;i++)
{
for(intj=0;j<9;j++)
{
scanf("%c",&c);
if(c=='.')map[i][j]=0;
elsemap[i][j]=c-'0';
}
scanf("%c",&c);//接收換行符
}
backtrace(0);
return0;
}
Ⅷ 如何用C解9*9數獨,求代碼,高手勿噴。
int i, j, n=3; int col = 1, line = 0; a[line][col] = 1"%d ", a[i][j]); printf("\\n"); } return 0; } 我有解
Ⅸ 數獨的計算公式是什麼
數獨的計算公式是每一橫行、每一豎行和每一斜行的和都等於15。
Ⅹ 數獨怎麼玩 數獨游戲的基本解法
數獨盤面是個九宮,每一宮又分為九個小格。在這八十一格中給出一定的已知數字和解題條件,利用邏輯和推理,在其他的空格上填入1-9的數字。使1-9每個數字在每一行、每一列和每一宮中都只出現一次,所以又稱「九宮格」。
解題手法
依解題填制的過程可區分為直觀法與候選數法。
直觀法就是不做任何記號,直接從數獨的盤勢觀察線索,推論答案的方法。
候選數法就是刪減等位群格位已出現的數字,將剩餘可填數字填入空格做為解題線索的參考,可填數字稱為候選數(Candidates,或稱備選數)。
直觀法和候選數法只是填制時候是否有注記的區別,依照個人習慣而定,並非鑒定題目難度或技巧難度的標准,無論是難題或是簡單題都可上述方法填制,一般程序解題以候選數法較多。
摒除法
摒除法:用數字去找單元內唯一可填空格,稱為摒除法,數字可填唯一空格稱為摒余解(Hidden Single)。
根據不同的作用范圍,摒余解可分為下述三種:
數字可填唯一空格在「宮」單元稱為宮摒余解(Hidden Single in Box),這種解法稱宮摒除法。
數字可填唯一空格在「行」單元稱為行摒余解(Hidden Single in Row),這種解法稱行摒除法。
數字可填唯一空格在「列」單元稱為列摒余解(Hidden Single in Column),這種解法稱列摒除法。
行摒余解和列摒余解合稱行列摒余解(Hidden Single in Line)。
得到行列摒余解的方法稱為行列摒除法。
余數法
Peer等位群格位
余數法:用格位去找唯一可填數字,稱為余數法,格位唯一可填數字稱為唯余解(Naked Single)。
余數法是刪減等位群格位(Peer)已出現的數字的方法,每一格位的等位群格位有 20 個,如圖七所示。
進階解法
上述方法稱為基礎解法(Basic Techniques),其他所有的解法稱為進階解法(Advanced Techniques),是在補基本解法之不足,所以又稱輔助解法。
進階解法包括:區塊摒除法(Locked Candidates)、數組法(Subset)、四角對角線(X-Wing)、唯一矩形(Unique Rectangle)、全雙值墳墓(Bivalue Universal Grave)、單數鏈(X-Chain)、異數鏈(XY-Chain)及其他數鏈的高級技巧等等。已發展出來的方法有近百種之多。
其中前三種加上基礎解法為一般數獨書中介紹並使用的方法,同時也是大部分人可以理解並掌握的數獨解題技法。
通過基礎解法出數只需一種解法,摒除法或唯余法,超出此范圍而需要施加進階解法時,解題點需要進階解法協助基礎解法來滿足隱性唯一或顯性唯一才能出數,該解題點的解法需要多個步驟協力完成,因此稱做組合解法。
解題必須以邏輯為依歸,猜測的方法被稱為暴力型解法(Brute Force),這不是提倡數獨的本意。
區塊摒除法
區塊摒除法包括宮區塊摒除法(Pointing)與行列區塊摒除法(Claiming)。
在基礎題里,利用區塊摒除可以替代一些基礎解法的觀察,或輔助基礎解法尋找焦點。
在非基礎題里,區塊可以隱藏任何其他結構,簡單的可以把基礎解法隱藏起來,難的可以隱藏數對等等其他進階技巧。
區塊摒除法
首先數字6對第五宮摒除,得到第五宮的6在R4C5或者R6C5。
不論是在R4C5或者R6C5,C5的其他格都不能再有數字6。(R4C5與R6C5就是數字6的區塊,這也是區塊摒除作用的觀點)
數字6對第二宮摒除,得解R1C4=6。
數對法
當一個單元(行、列、宮)的某兩個數字僅可能在某兩格時,我們稱這兩個格為這兩個數的數對(Pairs)。
數對出現在宮稱為宮數對;數對出現在行列成為行列數對。
用候選數法的觀點去看,數對有兩種,一種是在同單元內其中兩格有相同的雙候選數,一看就明白,因此稱為顯性數對(Naked Pair),另一種是,同單元內有兩個候選數佔用了相同的兩格,該兩格因為還有其它候選數很難辨認,因此稱為隱性數對(Hidden Pair)。