[백준 #2580] 스도쿠 - 파이썬(python)

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

백트래킹 문제 2

백트래킹문제는 항상 실제로 아날로그식으로 풀면 규칙도 다 알겠는데

코드 구현으로 이어지지가 않는게 문제인 것 같다.

 

스도쿠,, 어릴 때 심심풀이로 엄청 풀었던 것 같은데..

def get_ans(x,y):
    numlist=[str(i) for i in range(1,10)]
    row=[sdoku[x][i] for i in range(9)]
    column=[sdoku[i][y] for i in range(9)]
    used=list(set(row+column))
    for i in used:
        if i in numlist:
            numlist.remove(i)
    if len(numlist)==1:
        sdoku[x][y]=numlist[0]
    else:
        cell=get_square(x//3+1,y//3+1)
        for i in numlist:
            if  i in cell:
                numlist.remove(i)
        if len(numlist)==1:
            sdoku[x][y]=numlist[0]
        else: return '0'

def get_square(a,b):
    celllist=[]
    for i in range(a*3-3,a*3):
        for j in range(b*3-3,b*3):
            celllist.append(sdoku[i][j])
    return celllist
    
from sys import stdin,stdout
input=stdin.readline
sdoku=[list(map(str,input().split())) for _ in range(9)]
newlist=[(i,j) for i in range(9) for j in range(9) if sdoku[i][j]=='0']
print(newlist)
while True:
    for i in newlist:
        ver=get_ans(i[0],i[1])
        if ver=='0':
            newlist.remove((i[0],i[1]))
    if len(newlist)==0: break
    else: continue
            
for i in range(9):
    sdoku[i]=' '.join(sdoku[i])

stdout.write('\n'.join(sdoku))

수정의 수정의 수정을 거쳐서 제출했는데,

답은 틀렸다.

 

예제로 나온 입력값에는 분명히 다 맞았는데

뭐가 문젤까 하면서

인터넷에 스도쿠 문제를 검색해서 입력해 보았더니.

 

값이 하나로 귀결되는 경우도 있지만,

스도쿠를 풀다보면 한 칸에 들어갈 수 있는 숫자가 여러개라

일단 무작위로 하나 넣어 본 다음에

답이 나오는지 안나오는지를 해보고 또 다른 숫자를 해보고 

이런 경우가 있었는데,

 

이런 경우에는 무한 로딩 되면서 while문이 끝나지가 않는다..

 

도저히 안되겠다 싶어서 찾아봤는데

 

개념적으로 내가 쓴 while문과 맥락이 비슷한데

이렇게 구현하면 되는구나 하고 느꼈다. 

import sys
input=sys.stdin.readline
sdoku=[list(map(int,input().split())) for _ in range(9)]
zeropos=[(i,j) for i in range(9) for j in range(9) if sdoku[i][j]==0]

def get_ans(x,y):
    numlist=[i for i in range(1,10)]
    
    for i in range(9):
        if sdoku[x][i] in numlist:
            numlist.remove(sdoku[x][i])
        if sdoku[i][y] in numlist:
            numlist.remove(sdoku[i][y])
    x=x//3
    y=y//3
    for i in range(x*3,(x+1)*3):
        for j in range(y*3,(y+1)*3):
            if sdoku[i][j] in numlist:
                numlist.remove(sdoku[i][j])
    return numlist

def dfs(count):
    if count==len(zeropos):
        for row in sdoku:
            print(*row)
        sys.exit()
    (x,y)=zeropos[count]
    candi=get_ans(x,y)
    for num in candi:
        sdoku[x][y]=num
        dfs(count+1)
        sdoku[x][y]=0

dfs(0)

앞으로 더 익혀야 할 알고리즘들이 정말 많다는것을 새삼 또 느꼈다.