Algorithm Guidecomplexity: O(9^(빈 칸))

스도쿠 (Sudoku Solver)

9×9 격자에 행·열·3×3 박스마다 1~9가 한 번씩만 오도록 채우는 퍼즐입니다. 빈 칸에 가능한 숫자를 하나씩 시도하고, 모순이 생기면 0으로 되돌려 다른 숫자를 시도하는 백트래킹입니다.

01 알고리즘 작동 원리 탐색

Interactive Step-by-Step

TAP OR HOVER

Sudoku · 4×4

4×4 미니 스도쿠. 각 행·열·2×2 박스에 1~4가 한 번씩 와야 합니다. 빈 두 칸을 채웁니다.

Logic Node1 / 7

Live Python

1def solve(board):

2 cell = find_empty(board)

3 if not cell:

4 return True # 모두 채움

5 r, c = cell

6 for num in range(1, 5): # 4×4라 1~4

7 if is_valid(board, r, c, num):

8 board[r][c] = num

9 if solve(board):

10 return True

11 board[r][c] = 0 # 백트래킹

12 return False

02 쉽게 이해하기

For Everyone

🔑비유

빈칸에 연필로 숫자를 적어보고, 모순이 생기면 지우고 다시 적는 것과 같습니다.

💡쉽게 말하면

빈 칸에 가능한 숫자를 하나씩 넣어보고, 행·열·박스 규칙에 어긋나면 지우고 다음 숫자를 시도합니다.

모두 막히면 이전 칸으로 되돌아가요.

📍어디에 쓰나

–제약 충족 퍼즐
–시간표 짜기
–배치 문제

03 파이썬 구현 코드

스도쿠 (Sudoku Solver)의 핵심 로직을 담은 표준 구현 예시입니다. 가급적 간결하고 읽기 쉬운 코드로 작성되었습니다.

core_implementation.py

def solve_sudoku(board):
    empty = find_empty(board)
    if not empty:
        return True
    r, c = empty
    for num in range(1, 10):
        if is_valid(board, r, c, num):
            board[r][c] = num
            if solve_sudoku(board):
                return True
            board[r][c] = 0      # 백트래킹
    return False

Guide Progress0%