[백준 2239] 스토쿠 - 파이썬(Python)

 

 

문제

---

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

2239번: 스도쿠

 

나의 풀이

---

백트래킹을 사용해서 탐색을 해주면 된다. 검사할 항목은 가로, 세로, 3x3 사각형 안에 사용된 숫자들이 무엇인지이다. 이를 c1, c2, c3에 기록해두고 겹치지 않는 숫자 candidate들을 하나씩 넣어보면서 조건에 위배되는지를 살펴보고 위배된다면 백트래킹으로 다시 값들을 복구하고 다음 후보 숫자를 넣어 탐색하면 된다.

 

코드

---

# https://www.acmicpc.net/problem/2239

def cal(x,y):
    return (x//3)*3 + (y//3)

def sol(n):
    if n == 81:
        for a in A:
            print(''.join(list(map(str, a))))
        return True
    x = n // 9
    y = n % 9
    if A[x][y]:
        return sol(n+1)
    else:
        for i in range(1,10):
            if not c1[x][i] and not c2[y][i] and not c3[cal(x,y)][i]:
                c1[x][i] = c2[y][i] = c3[cal(x,y)][i] = True
                A[x][y] = i
                if sol(n+1):
                    return True
                c1[x][i] = c2[y][i] = c3[cal(x,y)][i] = False
                A[x][y] = 0
    
    return False

A = [list(map(int, input())) for _ in range(9)]
c1 = [[False]*10 for _ in range(9)] # row
c2 = [[False]*10 for _ in range(9)] # col
c3 = [[False]*10 for _ in range(9)] # 3x3 square
for i in range(9):
    for j in range(9):
        if A[i][j]:
            c1[i][A[i][j]] = True   # i행에 A[i][j] 숫자가 사용됨
            c2[j][A[i][j]] = True   # j열에 A[i][j] 숫자가 사용됨
            c3[cal(i,j)][A[i][j]] = True # cal(i,j)번째 square에 A[i][j] 숫자가 사용됨
sol(0)

 

Reference : https://hazung.tistory.com/153