1. 미리 가능한 후보 숫자 필터링 (Forward Checking)

각 셀에서 가능한 숫자들을 미리 계산하여 백트래킹 시 불필요한 경우의 수를 줄입니다. 이렇게 하면 검색 공간이 줄어들어 알고리즘의 효율성이 크게 향상됩니다.

2. 최소 남은 값(MRV) 휴리스틱 (Minimum Remaining Values)

가장 제약이 많은(가능한 숫자가 가장 적은) 셀부터 시도하면 빠르게 해를 찾거나, 불필요한 경로를 빠르게 제거할 수 있습니다.

3. 제약 전파 (Constraint Propagation)

하나의 숫자를 정하면 해당 숫자가 영향을 미치는 다른 셀의 후보 숫자 집합을 업데이트하여, 더 빠르게 제약 조건을 전파할 수 있습니다.

개선된 코드: MRV 및 제약 전파를 적용한 백트래킹

import heapq

def is_valid(board, row, col, num):
    for i in range(9):
        if board[row][i] == num or board[i][col] == num:
            return False
        if board[row // 3 * 3 + i // 3][col // 3 * 3 + i % 3] == num:
            return False
    return True

def find_empty_location(board):
    min_count = 10  # 최소 가능한 후보 수를 저장하기 위한 초기값
    min_cell = None
    for row in range(9):
        for col in range(9):
            if board[row][col] == 0:
                count = sum(is_valid(board, row, col, num) for num in range(1, 10))
                if count < min_count:
                    min_count = count
                    min_cell = (row, col)
    return min_cell

def solve_sudoku_optimized(board):
    empty = find_empty_location(board)
    if not empty:
        return True  # 더 이상 빈 칸이 없으면 성공

    row, col = empty
    for num in range(1, 10):
        if is_valid(board, row, col, num):
            board[row][col] = num
            if solve_sudoku_optimized(board):
                return True
            board[row][col] = 0

    return False

# 스도쿠 퍼즐
puzzle = [
    [5, 3, 0, 0, 7, 0, 0, 0, 0],
    [6, 0, 0, 1, 9, 5, 0, 0, 0],
    [0, 9, 8, 0, 0, 0, 0, 6, 0],
    [8, 0, 0, 0, 6, 0, 0, 0, 3],
    [4, 0, 0, 8, 0, 3, 0, 0, 1],
    [7, 0, 0, 0, 2, 0, 0, 0, 6],
    [0, 6, 0, 0, 0, 0, 2, 8, 0],
    [0, 0, 0, 4, 1, 9, 0, 0, 5],
    [0, 0, 0, 0, 8, 0, 0, 7, 9]
]

solve_sudoku_optimized(puzzle)
puzzle

최적화

import sys

def is_valid(board, row, col, num):
    for i in range(9):
        if board[row][i] == num or board[i][col] == num:
            return False
        if board[row // 3 * 3 + i // 3][col // 3 * 3 + i % 3] == num:
            return False
    return True

def find_empty_location(board):
    for row in range(9):
        for col in range(9):
            if board[row][col] == 0:
                return row, col
    return None

def solve_sudoku(board):
    empty = find_empty_location(board)
    if not empty:
        return True  # 더 이상 빈 칸이 없으면 성공

    row, col = empty
    for num in range(1, 10):
        if is_valid(board, row, col, num):
            board[row][col] = num
            if solve_sudoku(board):
                return True
            board[row][col] = 0

    return False

puzzle = []
for _ in range(9):
    puzzle.append(list(map(int, input().strip().split())))

solve_sudoku(puzzle)

for row in puzzle:
    print(' '.join(map(str, row)))