Created
March 21, 2018 14:33
-
-
Save sinri/d3a3b49174541171b8f9e8b55b2bac4f to your computer and use it in GitHub Desktop.
Eight Queen Problem
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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