[algorithm] 수도쿠 Sudoku 풀이 알고리즘

문제: 2차원 배열 형태의 수도쿠 문제를 입력 받아 풀이를 리턴하는 함수 작성.
0인 위치는 채워야할 빈칸이다.

예시:

let board = [
  [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],
];
let output = sudoku(board);
console.log(output); // -->
/* 
[
  [4, 3, 5, 2, 6, 9, 7, 8, 1],
  [6, 8, 2, 5, 7, 1, 4, 9, 3],
  [1, 9, 7, 8, 3, 4, 5, 6, 2],
  [8, 2, 6, 1, 9, 5, 3, 4, 7],
  [3, 7, 4, 6, 8, 2, 9, 1, 5],
  [9, 5, 1, 7, 4, 3, 6, 2, 8],
  [5, 1, 9, 3, 2, 6, 8, 7, 4],
  [2, 4, 8, 9, 5, 7, 1, 3, 6],
  [7, 6, 3, 4, 1, 8, 2, 5, 9],
];
 */

풀이전략

1. DFS로 접근한다
2. DFS 구현 중 recursive(재귀)를 이용했다. (iterative 방식은 차후 작성 예정)
3. DFS을 제외한 기본 로직으로는 특정 빈칸에 들어갈 숫자의 후보를 가로, 세로, 3x3박스 을 살펴서 판정한다는 것

구현코드

function makeExpectedNumbers(arr, rowIndex, columnIndex) {
  let inColumnExpectedList = [];
  let inRowExpectedList = [];
  let inSquareExpectedList = [];

  // 세로 줄에서 후보 숫자 목록 만들기
  for (let digit = 1; digit < 10; digit++) {
    let row = arr[rowIndex];
    if (!row.includes(digit)) {
      inRowExpectedList = [...inRowExpectedList, digit];
    }
  }

  // 가로 줄에서 후보 숫자 목록 만들기
  for (let digit = 1; digit < 10; digit++) {
    // colmun 정하기
    let column = arr.reduce((accum, curr) => [...accum, curr[columnIndex]], []);
    // 후보 숫자 목록 만들기
    if (!column.includes(digit)) {
      inColumnExpectedList = [...inColumnExpectedList, digit];
    }
  }

  // 3 x 3 박스에서 후보 숫자 목록 만들기
  for (let digit = 1; digit < 10; digit++) {
    // 3 x 3 박스 범위 정하기
    let square = [];
    let rowStartIndex = rowIndex - rowIndex % 3;
    let columnStartIndex = columnIndex - columnIndex % 3;
    for (let i = rowStartIndex; i < rowStartIndex + 3; i++) {
      for (let j = columnStartIndex; j < columnStartIndex + 3; j++) {
        square = [...square, arr[i][j]];
      }
    }
    // 후보 숫자 목록 만들기
    if (!square.includes(digit)) {
      inSquareExpectedList = [...inSquareExpectedList, digit];
    }
  }

  let expectedList = [];
  for (let i of inRowExpectedList) {
    if (inColumnExpectedList.includes(i) && inSquareExpectedList.includes(i)) {
      expectedList = [...expectedList, i];
    }
  }
  return expectedList;
}

function findEmptyPoint(arr) {
  for (let i = 0; i < 9; i++) {
    for (let j = 0; j < 9; j++) {
      if (arr[i][j] === 0) {
        return [i, j];
      }
    }
  }
}

function sudoku(board) {
  if (sudokuSolve(board)) {
    return board;
  }
  function sudokuSolve(board) { // 여기가 재귀함수
    let emptyPoint = findEmptyPoint(board); // 빈 자리 하나 찾는다. 
    if (emptyPoint === undefined) { // 빈자리가 없다면 끝났다는 것을 의미 -> 종료
      return true;
    }
    let expectedNumbers = makeExpectedNumbers(board, emptyPoint[0], emptyPoint[1]); // 빈 자리에 들어갈 후보들을 담은 배열
    for (let expectedNumber of expectedNumbers) {
      board[emptyPoint[0]][emptyPoint[1]] = expectedNumber; // 후보 숫자들을 하나씩 넣으면서 DFS 돌릴 거다
      if (sudokuSolve(board) === true) { // 개인적으로 
        return true;                     // 여기 if문이
      }                                     // 핵심이라고 생각한다.
    }
    board[emptyPoint[0]][emptyPoint[1]] = 0; // 빈칸에 들어간 후보자가 없을 경우 한 스탭 뒤로 간다.
    return false;
  }
}

중요 포인트

if(재귀호출 === true) { return true }
이렇게 재귀를 호출하는 부분이 if문 안에 들어있는 형식에 익숙해져야 한다.
물론 if문 안에 들어갈 수 있어야 하므로 전제적인 리턴 값은 Boolean값이다.
그래서 마지막에 return false 한 부분도 중요하다.