java數獨演算法

❶ 數獨的方法技巧與規律 數獨的方法技巧與規律介紹

1、在空格內填入1~9的任意一個數，使得盤面內，每一行、每一列、每一個正方形粗線九宮格區域內的數字，均包含1到9，不含有重復的數字。

2、唯一睜局盯余數法，簡稱唯余法悉和，是一種某個單元格中被摒除法排除情況後，只剩下1~9的其中某個數字沒有填，從而得到它就是此單元格的值的解法。唯一餘數法也可以適用於僅在同一個單元內部的推理，中文稱之為點演算法（Full House）。

3、區塊排除。這種技巧被稱為區塊摒除法，用區塊排除了行和列的，稱為宮對行列區塊摒除法（臘豎Pointing）；而下面這個例子則為行列區塊對宮摒除法（Claiming）；而它們各自構成一個區塊（Intersection），例如，單元格組{r1c5, r1c6}就構成一個區塊。

❷ 一個java解數獨的問題

可用遞歸方式來做，具體java代碼我就不寫了。
把格子從左上到右下排成64個，按次序每個做遍歷。
思路大概是這樣的：
function MakeAnswer(傳入父格子)
{
取父格子下的第一個子格子作為當前格子
計算當前格子所有可取的解

while (當前格子還有可取的未嘗試的解)
{
取一個這個當前格子未嘗試過的解，並把這個解標記成已嘗試
判斷是否這個當前格子已經是最後一個格子了，若是，則表示已經得到可行的解，則這個猜測是可行的，否則繼續遞歸 MakeAnswer(當前格子)
}
}

某個格子的嘗試的解改變了之後，往下遞歸子格子的時候，所有子格子的可能的解都有可能會變。

寫得比較抽象，不知你看懂沒

❸ 數獨的計算公式是什麼

1、聯除法。

在並排的三個九宮格中的兩排尋找相同數字，再利用九宮格得出另一排中該數字位置,該方法適用於中高級數獨.

2、巡格法

找出在每個九宮格中出現頻率較高的數字，得出該數字在其餘九宮格內位置,該方法應用於方法一之後。

3、排除法

這個方法是解決問題的關鍵，易被常人所忽略。在各行列或九宮格中觀察,若有個位置其它數字都不能填，就填餘下的數字

4、待定法

此方法不常用卻很有效。暫時確定某個數字在某個區域,再利用其來進行排除

5、行列法

此方法用於收官階段，利用先從行列突破來提高解題效率。

6、假設法

即在某個位置隨機的填上一個數字，再進行推演,並有可能最終產生矛盾而否定結論。

7、頻率法

這種方法相比於上一種方法更能提高效率。在某一行列或九宮格列舉出所有情況，再選擇某位置中出現頻率高的數字

8、候選數法

使用候選數法解數獨題目需先建立候選數列表，根據各種條件，逐步安全的清除每個宮格候選數的不可能取值的候選數，從而達到解題的目的。

(3)java數獨演算法擴展閱讀：

數獨的出題方法：

1、挖洞法

從有到無的出題方法。先生成一個終盤，然後挖去部分數字形成一道題目。

2、填數法

從無到有的出題方法。在一個空盤面上填上部分數字形成一道題目。2007年日本NPGenerator軟體的網站提出了一種邊推理邊出題的出題法，可以手工打造出漂亮圖案的數獨題目。

❹ 求用java寫一個數獨游戲

public class ShuDu {
/**存儲數字的數組*/
static int[][] n = new int[9][9];
/**生成隨機數字的源數組，隨機數字從該數組中產生*/
static int[] num = {1,2,3,4,5,6,7,8,9};
public static void main(String[] args) {
//生成數字
for(int i = 0;i < 9;i++){
//嘗試填充的數字次數
int time = 0;
//填充數字
for(int j = 0;j < 9;j++){
//產生數字
n[i][j] = generateNum(time);
//如果返回值為0，則代表卡住，退回處理
//退回處理的原則是：如果不是第一列，則先倒退到前一列，否則倒退到前一行的最後一列
if(n[i][j] == 0){
//不是第一列，則倒退一列
if(j > 0){
j-=2;
continue;
}else{//是第一列，則倒退到上一行的最後一列
i--;
j = 8;
continue;
}
}
//填充成功
if(isCorret(i,j)){
//初始化time，為下一次填充做准備
time = 0;
}else{ //繼續填充
//次數增加1
time++;
//繼續填充當前格
j--;
}
}
}
//輸出結果
for(int i = 0;i < 9;i++){
for(int j = 0;j < 9;j++){
System.out.print(n[i][j] + " ");
}
System.out.println();
}
}

/**
* 是否滿足行、列和3X3區域不重復的要求
* @param row 行號
* @param col 列號
* @return true代表符合要求
*/
public static boolean isCorret(int row,int col){
return (checkRow(row) & checkLine(col) & checkNine(row,col));
}

/**
* 檢查行是否符合要求
* @param row 檢查的行號
* @return true代表符合要求
*/
public static boolean checkRow(int row){
for(int j = 0;j < 8;j++){
if(n[row][j] == 0){
continue;
}
for(int k =j + 1;k< 9;k++){
if(n[row][j] == n[row][k]){
return false;
}
}
}
return true;
}

/**
* 檢查列是否符合要求
* @param col 檢查的列號
* @return true代表符合要求
*/
public static boolean checkLine(int col){
for(int j = 0;j < 8;j++){
if(n[j][col] == 0){
continue;
}
for(int k =j + 1;k< 9;k++){
if(n[j][col] == n[k][col]){
return false;
}
}
}
return true;
}

/**
* 檢查3X3區域是否符合要求
* @param row 檢查的行號
* @param col 檢查的列號
* @return true代表符合要求
*/
public static boolean checkNine(int row,int col){
//獲得左上角的坐標
int j = row / 3 * 3;
int k = col /3 * 3;
//循環比較
for(int i = 0;i < 8;i++){
if(n[j + i/3][k + i % 3] == 0){
continue;
}
for(int m = i+ 1;m < 9;m++){
if(n[j + i/3][k + i % 3] == n[j + m/3][k + m % 3]){
return false;
}
}
}
return true;
}

/**
* 產生1-9之間的隨機數字
* 規則：生成的隨機數字放置在數組8-time下標的位置，隨著time的增加，已經嘗試過的數字將不會在取到
* 說明：即第一次次是從所有數字中隨機，第二次時從前八個數字中隨機，依次類推，
* 這樣既保證隨機，也不會再重復取已經不符合要求的數字，提高程序的效率
* 這個規則是本演算法的核心
* @param time 填充的次數，0代表第一次填充
* @return
*/
public static int generateNum(int time){
//第一次嘗試時，初始化隨機數字源數組
if(time == 0){
for(int i = 0;i < 9;i++){
num[i] = i + 1;
}
}
//第10次填充，表明該位置已經卡住，則返回0，由主程序處理退回
if(time == 9){
return 0;
}
//不是第一次填充
//生成隨機數字，該數字是數組的下標，取數組num中該下標對應的數字為隨機數字
int ranNum = (int)(Math.random() * (9 - time));
//把數字放置在數組倒數第time個位置，
int temp = num[8 - time];
num[8 - time] = num[ranNum];
num[ranNum] = temp;
//返回數字
return num[8 - time];
}
}

❺ 數獨的進階解題方法

上述方法稱為基礎解法（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。