import sys
input = sys.stdin.readline
dy = [1,-1,0,0]
dx = [0,0,1,-1]
def put(n,c):
y,x = c
y,x = ord(y)-65,int(x)-1
board[y][x] = n
checky[y][n] = 1
checkx[x][n] = 1
checksq[(y//3,x//3)][n] = 1
def check(y,x,n):
if checky[y][n] or checkx[x][n] or checksq[(y//3,x//3)][n]:
return True
return False
def sudoku(y,x):
global finish
if finish:
return
if y == 9:
finish = True
print("Puzzle",test)
print(*map(lambda x:"".join(map(str,x)),board),sep="\n")
return
if x == 9:
sudoku(y+1,0)
return
if board[y][x]:
sudoku(y,x+1)
return
for n in range(1,10):
if dominocnt[n]==8 or check(y,x,n):
continue
for i in range(4):
y1,x1 = y+dy[i],x+dx[i]
if 9>y1>=0 and 9>x1>=0 and not board[y1][x1]:
for n1 in range(1,10):
if n == n1 or domino[(n,n1)] or check(y1,x1,n1):
continue
board[y][x] = n
board[y1][x1] = n1
dominocnt[n] += 1
dominocnt[n1] += 1
domino[(n,n1)] = domino[(n1,n)] = 1
checky[y][n] = checkx[x][n] = checksq[(y//3,x//3)][n] = 1
checky[y1][n1] = checkx[x1][n1] = checksq[(y1//3,x1//3)][n1] = 1
sudoku(y,x+1)
board[y][x] = 0
board[y1][x1] = 0
dominocnt[n] -= 1
dominocnt[n1] -= 1
domino[(n,n1)] = domino[(n1,n)] = 0
checky[y][n] = checkx[x][n] = checksq[(y//3,x//3)][n] = 0
checky[y1][n1] = checkx[x1][n1] = checksq[(y1//3,x1//3)][n1] = 0
test = 0
while True:
N = int(input())
if not N:
break
test += 1
board = [[0]*9 for i in range(9)]
domino = {(i,j):0 for i in range(1,10) for j in range(1,10)}
dominocnt = {i:0 for i in range(1,10)}
checky = {i:{n:0 for n in range(1,10)} for i in range(9)}
checkx = {i:{n:0 for n in range(1,10)} for i in range(9)}
checksq = {(i,j):{n:0 for n in range(1,10)} for i in range(3) for j in range(3)}
for i in range(N):
n1,c1,n2,c2 = input().split()
n1 = int(n1)
n2 = int(n2)
domino[(n1,n2)] = domino[(n2,n1)] = 1
dominocnt[n1] += 1
dominocnt[n2] += 1
put(n1,c1)
put(n2,c2)
co = input().split()
for i in range(9):
put(i+1,co[i])
finish = False
sudoku(0,0)전형적인 백트래킹 + 구현 문제이다.
Dict를 상당히 많이 활용했다. 개인적으로 dict의 시간복잡도 O(1)은 사기적이라고 생각해서 시간복잡도를 줄이기 위해서 많이 사용하는 것 같다.
알고리즘을 정리하면,
일단 선행과정으로
1. 모든 (i,j)에 대해서 domino dict를 만들어 도미노 사용여부를 저장한다.
2. 모든 숫자에 대해서 dominocnt dict를 만들어 도미노를 몇개 사용했는지 저장한다. (8개가 최대)
3. checky, checkx, checksq dict를 만들어 각 행, 열, 3*3 사각형에서 숫자의 사용여부를 저장한다.
4. checky, checkx, checksq가 모두 0이면 check함수는 False를 return한다.
그리고 백트래킹 하는 과정은
1. y == 9면 finish를 True로 바꾸고 현재 board를 print, x==9면 y를 +1
2. 현 위치가 0일 경우 모든 숫자에 대해 dominocnt가 8 이하이고, check함수가 False이면 현 위치를 기준으로 4방향 검사
3. 4방향에서 0인 자리에 대해 domino가 남아있으며 check함수가 False인 domino를 board에 삽입
4. 삽입할 때, domino, dominocnt, checky, checkx, checksq를 모두 갱신해야 하며, 백트래킹 할때도 마찬가지이다.
5. finish가 True이면 이미 결과가 나왔다는 뜻이므로 return한다.
재미있는 백트래킹 문제였다.
오늘의 교훈) dict는 유용하다.