javaで数独

数問解いた感じでは、解を全部出すやつ(getAll)で1秒弱くらい
速いのか遅いのか、どうなんだろう
これはポインタみたいにして、数字が入れられるか調べたけどこれより良い方法が思いつかない
なんとか作問につかえるレベルか・・・?
1問作るのに数秒はかかりそうだなぁ

コード

import java.util.ArrayList;
import java.util.Scanner;

public class solve {
	public static void main(String[] args){
		solve s=new solve();		
		
		int M[][]=new int[9][9];
		ArrayList<int[][]> ans;
		Scanner sc=new Scanner(System.in);
		for(int i=0;i<9;i++){
			String str=sc.nextLine();
			for(int j=0;j<9;j++){
				M[i][j]=Integer.parseInt(str.substring(j,j+1));
			}
		}
		sc.close();
		long start=System.currentTimeMillis();
		ans=s.getAll(M);
		long stop=System.currentTimeMillis();
		System.out.println("解は"+ans.size()+"個");
		for(int i=0;i<ans.size();i++){
			int a[][]=ans.get(i);
			s.output(a);
			System.out.println();
		}
		System.out.println("実行にかかった時間: "+(stop - start));
	}
	
	public void output(int M[][]){
		for(int i=0;i<M.length;i++){
			for(int j=0;j<M[i].length;j++){
				System.out.print(M[i][j]);
			}
			System.out.println();
		}
	}
	
	@SuppressWarnings("unused")
	private void outputBitInt(int x){
		System.out.println(x);
		for(int i=31;i>=0;i--){
			System.out.print((x&(1<<i))==0?0:1);
		}
		System.out.println();
	}
	
	static final int size=9;
	INT check[][][]=new INT[size][size][3];
	int ans[][];
	ArrayList<int[][]> ansArray;
	//[縦][横]
	//[0]=縦,[1]=横,[2]=塊
	public solve(){
		INT tate[]=new INT[size];
		INT yoko[]=new INT[size];
		for(int i=0;i<tate.length;i++){
			tate[i]=new INT(0);
			yoko[i]=new INT(0);
		}
		INT katamari[][]=new INT[3][3];
		for(int i=0;i<katamari.length;i++){
			for(int j=0;j<katamari[i].length;j++){
				katamari[i][j]=new INT(0);
			}
		}
		for(int i=0;i<size;i++){
			for(int j=0;j<size;j++){
				check[j][i][0]=tate[j];
				check[i][j][1]=yoko[j];
			}
		}
		for(int i=0;i<size;i+=3){
			for(int j=0;j<size;j+=3){
				for(int a=0;a<3;a++){
					for(int b=0;b<3;b++){
						check[i+a][j+b][2]=katamari[i/3][j/3];
					}
				}
			}
		}
	}
	
	private void init(){
		for(int i=0;i<size;i++){
			for(int j=0;j<size;j++){
				for(int k=0;k<3;k++){
					check[i][j][k].x=0;
				}
			}
		}
	}
	
	private boolean ok(int y,int x,int a){
		return (check[y][x][0].x&(1<<a))==0 && (check[y][x][1].x&(1<<a))==0 && (check[y][x][2].x&(1<<a))==0;
	}
	
	private void put(int y,int x,int a){
		check[y][x][0].x|=(1<<a);
		check[y][x][1].x|=(1<<a);
		check[y][x][2].x|=(1<<a);
		ans[y][x]=a;
	}
	
	private void take(int y,int x,int a){
		check[y][x][0].x&=~(1<<a);
		check[y][x][1].x&=~(1<<a);
		check[y][x][2].x&=~(1<<a);
		ans[y][x]=0;
	}
	
	public int[][] get1(int[][] M){
		init();
		ans=new int[size][size];
		if(M.length!=size){
			System.out.println("引数のサイズがおかしい");
			return ans;
		}
		for(int i=0;i<size;i++){
			if(M[i].length!=size){
				System.out.println("引数のサイズがおかしい");
				return ans;
			}
			for(int j=0;j<size;j++){
				if(M[i][j]!=0){
					put(i,j,M[i][j]);
				}
			}
		}
		if(!dfs1(0,0)){
			System.out.println("解無し");
		}
		return ans;
	}
	
	private boolean dfs1(int y,int x){
		if(y==8 && x==8){
			for(int i=1;i<=size;i++){
				if(ok(y,x,i)){
					put(y,x,i);
					return true;
				}
			}
			return false;
		}
		int yy=y+1,xx=x;
		if(yy>=size){
			yy=0;
			xx++;
		}
		if(ans[y][x]!=0){
			if(dfs1(yy,xx))
				return true;
		}else{
			for(int i=1;i<=size;i++){
				if(ok(y,x,i)){
					put(y,x,i);
					if(dfs1(yy,xx))
						return true;
					take(y,x,i);
				}
			}
		}
		return false;
	}
	
	@SuppressWarnings({ "rawtypes", "unchecked" })
	public ArrayList<int[][]> getAll(int[][] M){
		init();
		ans=new int[size][size];
		ansArray=new ArrayList();
		if(M.length!=size){
			System.out.println("引数のサイズがおかしい");
			return ansArray;
		}
		for(int i=0;i<size;i++){
			if(M[i].length!=size){
				System.out.println("引数のサイズがおかしい");
				return ansArray;
			}
			for(int j=0;j<size;j++){
				if(M[i][j]!=0){
					put(i,j,M[i][j]);
				}
			}
		}
		dfsAll(0,0);
		if(ansArray.size()==0){
			System.out.println("解無し");
		}
		return ansArray;
	}
	
	private void dfsAll(int y,int x){
		if(y==8 && x==8){
			for(int i=1;i<=size;i++){
				if(ok(y,x,i)){
					put(y,x,i);
					int tmp[][]=new int[9][9];
					for(int a=0;a<9;a++){
						for(int b=0;b<9;b++){
							tmp[a][b]=ans[a][b];
						}
					}
					take(y,x,i);
					ansArray.add(tmp);
				}
			}
			return;
		}
		int yy=y+1,xx=x;
		if(yy>=size){
			yy=0;
			xx++;
		}
		if(ans[y][x]!=0){
			dfsAll(yy,xx);
		}else{
			for(int i=1;i<=size;i++){
				if(ok(y,x,i)){
					put(y,x,i);
					dfsAll(yy,xx);
					take(y,x,i);
				}
			}
		}
	}

	class INT{
		int x;
		public INT(int x){
			this.x=x;
		}
	}
}

入出力例

060900030
009040010
002000000
006000500
500002008
001003900
000000800
070030400
020001070
解は1個
765918234
389246715
412375689
296187543
537492168
841563927
653724891
178639452
924851376

実行にかかった時間: 424

追記

f:id:hoshi524:20120910204917p:plain
画像のような場合、赤いマークがついているところは[4,5,8]は必ず入らないが
上記のコードでは考慮してしまうので改良の必要あり