Portfolio


const makeQueenMap = (n, cols) => {
	// 2차원 배열을 만든다.
  const arr = Array.from({length: n}, () => new Array(n).fill('.'));
	
	// Queen을 놓아준다.
  cols.forEach((y, x) => {
    arr[x][y] = 'Q';
  })
	// 조건에 맞게 1차원 배열로 변환시켜준다.
  return arr.map(innerArr => innerArr.join(''));
}

// 조건은 다음과 같다.
const check = (cols) => {
	// 배열의 길이다. (즉, 현재까지 처리된 행 수를 의미할 것이다)
  const arrLength = cols.length;
	// 만약 배열의 길이가 2보다 작으면, 결과적으로 비교할 queen이 없다는 거다. true.
  if (arrLength < 2) return true;
	// cols는 얕은 복사를 해준다. 그래야 영향을 미치지 않는다. (called by ref)
  const nowCols = [...cols];
	// 마지막 행을 비교하기 위해 이렇게 빼준다.
  const lastCol = nowCols.pop(); 
	// 이전의 행들의 퀸이 움직일 수 있는 값에 포함되지 않는지를 체크한다.
  return nowCols.every((nowCol, idx) =>
		// 같은 열이 아닐 때
		// 그리고 행 값 차이 = 열 값 차이가 아닐 때 (대각선 특징) 
    nowCol !== lastCol 
    && Math.abs(nowCol - lastCol) !== Math.abs(arrLength - 1 - idx)
  );
}

// n: 문제에서 설정된 값
// cols: 현재 사용된 열들을 행의 인덱스에 매칭되어 값을 설정
// res: 결과 값을 담은 배열
const backTracking = (n, cols, res) => {
	// 가지치기 -> 만약 현재 조건을 만족하지 못한다면 `res`를 반환한다.
  if (!check(cols)) return res;
	// 조건은 이제 통과. 만약 끝까지 다 갔고, 퀸을 있는 만큼 채웠다면,
	// `res에 `makeQueenMap`으로 만든 맵을 넣어 반환한다.
  if (cols.length === n) return [...res, makeQueenMap(n, cols)];

	// 아직 다 못 채웠다면 여기서 for문을 돌린다. 이때, 다시 재귀를 시키는데,
	// for문을 돌렸기 때문에 일단 '어느 행에 놓을 것인지'에 대한 문제는 해결했다. 
  // 다음 퀸의 열 값을 찾는 문제로 집중하자.
	// 따라서 현재 열 값을 `cols`에 넣어 재귀함수를 호출한다.
  for (let i = 0; i < n; i += 1) {
    res = backTracking(n, [...cols, i], res);
  }
	
	// 호출된 backTracking의 res값을 리턴해준다.
  return res;
}

const solveNQueens = n => backTracking(n, [], []);

//84ms


const solveNQueens = (n) => {
    const answer = [];
    let board = Array.from({length: n}, () => Array(n).fill("."));
    
    const isPossible = (x, y) => {
        //up
        for(let i = x - 1; i >= 0; i--){
            if(board[i][y] === "Q"){
                return false;
            }
        }
        
        //down
        for(let i = x + 1; i < n; i++){
            if(board[i][y] === "Q"){
                return false;
            }
        }
        
        //left
        for(let i = y - 1; i >= 0; i--){
            if(board[x][i] === "Q"){
                return false;
            }
        }
        
        //right
        for(let i = y + 1; i < n; i++){
            if(board[x][i] === "Q"){
                return false;
            }
        }
        
        //upper left
        for(let i = x - 1, j = y - 1; i >= 0 && j >= 0; i--, j--){
            if(board[i][j] === "Q"){
                return false;
            }
        }
        
        //upper right
        for(let i = x - 1, j = y + 1; i >= 0 && j < n; i--, j++){
            if(board[i][j] === "Q"){
                return false;
            }
        }
        
        //lower left
        for(let i = x + 1, j = y - 1; i < n && j >= 0; i++, j--){
            if(board[i][j] === "Q"){
                return false;
            }
        }
        
        //lower right
        for(let i = x + 1, j = y + 1; i < n && j < n; i++, j++){
            if(board[i][j] === "Q"){
                return false;
            }
        }
        
        return true;
    }
    
    const dfs = (x, queen) => {
        if(!queen){
            answer.push(board.slice().map(b => b.join("")));
            return;
        }
        
        for(let j = 0; j < n; j++){
            if(isPossible(x, j)){
                board[x][j] = "Q";
                dfs(x + 1, queen - 1);
                board[x][j] = ".";
            }
        }
    };
    
    dfs(0, n);
    
    return answer;
};


var solveNQueens = function(n) {
    const answer = [];
    const arr = new Array(n);
    
    const getQueen = (depth, queens) => {
        if (depth === n) {
            answer.push(queens);
            return;
        }

        for (let i = 0; i < n; i++) {
            arr[depth] = i;

            if (isPossible(depth)) {
                let queen = '';
                for (let j = 0; j < n; j++) {
                    queen += i === j ? 'Q' : '.';
                }
                getQueen(depth + 1, [...queens, queen]);
            }
        }
    }

    const isPossible = (depth) => {
        for (let i = 0; i < depth; i++) {
            if (arr[depth] === arr[i]
               || Math.abs(depth - i) === Math.abs(arr[depth] - arr[i])) {
                return false;
            } 
        }
        return true;
    }
    
    getQueen(0, []);

    return answer;
};