sa演算法解數獨

① 基於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），也稱行摒除法。

② 有沒有好的演算法編程解決數獨的正確答案

有啊，而且各種語言基本都有。
其中比較經典的舞蹈鏈演算法對常見的標准數獨來說簡直就是秒解！甚至每秒解幾千個幾萬個。

③ 數獨的計算公式是什麼

數獨的計算公式是每一橫行、每一豎行和每一斜行的和都等於15。

④ 數獨的一般解法

516274398

793568412

824391765

451637289

372189654

968452137

235846971

649715823

187923546

-----------

舉例說明你的問題：

如圖，紅色宮內的9應該填在哪裡？

就要用到你所說的第4步。利用相對稱的兩個數組合3和5，來確定B5、B6兩個空格只能為35或53.從而排除B5、B6為9的可能。

紅色宮內的9填在哪裡，應該清楚了吧。

⑤ 計算數獨有什麼方法

數獨解法全是由規則衍生出來的，基本解法分為兩類思路，一類為排除法，一類為唯一法。更復雜的解法，最終也會歸結到這兩大類中。 基礎摒除法 基礎摒除法就是利用1 ～ 9 的數字在每一行、每一列、每一宮都只能出現一次的規則進行解題的方法。基礎摒除法可以分為行摒除、列摒除、九宮格摒除。 實際尋找解的過程為： 尋找九宮格摒除解：找到了某數在某一個九宮格可填入的位置只餘一個的情形；意即找到了 該數在該九宮格中的填入位置。 尋找列摒除解：找到了某數在某列可填入的位置只餘一個的情形；意即找到了該數在該列中的填入位置。 尋找行摒除解：找到了某數在某行可填入的位置只餘一個的情形；意即找到了該數在該行中的填入位置。 基礎摒除法的提升方法是區塊摒除法,是直觀法中使用頻率最高的方法之一. 唯一解法 當某列已填數字的宮格達到8個,那麼該列剩餘宮格能填的數字就只剩下那個還沒出現過的數字了。成為列唯一解. 當某九宮格已填數字的宮格達到8個,那麼該九宮格剩餘宮格能填的數字就只剩下那個還沒出現過的數字了。成為九宮格唯一解. 唯余解法 唯余解法就是某宮格可以添入的數已經排除了8個,那麼這個宮格的數字就只能添入那個沒有出現的數字. 區塊摒除法 區塊摒除法是基礎摒除法的提升方法,是直觀法中使用頻率最高的方法之一. 余數測試法 所謂余數測試法就是在某行或列,九宮格所填數字比較多,剩餘2個或3個時,在剩餘宮格添入值進行測試的解題方法. 隱性唯一候選數法 當某個數字在某一列各宮格的候選數中只出現一次時，那麼這個數字就是這一列的唯一候選數了．這個宮格的值就可以確定為該數字． 這是因為，按照數獨游戲的規則要求每一列都應該包含數字1～9，而其它宮格的候選數都不含有該數，則該數不可能出現在其它的宮格，那麼就只能出現在這個宮格了． 對於唯一候選數出現行,九宮格的情況，處理方法完全相同。 三鏈數刪減法 找出某一列、某一行或某一個九宮格中的某三個宮格候選數中，相異的數字不超過3個的情形， 進而將這3個數字自其它宮格的候選數中刪減掉的方法就叫做三鏈數刪減法。 隱性三鏈數刪減法 在某行，存在三個數字出現在相同的宮格內，在本行的其它宮格均不包含這三個數字，我們稱這個數對是隱形三鏈數．那麼這三個宮格的候選數中的其它數字都可以排除． 當隱形三鏈數出現在列，九宮格，處理方法是完全相同的． －－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－ 修改為：在某行，存在三個候選數字分別出現在三個宮格內， 在本行的其它宮格均不包含這三個數字，我們稱這個數對是隱形三鏈數．那麼這三個宮格的其它候選數都可以排除． 當隱形三鏈數出現在列，九宮格，處理方法是完全相同的 或者： 利用「找出某3個數字僅出現在某行、某列或某一個九宮格的某三個宮格候選數中的情形，進而將這三個宮格的候選數刪減成該3個數字」的方法就叫做隱性三鏈數刪減法(Hidden Triples)。 矩形頂點刪減法 矩形頂點刪減法和直觀法講到的矩形摒除法分析方法是一樣的。矩形頂點刪減法在識別時比較不容易找到，所以最好先使用其它的方法。 三鏈列刪減法 三鏈列刪減法是矩形頂點刪減法的擴展，如果不清楚矩形頂點刪減法，可以參考矩形頂點刪減法，以便於更容易理解本節內容。 利用「找出某個數字在某三列僅出現在相同三行的情形，進而將該數字自這三行其他宮格候選數中刪減掉」； 或「找出某個數字在某三行僅出現在相同三列的情形，進而將該數字自這三列其他宮格候選數中刪減掉」的方法 就叫做三鏈列刪減法。 關鍵數刪減法 在進入到解題後期，利用前面講到的唯一候選數法、隱性唯一候選數法、 區塊刪減法、數對刪減法、隱性數對刪減法、 三鏈數刪減法、隱性三鏈數刪減法、矩形頂點刪減法、 三鏈列刪減法都無法有進展的時候，可以考慮使用關鍵數刪減法。關鍵數刪減法就是在後期找到一個數，這個數在行（或列，九宮格）僅出現兩次的數字。我們假定這個數在其中一個宮格類，繼續求解，如果發生錯誤，則確定我們的假設錯誤。如果繼續求解仍然出現困難，不妨假設這個數在另外一個宮格，看能不能得到錯誤。這就是關鍵數刪減法. 編輯本段排除法 當某一列，某一行或某一宮里已填7個數字時，可採用排除法，排除不可能出現在這個格子的數，從而確定格子里應該填什麼數。比如某一行已填1，3，4，5，7，8，9，還剩2，6，而其中一個空格所在的列上已有了2，可知這個空格里不可能是2，那麼另外一個空格里一定是2，那麼這個空格里一定是6。 當某一列，某一行或某一宮里已填6個數字時，也可採用排除法。

