Skip to content

Instantly share code, notes, and snippets.

@sinri
Created March 21, 2018 14:33
Show Gist options
  • Save sinri/d3a3b49174541171b8f9e8b55b2bac4f to your computer and use it in GitHub Desktop.
Save sinri/d3a3b49174541171b8f9e8b55b2bac4f to your computer and use it in GitHub Desktop.
Eight Queen Problem
let answerIndex=0;
let board=[];
for(let i=0;i<64;i++)board[i]=false;
findNextState(board,1,-1);
function findNextState(board,order,last){
//console.log("find Next State for board with order ",order," since index ",last);
//printBoard(board);
for(let i=last+1;i<64;i++){
if(i%8==0 && i-last>8){
//console.log("No hope, stop here, i as "+i);
return;
}
if(checkCellSafe(board,i)){
//console.log("Found a cell safe as ",i);
let b1=JSON.parse(JSON.stringify(board));
b1[i]=true;
findNextState(b1,order+1,i);
}
}
if(order>8){
answerIndex++;
console.log("Finally order as "+order+" (Answer No."+answerIndex+")");
printBoard(board);
return;
}
}
function checkCellSafe(board,index){
/*
same row: index/8==i/8
same column: index%8==i%8
same \: abs(x-i)%9==0
same /: abs(x-i)%7==0
0 1 2 3 4 5 6 7
8 9 10 11 12 13 14 15
16 17 18 19 20 21 22 23
24 25 26 27 28 29 30 31
32 33 34 35 36 37 38 39
however, for 22, 22+7x would be normal, but 22-7x would be strange.
see,
Not 8 --- %8=0
15 --- %8=7 above, mod should not smaller then 6
22 --- %8=6 ------
29 --- %8=5 below, mod should not greater than 6
and for 25,
7 --- %8=7
16 --- %8=0 above, mod should not greater than 1
25 --- %8=1 ----
34 --- %8=2 below, mod should not smaller than 1
*/
let note='';
let result=true;
if(board[index]){
note='X Q';
result=false;
}
else for(let i=0;i<64;i++){
if(!board[i])continue;
if(Math.floor(index/8)%8==Math.floor(i/8)%8){
note='X Row '+i;
result=false;
break;
}
if(Math.floor(index%8)==Math.floor(i%8)){
note='X Col '+i;
result=false;
break;
}
if(Math.abs(index-i)%9==0){
if(
(i<index && (i%8)<(index%8))
|| (i>index && (i%8)>(index%8))
){
note='X \\ '+i;
result=false;
break;
}
}
if(Math.abs(index-i)%7==0){
if(
(i<index && (i%8)>(index%8))
|| (i>index && (i%8)<(index%8))
){
note='X // '+i;
result=false;
break;
}
}
}
//console.log('check cell safe',index,' of board --> '+(result?'SAFE':'FATAL')+ " reason: "+note);
return result;
}
function printBoard(board){
/*
console.log("--------");
for(let i=0;i<8;i++){
let s='';
for(let j=0;j<8;j++)s+=(board[i*8+j]?'Q':'X');
console.log(s);
}
console.log("========");
*/
let s='';
for (let i=0;i<64;i++)if(board[i])s+=" "+i;
console.log("# "+s);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment