백준(BOJ) 2580 스도쿠(Python)

문제 내용

 

백트래킹 문제.

빈 칸의 좌표를 먼저 모두 담은 리스트를 만들고, 그 리스트의 원소의 개수만큼 백트래킹을 하며 문제를 해결했다.

어떤 수를 빈 칸에 넣을 때 행과 열, 3X3 칸에 같은 수가 존재하는 지를 확인하고 존재하지 않는다면 다음 칸으로 넘어가는 방식으로 해결했다.

 

코드는 다음과 같다.

 

# -*- coding: utf-8 -*-
import sys
from collections import deque
import heapq
import copy
from itertools import combinations
import bisect
#input=sys.stdin.readline
#sys.setrecursionlimit(100000000)

L=[list(map(int,input().split())) for i in range(9)]
X=[]
for i in range(9):
    for j in range(9):
        if L[i][j]==0:
            X.append([i,j])
            
def check(x,y,k):
    for i in range(9):
        if L[x][i]==k:
            return 0
    for i in range(9):
        if L[i][y]==k:
            return 0
    x=x//3*3
    y=y//3*3
    for i in range(3):
        for j in range(3):
            if L[x+i][y+j]==k:
                return 0
    return 1

x=len(X)
def func(k):
    global x
    if k==x:
        for i in L:
            print(' '.join(list(map(str,i))))
        sys.exit(0)
    for i in range(1,10):
        if check(X[k][0],X[k][1],i):
            L[X[k][0]][X[k][1]]=i
            func(k+1)
            L[X[k][0]][X[k][1]]=0
func(0)

신촌캠프 문제였다.