⑥ 數獨解題的方法

原創回答：
建議你去OUBK網學習，那裡有全面的數獨技巧教學，每種技巧一片文章，文章不長，有一個小時就能看完，還有動態圖的示例~
網站里還有大量的數獨題目和解答過程~

數獨解法一般分兩類~一類是直觀法，一類是候選法~
直觀法(Direct Elimination Techniques)中，常用的演算法包括：
單元唯一法 ( Sole Position Technique )
單元排除法 ( Basic Elimination Technique )
區塊排除法 ( Block Elimination Technique )
唯一餘數法 ( Sole Number Technique )
組合排除法 ( Combination Elimination Technique)
矩形排除法 ( Rectangle Elimination Technique)

在候選法中，常用的演算法包括：
顯式唯一法 (Naked Single)
隱式唯一法 (Hidden Single)
區塊刪減法 (Intersection Removal)
顯式數對法 (Naked Pair)
顯式三數集法 (Naked Triplet)
顯式四數集法 (Naked Quad)
隱式數對法 (Hidden Pair)
隱式三數集法 (Hidden Triplet)
隱式四數集法 (Hidden Quad)
矩形對角線法 (X-wing)
XY形態匹配法（XY-wing）
XYZ形態匹配法（XYZ-wing)
三鏈數刪減法 (Swordfish)
WXYZ形態匹配法（WXYZ-wing)

⑦ 數獨高級解法有哪些

具體如下：

1、聯除法：在兩行三個隔膜中查找相同的數字，然後用它們查找另一行中的位數。該方法適用於中、高級數獨。

2、巡格法：找出每個橫膈膜數字的頻率，找出它的位置。

3、排它法：這種方法是解決問題的關鍵，容易被普通老百姓所忽視。觀察隊列或橫膈膜，如果有一個位置不能被其他數字填補，填補剩下的數字。

4、待定法：這種方法不常使用，但很有效。在區域中臨時定位一個數字，並將其用於排除。

5、行列法：該方法用於提高破階求解問題的效率。

6、假設法：作為專家，我並不主張這種做法。

7 、頻率法：這種方法比以前的方法更有效。列出行中或框中的所有情況，然後選擇一個高頻率的數字。

8、用候選方法解決數獨問題的候選演算法首先，必須建立一個候選列表。在不同的條件下，每個宮格不可能的候選人可以逐步和安全地被清除。

候選數方法可以用來解決復雜的數獨問題，但是候選數方法的使用不像直覺方法那樣直接，需要建立候選人名單的准備過程，所以實際使用可以先用可視化方法解決問題，而不能用候選人的方法來解決問題。

候選人數方法的解決方法是逐步排除不合適候選數的過程，所以在刪除候選數時一定要小心，要確定刪除的候選人是否安全，否則，多次都要重做的問題。在電腦軟體的幫助下，使得候選數表的維護變得輕鬆起來。

常規解題手法：

依解題填制的過程可區分為直觀法與候選數法。

直觀法就是不做任何記號，直接從數獨的盤勢觀察線索，推論答案的方法。

候選數法就是刪減等位群格位已出現的數字，將剩餘可填數字填入空格做為解題線索的參考，可填數字稱為候選數(Candidates，或稱備選數)。

