[BOJ] 9663 N-Queen

const readline = require('readline');

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
    prompt: 'input N from N Queen /> ',
});

rl.prompt();
rl.on('line', (input) => {
    if (input === 'exit') rl.close();

    const inputNumber = +input;

    if (isNaN(inputNumber)) {
        console.log('숫자를 입력하세요!');
        rl.prompt();
    } else {
        chessMain(inputNumber);
        rl.prompt();
    }
}).on('close', () => {
    console.log('exit');
    process.exit(0);
});

function chessMain(inputNumber) {
    console.time('queen');
    let chessMap = chessInit(inputNumber);
    let queenQueue = searchEmpties(chessMap, true);
    let possibleCaseNumber = [0];
    let possibleCases = [];
    queenQueue.forEach((queenCoord) => {
        const tempchessMap = chessInit(inputNumber);
        const [X, Y] = queenCoord;
        searchPossibles(
            tempchessMap,
            X,
            Y,
            inputNumber,
            possibleCaseNumber,
            possibleCases
        );
        // console.log('------@@@@@@-------');
        // placeQueen(chessMap, Y, X);
        // 여기서 재귀로 X, Y에 퀸을 놓은 후 N개를 놓을 수 있는 경우를 모두 탐색
    });
    // placeQueen(chessMap, 0, 0);
    // console.log(searchEmpties(chessMap));
    // console.log(chessMap);
    console.log(possibleCaseNumber);
    console.timeEnd('queen');
}

function searchPossibles(chessMap, x, y, N, possibleCaseNumber, possibleCases) {
    // 4x4 배열이라고 하고
    // input = chessMap
    // input = [0, 0], [0, 1], [0, 2], [1, 0] ...
    // [0, 0]일 때는 다음 input은 [2, 1], [3, 1] ...
    // console.log(possibleCaseNumber);
    placeQueen(chessMap, x, y);
    N -= 1;
    // console.log(chessMap);
    // console.log('-----------');
    if (N === 0) {
        if (checkExist(chessMap, possibleCases)) {
            return;
        }
        possibleCases.push(chessMap);
        possibleCaseNumber[0] = possibleCaseNumber[0] + 1;
        console.log(chessMap);
        console.log('--------------------------------');
        return;
    }
    const emptyNumber = getEmptyNumber(chessMap);
    if (emptyNumber === 0) {
        return;
    }
    const empties = searchEmpties(chessMap);
    empties.forEach((coords) => {
        const tempChessMap = JSON.parse(JSON.stringify(chessMap));
        const [X, Y] = coords;
        return searchPossibles(
            tempChessMap,
            X,
            Y,
            N,
            possibleCaseNumber,
            possibleCases
        );
    });
}

function checkExist(chessMap, possibleCases) {
    let result;
    possibleCases.forEach((eachCase) => {
        if (JSON.stringify(eachCase) === JSON.stringify(chessMap)) {
            return (result = true);
        }
    });
    return result;
}

function getEmptyNumber(chessMap) {
    const length = chessMap.length;
    let emptyNumber = 0;
    for (let i = 0; i < length; i++) {
        for (let j = 0; j < length; j++) {
            if (chessMap[i][j] === ' ') {
                emptyNumber += 1;
            }
        }
    }
    return emptyNumber;
}

function chessInit(N) {
    let chessMap = [];
    for (let i = 0; i < N; i++) {
        chessMap.push(Array(N).fill(' '));
    }
    return chessMap;
}

function placeQueen(chessMap, x, y) {
    chessMap[y][x] = 'Q';
    queenEffect(chessMap, x, y);
}

function queenEffect(chessMap, x, y) {
    // x, y 는 queen의 위치
    const N = chessMap.length;
    let effectX = x;
    let effectY = y;
    while (effectX - 1 >= 0) {
        chessMap[effectY][effectX - 1] = 'X';
        effectX -= 1;
    }
    effectX = x;
    while (effectX + 1 < N) {
        chessMap[effectY][effectX + 1] = 'X';
        effectX += 1;
    }
    effectX = x;
    while (effectY - 1 >= 0) {
        chessMap[effectY - 1][effectX] = 'X';
        effectY -= 1;
    }
    effectY = y;
    while (effectY + 1 < N) {
        chessMap[effectY + 1][effectX] = 'X';
        effectY += 1;
    }
    effectY = y;
    while (effectX - 1 >= 0 && effectY - 1 >= 0) {
        chessMap[effectY - 1][effectX - 1] = 'X';
        effectY -= 1;
        effectX -= 1;
    }
    effectX = x;
    effectY = y;
    while (effectX + 1 < N && effectY - 1 >= 0) {
        chessMap[effectY - 1][effectX + 1] = 'X';
        effectY -= 1;
        effectX += 1;
    }
    effectX = x;
    effectY = y;
    while (effectX - 1 >= 0 && effectY + 1 < N) {
        chessMap[effectY + 1][effectX - 1] = 'X';
        effectY += 1;
        effectX -= 1;
    }
    effectX = x;
    effectY = y;
    while (effectX + 1 < N && effectY + 1 < N) {
        chessMap[effectY + 1][effectX + 1] = 'X';
        effectY += 1;
        effectX += 1;
    }
    effectX = x;
    effectY = y;
}

function searchEmpties(chessMap, isInit) {
    const empties = [];
    const N = chessMap.length;
    let Delta = 0;
    let deltaX = Delta % N;
    let deltaY = Math.floor(Delta / N);
    const lastDelta = N * N - 1;
    if (isInit === true) {
        const isOdd = N % 2 === 1;
        const halfN = Math.floor(N / 2);
        const quarterLastDelta = Math.floor((N * N) / 4) - 1;
        while (Delta <= quarterLastDelta) {
            deltaX = Delta % halfN;
            deltaY = Math.floor(Delta / halfN);
            if (chessMap[deltaY][deltaX] === ' ') {
                empties.push([deltaX, deltaY]);
            }
            Delta += 1;
        }
        if (isOdd) {
            let oddX = halfN;
            let oddY = 0;
            while (oddY <= halfN) {
                empties.push([oddX, oddY++]);
            }
        }
    } else {
        while (Delta <= lastDelta) {
            deltaX = Delta % N;
            deltaY = Math.floor(Delta / N);
            if (chessMap[deltaY][deltaX] === ' ') {
                empties.push([deltaX, deltaY]);
            }
            Delta += 1;
        }
    }
    return empties;
}
function rotateMapClockwise(chessMap) {
    return rotatedChessmap;
}