欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

Java實現(xiàn)解數(shù)獨的小程序

 更新時間:2017年01月22日 09:46:14   作者:databatman  
最近在學習Java,然后上個月迷上了九宮格數(shù)獨,玩了幾天,覺得實在有趣,就想著能不能用編程來解決,于是就自己寫了個,還真解決了。下面這篇文章就給大家主要介紹了Java實現(xiàn)解數(shù)獨的小程序,需要的朋友可以參考借鑒。

前言

數(shù)獨相信很多人都玩過,趣味性很強,十分的耐玩??捎袥]有程序員想過玩實現(xiàn)一個數(shù)獨布局的算法呢?算法是個很有意思,很神奇的東西。

算法如下,需要預先給出幾個固定的值,目前解決的一個最難的數(shù)獨是大概26個已知值的情況,理論上應該能解決任意已知值的數(shù)獨,不過不知道會不會迭代棧溢出……因為在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)

將上面的數(shù)字保存到num.txt文件中,再把底下附的源代碼保存為Sudoku.java。

然后在cmd命令行模型下輸入:

javac Sudoku.java 
java Sudoku <num.txt 

即可得到結果。

這個解法是我之前看到八皇后排列問題的解法后結合應用的,在數(shù)獨中采用了這種解法,不過應該算是比較暴力的拆解,所以我后面命名成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矩陣保存數(shù)獨正確的值 
 2、建立一個9X9列表,每個列表里保存著該位置,數(shù)獨可以填入的可能值 
  如ArrayList[1][1]={1,2,3}即1,1這個位置的數(shù)獨可能可以填入其中一個 
  當矩陣該位置已保存了正確值時,清空對應位置的ArrayList 
 3、當列表ArrayList里只有一個可能值時,那個值就是數(shù)獨的正確值,將該值填入數(shù)獨矩陣 
  并更新ArrayList 
 
 PS:以上算法只能用于求困難級別的數(shù)獨,因為我在玩游戲的時候發(fā)現(xiàn),每個時刻必定會有 
  一個數(shù)獨空位,是只能填入一個值的,所以這個算法才能運行 
  當一個數(shù)獨(即已知位置的值變少時),可能會出現(xiàn)所有的空位都最起碼有兩個值時, 
  需要改進算法,通過代入來判斷這個數(shù)獨是否成立 
 
 4、于是后期我加入了暴力破解法,在上面的步驟執(zhí)行后無法得出數(shù)獨,即使用暴力破解 
*  
*/ 
 
 
 
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,即此時沒有填充數(shù)字 
  for(int i=0;i<10;i++) 
   for(int j=0;j<10;j++) 
    correctNum[i][j]=-1; 
 
 
 } 
 
 public Sudoku(){} 
 
 //在對應數(shù)獨位置插入正確值 
 public void insert(int row,int col,int value){ 
  correctNum[row][col]=value; 
  availableNum[row][col]=null; 
  delete(row,col,value); 
 
 } 
 //每插入一個數(shù)值,就刪除相應的行列和小框框3X3數(shù)獨里對應的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)); 
    } 
 
 } 
 //判斷插入的值時處于哪個小框框數(shù)獨里 
 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; 
 
 } 
 
 //判斷空格里所能填的數(shù)字是不是只能有一個,當返回-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個的數(shù)時,我們直接將哪個正確的值填入 
 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); 
     } 
    } 
     
   } 
  } 
 } 
 
 
 
 
 
 
 //判斷數(shù)獨的矩陣是否填滿,沒有則繼續(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; 
 } 
 
 //先輸入已知位置的數(shù)字 
 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); 
  } 
 } 
 
  
 
 //打印數(shù)獨結果 
 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; 
 } 
 
 
 //數(shù)獨開始運算的函數(shù) 
 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)方法實例

    Servlet輸出一個驗證碼圖片的實現(xiàn)方法實例

    這篇文章主要給大家介紹了關于Servlet輸出一個驗證碼圖片的實現(xiàn)方法,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧
    2021-01-01
  • 在IDEA中集成maven詳細流程圖示例

    在IDEA中集成maven詳細流程圖示例

    最近利用兩天時間學習了MyBatis以及maven,避免經典的學過就忘記,我打算做出點總結以便日后復習,當然如果能幫到需要的人也是極好的,需要的朋友可以參考下
    2021-06-06
  • 使用@RequestBody傳對象參數(shù)時碰到的坑

    使用@RequestBody傳對象參數(shù)時碰到的坑

    這篇文章主要介紹了使用@RequestBody傳對象參數(shù)時碰到的坑,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教
    2021-08-08
  • 詳解如何使用ModelMapper庫進行對象之間的屬性映射

    詳解如何使用ModelMapper庫進行對象之間的屬性映射

    這篇文章主要介紹了如何使用ModelMapper庫進行對象之間的屬性映射實現(xiàn)詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪
    2023-07-07
  • Spring中基于xml的AOP的詳細步驟

    Spring中基于xml的AOP的詳細步驟

    這篇文章主要介紹了Spring中基于xml的AOP的詳細步驟,本文通過實例代碼給大家介紹的非常詳細,對大家的學習或工作具有一定的參考借鑒價值,需要的朋友可以參考下
    2020-06-06
  • java和c/c++ 數(shù)據(jù)類型長度的比較

    java和c/c++ 數(shù)據(jù)類型長度的比較

    本篇文章主要是對java和c/c++ 數(shù)據(jù)類型長度的進行了詳細的比較。需要的朋友可以過來參考下,希望對大家有所幫助
    2014-01-01
  • JavaEE中volatile、wait和notify詳解

    JavaEE中volatile、wait和notify詳解

    這篇文章主要給大家介紹了關于JavaEE中volatile、wait和notify的相關資料,文中通過實例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下
    2023-02-02
  • Java實現(xiàn)Excel導入導出數(shù)據(jù)庫的方法示例

    Java實現(xiàn)Excel導入導出數(shù)據(jù)庫的方法示例

    這篇文章主要介紹了Java實現(xiàn)Excel導入導出數(shù)據(jù)庫的方法,結合實例形式分析了java針對Excel的讀寫及數(shù)據(jù)庫操作相關實現(xiàn)技巧,需要的朋友可以參考下
    2017-08-08
  • Java 深入淺出講解泛型與包裝類

    Java 深入淺出講解泛型與包裝類

    泛型是在Java SE 1.5引入的的新特性,本質是參數(shù)化類型,也就是說所操作的數(shù)據(jù)類型被指定為一個參數(shù)。這種參數(shù)類型可以用在類、接口和方法的創(chuàng)建中,分別稱為泛型類、泛型接口、泛型方法,本篇我們一起來學習泛型以及包裝類
    2022-04-04
  • Spring菜鳥教你看源碼沖面試

    Spring菜鳥教你看源碼沖面試

    這篇文章主要介紹了Spring菜鳥教你看源碼沖面試,本文給大家介紹的非常詳細,對大家的學習或工作具有一定的參考借鑒價值,需要的朋友可以參考下
    2021-03-03

最新評論