直觀法和候選數法只是填制時候是否有注記的區別，依照個人習慣而定，並非鑒定題目難度或技巧難度的標准，無論是難題或是簡單題都可上述方法填制，一般程序解題以候選數法較多。

⑧ 數獨萬能解法數獨口訣是什麼

九宮格數獨口訣是戴九履一，左三右七，二四有肩，八六為足，五居中央。還有口訣：「一居上行正中央，依次斜填切莫忘；上出框時向下放，右出框時向左放；排重便在下格填，右上排重一個樣。」 這口訣不僅適用於九宮，也適用於推廣的奇數九宮，如五五圖，七七圖等。

余數法：用格位去找唯一可填數字，稱為余數法，格位唯一可填數字稱為唯余解 。余數法是刪減等位群格位（Peer）已出現的數字的方法，每一格位的等位群格位有 20 個。

直觀法：直觀法就是不做任何記號，直接從數獨的盤勢觀察線索，推論答案的方法。

摒除法：用數字去找單元內唯一可填空格，稱為摒除法，數字可填唯一空格稱為摒余解 。數字可填唯一空格在「宮」單元稱為宮摒余解，這種解法稱宮摒除法。

如果這些數字的每一個區域、每一行、每一列都是1到9之間的數字，那麼玩家需要使用一些排除、鏈刪除等演算法來填充整個9*9的地圖，那麼在游戲開始的時候，會有一些數字，而且這些數字是不能移動和刪除的哦，這是游戲的難度等級，如果難度越大就意味著有更多的固定數字。

⑨ 數獨演算法

給你數獨計算器：
http://blog.xunlei.com/web/category.html?uin=mianmiany1978&category_id=143
數獨游戲：
http://blog.xunlei.com/web/category.html?uin=mianmiany1978&category_id=174
數獨演算法：
http://www.puzzle8.com/suku/news.asp
數獨快速入門（上篇）
數獨快速入門（中篇）
數獨快速入門（下篇）
唯一解法
唯一候選數法
隱性三鏈數刪減法
隱性數對刪減法
三鏈列刪減法
區塊刪減法
矩形頂點刪減法
關鍵數刪減法

補充：
合格的數獨是只有唯一解。
而數獨有難易度的分類，找一份報紙注意刊登的數獨謎題是1星，還是5星。
在網路上，更分成容易題、進階題、難題、極難題、超難題....
一般都是依據需要運用的技巧，而技巧是區分難易的。

數獨不用猜測，解題全部是運用邏輯推理。
數獨不用電腦程序分析，就可以解的題目是直觀法數獨題。
而超難題是需要電腦分析，及把全盤標示可選數，那是可選數謎題。
沒有所謂解題通則。

1.直觀解(一般報紙、書籍)
直觀法技巧
直觀法技巧 01 (容易級) 唯一解
直觀法技巧 02 (容易級) 基本摒除
直觀法技巧 03 (進階級) 宮對行列摒除
直觀法技巧 04 (進階級) 行列對宮摒除
直觀法技巧 05 (進階級) 群組解法
直觀法技巧 06 (困難級) X-Wing摒除法01
直觀法技巧 06 (困難級) X-Wing摒除法02
直觀法技巧 07 (困難級) 數偶摒除法

http://hi..com/kiwy07/blog/item/181fc482a153f3bd6c8119ab.html

2.可選數(以程序自動生成可選數)

Last value in block, row or column
Hidden Single in block
Hidden Single in row or column
Direct Pointing
Direct Claiming
Direct Hidden Pair
Naked Single
Direct Hidden Triplet
Pointing
Claiming
Naked Pair, X-Wing, Hidden Pair
Naked Triplet, Swordfish, Hidden Triplet
XY-Wing, XYZ-Wing
Unique rectangles and loops
Naked Quad, Jellyfish, Hidden Quad
Bivalue Universal Graves
Aligned Pair Exclusion
Bidirectioal X-Cycles and Y-Cycles
Forcing X-Chains
Forcing Chains, Bidirectional Cycles
Nishio
Cell/Region Forcing Chains
Dynamic Forcing Chains

http://diuf.unifr.ch/people/juillera/Sudoku/FAQ.html

通則無法解的題
直觀難題
006589307
030602008
809703500
000891403
394265871
180374000
003026785
000458030
008037200
可選數極難題
970000000
003927000
008410709
300700400
060050070
007040003
105074900
000068507
786000042
不要把謎題解一次列出，而是找出下一步，及他的邏輯推理方法。
不要用猜測。

⑩ 什麼是SA演算法

又叫模擬退火演算法