스도쿠 백트래킹

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

5
2
7
9
8
1
6
5
8
4
1
7
6
3
2
1
8
1
5
6
1
9
6
3
3
4
6
2
8
9
9
2
7
4
8

백트래킹

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

아래 과정을 반복합니다.

  1. 선택: 현재 상황에서 가능한 선택지 중 하나를 선택
  2. 탐색: 선택한 결과로 다음 단계를 진행
  3. 되돌아가기: 현재 선택이 해답으로 이어지지 않는다면 선택을 취소하고 다른 선택지를 시도

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

알고리즘의 시간 복잡도

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

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

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

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

function* solve(board: Board): Generator<Step> {

  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까지의 숫자가 겹치지 않게 한 번씩만 들어가야 합니다.
  • 모든 칸을 규칙에 맞게 채우면 퍼즐이 완성됩니다.

아래에서 각 셀에 초깃값을 입력하고, 스도쿠 백트래킹 과정을 관찰해보세요.

시도할 때는 회색 배경, 되돌아갈 때는 빨간 배경이 표시됩니다.