각 셀에서 가능한 숫자들을 미리 계산하여 백트래킹 시 불필요한 경우의 수를 줄입니다. 이렇게 하면 검색 공간이 줄어들어 알고리즘의 효율성이 크게 향상됩니다.
가장 제약이 많은(가능한 숫자가 가장 적은) 셀부터 시도하면 빠르게 해를 찾거나, 불필요한 경로를 빠르게 제거할 수 있습니다.
하나의 숫자를 정하면 해당 숫자가 영향을 미치는 다른 셀의 후보 숫자 집합을 업데이트하여, 더 빠르게 제약 조건을 전파할 수 있습니다.
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)))