N-Queen

.js

// n-queens

function getNQueens (n) {
    let workQueue = [];
    let solutions = [];

    for (let col = 0; col < n; col++) {
        workQueue.push([col]);
    }
    
    let board = [];
    while (workQueue.length > 0) {
        board = workQueue.shift();
        
        if (board.length === n) {
            solutions.push(board);
        } else {
            workQueue = workQueue.concat(nextValidMoves(board, n));
        }
    }
    

    for (let sol of solutions) {
        prettyPrint(sol, n);
    }

    console.log(solutions.length);
}

// an [[0,2], [0,3], ..., [0, 7]]
function nextValidMoves(board, n) {
    let moves = [];
    let nextMove = [];
    for (let col = 0; col < n; col++) {
        nextMove = [...board, col];
        if (isValid(nextMove)) {
            moves.push(nextMove);
        }
    }

    return moves;
}

function isValid(board) {

    // filter queen on same column (index of array === value at index)
    // diagonal? walk the diagonal and check 
    // [0, 2, 1]
    // Q _ _ _ 
    // _ _ Q _
    // _ Q _ _
    // 
    let lastIdx = board.length - 1;
    if (board.slice(0, board.length - 1).includes(board[lastIdx])) {
        return false;
    }

    
    for (let idx = 0; idx < lastIdx; idx++) {
        if (Math.abs(board[idx] - board[lastIdx]) === lastIdx - idx) {
            return false;
        }
    }

    return true;
}

function prettyPrint(arr, n) {

    let board = '';
    let rowStr = '';

    for (let row = 0; row < n; row++) {

        let col = arr[row];
        rowStr = '';

        for (let i = 0; i < n; i++) {

            if (i === col) {
                rowStr += ' Q ';
            } else {
                rowStr += ' _ ';
            }

            
        }
        board += rowStr + '\n';
    }

    console.log(board);
}