solver.java

用java写的数独的算法程序

package phz;

public class Solver{
    private static final int SIZE = Puzzler.SIZE;
    private Solver(){
    }
    public static boolean solve(Puzzler p){
        int[][]    num =new int[SIZE][SIZE];
        boolean[][] rFlags =new boolean[SIZE][SIZE+1],
                cFlags =new boolean[SIZE][SIZE+1],
                zFlags =new boolean[SIZE][SIZE+1];
        for(int r=0;r<SIZE;r++)
            for(int c=0;c<SIZE;c++)
                if(p.isFixed(r,c)){
                    int t =p.getNumber(r,c);
                    num[r][c] =t;
                    rFlags[r][t] =true;
                    cFlags[c][t] =true;
                    zFlags[r/3*3+c/3][t] =true;
                }
        
        int r =0,c =0;
        
        outLoop:
            for(;;){//&#
                if(p.isFixed(r,c)){
                    c ++;
                    if(c>=SIZE){
                        c =0;
                        r ++;
                        if(r>=SIZE) break outLoop;
                    }
                    continue outLoop;
                } //&#if(p.isFixed())
                int t =SIZE;
                for(c++;;){//&#
                    if(t>=SIZE){
                        c --;
                        if(c<0){
                            c =SIZE -1;
                            r --;
                            if(r<0) break outLoop;
                        }
                        if(p.isFixed(r,c)) continue;
                        t =num[r][c];
                        if(t!=0){
                            rFlags[r][t] =false;
                            cFlags[c][t] =false;
                            zFlags[r/3*3+c/3][t] =false;
                            num[r][c] =0;
                        }
                    } else{
                        t ++;
                        if(!(rFlags[r][t]||
                                cFlags[c][t]||
                                zFlags[r/3*3+c/3][t])
                                ) break;
                    }
                }//&#for(c++;;);
                num[r][c] =t;
                rFlags[r][t] =true;
                cFlags[c][t] =true;
                zFlags[r/3*3+c/3][t] =true;
                c ++;
                if(c>=SIZE){
                    c =0;
                    r ++;
                    if(r>=SIZE) break outLoop;
                }
            }
            if(r<0) return false;
            for(r=0;r<SIZE;r++)
                for(c=0;c<SIZE;c++)
                    if(!p.isFixed(r,c)) p.setNumber(r,c,num[r][c]);
            return true;
    }
    //test
    public static void main(String[] args){
    	
    	int[][] array = { { 7, 5, 0, 2, 0, 0, 0, 0, 0 },
				{ 0, 0, 4, 0, 9, 6, 0, 0, 2},
				{ 0, 2, 0, 0, 0, 0, 0, 9, 0 },
				{ 0, 4, 3, 0, 2, 1, 0, 6, 0 },
				{ 9, 0, 0, 0, 6, 3, 4, 0, 0 },
				{ 0, 0, 6, 0, 0, 9, 0, 0, 7 },
				{ 4, 9, 2, 0, 0, 7, 3, 0, 0 },
				{ 0, 3, 7, 6, 0, 5, 2, 0, 0 },
				{ 5, 0, 0, 0, 0, 0, 0, 7, 0 } };
    	
        Puzzler p =new Puzzler(array);
        System.out.println(solve(p));
        for(int r =0;r<SIZE;r++){
            for(int c=0;c<SIZE;c++) System.out.print(p.getNumber(r,c)+" ");
            System.out.println();
        }
    }
}