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

스도쿠 (Sudoku Solver)

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

01 Explore How It Works

Interactive Step-by-Step

HOVER OR SCROLL

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 Understand It Simply

For Everyone

🔑Analogy

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

💡In Plain Words

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

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

📍Where It's Used

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

03 Python Implementation

A clean, readable reference implementation of the core logic of 스도쿠 (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

04 Frequently Asked Questions

FAQ

What is 스도쿠 (Sudoku Solver)?+

What is the time complexity of 스도쿠 (Sudoku Solver)?+

The time complexity of 스도쿠 (Sudoku Solver) is O(9^(빈 칸)). Follow the step-by-step visualization to see exactly why.

Where is 스도쿠 (Sudoku Solver) used?+

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

What's a simple analogy for 스도쿠 (Sudoku Solver)?+

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

→ Backtracking — see allRelated

Guide Progress0%