shudu.java

数独求解器 可以快速求解数独。 bug:不支持无解数独

/*
* @author: [e-mail]
* Copyright: NJUSoftware 2009
*/
import java.awt.Point;
import java.util.ArrayList;
public class ShuDu {
	private static int[] num;
	public ShuDu(int[] Num){
		num=Num;
	}
	/*={0,
		9,0,0,6,0,1,0,0,2,
		0,0,0,0,3,0,0,6,0,
		0,0,0,2,5,0,0,0,0,
		0,7,0,9,6,0,0,0,8,
		0,3,4,0,0,0,1,0,0,
		0,0,0,0,0,8,0,0,0,
		0,0,9,0,2,7,0,0,0,
		0,0,7,0,0,0,5,0,4,
		0,6,0,0,0,0,0,8,0};*/
	static ArrayList<Point> pos=new ArrayList<Point>();
	private static boolean go_on=true;
	//private static ArrayList<ArrayList<Integer>> posible=new ArrayList<ArrayList<Integer>>(); 
    public  boolean calcSoduku(){
    	//printArray();
     	int level=0;
    	ALink root=new ALink();
    	ALink tmpLink=root;
    	Integer[] values;
    	ArrayList<Integer> tmp=null;
    	for(int ix=1;ix<10;ix++){
			for(int jx=1;jx<10;jx++){
				values=getValue(ix,jx);
				int len=values.length;
				if(len>0){
					//print(len);
					level++;
					pos.add(new Point(ix,jx));
					tmp=new ArrayList<Integer>();
					for(int k=0;k<len;k++)
						tmp.add(values[k]);
					ALink cur=new ALink(tmp);
					cur.setLevel(level);
					tmpLink.setNextALink(cur);
					tmpLink=cur;
				}
			}
    	}
    //	print("LevelRoot:"+root.getLevel());
    	//display(root);
    	checkAns(root.getNextALink());
    	if(go_on==false)
    		return true;
    	else
    		return false;
    	//printArray();
     }
 /*   private  void printArray(){
		for(int i=1;i<82;i++){
			System.out.print(num[i]);
			if(i%9==0)
				System.out.println();
		}
	}*/
  /*  private  void display(ALink root){
    	System.out.println("Level:"+root.getLevel());
    	if(root.getArrayList()==null){
    		display(root.getNextALink());
    		return;
    	}
    	ArrayList<Integer> dis=root.getArrayList();
    	
    	for(int ix=0;ix<dis.size();ix++){
    	
    		System.out.print(dis.get(ix)+",");
    		
    	}
    	System.out.println();
    	if (root.getNextALink()!=null)
    		display(root.getNextALink());
    }
    */
    private  void setZero(ALink root){
    	if(root.getLevel()>0){
    		int index=(pos.get(root.getLevel()-1).x-1)*9+pos.get(root.getLevel()-1).y;
    		num[index]=0;
    	}
		if(root.getNextALink()==null)
			return;
		setZero(root.getNextALink());
	}
	private  void checkAns(ALink root){
		//print("Level:"+ root.getLevel());
		setZero(root);
		ArrayList<Integer> tmp=root.getArrayList();
		int len=tmp.size();
		if(len>0){
			int index;
			index=(pos.get(root.getLevel()-1).x-1)*9+pos.get(root.getLevel()-1).y;
			Integer[] enable=getValue(pos.get(root.getLevel()-1).x,pos.get(root.getLevel()-1).y);
			for(int ix=0;ix<len;ix++){
				if(!go_on)
					return;
				int tmpNum=tmp.get(ix);
				//print(enable);
				boolean go=canBePutDown(enable,tmpNum);
				if(!go ){
					if(ix==len-1)
						return;
					else
						continue;
				}
				else{
					num[index]=tmpNum;
					//printArray();
					//print("-------------");
					if(root.getNextALink()==null){
						go_on=false;
						return;
					}
					else{
						if(go_on)
							checkAns(root.getNextALink());
					}
				}
			}
			
			
		}
	}
	
	private  boolean canBePutDown(Integer[] int1,int tmp){
		int len=int1.length;
		if(len==0)
			return false;
		for(int i=0;i<len;i++){
			if (tmp==int1[i])
				return true;
		}
		return false;
	}
	/*private  void print(Integer[] r){
		if (r.length==0){
			System.out.print("No Value!");
			return;
		}
		for(int i=0;i<r.length;i++){
			System.out.print(r[i] + "..");
		}
		System.out.println();
		System.out.println("******************");
	}
	private  void print(int num){
		System.out.println(num);
	}
	private  void print(String str){
		System.out.println(str);
	}*/
	private  Integer[] getRow(int row){
	
		ArrayList<Integer> tmp= new ArrayList<Integer>();
		Integer[] rec;
		for(int i =1;i<=9;i++){
			boolean has =false;
			for(int j=9*(row-1)+1;j<=9*(row-1)+9;j++){
	
				if (i==num[j]){
					has=true;
					break;
				}
			}
			if(has==false){
				tmp.add(i);
			}
		}
		
		rec=(Integer[])tmp.toArray(new Integer[tmp.size()]);
		return rec;
	}
	private  Integer[] getCol(int col){
		ArrayList<Integer> tmp= new ArrayList<Integer>();
		Integer[] rec;
		for(int i =1;i<=9;i++){
			boolean has=false;
			for(int j=col;j<=col+72;j+=9){
				if (i==num[j]){
					has=true;
					break;
				}
			}
			if (has==false)
				tmp.add(i);
		} 
		rec=(Integer[])tmp.toArray(new Integer[tmp.size()]);
		return rec;
	}
	private  Integer[] joinSet(Integer[] int1,Integer[] int2){
		ArrayList<Integer> tmp= new ArrayList<Integer>();
		Integer[] rec;
		for(int i=0;i<int1.length;i++){
			for(int j=0;j<int2.length;j++){
				if( int1[i]==int2[j]){
				tmp.add(int1[i]);
				break;
				}
			}  			
		}
		rec=(Integer[])tmp.toArray(new Integer[tmp.size()]);
		return rec;
	}
	private  Integer[] getThr(int row,int col){
		ArrayList<Integer> tmp= new ArrayList<Integer>();
		Integer[] rec;
		int _row;
		int _col;
		if((row % 3==0))
			_row=(row/3-1)*3+1;
		else
			_row=(row/3)*3+1;
		if((col % 3==0))
			_col=(col/3-1)*3+1;
		else
			_col=(col/3)*3+1;
		for(int t=1;t<=9;t++){
		 		
			boolean has =false;
			for(int i=1;i<=3;i++){
				int temp=(_row-1)*9+_col+(i-1)*9;
				if(has==true)
					break;
				for(int j=temp;j<temp+3;j++){
			
					if(t==num[j]){
			//	System.out.print(num[j]);
						has=true;
						break;
					}
				}
			}
		if(has==false)
			tmp.add(t);
		}
		rec=(Integer[])tmp.toArray(new Integer[tmp.size()]);
		return rec;	
	}
	private  Integer[] getValue(int row,int col){
		Integer[] rec=new Integer[0];	
		if(num[(row-1)*9+col]!=0)
			return rec;
		return joinSet(joinSet(getRow(row),getCol(col)),getThr(row,col));
	}
}