BOJ 2580번: 스도쿠

www.acmicpc.net/problem/2580

2580번: 스도쿠

아이디어:

열: row = [[False]*10 for _ in range(9)]
행: col = [[False]*10 for _ in range(9)]
3*3: square = [[False]*10 for _ in range(9)]

-> 1~9까지 숫자가 있으면 해당 인덱스 True

주어진 스도쿠 행렬을 돌면서 0인 경우 조건을 검사하고 조건에 부합하면 일단 넣기.

 

어려웠던 부분:

이차 배열 선언을 [[False]*10]*9 이렇게 하면 변경이 모든 행에 적용된다.

재귀함수 쓰고 돌아왔을 때 초기화를 안해서 오류가 났다.

 

 

import sys
arr= []
for _ in range(9):
    arr.append(list(map(int, sys.stdin.readline().split())))

row = [[False]*10 for _ in range(9)]
col = [[False]*10 for _ in range(9)]
square = [[False]*10 for _ in range(9)]
                
for i in range(9):
    for j in range(9):
        row[i][arr[i][j]]=True
        col[j][arr[i][j]]=True
        square[i//3*3+j//3][arr[i][j]]=True     

def solve(cnt):
    if (cnt==81):
        for i in range(9):
            for j in range(9):
                print(arr[i][j], end=" ")
            print()
        exit(0)
        
    y = cnt//9
    x = cnt%9
    
    if (arr[y][x]!=0):
        solve(cnt+1)
    
    else:

        for k in range(1,10):
            if (row[y][k]==False and col[x][k]==False and square[y//3*3+x//3][k]==False):
                arr[y][x]=k
                row[y][k]=True
                col[x][k]=True
                square[y//3*3+x//3][k]=True
                solve(cnt+1)
                arr[y][x]=0
                row[y][k]=False
                col[x][k]=False
                square[y//3*3+x//3][k]=False
                

solve(0)