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

스도쿠 (Sudoku Solver)

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

01 알고리즘 작동 원리 탐색

Interactive Step-by-Step
Sudoku · 4×4
1
2
3
4
3
4
1
2
4
3
2
1
2
1

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

Logic Node1 / 7

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

04 자주 묻는 질문

FAQ
스도쿠 (Sudoku Solver)란 무엇인가요?+

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

스도쿠 (Sudoku Solver)의 시간복잡도는 어떻게 되나요?+

스도쿠 (Sudoku Solver)의 시간복잡도는 O(9^(빈 칸)) 입니다. 시각화의 단계별 진행을 따라가며 왜 이런 복잡도가 나오는지 직접 확인할 수 있습니다.

스도쿠 (Sudoku Solver)은(는) 어디에 사용하나요?+

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

스도쿠 (Sudoku Solver)를 쉽게 비유하면?+

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

→ 백트래킹 전체 보기Related
🧩N-퀸 (N-Queens)
O(N!)
🧩미로 탈출 (Maze Solver)
O(4^(N·M))
Guide Progress0%