[BOJ] 2580

문제

me

• 백트래킹을 적용하고 싶었다.
• 0을 모두 채웠다면 종료하는 방식으로 만들어봤지만 나오는 것은 없었다.

import sys
input = sys.stdin.readline
#boards=[list(map(int,input().split())) for _ in range(9)]
boards=[]
zero_cnt=0
for i in range(9):
    boards.append(list(map(int,input().split())))
    zero_cnt+=boards[i].count(0)
set_nums = set([n for n in range(10)])
def checkRow(i):
    return list(set_nums-set(boards[i]))
def checkCol(j):
    return list(set_nums-set([boards[c][j] for c in range(9)]))
def checkSquare(i,j):
    dx=[-1,-1,-1,0,0,+1,+1,+1]
    dy=[-1,0,+1,-1,+1,-1,0,+1]
    return list(set_nums-set([ boards[i+dx[t]][j+dy[t]] for t in range(8)]))

def dfs(x,y):
    global fill_cnt
    print(fill_cnt,x,y)
    if fill_cnt==zero_cnt:
        for board in boards:
            for b in board:
                print(b,end=" ")
            print()
        return
    else:
        r=checkRow(x)
        c=checkCol(y)
        s=c[:]
        if 0<x<8 and 0<y<8:
            s=checkSquare(x,y)
        candidates=list(set(r)&set(c)&set(s))

        for candidate in candidates:
            boards[x][y]=candidate
            fill_cnt+=1
            for i in range(x+1,9):
                if boards[i][y]==0:
                    dfs(i,y)
            for j in range(y+1,9):
                if boards[x][j]==0:
                    dfs(x,j)
            fill_cnt-=1
            boards[x][y]=0

fill_cnt=0
for i in range(9):
    for j in range(9):
        if boards[i][j]==0:
            dfs(i,j)

sol

import sys
graph = []
blank = []

for i in range(9):
    graph.append(list(map(int, sys.stdin.readline().rstrip().split())))

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

def checkRow(x, a):
    for i in range(9):
        if a == graph[x][i]:
            return False
    return True

def checkCol(y, a):
    for i in range(9):
        if a == graph[i][y]:
            return False
    return True

def checkRect(x, y, a):
    nx = x // 3 * 3
    ny = y // 3 * 3
    for i in range(3):
        for j in range(3):
            if a == graph[nx+i][ny+j]:
                return False
    return True


def dfs(idx):
    if idx == len(blank):
        for i in range(9):
            print(*graph[i])
        exit(0)

    for i in range(1, 10):
        x = blank[idx][0]
        y = blank[idx][1]

        if checkRow(x, i) and checkCol(y, i) and checkRect(x, y, i):
            graph[x][y] = i
            dfs(idx+1)
            graph[x][y] = 0

dfs(0)

• 나는 빈칸에 들어갈 수 있는 숫자를 찾았지만, 이런 방식이면 어떤 숫자가 들어갈 수 있는지 없는지 체크하는 방식이다. 항상 매번 후보를 찾게 했는데 저렇게 한다면 내가 고민하던 "과연 이 숫자가 올바른 것인가"에 대한 문제도 해결할 수 있는 것 같다.

출처