Java實現(xiàn)解數獨的小程序
更新時間：2017年01月22日 09:46:14 作者：databatman
最近在學習Java，然后上個月迷上了九宮格數獨，玩了幾天，覺得實在有趣，就想著能不能用編程來解決，于是就自己寫了個，還真解決了。下面這篇文章就給大家主要介紹了Java實現(xiàn)解數獨的小程序,需要的朋友可以參考借鑒。
前言
數獨相信很多人都玩過，趣味性很強，十分的耐玩。可有沒有程序員想過玩實現(xiàn)一個數獨布局的算法呢？算法是個很有意思，很神奇的東西。
算法如下，需要預先給出幾個固定的值，目前解決的一個最難的數獨是大概26個已知值的情況，理論上應該能解決任意已知值的數獨，不過不知道會不會迭代棧溢出……因為在26個已知值的情況下就迭代了3000多次了，囧~~~
結果顯示如下：
這是已知值:
1 1 2 1 4 8 1 5 5 1 6 1 1 7 7 1 8 3 2 1 1 2 2 6 2 4 4 3 5 9 3 7 8 3 8 4 4 7 9 5 8 7 6 1 3 6 6 8 6 7 4 6 8 6 7 3 7 7 6 4 7 7 1 8 3 3 8 6 7 9 3 4 9 4 6 9 7 3 9 8 2
（PS：如9 8 2表示第9行第二列的值是2）
將上面的數字保存到num.txt文件中,再把底下附的源代碼保存為Sudoku.java。
然后在cmd命令行模型下輸入：
javac Sudoku.java java Sudoku <num.txt
即可得到結果。
這個解法是我之前看到八皇后排列問題的解法后結合應用的，在數獨中采用了這種解法，不過應該算是比較暴力的拆解，所以我后面命名成violentBreak。。。
雖然只是一個很小的事，但是能嘗試著用編程去解決日常遇到的事，突然覺得很開心，學以致用！
java源代碼：
import java.lang.System.*;
import java.util.ArrayList;
import java.util.Scanner;
/**This class named Sudoku can auto calculate Sudoku but
*you should input some nums which are already known.
*For instance:
*1 5 3
*2 4 7
*There two rows means [1][5]=3 [2][4]=7
*i.e. In row 1 col 5 is value:5
*you can write all known num into one txt file
*and input into this program .
*such as java Sudoku < num.txt
*/
/**代碼邏輯解析：
* 1、建立一個9X9矩陣保存數獨正確的值
2、建立一個9X9列表，每個列表里保存著該位置，數獨可以填入的可能值
如ArrayList[1][1]={1,2,3}即1,1這個位置的數獨可能可以填入其中一個
當矩陣該位置已保存了正確值時，清空對應位置的ArrayList
3、當列表ArrayList里只有一個可能值時，那個值就是數獨的正確值，將該值填入數獨矩陣
并更新ArrayList
PS：以上算法只能用于求困難級別的數獨，因為我在玩游戲的時候發(fā)現(xiàn)，每個時刻必定會有
一個數獨空位，是只能填入一個值的，所以這個算法才能運行
當一個數獨(即已知位置的值變少時)，可能會出現(xiàn)所有的空位都最起碼有兩個值時，
需要改進算法，通過代入來判斷這個數獨是否成立
4、于是后期我加入了暴力破解法，在上面的步驟執(zhí)行后無法得出數獨，即使用暴力破解
*
*/
public class Sudoku{
//弄十的原因是為了好記憶，0,0不用，只用1-9的list
private ArrayList<Integer>[][] availableNum=new ArrayList[10][10];
private int[][] correctNum=new int[10][10];
private Scanner scan=new Scanner(System.in);
private int countNum=0;
{
for(int i=0;i<10;i++){
for(int j=0;j<10;j++){
availableNum[i][j]=new ArrayList<>();
}
}
for(int row=1;row<10;row++){
for(int col=1;col<10;col++){
for(int i=1;i<10;i++)
availableNum[row][col].add(new Integer(i));
}
}
//先都初始化為-1，即此時沒有填充數字
for(int i=0;i<10;i++)
for(int j=0;j<10;j++)
correctNum[i][j]=-1;
}
public Sudoku(){}
//在對應數獨位置插入正確值
public void insert(int row,int col,int value){
correctNum[row][col]=value;
availableNum[row][col]=null;
delete(row,col,value);
}
//每插入一個數值，就刪除相應的行列和小框框3X3數獨里對應的ArrayList里可能的該值
public void delete(int row,int col,int value){
//delte row
for(int i=1;i<10;i++){
if (availableNum[row][i]!=null)
availableNum[row][i].remove(new Integer(value));
}
//delete column
for(int i=1;i<10;i++){
if (availableNum[i][col]!=null)
availableNum[i][col].remove(new Integer(value));
}
//delete box num
int[] itsCenter=judgeCenterPos(row,col);
for(int temp1=itsCenter[0]-1;temp1<=itsCenter[0]+1;temp1++)
for(int temp2=itsCenter[1]-1;temp2<=itsCenter[1]+1;temp2++)
if(availableNum[temp1][temp2]!=null){
availableNum[temp1][temp2].remove(new Integer(value));
}
}
//判斷插入的值時處于哪個小框框數獨里
public int[] judgeCenterPos(int row,int col){
int[] itsCenter=new int[2];
for(int centerRow=2;centerRow<9;centerRow+=3)
for(int centerCol=2;centerCol<9;centerCol+=3){
if( Math.abs(row-centerRow)<=1 &&
Math.abs(col-centerCol)<=1 ){
itsCenter[0]=centerRow;
itsCenter[1]=centerCol;
return itsCenter;
}
}
System.out.println("Some unchecked error was happened");
return itsCenter;
}
//判斷空格里所能填的數字是不是只能有一個,當返回-1時通過檢測報錯
public int[] judgeIfOnlyOne(){
for(int row=1;row<10;row++)
for(int col=1;col<10;col++){
if(availableNum[row][col]!=null)
if(availableNum[row][col].size()==1)
return new int[]{row,col};
}
return new int[]{-1,-1};
}
// 判斷為唯一，但是空格里還有多于1個的數時，我們直接將哪個正確的值填入
public void insertIfCan(){
for(int row=1;row<=7;row+=3){
for(int col=1;col<=7;col+=3){
for(int z=1;z<10;z++){
int count=0;
Integer temp=new Integer(z);
int itemp=0,jtemp=0;
outer:
for(int i=row;i<row+3;i++){
for(int j=col;j<col+3;j++){
if(availableNum[i][j]!=null){
if(availableNum[i][j].contains(temp)){
count++;
itemp=i;
jtemp=j;
if (count>1)
break outer;
}
}
}
}
if(count==1 && itemp!=0){
insert(itemp,jtemp,z);
}
}
}
}
}
//判斷數獨的矩陣是否填滿，沒有則繼續(xù)
public boolean judgeMatrixFull(){
for(int i=1;i<10;i++)
for(int j=1;j<10;j++)
if(correctNum[i][j]==-1)
return false;
return true;
}
//先輸入已知位置的數字
public void inputNumKnown(){
while(scan.hasNextInt()){
int row=scan.nextInt();
int col=scan.nextInt();
int value=scan.nextInt();
insert(row,col,value);
delete(row,col,value);
}
}
//打印數獨結果
public void printSudoku(){
printSudoku(correctNum);
}
public void printSudoku(int[][] arr){
System.out.println("Sudoku result:");
for(int i=1;i<10;i++){
for(int j=1;j<10;j++)
System.out.print(arr[i][j]+" ");
System.out.println(" ");
}
}
public void printList(){
for(int i=1;i<10;i++)
for(int j=1;j<10;j++){
System.out.print(i+" "+j+":");
if(availableNum[i][j]!=null)
for(int z=0;z<availableNum[i][j].size();z++){
System.out.print(availableNum[i][j].get(z)+" ");
}
System.out.println(" ");
}
}
//暴力破解
public void violentBreak(){
int i=1,j=1;
outer:
for(;i<10;i++)
for(;j<10;j++)
if(correctNum[i][j]!=-1)
break outer;
violentInsert(i,j,correctNum[i][j],correctNum);
}
public void violentInsert(int row,int col,int value,int[][] arr){
countNum++;
int[][] tempMatrix=new int[10][10];
for(int i=1;i<10;i++)
for(int j=1;j<10;j++)
tempMatrix[i][j]=arr[i][j];
tempMatrix[row][col]=value;
//不能insert的話說明填滿了
int[] insertPos=canInsert(tempMatrix);
if(insertPos[0]==-1){
System.out.println("all insert is done.This is the last Sudoku:");
printSudoku(tempMatrix);
return;
}
for(int val=1;val<=10;val++){
if(val==10){
tempMatrix=null; //讓JVM回收垃圾
//System.out.println("value=10 happened.");
return;
}
if(judgeIfViolentInsert(insertPos[0],insertPos[1],val,tempMatrix)){
//System.out.println("insert happened.");
violentInsert(insertPos[0],insertPos[1],val,tempMatrix);
}
}
}
public int[] canInsert(int[][] tempMatrix){
int[] pos={-1,-1};
for(int i=1;i<10;i++)
for(int j=1;j<10;j++){
if(tempMatrix[i][j]==-1){
pos[0]=i;
pos[1]=j;
return pos;
}
}
return pos;
}
public boolean judgeIfViolentInsert(int row,int col,int value,int[][] tempMatrix){
for(int j=1;j<10;j++)
if(value==tempMatrix[row][j])
return false;
for(int i=1;i<10;i++)
if(value==tempMatrix[i][col])
return false;
int[] itsCenter=judgeCenterPos(row,col);
for(int temp1=itsCenter[0]-1;temp1<=itsCenter[0]+1;temp1++)
for(int temp2=itsCenter[1]-1;temp2<=itsCenter[1]+1;temp2++)
if(value==tempMatrix[temp1][temp2])
return false;
return true;
}
//數獨開始運算的函數
public void start(){
int[] nextInsert=new int[2];
int count=0;
this.inputNumKnown();
while(!judgeMatrixFull()){
nextInsert=judgeIfOnlyOne();
if(nextInsert[0]==-1){
this.insertIfCan();
count++;
if(count==15){
System.out.println("Cannot fullfill this sodoku through finding the only one left.");
System.out.println("count:"+count);
break;
}
continue;
}
int value=availableNum[nextInsert[0]][nextInsert[1]].get(0);
insert(nextInsert[0],nextInsert[1],value);
}
printSudoku();
//滿了就不用暴力破解了
if(judgeMatrixFull())
return;
System.out.println("Now we should break this Sudoku by violent method.");
violentBreak();
System.out.println("Recursion times:"+countNum);
}
public static void main(String[] args){
Sudoku test1=new Sudoku();
test1.start();
int[] a=new int[2];
System.out.println(a);
System.out.println(a[0]);
}
}
總結
以上就是這篇文章的全部內容了，希望本文的內容對大家的學習或者工作能帶來一定的幫助，如果有疑問大家可以留言交流。
相關文章
這篇文章主要給大家介紹了關于Servlet輸出一個驗證碼圖片的實現(xiàn)方法，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2021-01-01
最近利用兩天時間學習了MyBatis以及maven,避免經典的學過就忘記,我打算做出點總結以便日后復習,當然如果能幫到需要的人也是極好的,需要的朋友可以參考下2021-06-06
這篇文章主要介紹了使用@RequestBody傳對象參數時碰到的坑，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-08-08
這篇文章主要介紹了如何使用ModelMapper庫進行對象之間的屬性映射實現(xiàn)詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2023-07-07
這篇文章主要介紹了Spring中基于xml的AOP的詳細步驟，本文通過實例代碼給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值,需要的朋友可以參考下2020-06-06
本篇文章主要是對java和c/c++ 數據類型長度的進行了詳細的比較。需要的朋友可以過來參考下，希望對大家有所幫助2014-01-01
這篇文章主要給大家介紹了關于JavaEE中volatile、wait和notify的相關資料,文中通過實例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2023-02-02
這篇文章主要介紹了Java實現(xiàn)Excel導入導出數據庫的方法,結合實例形式分析了java針對Excel的讀寫及數據庫操作相關實現(xiàn)技巧,需要的朋友可以參考下2017-08-08
泛型是在Java SE 1.5引入的的新特性，本質是參數化類型，也就是說所操作的數據類型被指定為一個參數。這種參數類型可以用在類、接口和方法的創(chuàng)建中，分別稱為泛型類、泛型接口、泛型方法，本篇我們一起來學習泛型以及包裝類2022-04-04
這篇文章主要介紹了Spring菜鳥教你看源碼沖面試,本文給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2021-03-03