[BOJ]2580 스토쿠

문제 링크

https://www.acmicpc.net/problem/2580

핵심 아이디어

• Brute Force방식으로 생각 할 시 $9^{81}$임으로 백 트레킹 방식으로 고려

• 현재 넣으려고 하는 수를 3가지 조건관점에서 넣을 수 있는지 고려(수평, 수직, 정사각형)

• 처음 게임판에서 비어있는 좌표(0)인 부분들만 고려하고 2가지 조건 검색에서 for문으로 돌면서 만족하지 않으면 불필요한 연산은 필요없게 break문을 걸어 연산 최소화

소스코드

import sys

input = sys.stdin.readline


def solve(idx):
    # 정답의 도출
    if idx == len(zero):
        for b in board:
            b = list(map(str, b))
            print(" ".join(b))
        sys.exit(0)

    # 조사 점을 가져옴
    r, c = zero[idx]

    # 값이 채워져 있지 않은 경우
    for n in range(1, 10):

        is_valid = True

        # 유효 수 조사
        for i in range(9):
            if board[r][i] == n:
                is_valid = False
                break
            if board[i][c] == n:
                is_valid = False
                break

        for i in range(3):
            for j in range(3):
                if board[r // 3 * 3 + i][c // 3 * 3 + j] == n:
                    is_valid = False
                    break
            if not is_valid:
                break

        if not is_valid:
            continue

        board[r][c] = n
        solve(idx + 1)
        board[r][c] = 0


global zero
global board

if __name__ == '__main__':
    zero = []
    board = [list(map(int, input().split())) for _ in range(9)]

    for r in range(9):
        for c in range(9):
            if board[r][c] == 0:
                zero.append((r, c))

    solve(0)