Java实现解数独的小程序
程序员文章站
2024-03-08 15:50:53
前言
数独相信很多人都玩过,趣味性很强,十分的耐玩。可有没有程序员想过玩实现一个数独布局的算法呢?算法是个很有意思,很神奇的东西。
算法如下,需要预先给出几个固定的值,...
前言
数独相信很多人都玩过,趣味性很强,十分的耐玩。可有没有程序员想过玩实现一个数独布局的算法呢?算法是个很有意思,很神奇的东西。
算法如下,需要预先给出几个固定的值,目前解决的一个最难的数独是大概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:以上算法只能用于求困难级别的数独,因为我在玩游戏的时候发现,每个时刻必定会有 一个数独空位,是只能填入一个值的,所以这个算法才能运行 当一个数独(即已知位置的值变少时),可能会出现所有的空位都最起码有两个值时, 需要改进算法,通过代入来判断这个数独是否成立 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]); } }
总结
以上就是这篇文章的全部内容了,希望本文的内容对大家的学习或者工作能带来一定的帮助,如果有疑问大家可以留言交流。
上一篇: Java中集合框架都有什么?