2580. 스도쿠

문제가 길다...

 

백트래킹 방식으로 풀 수 있다. N-queen문제의 접근 방법과 비슷한데, 가로, 세로, 3x3 박스 각각 체크할 수 있도록 체크 배열을 만들면 된다.

1. 가로를 체크하는 check_row 배열의 경우 몇번째 줄에 어떤 숫자가 들어갔는지를 체크하도록 해야 한다.

즉, check_row[3][2] = True 라면, 네번째 줄 (첫번째 줄은 0번 index니까)에 2라는 숫자가 존재한다는 것.

2. 세로를 체크하는 check_col 배열도 동일하다.

3. 3x3 박스를 체크하는 check_box 배열의 경우 몇번째 box에 어떤 숫자가 들어갔는지를 체크해야 한다.

몇번째 박스인지를 어떻게 알까? \

3개씩 끊어주면 되니까 3으로 나눈 값을 잘 사용하면 나타낼 수 있을 것 같다.

난 각 box를 (i//3)*2+j//3으로 표현하여 사용하였다. 이러면 3x3 박스를 각각 0부터 8번 index까지 나타낼 수 있다. (한 번 직접 계산해보면 알 수 있다.)

 

이제 입력값을 받은 스도쿠 판을 확인하여 체크 배열들을 채워주어야 한다.

체크 배열들을 잘 채워주었다면 각 가로세로박스에 대하여 False인 값들이 우리가 채워주어야 하는 값들이 될 것이다.

 

이후는 백트래킹 방식을 잘 사용해주면 된다. cnt를 증가시키면서 가로세로 좌표값을 얻어주고 각 칸에 대해 칸의 값이 0이라면 비어있는 칸이므로 1부터 숫자를 넣어주면서 만족하는지 확인해준다. 코드를 뜯어보면 훨씬 이해하기 쉬울 것이다.

 

# 스도쿠
# 가로줄과 세로줄에는 1부터 9까지의 숫자가 한번씩만 나타나야 함
# 굵은 선으로 구분되어 있는 정사각형 안에도 1부터 9까지의 숫자가 한 번씩만 나타나야 함
import sys
input = sys.stdin.readline

ROW = 9
check_row = [[False] * 10 for _ in range(10)] 
check_col = [[False] * 10 for _ in range(10)] 
check_box = [[False] * 10 for _ in range(10)] 

def pre_check() :
    for i in range(9) :
        for j in range(9) :
            if board[i][j] == 0 :
                continue
            check_row[i][board[i][j]] = True
            check_col[j][board[i][j]] = True
            check_box[(i//3)*3+(j//3)][board[i][j]] = True

def make_sudoku(cnt) :
    if cnt == ROW*ROW :
        return True
    x = cnt//9
    y = cnt%9
    if board[x][y] > 0 :
        return make_sudoku(cnt+1)
    for i in range(1, 10) :
        if check_row[x][i] or check_col[y][i] or check_box[(x//3)*3+(y//3)][i] :
            continue
        board[x][y] = i
        check_row[x][i] = True
        check_col[y][i] = True
        check_box[(x//3)*3+(y//3)][i] = True
        if make_sudoku(cnt+1) :
            return True
        board[x][y] = 0
        check_row[x][i] = False
        check_col[y][i] = False
        check_box[(x//3)*3+(y//3)][i] = False
    return False

board = [list(map(int, input().split())) for _ in range(9)]

pre_check()
make_sudoku(0)

for line in board : 
    print(*line)