선택, 탐색, 되돌아가기

제네레이터를 이용해서 스도쿠 백트래킹 과정을 시각화해 봤다.

백트래킹

백트래킹(Backtracking)은 문제 해결 과정에서 막다른 길에 도달했을 때 이전 단계로 돌아가서 다른 선택지를 시도하는 알고리즘이다.

예를 들어, 어떤 퍼즐의 특정 위치에 숫자를 넣었는데 그 숫자가 규칙을 위반한다면 이후 모든 탐색은 무의미해지므로 더 이상 진행하지 않고 이전 단계로 되돌아가서 다른 선택을 시도하게 된다.

알고리즘의 시간 복잡도

스도쿠 백트래킹은 최악의 경우 시간 복잡도는 O(9^(n^2))이다. 여기서 n은 보드의 크기다. 81개의 빈칸이 있다면 각 칸에 9개의 숫자를 시도할 수 있으므로 이론적으로는 9^81가지 경우의 수가 있다.

하지만 실제로는 제약 조건 때문에 대부분은 조기에 제거되어 훨씬 빠르게 동작한다.

제네레이터를 이용한 시각화

재귀 함수로 백트래킹을 구현하면 과정을 중간에 멈추거나 단계별로 보여주기 어렵다. 하지만 제네레이터를 사용하면 각 단계를 yield로 반환하여 실행을 일시 정지하고, 필요할 때마다 다음 단계를 진행할 수 있다.

function* solve(board: Board): Generator<Step, boolean> {
  const emptyCell = findEmptyCell(board);
  if (!emptyCell) {
    yield { board, row: -1, col: -1, status: 'done' };

    return true;
  }

  const [row, col] = emptyCell;

  for (let value = 1; value <= 9; value++) {
    if (!isPlacementValid(board, row, col, value)) continue;

    const newBoard = cloneBoard(board);
    newBoard[row][col] = value;

    yield { board: newBoard, row, col, status: 'try' };

    const solved = yield* solve(newBoard);
    if (solved) return true;

    yield { board: newBoard, row, col, status: 'backtrack' };
  }

  return false;
}

직접 해보기

스도쿠 규칙

• 9x9 격자판에 1부터 9까지의 숫자를 채워 넣는 퍼즐이다.
• 각 가로줄에는 1부터 9까지의 숫자가 겹치지 않게 한 번씩만 들어가야 한다.
• 각 세로줄에도 1부터 9까지의 숫자가 겹치지 않게 한 번씩만 들어가야 한다.
• 각 3x3 블록에도 1부터 9까지의 숫자가 겹치지 않게 한 번씩만 들어가야 한다.
• 모든 칸을 규칙에 맞게 채우면 퍼즐이 완성된다.