數獨演算法
『壹』 數獨演算法思路
數獨(數和)(英: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.聯除法.
在並排的三個九宮格中的兩排尋找相同數字,再利用九宮格得出另一排中該數字位置,該方法適用於中高級數獨.
2.巡格法
找出在每個九宮格中出現頻率較高的數字,得出該數字在其餘九宮格內位置,該方法應用於方法一之後.
3.排它法
這個方法是解決問題的關鍵,易被常人所忽略.在各行列或九宮格中觀察,若有個位置其它數字都不能填,就填餘下的數字
4.待定法
此方法不常用卻很有效.暫時確定某個數字在某個區域,再利用其來進行排除
5.行列法
此方法用於收官階段,利用先從行列突破來提高解題效率.
6.假設法
作為一名高手,我不提倡這種方法.即在某個位置隨機的填上一個數字,再進行推演,並有可能最終產生矛盾而否定結論.
7.頻率法
這種方法相比於上一種方法更能提高效率.在某一行列或九宮格列舉出所有情況,再選擇某位置中出現頻率高的數字
『叄』 數獨的計算公式是什麼
數獨不是計算的
數獨的要求就是
橫
縱
之間不能有重復的數字
『肆』 請教九宮數獨的演算法
九宮一般用排除法做 比如1個任意格子的數字 他不能和所在行 列 宮已有數字相同 有些不確定的時候可以用假設法推 如果你假設的數字不正確到後面就會出現錯誤
http://ke..com/view/961.htm
網路上有比較詳細的過程
『伍』 數獨演算法
給你數獨計算器:
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
不要把謎題解一次列出,而是找出下一步,及他的邏輯推理方法。
不要用猜測。
『陸』 數獨的計算公式是什麼
數獨的計算公式是每一橫行、每一豎行和每一斜行的和都等於15。
『柒』 跪求生成數獨的演算法
這里講的話字數有限制,還是給樓主你網站吧
數獨計算器
『捌』 計算數獨有什麼方法
數獨(すうどく,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。
『玖』 最簡單的數獨計算方法,要具體
數獨解法全是由規則衍生出來的,基本解法分為兩類思路,一類為排除法,一類為唯一法。更復雜的解法,最終也會歸結到這兩大類中。數獨直觀法解題技巧主要有:唯一解法、基礎摒除法、區塊摒除法、唯余解法、矩形摒除法、單元摒除法,余數測試法等。
『拾』 九宮格數獨 演算法
見到很多同樣喜歡數學問題的朋友提問關於9宮格等的問題,我在此做出答案和解法,希望能給大家一點幫助。
九宮格,二十五宮格,甚至八十一宮格,只要是奇數的平方宮格者能做到橫格相加,堅格相加,斜格相加得數相同。而偶數的宮格只有十六宮格有些規律。
下面是三宮格、五宮格、七宮格、九宮格圖.
三宮格(和15)
8 1 6
3 5 7
4 9 2
五宮格(和65)
17 24 1 8 15
23 5 7 14 16
4 6 13 20 22
10 12 19 21 3
11 18 25 2 9
七宮格(和175)
30 39 48 1 10 19 28
38 47 7 9 18 27 29
46 6 8 17 26 35 37
5 14 16 25 34 36 45
13 15 24 33 42 44 4
21 23 32 41 43 3 12
22 31 40 49 2 11 20
九宮格(和369)
47 58 69 80 1 12 23 34 45
57 68 79 9 11 22 33 44 46
67 78 8 10 21 32 43 54 56
77 7 18 20 31 42 53 55 66
6 17 19 30 41 52 63 65 76
16 27 29 40 51 62 64 75 5
26 28 39 50 61 72 74 4 15
36 38 49 60 71 73 3 14 25
37 48 59 70 81 2 13 24 35
這是八十一宮格的排列圖,你可以從中找出規律。
首先在第一行中間寫下1,然後向下移動到最底下,向右移一格寫下2,然後一下向右上方寫到最邊處,
然後平移到最左邊,向上移動一格再向右上方寫。遇到數字後向下寫一格,繼續向右上寫。
按此規律,可寫出任意奇數的平方宮格。
偶數宮格好象沒有規律,且除了十六宮格外,其它的好象也填不出來。填寫十六宮格也有一個規律,叫做「順序排列,雙肩互換」,就是第一行寫上1、2、3、4,第二行5、6、7、8,一直到第四行13、14、15、16,然後2與15對調,3與14對調,5與12對調,8與9對調就可以了。
奇宮格我有另外的方法,1站當中,以馬步照順序下去就可以了,但要注意一點,幾宮格逢幾下一個數直接寫下面,如5宮:
23 12 1 20 9
4 18 7 21 15
10 24 13 2 16
11 5 19 8 22
17 6 25 14 3
《寰神結》橘山黃陵九宮格解法
tuan 2002-12-24 10:13:24
因為是剛剛用記憶邊回想邊畫的,如果有錯請大家多指教,第一次進陽之間九宮格應該要全部壓下
1 2 3
4 5 6
7 8 9
而一進去陽之間時應該呈現的是
2 4 6 8為突起
其餘的為凹下
其破解順序為2-4-8-6
按下後就會出現陰之間
而陰之間九宮格應該要全部壓下
而一進去陰之間時應該呈現的是
3 4 5 6 7為突起
其餘的為凹下
其破解順序為7-3-2-8-1-7-9-3-5-2-4-8-6
然後就可以回到陽之間
再將九宮格全部隆起
其原九宮格跟第一次進陽之間時所呈現的一樣
所以破解順序就為5-1-7-9-3-2-4-8-6
原本的封塵之間就會變為龍泉之間了