[v.백트래킹-스도쿠-2580]BAEKJOON_Python

220126 작성

<본 블로그는 BAEKJOON 을 참고해서 저만의 풀이를 작성하였습니다>

 

 

 

2580

스도쿠 판의 빈 칸의 경우에는 0이 주어진다
게임 시작 전 스도쿠 판에 쓰여 있는 숫자들의 정보가 주어질 때 모든 빈 칸이 채워진 최종 모습을 출력

 

 

내 풀이

import sys

graph = []
blank = []

for i in range(9) :
    graph.append(list(map(int, sys.stdin.readline().rstrip().split())))   # rstip : 인자로 전달된 문자를 String의 오른쪽에서 제거

for i in range(9) :
    for j in range(9) :
        if graph[i][j] == 0 :     # 0으로 비어 있으면!
            blank.append((i,j))

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

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

def checkRect(x, y, a) :
    nx = x // 3 * 3
    ny = y // 3 * 3

    for i in range(3) :
        for j in range(3) :
            if a == graph[nx+i][ny+j] :
                return False
    return True

def dfs(idx) :
    if idx == len(blank) :
        for i in range(9) :
            print(*graph[i])
        exit(0)

    for i in range(1, 10) :
        x = blank[idx][0]
        y = blank[idx][1]

        if checkRow(x, i) and checkCol(y, i) and checkRect(x, y, i) :
            graph[x][y] = i
            dfs(idx + 1)
            graph[x][y] = 0

dfs(0)

 

 

 

 

 

 

 

0 3 5 4 6 9 2 7 8
7 8 2 1 0 5 6 0 9
0 6 0 2 7 8 1 3 5
3 2 1 0 4 6 8 9 7
8 0 4 9 1 3 5 0 6
5 9 6 8 2 0 4 1 3
9 1 7 6 5 2 0 8 0
6 0 3 7 0 1 9 5 2
2 5 8 3 9 4 7 6 0

// 결과
1 3 5 4 6 9 2 7 8
7 8 2 1 3 5 6 4 9
4 6 9 2 7 8 1 3 5
3 2 1 5 4 6 8 9 7
8 7 4 9 1 3 5 2 6
5 9 6 8 2 7 4 1 3
9 1 7 6 5 2 3 8 4
6 4 3 7 8 1 9 5 2
2 5 8 3 9 4 7 6 1

 

난 절대.. 혼자 모태.. .절대로..ㅜㅡㅜ

 

 

 

 

 

 

자세한 설명 감사합니당

참고한 블로그 입니다!! bb

https://hongcoding.tistory.com/118

[백준] 2580 스도쿠 (Python 파이썬)