Sudoku Solver

Q: 백트래킹 스도쿠 풀이기의 시간 복잡도는 얼마인가요?

최악의 경우 지수 시간인 O(9^m) 이며, 빈 칸이 m 개일 때 각 칸에서 최대 9개의 숫자로 분기할 수 있습니다. 실제 퍼즐에서는 행, 열, 박스 규칙이 대부분의 분기를 줄여 주고, 가장 비어 있는 칸을 먼저 채우면 나머지 대부분도 줄어듭니다.

어려움백트래킹

+10

스도쿠 보드는 아홉 개의 3 × 3 상자로 나뉜 9 × 9 격자입니다. 풀린 보드에서는 각 행, 각 열, 각 상자에 1부터 9까지의 숫자가 각각 정확히 한 번씩 들어 있습니다.

퍼즐은 문자열 9개로 주어지며, 위쪽 행부터 행마다 하나씩 배치됩니다. .은 빈 칸입니다. 모든 빈 칸을 채우고 같은 형식으로 풀이된 보드를 반환하세요. 보드의 해답은 정확히 하나입니다.

함수

solveSudoku(board: string-array) → string-array

boardstring-array: 퍼즐의 9개 행, 빈 셀마다 점 하나
반환값string-array: 해결된 보드의 9개 행

제약 조건

board에는 길이가 9인 문자열 9개가 들어 있습니다.
모든 문자는 .이거나 1부터 9까지의 숫자 중 하나입니다.
주어진 숫자는 한 행, 한 열 또는 한 박스 안에서 반복되지 않습니다.
보드에는 해답이 정확히 하나 있습니다.

예제

입력: board = ["9.7.....6", "824.3....", "..1..9..2", ".9...2.18", "...4....5", "1325.8...", "...687...", "......8.9", ".4.9...5."]
출력: ["957214386", "824736591", "361859742", "495372618", "786491235", "132568974", "519687423", "273145869", "648923157"]
설명: 맨 윗줄 9.7.....6에는 이미 9, 7, 6이 있으므로 빈칸 여섯 개에는 1, 2, 3, 4, 5, 8이 들어갑니다. 각 숫자가 어디에 들어갈지는 열과 박스에 따라 결정되며, 행은 957214386이 됩니다.

후속 질문

킬러 스도쿠에서는 셀의 케이지에 있는 숫자의 합도 지정된 값이 되어야 합니다. 이 규칙을 탐색에 어떻게 추가하고, 이를 이용해 가지치기를 조기에 수행할 수 있을까요?

풀이

백트래킹으로 풀어 보세요. 조건에 맞는 숫자를 놓고 계속 진행하다가, 보드를 완성할 수 없으면 그 숫자를 되돌립니다. 셀을 어떤 순서로 채우느냐에 따라 속도가 달라집니다. 어려운 보드에서는 읽는 순서대로 진행하면 부분적으로 채워진 보드를 수억 개나 확인할 수 있지만, 선택지가 가장 적은 셀을 먼저 채우면 약 백 개만 확인하면 됩니다.

읽기 순서에서의 백트래킹

정답이지만 가장 큰 테스트에서는 끝나지 않음

핵심 아이디어

빈 셀을 읽는 순서대로 채우되, 각 셀에는 들어갈 수 있는 가장 작은 숫자를 넣습니다. 어떤 셀에 남은 숫자가 없으면 이전 셀로 돌아가 다음 숫자를 시도합니다. 규칙을 만족하는 모든 조합을 차례로 시도하므로 탐색을 통해 해를 찾습니다.

세 개의 테이블을 사용하면 각 적합성 검사를 O(1)에 수행할 수 있습니다. rowUsed[r][d], colUsed[c][d], boxUsed[b][d]이며, 박스는 b = (r / 3) * 3 + c / 3입니다. 숫자를 놓으면 세 항목을 설정하고, 숫자를 제거하면 해당 항목을 지웁니다.

고정된 순서가 약점입니다. 탐색은 행 전체를 해당 위치에 들어가는 숫자로 채운 다음, 나중에 많은 셀이 더 이상 놓을 자리가 없게 만든다는 사실을 알게 될 수 있습니다. 맨 위쪽 행에 단서가 거의 없고 해답이 큰 숫자인 보드는 3억 개가 넘는 부분 보드를 탐색하게 합니다.

