読者です 読者をやめる 読者になる 読者になる

jsで数独

INT=function(x){
	this.x=x;
}

const bitnum=new Array(
	1<<0, 1<<1, 1<<2, 1<<3, 1<<4, 1<<5, 1<<6, 1<<7, 1<<8, 1<<9
);

const notbitnum=new Array(
	~(1<<0), ~(1<<1), ~(1<<2), ~(1<<3), ~(1<<4), ~(1<<5), ~(1<<6), ~(1<<7), ~(1<<8), ~(1<<9)
);

const maxAnsNum=10;
var field;
var ans;
var ansNum;
var check;
{
	ans=new Array(9);
	for(i=0;i<ans.length;i++){
		ans[i]=new Array(9);
	}
	field=new Array(81);
	check=new Array(81);
	for(i=0;i<check.length;i++){
		check[i]=new Array(3);
	}
	tate=new Array(9);
	yoko=new Array(9);
	for(i=0;i<tate.length;i++){
		tate[i]=new INT(0);
		yoko[i]=new INT(0);
	}
	katamari=new Array(3);
	for(i=0;i<katamari.length;i++){
		katamari[i]=new Array(3);
		for(j=0;j<katamari[i].length;j++){
			katamari[i][j]=new INT(0);
		}
	}
	for(i=0;i<9;i++){
		for(j=0;j<9;j++){
			check[j*9+i][0]=tate[j];
			check[i*9+j][1]=yoko[j];
		}
	}
	for(i=0;i<9;i+=3){
		for(j=0;j<9;j+=3){
			for(a=0;a<3;a++){
				for(b=0;b<3;b++){
					check[(i+a)*9+j+b][2]=katamari[i/3][j/3];
				}
			}
		}
	}
}

function canPut(pos){
	return check[pos][0].x & check[pos][1].x & check[pos][2].x;
}

function ok(pos,a){
	return (canPut(pos) & bitnum[a]) == bitnum[a];
}

function put(pos,a){
	check[pos][0].x&=notbitnum[a];
	check[pos][1].x&=notbitnum[a];
	check[pos][2].x&=notbitnum[a];
	field[pos]=a;
}

function take(pos,a){
	check[pos][0].x|=bitnum[a];
	check[pos][1].x|=bitnum[a];
	check[pos][2].x|=bitnum[a];
	field[pos]=0;
}

change=new Array(81);
edakari=new Array(81);
for(i=0;i<81;i++){
	edakari[i]=new Array(81);
}
function dfs(){
	for(i=0;i<81;i++){
		change[i]=field[i]==0;
		for(j=0;j<81;j++){
			edakari[i][j]=false;
		}
	}
	
	now=0,prev=0;
	while(now>=0){
		if(now==81){
			if(ansNum==0){
				for(i=0;i<9;i++){
					for(j=0;j<9;j++){
						ans[i][j]=field[i*9+j];
					}
				}
			}
			ansNum++;
			prev=now;
			now--;
		}else{
			if(change[now]){
				i=field[now]+1;
				if(field[now]!=0){
					for(k=now+1;k<81;k++){
						if(edakari[now][k]){
							take(k,field[k]);
							edakari[now][k]=false;
							change[k]=true;
						}
					}
					take(now,field[now]);
				}
				for(;i<=9;i++){
					if(ansNum<maxAnsNum && ok(now,i)){
						put(now,i);
						
						flag=true;
						while(flag){
							flag=false;
							for(k=now+1;k<81;k++){
								if(field[k]==0){
									var cp=canPut(k);
									for(m=1;m<=9;m++){
										if(cp==bitnum[m]){
											put(k,m);
											edakari[now][k]=true;
											change[k]=false;
											flag=true;
											break;
										}
									}
								}
							}
						}
						
						flag=true;
						for(k=now+1;k<81;k++){
							if(field[k]==0 && canPut(k)==0){
								flag=false;
							}
						}
						if(flag){
							prev=now;
							now++;
							break;
						}else{
							for(k=now+1;k<81;k++){
								if(edakari[now][k]){
									take(k,field[k]);
									edakari[now][k]=false;
									change[k]=true;
								}
							}
							take(now,field[now]);
						}
					}
				}
				if(i>=10){
					prev=now;
					now--;
				}
			}else{
				if(prev<=now){
					prev=now;
					now++;
				}else{
					prev=now;
					now--;
				}
			}
		}
	}
}


addEventListener("message", function(event){
	ansNum=0;
	for(i=0;i<81;i++){
		field[i]=0;
		for(k=0;k<3;k++){
			check[i][k].x=(1<<10)-2;
		}
	}
	for(i=0;i<9;i++){
		for(j=0;j<9;j++){
			ans[i][j]=0;
			if(event.data.buf[i][j]!=0){
				if(ok(i*9+j,event.data.buf[i][j])){
					put(i*9+j,event.data.buf[i][j]);
				}else{
					ansNum=0;
				    postMessage({"ans":ans,"ansNum":ansNum});
					return;
				}
			}
		}
	}
	
	var flag=true;
	while(flag){
		flag=false;
		for(k=0;k<81;k++){
			if(field[k]==0){
				var cp=canPut(k);
				for(m=1;m<=9;m++){
					if(cp==bitnum[m]){
						put(k,m);
						flag=true;
						break;
					}
				}
			}
		}
	}
	flag=true;
	for(k=0;k<81;k++){
		if(field[k]==0 && canPut(k)==0){
			flag=false;
		}
	}
	if(flag)dfs();
	
    postMessage({"ans":ans,"ansNum":ansNum});
}, false);

javaのより全然高速(javaの速いのに更新するかも)
解がない場合は全探索になりめちゃくちゃ遅くなることがあるので、それを防ぐため値を埋める→埋められないマスがないか探すをするだけで、かなり速くなる
解がある問題を解く前提ならいらん処理だけど

これ単体では実行できなくて
web workerで配列[9][9]を渡して実行する