Eight Queen Problem/nextream

8queen.html (javascript) ¶

모든 분들이 C/C++ 아니면 파이선이라, C로 할까 하다가 좀 특이하게 자바스크립트를 써봤습니다.

처음엔 2차원 배열 메모리 공간을 두고 메모리 상에 체크해 가며 루프를 돌릴까 하다가 생각을 바꿔서 재귀호출을 이용하게 되었습니다. 첫 문제에서 일단 제일 첫 퀸은 무조건 (0,0) 이라고 고정하고 재귀를 두번째 퀸부터 돌렸는데, 오히려 나중에 이 생각이 두번째 문제 풀때 딱 한글자만 바꿔서 적응이 되는 것을 가능케 한것 같습니다.

원래 첫번째 해법은, 한개만 뽑든지, 아니면 다뽑든지 둘중 하나였어야 하는데, 결론적으로는 문제를 풀긴 했지만, 어정쩡한 모습이 되버리고 말았습니다.

기본 아이디어는 한 라인씩 진행해 가면서 현재 라인 선상에서 X좌표값을 바꿔가며 위에 있는 퀸들에 의해 위협을 받는지 검사해서 안전한 경우에는 계속 다음 라인으로 진행하고, 아닌 경우에는 철수하는 것입니다. 위협여부에 대해서는 같은 세로선상이거나, 대각선인 경우는 X, Y 좌표의 합과 차가 각각 동일한 것이 있는지를 조사하는 것으로 만들었습니다.

~cpp 
<script>
var positions = [0,0,0,0,0,0,0,0];
function display() {
    for (var i=0; i<8; i++) document.write(positions[i] + " ");
    document.write("<br>");
}
function safe(line) {
    for (var i=0; i<line; i++)
        if (positions[line]==positions[i] || i+positions[i]==line+positions[line] || i-positions[i]==line-positions[line])
            return false;
    return true;
}
function check(line) {
    if (line>=8) { display(); return; }
    for (var i=0; i<8; i++) {
        positions[line] = i;
        if (safe(line)) check(line+1);
    }
}
check(1);
</script>

결과물 확인하기 좋게 display 부분을 약간 수정해봤습니다. --1002

~cpp 
<script> 
var positions = [0,0,0,0,0,0,0,0]; 

function printBefore(position) {
    for (var j=0; j<position; j++)
        document.write("X"); 
}
function printAfter(position) {
    for (var j=position+1;j<8; j++)
        document.write("X");
}

function display() { 
    for (var i=0; i<8; i++) {
        printBefore(positions[i]);
        document.write("O");
        printAfter(positions[i]);
        document.write("<br>");
    }
    document.write("<br>"); 
} 
function safe(line) { 
    for (var i=0; i<line; i++) 
        if (positions[line]==positions[i] || i+positions[i]==line+positions[line] || i-positions[i]==line-positions[line]) 
            return false; 
    return true; 
} 
function check(line) { 
    if (line>=8) { display(); return; } 
    for (var i=0; i<8; i++) { 
        positions[line] = i; 
        if (safe(line)) check(line+1); 
    } 
} 
check(1); 
</script>

EightQueenProblem