알고리즘

보드를 빈 셀은 0으로 표시하여 그리드에 읽어 들이고, rowUsed, colUsed, boxUsed를 채운 다음 빈 셀을 읽는 순서대로 나열합니다.
backtrack(k): k가 빈 셀의 개수와 같으면 true를 반환합니다.
셀 k의 행, 열, 박스에서 사용되지 않은 1부터 9까지의 각 숫자 d에 대해 숫자를 넣고 표시한 다음, backtrack(k+1)이 true를 반환하면 true를 반환합니다. 그렇지 않으면 표시를 해제합니다.
어떤 숫자도 들어갈 수 없으면 셀을 비우고 false를 반환합니다. backtrack(0)을 호출하고 그리드를 다시 문자열로 변환합니다.

def solveSudoku(board):
    grid = [[0 if ch == "." else int(ch) for ch in row] for row in board]
    # row_used[r][d] is True when digit d already sits in row r; same for
    # columns and boxes. Box b holds the cells with (r // 3) * 3 + c // 3 == b.
    row_used = [[False] * 10 for _ in range(9)]
    col_used = [[False] * 10 for _ in range(9)]
    box_used = [[False] * 10 for _ in range(9)]
    empties = []
    for r in range(9):
        for c in range(9):
            d = grid[r][c]
            if d:
                row_used[r][d] = col_used[c][d] = box_used[(r // 3) * 3 + c // 3][d] = True
            else:
                empties.append((r, c))

    def backtrack(k):
        if k == len(empties):
            return True
        r, c = empties[k]
        b = (r // 3) * 3 + c // 3
        for d in range(1, 10):
            if not row_used[r][d] and not col_used[c][d] and not box_used[b][d]:
                grid[r][c] = d
                row_used[r][d] = col_used[c][d] = box_used[b][d] = True
                if backtrack(k + 1):
                    return True
                row_used[r][d] = col_used[c][d] = box_used[b][d] = False
        grid[r][c] = 0
        return False

    backtrack(0)
    return ["".join(str(d) for d in row) for row in grid]

가장 비어 있는 셀을 먼저 채우세요

핵심 아이디어

해결 방법은 채우는 순서에 따라 달라지지 않으므로, 탐색 범위를 가장 작게 유지하는 순서를 선택하세요. 매 단계에서 허용되는 숫자가 가장 적은 빈칸을 채웁니다. 허용되는 숫자가 하나뿐인 칸은 강제로 정해지므로 분기가 추가되지 않습니다. 허용되는 숫자가 하나도 없는 칸은 즉시 선택하므로 잘못된 보드를 바로 찾아낼 수 있습니다.

단계마다 81개의 칸에서 허용되는 숫자를 효율적으로 세려면 각 행, 열, 박스를 비트마스크로 저장합니다. rows[r]의 비트 d는 숫자 d가 행 r에 있을 때 설정됩니다. 한 칸에 허용되는 숫자는 ~(rows[r] | cols[c] | boxes[b]) & 0x3FE이며, 여기서 0x3FE는 1부터 9까지의 비트를 유지하고, 개수는 설정된 비트의 수입니다. d를 배치하면 세 마스크에서 비트 d가 설정됩니다. 배타적 논리합을 사용하면 해당 비트를 제거할 수 있습니다.

알고리즘

주어진 숫자로 격자와 마스크 rows, cols, boxes를 구성합니다.
backtrack(): 모든 셀을 살펴보고, 각 빈 셀에 허용되는 숫자를 계산한 다음, 허용되는 숫자의 개수가 가장 적은 첫 번째 셀을 선택합니다. 빈 셀이 없으면 true를 반환합니다.
해당 셀에 허용되는 각 숫자를 배치하고, 세 마스크에서 해당 비트를 설정한 다음, backtrack()이 true를 반환하면 true를 반환하고, 그렇지 않으면 비트를 지웁니다.
어떤 숫자도 맞지 않으면 셀을 비우고 false를 반환합니다. backtrack()을 호출하고 격자를 다시 문자열로 변환합니다.

def solveSudoku(board):
    grid = [[0 if ch == "." else int(ch) for ch in row] for row in board]
    # Bit d of rows[r] is set when digit d already sits in row r; same for
    # columns and boxes. Box b holds the cells with (r // 3) * 3 + c // 3 == b.
    rows, cols, boxes = [0] * 9, [0] * 9, [0] * 9
    for r in range(9):
        for c in range(9):
            d = grid[r][c]
            if d:
                rows[r] |= 1 << d
                cols[c] |= 1 << d
                boxes[(r // 3) * 3 + c // 3] |= 1 << d

    def backtrack():
        # Pick the empty cell with the fewest digits left (the first one on a tie).
        best_r, best_c, best_allowed, best_count = -1, -1, 0, 10
        for r in range(9):
            for c in range(9):
                if grid[r][c] == 0:
                    # Bits 1 to 9 of 0x3FE are the nine digits.
                    allowed = ~(rows[r] | cols[c] | boxes[(r // 3) * 3 + c // 3]) & 0x3FE
                    count = bin(allowed).count("1")
                    if count < best_count:
                        best_r, best_c, best_allowed, best_count = r, c, allowed, count
        if best_r == -1:
            return True  # no empty cell is left: the board is solved
        r, c = best_r, best_c
        b = (r // 3) * 3 + c // 3
        for d in range(1, 10):
            bit = 1 << d
            if best_allowed & bit:
                grid[r][c] = d
                rows[r] |= bit
                cols[c] |= bit
                boxes[b] |= bit
                if backtrack():
                    return True
                rows[r] ^= bit
                cols[c] ^= bit
                boxes[b] ^= bit
        grid[r][c] = 0
        return False

    backtrack()
    return ["".join(str(d) for d in row) for row in grid]

함정과 경계 사례

숫자를 되돌릴 때 행, 열, 박스 기록에서 해당 숫자를 지우지 않는 경우. 이후의 칸에서는 그 숫자가 이미 사용된 것으로 간주되어 탐색이 해답을 찾지 못합니다.
박스 인덱스를 구할 때 r / 3 + c / 3을 사용하는 경우. (0, 4)와 (4, 0)은 모두 1에 해당하므로 두 박스가 하나의 기록을 공유하고, 보드를 채울 수 없게 됩니다. 정수 나눗셈을 사용해 (r / 3) * 3 + c / 3을 사용하세요.
첫 번째 해답을 찾았을 때 멈추지 않는 경우. 그러면 해답을 읽기 전에 되돌리기 단계에서 보드가 다시 비워집니다.

자주 묻는 질문3

백트래킹 스도쿠 풀이기의 시간 복잡도는 얼마인가요?

최악의 경우 지수 시간인 O(9^m)이며, 빈 칸이 m개일 때 각 칸에서 최대 9개의 숫자로 분기할 수 있습니다. 실제 퍼즐에서는 행, 열, 박스 규칙이 대부분의 분기를 줄여 주고, 가장 비어 있는 칸을 먼저 채우면 나머지 대부분도 줄어듭니다.

스도쿠에 해답이 정확히 하나만 있는지 어떻게 확인하나요?

같은 백트래킹 탐색을 실행하되, 해의 개수를 세고 그 개수가 2에 도달하면 중단하세요. 개수가 1이면 퍼즐의 해가 하나뿐이고, 0이면 해가 없다는 뜻입니다. 퍼즐 생성기는 각 단서를 제거한 후 이 검사를 실행합니다.

백트래킹보다 스도쿠를 더 빠르게 푸는 방법이 있나요?

대부분의 빠른 풀이 방법도 여전히 되돌아가며 탐색하지만, 추측을 하기 전에 더 많은 것을 추론합니다. 제약 조건 전파는 선택지가 하나뿐인 모든 칸과 해당 행, 열 또는 박스에서 들어갈 수 있는 칸이 하나뿐인 모든 숫자를 채운 다음, 이를 반복합니다. 스도쿠는 정확 덮기 문제로도 표현할 수 있으며 Knuth의 알고리즘 X로 풀 수 있습니다.

def solveSudoku(board):
    # 여기에 코드를 작성하세요

테스트 #1

인자

board = ["9.7.....6", "824.3....", "..1..9..2", ".9...2.18", "...4....5", "1325.8...", "...687...", "......8.9", ".4.9...5."]

예상 출력

["957214386", "824736591", "361859742", "495372618", "786491235", "132568974", "519687423", "273145869", "648923157"]