알고리즘 - 백트랙킹 (2580 스도쿠)

문제

스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루어진 정사각형 판 위에서 이뤄지는데, 게임 시작 전 일부 칸에는 1부터 9까지의 숫자 중 하나가 쓰여 있다.

나머지 빈 칸을 채우는 방식은 다음과 같다.

1. 각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.
2. 굵은 선으로 구분되어 있는 3x3 정사각형 안에도 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.

위의 예의 경우, 첫째 줄에는 1을 제외한 나머지 2부터 9까지의 숫자들이 이미 나타나 있으므로 첫째 줄 빈칸에는 1이 들어가야 한다.

또한 위쪽 가운데 위치한 3x3 정사각형의 경우에는 3을 제외한 나머지 숫자들이 이미 쓰여있으므로 가운데 빈 칸에는 3이 들어가야 한다.

이와 같이 빈 칸을 차례로 채워 가면 다음과 같은 최종 결과를 얻을 수 있다.

게임 시작 전 스도쿠 판에 쓰여 있는 숫자들의 정보가 주어질 때 모든 빈 칸이 채워진 최종 모습을 출력하는 프로그램을 작성하시오.

 

입력

아홉 줄에 걸쳐 한 줄에 9개씩 게임 시작 전 스도쿠판 각 줄에 쓰여 있는 숫자가 한 칸씩 띄워서 차례로 주어진다. 스도쿠 판의 빈 칸의 경우에는 0이 주어진다. 스도쿠 판을 규칙대로 채울 수 없는 경우의 입력은 주어지지 않는다.

출력

모든 빈 칸이 채워진 스도쿠 판의 최종 모습을 아홉 줄에 걸쳐 한 줄에 9개씩 한 칸씩 띄워서 출력한다.

스도쿠 판을 채우는 방법이 여럿인 경우는 그 중 하나만을 출력한다.

---

문제 분석

빈칸은 0, 나머지는 1~9까지의 수를 입력하여 넣는다.

스도쿠를 푸는 것과 같다

 

 

접근 방식

실제로 풀때도 빈칸을 하나하나확인하면서 들어갈 수 있는 수를 구한 후 1개씩 넣었다.

 

먼저 스도쿠의 맵을 받아오는데 전체를 for문을 계속 돌릴수는 없으니 필요한 부분만 들리기 위해 배열(need) 하나를 생성하여 0일때만 추가하였다.

 

처음에는 queue에 넣어서 1개 남은 것들 부터 지우고 여러개 남으면 뒤로 보내고 하는 방식으로 할려 했지만 생각해보니 여러 개중 하나를 선택해야 하는 때가 올 수 있다. 따라서 이를 해결하기 위해 2개 이상 남들것들만 남았을때 즉 선택해야 하는 순간을 찾을까 생각했지만 2개 이상 남는 것들을 찾기 위해 need배열을 다시 한 번 돌려야 하는 방식이 별로여서 처음 부터 모든 경우의수를 찾는 방법을 사용하고자 했다. (코드의 길이도 길어지고 해서 패스)

 

need 배열에는 0인 좌표가 들어가 있고, 해당 좌표에서 들어갈 수 있는 값을 배열로 만들어 이 들어갈 수 있는 값들의 조합으로 문제를 해결하고자 했다.

 

가능한 수를 찾는 방법:

가로, 세로, 하나의 칸에 대해 총 9개의 수를 검색하는 것은 같기에 하나의 for문을 이용하고자 했으며

가로 세로 하나의 칸의  좌표를 접근하여 값을 가져오고 그 인덱스의 값을 1로 변경해주었다.

 

sudoku = []
need = []
for i in range(9):
    temp = list(map(int, input().split()))
    for j in range(9):
        if temp[j] == 0:
            need.append([i,j])
    sudoku.append(temp)
 
def isIn(loc):
    isAble = [0] * 9
    r_y = loc[0] // 3 * 3
    r_x = loc[1] // 3 * 3
 
    for i in range(9):
        row = sudoku[loc[0]][i]
        col = sudoku[i][loc[1]]
        round = sudoku[r_y + i//3][r_x+i%3]
        if row != 0:
            isAble[row-1] = 1
        if col != 0:
            isAble[col-1] = 1
        if round != 0:
            isAble[round-1] = 1
        
    re = []
    for i in range(9):
        if isAble[i] == 0:
            re.append(i+1)
    return re
 
def printSudoku():
    for i in sudoku:
        print(' '.join(list(map(str, i))))
 
needSize=len(need)   
def check(index):
    if index == needSize:
        return False
    
    haveTo= isIn(need[index])
    
    if len(haveTo)==1 and index == needSize-1:
        sudoku[need[index][0]][need[index][1]] = haveTo[0]
        printSudoku()
        return True
    
    for data in haveTo:
        sudoku[need[index][0]][need[index][1]] = data
        if check(index+1):
            return True
        sudoku[need[index][0]][need[index][1]] = 0
 
check(0)