[백준-2580] 스도쿠 (Python)

www.acmicpc.net/problem/2580

2580번: 스도쿠

---

[풀이]

 

- 기본적인 백트래킹 문제였다.

 

- 주어진 maps 리스트에서 빈 칸(0)의 좌표를 blank에 저장하고, 빈 칸 하나하나 1부터 9까지 넣을 수 있는지 없는지 판단하였다.

 

- 가능한 숫자는 maps[x][y]에 저장하고, 다음 빈 칸을 위와 똑같이 채워주었다.

 

- isPossilbe(x,y,num) 함수는 maps[x][y]에 num의 숫자가 가로,세로,작은 사각형 모두 존재하지 않으면 True를, 그렇지 않으면 False를 return 하는 함수이다.

 

- sdoku 함수가 모든 빈 칸에 수를 대입하여 base condition이 되면 스도쿠 맵을 출력하고, 재귀호출을 종료했다.

 

def isPossible(x,y,num):
    if num in maps[x]:
        return False
    for i in range(9):
        if maps[i][y]==num:
            return False
    a,b=x//3*3, y//3*3
    for i in range(3):
        for j in range(3):
            if maps[a+i][b+j]==num:
                return False
    return True

def sdoku(z,lim):
    global flag
    if z==lim:
        for row in maps:
            for col in row:
                print(col, end=' ')
            print()
        flag=True

    else:
        x,y=blank[z]
        for i in range(1,10):
            if isPossible(x,y,i):
                maps[x][y]=i
                sdoku(z+1,lim)
                if flag: return
                maps[x][y]=0

maps=[list(map(int, input().split())) for _ in range(9)]
blank=[(i,j) for i in range(9) for j in range(9) if maps[i][j]==0 ]
print(blank)
flag=False
sdoku(0,len(blank))