백준 4574 파이썬 - 스도미노쿠

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

4574번: 스도미노쿠

문제

스도쿠가 세계적으로 유행이 된 이후에, 비슷한 퍼즐이 매우 많이 나왔다. 게임 매거진 2009년 7월호에는 스도쿠와 도미노를 혼합한 게임인 스도미노쿠가 소개되었다. 

이 퍼즐은 스도쿠 규칙을 따른다. 스도쿠는 9×9 크기의 그리드를 1부터 9까지 숫자를 이용해서 채워야 한다. 스도쿠는 다음과 같은 조건을 만족하게 숫자를 채워야 한다.

• 각 행에는 1부터 9까지 숫자가 하나씩 있어야 한다.
• 각 열에는 1부터 9까지 숫자가 하나씩 있어야 한다.
• 3×3크기의 정사각형에는 1부터 9가지 숫자가 하나씩 있어야 한다.

스도미노쿠의 그리드에는 1부터 9까지 숫자가 쓰여져 있고, 나머지 72칸은 도미노 타일 36개로 채워야 한다. 도미노 타일은 1부터 9까지 서로 다른 숫자의 가능한 쌍이 모두 포함되어 있다. (1+2, 1+3, 1+4, 1+5, 1+6, 1+7, 1+8, 1+9, 2+3, 2+4, 2+5, ...) 1+2와 2+1은 같은 타일이기 때문에, 따로 구분하지 않는다. 도미노 타일은 회전 시킬 수 있다. 또, 3×3 크기의 정사각형의 경계에 걸쳐서 놓여질 수도 있다.

왼쪽 그림은 퍼즐의 초기 상태를 나타내고, 오른쪽은 퍼즐을 푼 상태이다.

스도미노쿠의 퍼즐의 초기 상태가 주어졌을 때, 퍼즐을 푸는 프로그램을 작성하시오.

코드

import sys
dx = [0, 1]
dy = [1, 0]
def convert(s):
    return (ord(s[0]) - ord('A'), ord(s[1]) - ord('1'))
def square(x, y):
    return (x // 3) * 3 + (y // 3)
def can(x, y, num):
    return not c[x][num] and not c2[y][num] and not c3[square(x, y)][num]
def check(x, y, num, what):
    c[x][num] = what
    c2[y][num] = what
    c3[square(x, y)][num] = what
def check_range(x, y):
    return 0 <= x < 9 and 0 <= y < 9
def go(z):
    if z == 81:
        for i in range(9):
            sys.stdout.write(''.join(map(str, a[i])))
            print()
        return True
    x = z // 9
    y = z % 9
    if a[x][y] != 0:
        return go(z + 1)
    else:
        for k in range(2):
            nx, ny = x + dx[k], y + dy[k]
            if not check_range(nx, ny):
                continue
            if a[nx][ny] != 0:
                continue
            for i in range(1, 10):
                for j in range(1, 10):
                    if i == j:
                        continue
                    if domino[i][j]:
                        continue
                    if can(x, y, i) and can(nx, ny, j):
                        check(x, y, i, True)
                        check(nx, ny, j, True)
                        domino[i][j] = domino[j][i] = True
                        a[x][y] = i
                        a[nx][ny] = j
                        if go(z+1):
                            return True
                        check(x, y, i, False)
                        check(nx, ny, j, False)
                        domino[i][j] = domino[j][i] = False
                        a[x][y] = 0
                        a[nx][ny] = 0
    return False

count = 1
while True:
    c = [[False] * 10 for _ in range(10)]
    c2 = [[False] * 10 for _ in range(10)]
    c3 = [[False] * 10 for _ in range(10)]
    domino = [[False] * 10 for _ in range(10)]
    a = [[0] * 9 for _ in range(9)]
    m = int(sys.stdin.readline())
    if m == 0:
        break
    for i in range(m):
        n1, s1, n2, s2 = sys.stdin.readline().rstrip().split()
        n1 = int(n1)
        n2 = int(n2)
        x1, y1 = convert(s1)
        x2, y2 = convert(s2)
        a[x1][y1] = n1
        a[x2][y2] = n2
        domino[n1][n2] = domino[n2][n1] = True
        check(x1, y1, n1, True)
        check(x2, y2, n2, True)
    temp = sys.stdin.readline().rstrip().split()
    for i in range(1, 10):
        s = temp[i-1]
        x, y = convert(s)
        a[x][y] = i
        check(x, y, i, True)
    print('Puzzle', count)
    go(0)
    count += 1

풀이

서로 다른 수가 적혀있는 블록으로 스도쿠처럼 칸을 채워야 한다. 블럭끼리는 모두 다 다르고, 회전시키거나 뒤집을 수 있다. (1, 2), (1, 3), (1, 4), ..... , (8, 9)  와 같은 블럭들이 있다고 한다. 9 * 9 크기의 보드에 9 자리는 차있고 나머지 72칸을 36개의 블럭으로 채우면 된다. 인접한 두 위치를 구한 뒤 조건을 만족하는 두 수를 넣어주면서 재귀함수를 호출한다.