2239: 스도쿠

풀이 시간

• 30m
• 100% 쯤에서 계속 indexError가 떠서 질문게시판을 확인한 결과 stdin을 받을 때, input[:-1]가 아닌 input[:9]로 해야 통과한다는 글을 보고 해결함. 문제의 입력에 오류가 있는듯

구현 방식

• dfs + backtracking을 통해 board[x][y]가 0인 칸에 모든 수를 넣어보는 방식으로 해결함
• 빈칸의 좌표를 넣은 zero 리스트를 이용하여 dfs 탐색 진행
• dfs의 종료 조건은 zero 리스트의 모든 좌표에 값을 넣었을 때, 즉 depth가 len(zero)와 같을 때이다

코드

import sys


def checkRow(i, x):
    for y in range(9):
        if board[x][y] == i:
            return False
    return True

def checkCol(i, y):
    for x in range(9):
        if board[x][y] == i:
            return False
    return True

def checkSquare(i, x, y):
    x = (x // 3) * 3; y = (y // 3) * 3
    for a in range(x, x+3):
        for b in range(y, y+3):
            if board[a][b] == i:
                return False
    return True

def dfs(idx):
    if idx == len(zero):
        for a in range(9):
            for b in range(9):
                print(board[a][b], end="")
            print()
        exit()

    x = zero[idx][0]; y = zero[idx][1]
    for i in range(1, 10):
        if checkRow(i, x) and checkCol(i, y) and checkSquare(i, x, y):
            board[x][y] = i
            dfs(idx + 1)
            board[x][y] = 0


board = []; zero = []
for _ in range(9):
    tmp = list(map(int, sys.stdin.readline()[:9]))
    for i in range(9):
        if tmp[i] == 0:
            zero.append((_, i))
    board.append(tmp)

dfs(0)

결과