백준 4574 스도미노쿠

import sys
input = sys.stdin.readline
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

turn = 1

while True:
    g = [[0] * 9 for _ in range(9)]
    n = int(input())

    if n == 0:
        break
    
    sudominoku = []
    for i in range(1, 10):
        for j in range(i+1, 10):
            sudominoku.append((i, j))

    for _ in range(n):
        u, lu, v, lv = map(str, input().split())
        u = int(u)
        v = int(v)
        g[ord(lu[0])-65][int(lu[1])-1] = u
        g[ord(lv[0])-65][int(lv[1])-1] = v
        sudominoku.remove((min(u, v), max(u, v)))
    l = list(map(str, input().split()))

    for i, s in enumerate(l):
        g[ord(s[0])-65][int(s[1])-1] = i+1

    def check(x, y, tmp, g):
        for i in range(9):
            if g[x][i] == tmp:
                return False
        for i in range(9):
            if g[i][y] == tmp:
                return False
        nx, ny = x//3 * 3, y//3 * 3
        for i in [nx, nx+1, nx+2]:
            for j in [ny, ny+1, ny+2]:
                if g[i][j] == tmp:
                    return False
        return True

    blank = []
    for i in range(9):
        for j in range(9):
            if g[i][j] == 0:
                blank.append((i, j))
    flag = 0
    def go(g, sudominoku):
        global flag
        if len(sudominoku) == 0:
            flag = 1
            print('Puzzle', turn)
            for u in range(9):
                for v in range(9):
                    print(g[u][v], end='')
                print()
            return
        if flag == 1:
            return
        # 도미노 넣을 빈칸 탐색
        for i in range(9):
            for j in range(9):
                if g[i][j] == 0:
                    x, y = i, j
        # 빈칸에 모든 도미노 넣어봄
        for n1, n2 in sudominoku:
            # 도미노의 한칸을 빈칸에 두고 나머지 한칸은 상하좌우로 붙일 수 있음
            for d in range(4):
                nx, ny = x + dx[d], y + dy[d]
                # 스도쿠 판 벗어나면 
                if nx < 0 or nx >= 9 or ny < 0 or ny >= 9:
                    continue
                # 빈칸이 아니면
                if g[nx][ny] != 0:
                    continue
                # tmp 배열 만들어서 빈칸에 넣을 도미노는 배열에서 뺌
                tmp = sudominoku[:]
                tmp.remove((n1, n2))
                # 겹치는 숫자 체크
                if check(x, y, n1, g) and check(nx, ny, n2, g):
                	# 스도쿠 빈칸에 도미노 넣음
                    g[x][y], g[nx][ny] = n1, n2
                    # 정답 찾았으면 종료하기 위해
                    if flag == 1:
                        return
                    go(g, tmp)
                # 이 줄을 안넣어서 한참 헤맴.. 이 줄을 안넣으면 체크가 안된다.
                g[x][y], g[nx][ny] = 0, 0
                # n1, n2 바꿔서 넣는 경우 재귀 돌림
                tmp = sudominoku[:]
                tmp.remove((n1, n2))
                if check(x, y, n2, g) and check(nx, ny, n1, g):
                    g[x][y], g[nx][ny] = n2, n1
                    if flag == 1:
                        return
                    go(g, tmp)
                g[x][y], g[nx][ny] = 0, 0

    go(g, sudominoku)
    turn += 1

처음에 원래 있는 도미노랑 겹치면 안되는줄 모르고 한참 헤맴... 문제를 제대로 이해해야함..