https://www.acmicpc.net/problem/2580
2580번: 스도쿠스도쿠는 18세기 스위스 수학자가 만든 ‘라틴 사각형’이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루www.acmicpc.net
스도쿠를 받으면서, 공백의 위치만 따로 기억한다.
이후, 첫번째 공백부터 1~9의 숫자로 채우며, 가로,세로,3*3사각형을 검사한다.
이후 되는경우만 밀고나간다.
##코드##
import sysinput=sys.stdin.readlinedef check(a,b,value):
for i in range(9): #가로 if arr[a][i]==value:
return False #세로 if arr[i][b]==value:
return False #사각형 start_a=a//3*3 start_b=b//3*3
for i in range(start_a,start_a+3): for j in range(start_b,start_b+3):
if arr[i][j]==value: return False return True
def dfs(cnt=0): if cnt==len(blank): for ar in arr:
print(* ar) exit() for i in range(1,10):
a,b=blank[cnt] #세로,가로 if check(a,b,i): arr[a][b]=i
dfs(cnt+1) arr[a][b]=0 returnarr=[] #스도쿠blank=[]
for i in range(9): tmp=[*map(int,input().strip().split())] arr.append(tmp)
for j in range(9): if tmp[j]==0: blank.append((i,j))dfs()진짜 가면갈수록자괴감느낀다.
이걸 도저히 이해못하겠는 복잡한 코드를 짜서 200ms대에 푸는 사람이 있다.
봐도 이해를 못하겠다.