board.java

我写的自动解数独题目的小程序,用回朔递归解的 有兴趣的可以看看 很简单的小程序

package shudu;
import java.util.ArrayList;

//总结：ArrayList 的index会随数组的变化而变化。代码拼写错误


public class board extends Thread{

	private smallboard[] smallboards = new smallboard[9];
	private int mode;
	
	private shudu face;
	public board(shudu face,int squ[][])//squ[i][j] i为第i块小九宫,j为小九宫中位置为j 植为方格中的数字
	{
		this.face=face;
		for(int i = 0;i<9;i++)
		{
			smallboards[i] = new smallboard(squ[i]);
		}
		
	}
	public void run()
	{
		mode =1;
		markcandidate();
		mode =2;
		for(int i=0;i<9;i++)
		{
			for(int j=0;j<9;j++)
			{
				System.out.println("sb: "+i+" sq: "+j+" candidate: "+smallboards[i].getSquare(j).getCandidate()+" num: "+smallboards[i].getSquare(j).getNumber());
			}
		}
		System.out.println("--------------------------------");
		testfill(0,0);
	}
	private boolean testfill(int sb,int sq)
	{	
		
		if(sb==9)        
		{
			System.out.println("succeed way!");
			return true;
		}	
		ArrayList<Integer> cc =smallboards[sb].getSquare(sq).getCandidate();		
		System.out.println("sb: "+sb+" sq: "+sq+" candidate: "+smallboards[sb].getSquare(sq).getCandidate()+" num: "+smallboards[sb].getSquare(sq).getNumber());
		if(cc.size()==0){System.out.println("bad way!");return false;}
		smallboard[] sbs = new smallboard[9];
		for(int i=0;i<9;i++)
		{
			smallboard tmp = new smallboard(); 
			for(int j=0;j<9;j++)
			{
				square t = new square(smallboards[i].getSquare(j).getNumber());
				ArrayList<Integer> tt= (ArrayList<Integer>) smallboards[i].getSquare(j).getCandidate().clone();
				t.setCandidate(tt);
				tmp.setsquare(j, t);
			}
			sbs[i] = tmp;
		}
		for(int i=0;i<cc.size();i++)
		{	
			if(smallboards[sb].getSquare(sq).getNumber()==0){
			fillSquare(sb,sq, cc.get(i));
			ArrayList<Integer> t = new ArrayList<Integer>();t.add(cc.get(i));
			smallboards[sb].getSquare(sq).setCandidate(t);
			}
			System.out.println("after sb: "+sb+" sq: "+sq+" candidate: "+smallboards[sb].getSquare(sq).getCandidate()+" num: "+smallboards[sb].getSquare(sq).getNumber());
			System.out.println("after2 sb: "+sb+" sq: "+sq+" candidate: "+sbs[sb].getSquare(sq).getCandidate()+" num: "+sbs[sb].getSquare(sq).getNumber());

			if(testfill(((sq+1)%9==0)?sb+1:sb,(sq+1)%9))
				return true;
			else
			{
				smallboards = new smallboard[9];
				for(int n=0;n<9;n++)
				{
					smallboard tmp = new smallboard(); 
					for(int j=0;j<9;j++)
					{
						square t = new square(sbs[n].getSquare(j).getNumber());
						ArrayList<Integer> tt= (ArrayList<Integer>) sbs[n].getSquare(j).getCandidate().clone();
						t.setCandidate(tt);
						tmp.setsquare(j, t);
					}
					smallboards[n] = tmp;
				}
			}			
		}
		return false;

	}

	private void fillSquare(int sb,int sq,int num)
	{
		smallboards[sb].getSquare(sq).setNumber(num);
		face.updateSquare(sb, sq, num);
		cutRelateCandidate(sb, sq,num);

//		try {
//			Thread.sleep(50);
//		} catch (InterruptedException e) {
//			// TODO Auto-generated catch block
//			e.printStackTrace();
//		}
	}

