欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

Java实现解数独的小程序

程序员文章站 2024-03-08 15:50:53
前言 数独相信很多人都玩过,趣味性很强,十分的耐玩。可有没有程序员想过玩实现一个数独布局的算法呢?算法是个很有意思,很神奇的东西。 算法如下,需要预先给出几个固定的值,...

前言

数独相信很多人都玩过,趣味性很强,十分的耐玩。可有没有程序员想过玩实现一个数独布局的算法呢?算法是个很有意思,很神奇的东西。

算法如下,需要预先给出几个固定的值,目前解决的一个最难的数独是大概26个已知值的情况,理论上应该能解决任意已知值的数独,不过不知道会不会迭代栈溢出……因为在26个已知值的情况下就迭代了3000多次了,囧~~~

结果显示如下:

Java实现解数独的小程序

这是已知值:

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:以上算法只能用于求困难级别的数独,因为我在玩游戏的时候发现,每个时刻必定会有 
  一个数独空位,是只能填入一个值的,所以这个算法才能运行 
  当一个数独(即已知位置的值变少时),可能会出现所有的空位都最起码有两个值时, 
  需要改进算法,通过代入来判断这个数独是否成立 
 
 4、于是后期我加入了暴力破解法,在上面的步骤执行后无法得出数独,即使用暴力破解 
*  
*/ 
 
 
 
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); 
     } 
    } 
     
   } 
  } 
 } 
 
 
 
 
 
 
 //判断数独的矩阵是否填满,没有则继续 
 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]); 
 
 } 
 
} 

总结

以上就是这篇文章的全部内容了,希望本文的内容对大家的学习或者工作能带来一定的帮助,如果有疑问大家可以留言交流。