9*9 보드가 주어졌을 때 스도쿠 규칙에 따라 빈칸을 채워서, 완성된 보드를 리턴하는 함수 만들기

내가 풀지는 못했지만 이해한 코드.

백트래킹 알고리즘을 이용하였다.

1. 먼저 스도쿠 보드를 순회하면서 빈칸을 찾는다.

2. 빈칸을 찾은 즉시, 빈칸에 1-9까지 모든 숫자를 하나씩 다 넣어보면서 아래의 조건문을 모두 만족하는지 다 확인한다.

빈칸과 같은 행에 있는 숫자와 겹치지 않는 숫자
빈칸과 같은 열에 있는 숫자와 겹치치 않는 숫자
3*3 칸에 있는 숫자와 겹치치 않는 숫자

3. 조건문을 만족하는 즉시, 빈칸에 해당 숫자를 대입한다.

4. 보드가 업데이트 되었으므로, 1)의 과정으로 다시 넘어간다. (재귀)

5. 만약에, 2) 의 과정에서 조건을 만족하는 숫자가 하나도 없다면, 이전 과정에서 잘못된 후보 숫자를 넣었다는 뜻이 된다. 이 경우, 이전 과정으로 다시 돌아가서, 빈칸에 새로운 숫자를 넣어주어야 한다.

• 만약에 연속으로 잘못된 후보 숫자를 넣게 된 경우에는 처음으로 후보 숫자를 잘못 넣은 칸까지 되돌아가서 0으로 만들어 준다.

6. 위 과정을 반복하여 빈칸이 더 이상 남아 있지 않을 경우, 보드를 리턴한다.

출처

function nextEmptySpot(board) {
  // check empty spot. if none, returns [-1, -1]
  for (let i = 0; i < 9; i++) {
    for (let j = 0; j < 9; j++) {
      if (board[i][j] === 0)
        return [i, j];
    }
  }
  return [-1, -1];
}

function checkRow(board, row, value){
  // return false once value exists in that row
  for(let i = 0; i < board[row].length; i++) {
    if(board[row][i] === value) {
      return false;
    }
  }
  return true;
}

function checkColumn(board, column, value){
  // return false once value exists in that column
  for(let i = 0; i < board.length; i++) {
    if(board[i][column] === value) {
      return false;
    }
  }
  return true;
};

function checkSquare(board, row, column, value){
  const boxRow = Math.floor(row / 3) * 3;
  const boxCol = Math.floor(column / 3) * 3;

  for (let r = 0; r < 3; r++){
    for (let c = 0; c < 3; c++){
      if (board[boxRow + r][boxCol + c] === value)
        return false;
    }
  }
  return true;
};

function checkValue(board, row, column, value) {
  // return true if value can be inserted in that spot without collapsing
  if(checkRow(board, row, value) &&
      checkColumn(board, column, value) &&
      checkSquare(board, row, column, value)) {
    return true;
  }
  return false;
};

//**
function sudoku(board) {
  let emptySpot = nextEmptySpot(board);
  const [row,col] = emptySpot;

  // there is no more empty spots: base case
  if (row === -1){
    return board;
  }

  for(let num = 1; num<=9; num++){
    if (checkValue(board, row, col, num)){
      // console.log("후보숫자구하기","row",row,"col",col,"num",num)
      board[row][col] = num; 
      sudoku(board);
    }
  }
  // console.log("후보구하기실패ㅠㅠ","row",row,"col",col)
 
  if (nextEmptySpot(board)[0] !== -1){ 
		//다음 빈칸이 여전히 비었다면 현재 빈칸은 0으로 만들기
    //!!! console.log("어떨 때 여기 통과해?", "row", row, "col", col, "board[row][col]", board[row][col], "nextEspot-board", nextEmptySpot(board))
    board[row][col] = 0; 
  }
  // !!!console.log("row",row,"col",col,"board[row][col]",board[row][col])
  return board;
}

let board2 = [
  [0, 3, 0, 2, 6, 0, 7, 0, 1],
  [6, 8, 0, 0, 7, 0, 0, 9, 0],
  [1, 9, 0, 0, 0, 4, 5, 0, 0],
  [8, 2, 0, 1, 0, 0, 0, 4, 0],
  [0, 0, 4, 6, 0, 2, 9, 0, 0],
  [0, 5, 0, 0, 0, 3, 0, 2, 8],
  [0, 0, 9, 3, 0, 0, 0, 7, 4],
  [0, 4, 0, 0, 5, 0, 0, 3, 6],
  [7, 0, 3, 0, 1, 8, 0, 0, 0],
];

sudoku(board2);

이해가 잘 안되었던 부분

(1) if (nextEmptySpot(board)[0] !== -1) 와 같이 조건문을 쓴 이유

(board[row][col] === 0 으로 쓰면 안되는 이유 / if 문을 제거하면 안되는 이유 )?