	private void markcandidate()
	{
		for(int i=0;i<9;i++)//i为大九宫中的第i个小九宫
		{
			for(int j=0;j<9;j++)//j为小九宫中的第j个格子
			{	
				if(smallboards[i].getSquare(j).getNumber()==0)//表示该格为空
				{
					ArrayList<Integer> an = findAvailableNum(i, j);
					if(an.size()==1)//如果该格子能填的数字只有一个 则把该数填到格子里,
					{			    //并把相关的候选数字去掉(小九宫内,行列)						
						fillSquare(i,j,an.get(0));
					}else			//如果能填的数字有多个则把这多个数字设为该格的侯选数字
					{			
						smallboards[i].getSquare(j).setCandidate(an);
					}					
				}
			}			
		}				
	}
	
	private void cutRelateCandidate(int sbindex,int sqindex,int candidate)
	{
		for(int i=0;i<9;i++)
		{
			square currentsq = smallboards[sbindex].getSquare(i);
			if(currentsq.getNumber()==0)
			{
				currentsq.getCandidate().remove((Integer)candidate);
				if(mode ==1)
				if(currentsq.getCandidate().size()==1)					
					fillSquare(sbindex,i,currentsq.getCandidate().get(0));
				
			}
		}
		for(int i = 1;i<=2;i++)
		{
			int currentsb = (sbindex)/3*3+(sbindex%3+i)%3;
			for(int j=0;j<3;j++)
			{
				int currentsq = (sqindex)/3*3+(sqindex%3+j)%3;
				if(smallboards[currentsb].getSquare(currentsq).getNumber()==0)
				{
					smallboards[currentsb].getSquare(currentsq).getCandidate().remove((Integer)candidate);
					if(mode ==1)
					if(smallboards[currentsb].getSquare(currentsq).getCandidate().size()==1)
						fillSquare(currentsb,currentsq,smallboards[currentsb].getSquare(currentsq).getCandidate().get(0));					
				}
			}
		}
		for(int i = 1;i<=2;i++)
		{
			int currentsb = (sbindex/3*3+sbindex%3+i*3)%9;
			for(int j=0;j<3;j++)
			{
				int currentsq = (sqindex/3*3+sqindex%3+j*3)%9;
				if(smallboards[currentsb].getSquare(currentsq).getNumber()==0)
				{
					smallboards[currentsb].getSquare(currentsq).getCandidate().remove((Integer)candidate);
					if(mode ==1)
					if(smallboards[currentsb].getSquare(currentsq).getCandidate().size()==1)
						fillSquare(currentsb,currentsq,smallboards[currentsb].getSquare(currentsq).getCandidate().get(0));
					
				}			
			}
		}
	
	}

	private ArrayList<Integer> findAvailableNum(int sbindex,int sqindex)
	{
		ArrayList<Integer> an = smallboards[sbindex].getSquare(sqindex).getCandidate();
		
		//在小九宫内去掉的不可行数字
		for(int i=0;i<9;i++)
		{
			if(smallboards[sbindex].getSquare(i).getNumber()!=0)
			{
				an.remove((Integer)smallboards[sbindex].getSquare(i).getNumber());
			}
		}
	
		//在横排内去掉的不可行数字
		for(int i = 1;i<=2;i++)
		{
			int currentsb = (sbindex)/3*3+(sbindex%3+i)%3;
			for(int j=0;j<3;j++)
			{
				int currentsq = (sqindex)/3*3+(sqindex%3+j)%3;
				if(smallboards[currentsb].getSquare(currentsq).getNumber()!=0)
					an.remove((Integer)smallboards[currentsb].getSquare(currentsq).getNumber());
			}
		}
		//在竖排内去掉不可行数字
		for(int i = 1;i<=2;i++)
		{
			int currentsb = (sbindex/3*3+sbindex%3+i*3)%9;
			for(int j=0;j<3;j++)
			{
				int currentsq = (sqindex/3*3+sqindex%3+j*3)%9;
				if(smallboards[currentsb].getSquare(currentsq).getNumber()!=0)
					an.remove((Integer)smallboards[currentsb].getSquare(currentsq).getNumber());
			}
		}	
		return an;
	}
	

}