[백준/2580/파이썬] 스도쿠

https://www.acmicpc.net/problem/2580

2580번: 스도쿠

Problem

 

스도쿠의 빈칸을 채워라!

 

조건

스도쿠의 규칙이랑 같다.

단, 스도쿠를 완성 시키는 방법이 여러가지라면, 그 중에 아무거나 1개만 출력해라.

 

SOL)

우리가 잘 아는 스도쿠이다.

일단, 0인 곳을 기준으로, 행/렬/3*3 작은 직사각형을 확인해보면 된다.

하지만, 숫자를 넣어봤을때, 완성되지 않는다면,그 이전에 넣었던 곳이 잘못넣어진거이므로, 다른 숫자를 넣어봐야함. 즉, backtracking의 과정이 필요하다!

 

1. 0인 곳을 따로 blank라는 배열에 담을거임.

2. 0인 곳을 기준으로, 행/렬/3*3 작은 직사각형을 chk

3. 비어있는 곳에 1~9 숫자 중, 가능한 후보를 하나 일단 집어넣어봄.

4. 그 상태로 쭉 진행하다가, 진행이 안되면, 다른 숫자를 넣어봐야함.(backtracking)

 

chkrow,chkcol은 간단했지만, chk3to3는 3*3 크기 직사각형의 시작점을 구하는 방법인, ny=y//3 *3,nx=x//3*x 이 있다.

예를들어, y=5,x=2인 (5,2)번째의 빈칸이 있다면, 그 빈칸의 시작점은 (3,0)임! 이걸 반영해주려면, 위와같은 식으로 정의할 수 있다.

 

import sys
input = sys.stdin.readline

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

for i in range(9):
    for j in range(9):
        if board[i][j]==0:
            blank.append((i,j))

#print(*board)
def chkrow(y,a):
    for i in range(9):
        if a==board[y][i]:
            return False
    return True
def chkcol(x,a):
    for i in range(9):
        if a==board[i][x]:
            return False
    return True

def chk3to3(y,x,a):
    ny=y//3*3 #3*3의 시작점 좌표를 구하는 방법
    nx=x//3*3
    for i in range(3):
        for j in range(3):
            if a==board[ny+i][nx+j]:
                return False
    return True

def dfs(idx):
    if idx==len(blank):
        for i in range(9):
            print(*board[i])
        exit(0)
    for k in range(1,10):
        y=blank[idx][0]
        x=blank[idx][1]
        if chkrow(y,k) and chkcol(x,k) and chk3to3(y,x,k):
            board[y][x]=k
            dfs(idx+1)
            board[y][x]=0

dfs(0)