这里有新鲜出炉的 Java 并发编程示例,程序狗速度看过来!
java 是一种可以撰写跨平台应用软件的面向对象的程序设计语言,是由 Sun Microsystems 公司于 1995 年 5 月推出的 Java 程序设计语言和 Java 平台(即 JavaEE(j2ee), JavaME(j2me), JavaSE(j2se))的总称。
最近在学习 Java,然后上个月迷上了九宫格数独,玩了几天,觉得实在有趣,就想着能不能用编程来解决,于是就自己写了个,还真解决了。下面这篇文章就给大家主要介绍了 Java 实现解数独的小程序, 需要的朋友可以参考借鉴。
前言
数独相信很多人都玩过,趣味性很强,十分的耐玩。可有没有程序员想过玩实现一个数独布局的算法呢?算法是个很有意思,很神奇的东西。
算法如下,需要预先给出几个固定的值,目前解决的一个最难的数独是大概 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]);
- }
- }
总结
以上就是这篇文章的全部内容了,希望本文的内容对大家的学习或者工作能带来一定的帮助,如果有疑问大家可以留言交流。
来源: http://www.phperz.com/article/17/1221/358710.html