解數獨演算法
有啊，而且各種語言基本都有。
其中比較經典的舞蹈鏈演算法對常見的標准數獨來說簡直就是秒解！甚至每秒解幾千個幾萬個。
② 數獨演算法思路
數獨(數和)（英：Cross Sums；日：カックロ）是一種數學智力游戲。數和把填字游戲和數獨巧妙地結合在一起，採用填字游戲式的棋盤，解題時在空格中填上1-9的數字。這種游戲不僅需要邏輯思維能力，還需要一點加法運算。
電腦自動生成數獨游戲的謎題
要得出所有滿足條件的組合確實不是件容易的事情（主要是很多，列印起來很慢） 。但偶們的目標只是每次能得到一個新的組合，然後從格子裡面隨機遮掉一些數字就可以了。所以只需要在解數獨游戲演算法的基礎上稍作修改即可。
所以，演算法的步驟是：
1.往第一行或第一列隨機填1-9的數字
2.調用解數獨演算法得到一個結果
3.每行隨機遮掉1-8個數字。如果需要較大的難度，也可以將1-8改為2-8或3-8，等等。
以下是console工程的代碼：
// sudoku.cpp : 定義控制台應用程序的入口點。
// by superarhow([email protected])
#include "stdafx.h"
#include "conio.h"
#define SUCCESS 1
#define _FAILED 0
/* 地圖類型9*9的char，每個char從0-9，0表示待填 */
typedef char MAPTYPE[9][9];
/* 行數據，同時用作「可能性」數據。如LINETYPE a; 當a[0]為真時表示
當前位置可填1，a[1]為真時表示可填2，以此類推 */
typedef char LINETYPE[9];
typedef void (*ONMAPOKCALLBACK)(MAPTYPE map);
/* 列印地圖 */
void mp_map(MAPTYPE dest)
{
for ( int j = 0; j < 9; j++ )
{
for ( int i = 0; i < 9; i++ )
{
printf("%d ", dest[i][j]);
}
printf("\n");
}
printf("\n");
}
int fill_line(MAPTYPE dest, int line, ONMAPOKCALLBACK callback);
/* 填下一個格子。本行的可能性已在調用前算好，要考慮的是列的可能性和九宮格的可能性 */
/* nums_possible : array (0-8) means possible of number (1-9) */
int fill_pos(MAPTYPE dest, LINETYPE nums_possible, int line, int pos, ONMAPOKCALLBACK callback)
{
if ( pos >= 9 )
{
return fill_line(dest, line + 1, callback);
}
if ( dest[pos][line] != 0 ) return fill_pos(dest, nums_possible, line, pos + 1, callback);
for ( int i = 0; i < 9; i++ )
{
if ( !nums_possible[i] ) continue;
/* 檢查本列是否重復 */
int vetical_failed = 0;
for ( int j = 0; j < 9; j++ )
if ( dest[pos][j] == i + 1 )
{
vetical_failed = 1;
break;
}
if ( vetical_failed ) continue;
/* 檢查九宮格是否重復 */
int nine_failed = 0;
int m = pos / 3;
int n = line / 3;
m *= 3;
n *= 3;
for ( int y = n; y < n + 3; y++ )
{
for ( int x = m; x < m + 3; x++ )
{
if ( dest[x][y] == i + 1 )
{
nine_failed = 1;
break;
}
}
if ( nine_failed ) break;
}
if ( nine_failed ) continue;
/* all ok, try next position */
dest[pos][line] = i + 1;
nums_possible[i] = 0;
if ( fill_pos(dest, nums_possible, line, pos + 1, callback) )
{
/* 本行已全部OK，嘗試下一行 */
if ( fill_line(dest, line + 1, callback) ) return SUCCESS;
/* 下一行失敗，重新嘗試本位置的剩餘可能性 */
}
nums_possible[i] = 1;
dest[pos][line] = 0;
}
return _FAILED;
}
/* 填下一行 */
int fill_line(MAPTYPE dest, int line, ONMAPOKCALLBACK callback)
{
if ( line >= 9 )
{
/* map */
callback(dest);
return SUCCESS;
}
LINETYPE nums;
LINETYPE saveline;
/* calc possibility(for the current line) */
for ( int i = 0; i < 9; i++ ) nums[i] = 1; /* all can be */
for ( int i = 0; i < 9; i++ )
{
char n = dest[i][line];
/* save line */
saveline[i] = dest[i][line];
if ( n != 0 ) nums[n - 1] = 0; /* appears */
}
if ( !fill_pos(dest, nums, line, 0, callback) )
{
/* restore line */
for ( int i = 0; i < 9; i++ ) dest[i][line] = saveline[i];
return _FAILED;
}
return SUCCESS;
}
MAPTYPE g_result;
void on_map_ok(MAPTYPE map)
{
memcpy(g_result, map, sizeof(MAPTYPE));
}
#include "windows.h"
int _tmain(int argc, _TCHAR* argv[])
{
MAPTYPE dest;
memset(dest, 0, sizeof(MAPTYPE));
srand( GetTickCount() );
/* 隨機填充第一行 */
char ch[9] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
for ( int i = 0; i < 9; i++ )
{
int p = rand() % 9;
char t = ch[p];
ch[p] = ch[i];
ch[i] = t;
}
for ( int i = 0; i < 9; i++ ) dest[i][0] = ch[i];
if ( fill_line(dest, 0, on_map_ok) )
{
/* 修剪掉一些塊 */
for ( int i = 0; i < 9; i++ )
{
/* 調整n的取值范圍可改變難度 %6 + 3是比較難的 */
int n = (rand() % 6) + 3;
for ( int j = 0; j < 9; j++ ) ch[j] = j; /* ch: index to erase */
for ( int j = 0; j < 9; j++ )
{
int p = rand() % 9;
char t = ch[p];
ch[p] = ch[i];
ch[i] = t;
}
for ( int j = 0; j < n; j++ ) g_result[ch[j]][i] = 0;
}
mp_map(g_result);
}
getch();
return 0;
}
看完這些，你對數獨的演算法了解了嗎？
③ 請教九宮數獨的演算法
九宮一般用排除法做 比如1個任意格子的數字 他不能和所在行 列 宮已有數字相同 有些不確定的時候可以用假設法推 如果你假設的數字不正確到後面就會出現錯誤
http://ke..com/view/961.htm
網路上有比較詳細的過程
④ 怎麼用python解數獨的演算法題，給個矩陣裡面填充了若干數，用程序自動給填充完整
classSolution:
#@paramboard,a9x92Darray
#-place.
#Donotreturnanyvalue.
defsolveSudoku(self,board):
self.board=board
self.solve()
deffindUnassigned(self):
forrowinrange(9):
forcolinrange(9):
ifself.board[row][col]==".":
returnrow,col
return-1,-1
defsolve(self):
row,col=self.findUnassigned()
#nounassignedpositionisfound,puzzlesolved
ifrow==-1andcol==-1:
returnTrue
fornumin["1","2","3","4","5","6","7","8","9"]:
ifself.isSafe(row,col,num):
self.board[row][col]=num
ifself.solve():
returnTrue
self.board[row][col]="."
returnFalse
defisSafe(self,row,col,ch):
boxrow=row-row%3
boxcol=col-col%3
ifself.checkrow(row,ch)andself.checkcol(col,ch)andself.checksquare(boxrow,boxcol,ch):
returnTrue
returnFalse
defcheckrow(self,row,ch):
forcolinrange(9):
ifself.board[row][col]==ch:
returnFalse
returnTrue
defcheckcol(self,col,ch):
forrowinrange(9):
ifself.board[row][col]==ch:
returnFalse
returnTrue
defchecksquare(self,row,col,ch):
forrinrange(row,row+3):
forcinrange(col,col+3):
ifself.board[r][c]==ch:
returnFalse
returnTrue
⑤ 數獨的進階解題方法
上述方法稱為基礎解法（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。
⑥ 數獨演算法
給你數獨計算器：
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
不要把謎題解一次列出，而是找出下一步，及他的邏輯推理方法。
不要用猜測。
⑦ 請哪位大佬幫我設計一個破解數獨游戲的演算法。多謝啦！
1.聯除法.
在並排的三個九宮格中的兩排尋找相同數字,再利用九宮格得出另一排中該數字位置,該方法適用於中高級數獨.
2.巡格法
找出在每個九宮格中出現頻率較高的數字,得出該數字在其餘九宮格內位置,該方法應用於方法一之後.
3.排它法
這個方法是解決問題的關鍵,易被常人所忽略.在各行列或九宮格中觀察,若有個位置其它數字都不能填,就填餘下的數字
4.待定法
此方法不常用卻很有效.暫時確定某個數字在某個區域,再利用其來進行排除
5.行列法
此方法用於收官階段,利用先從行列突破來提高解題效率.
6.假設法
作為一名高手,我不提倡這種方法.即在某個位置隨機的填上一個數字,再進行推演,並有可能最終產生矛盾而否定結論.
7.頻率法
這種方法相比於上一種方法更能提高效率.在某一行列或九宮格列舉出所有情況,再選擇某位置中出現頻率高的數字
8.候選數法 使用候選數法解數獨題目需先建立候選數列表，根據各種條件，逐步安全的清除每個宮格候選數的不可能取值的候選數，從而達到解題的目的。
使用候選數法一般能解比較復雜的數獨題目，但是候選數法的使用沒有直觀法那麼直接，需要先建立一個候選數列表的准備過程，所以實際使用時可以先利用直觀法進行解題，到無法用直觀法解題時再使用候選數法解題。
候選數法解題的過程就是逐漸排除不合適的候選數的過程，所以在進行候選數刪除的時候一定要小心，確定安全地刪除不合適的候選數，否則，很多時候只有重新做題了。有了計算機軟體的幫助，使得候選數表的維護變得輕鬆起來。
數獨直觀法解題技巧主要有：唯一候選數法、隱性唯一候選數法、 區塊刪減法、數對刪減法、隱性數對刪減法、三鏈數刪減法、隱性三鏈數刪減法、矩形頂點刪減法、三鏈列刪減法、關鍵數刪減法、關連數刪減法。
⑧ 九宮格數獨要怎麼玩，詳細高手教程有嗎就是有沒有什麼演算法啊啥的
數獨顧名思義——每個數字只能出現一次。數獨是一種源自18世紀末的瑞士，後在美國發展、並在日本得以發揚光大的數字謎題。數獨盤面是個九宮，每一宮又分為九個小格。在這八十一格中給出一定的已知數字和解題條件，利用邏輯和推理，在其他的空格上填入1-9的數字。使1-9每個數字在每一行、每一列和每一宮中都只出現一次。這種游戲全面考驗做題者觀察能力和推理能力，雖然玩法簡單，但數字排列方式卻千變萬化，所以不少教育者認為數獨是訓練頭腦的絕佳方式。
數獨解法全是由規則衍生出來的，基本解法分為兩類思路，一類為排除法，一類為唯一法。更復雜的解法，最終也會歸結到這兩大類中。下邊以圖示簡單介紹幾種解法，只要你花幾分鍾看一遍，馬上就可以開始做數獨了。數獨直觀法解題技巧主要有：唯一解法、基礎摒除法、區塊摒除法、唯余解法、矩形摒除法、單元摒除法,余數測試法等。
⑨ 數獨問題'高級數獨沒有更快捷的解答方式嗎
計算機演算法簡介
本文所討論的演算法是一種通用演算法，雖然不能說是最快的演算法，但卻可以求解所有的數獨游戲。
演算法准備：
1、一個可能性：表示某個格子可能填寫的數字。
2、可能性數目：表示某個格子可能性的數量。為0表示已經確定。
3、區域標志：表示某個格子所在區域（小九宮）的ID，所有區域標志都是預定義的。
4、確定數量：表示所有數字已經確定的格子的數量，為81時則表示已經找到解。
5、整個九宮格用三個矩陣表示：可能性矩陣，數目矩陣，區域標志矩陣
演算法的基本思想：
步驟1、將所有未確定的格子的可能性定義為0xFFFF（即所有數字都可能），可能數目為9。
步驟2、尋找所有確定的格子A（可能數目為0），在所有與A同行、同列和同區域的未確定的格子的可能性中減去與A相同的可能性。例如：A確定為9，則與A同行、同列和同區域（區域標志相同）的未確定的格子的可能性與0xFEFF按位與（除去可能性9），並將其可能性數目減少。
在除去可能性的過程中如果發現某個格子B的可能性數目由1減小為0，說明B和A只能取相同的數字，這可能是題目本身無解引起，也肯能是由於步驟3中搜索方向不對引起的，可認為此方向的搜索無解，退出這一方向的搜索。定義這個檢查為唯一性檢查。
步驟3、尋找所有未確定格子中可能性數目最少的格子M，如果M的可能性數目為1，則確定M：將M的可能性數目定義為0，並把確定數量加1，如果此時確定數量達到81，則報告找到解，否則，在所有與M同行、同列和同區域的未確定的格子的可能性中減去與M相同的可能性，並進行唯一性檢查。然後重復步驟3。
如果M的可能性大於1，則把M假設為所有M的可能性，分多個方向進行搜索，在每一個搜索方向重復步驟3（這個可以用遞歸來實現）。
演算法性能
本演算法可以在50毫秒以內求解任意有解的數獨游戲。
⑩ 數獨解題的方法
原創回答：
建議你去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)