[백준 2580] 스도쿠 (python)

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

2580번: 스도쿠

스도쿠 문제

스도쿠를 모두 채울 수 있을 경우, 그때 가능한 경우의 수 1개 만을 출력하는 문제

백트래킹을 이용하여 해결 할 수 있었다.

📌문제 접근 포인트

1. 스도쿠에 대해서 생각해보자. 스도쿠는 가로 9칸에 숫자가 겹치면 안 되고, 세로 9칸에도 숫자가 겹치면 안 되며, 해당 3*3칸에서도 숫자가 겹치면 안 된다.
2. 유망한 조건으로 위에 3가지 조건을 만들어주자. 또, 비어있는 칸에 숫자를 넣어야 하니, 빈 숫자 칸 위치만을 찾을 수 있게 리스트를 하나 만들어주자.
3. 빈 숫자 칸 위치의 y, x의 좌표에 대해 위 2번에서 만들어준 유망조건들을 통과하도록 백트래킹을 구성해 주자. 문제의 요구조건은 가능한 경우의 수 1개만 출력하는 거니 모든 빈 공간에 해당하는 칸을 채웠을 때 출력하고, 그 후로 더 진행되지 않게 강제로 exit() 함수를 주어 종료시켜 버리면 된다.

반응형

⚙ 내가 푼 정답코드

def row(a, n): # 가로
    for i in range(9):
        if n == sudoku[a][i]: # 이미 있으면
            return False
    return True

def column(a, n): # 세로
    for i in range(9):
        if n == sudoku[i][a]: # 이미 있으면
            return False
    return True

def square(y, x, n): # 3x3 칸
    for i in range(3):
        for j in range(3):
            if n == sudoku[y//3 * 3 + i][x//3 * 3 + j]: # 칸내에 이미 있으면
                return False
    return True

def find(n):
    if n == len(blank): # 빈 공간 만큼 사용했으면
        for i in sudoku: # 출력 후
            print(*i) 
        exit() # 강제 종료

    for i in range(1,10):
        y = blank[n][0]
        x = blank[n][1]
        if column(x,i) and row(y,i) and square(y, x, i):
            sudoku[y][x] = i
            find(n+1)
            sudoku[y][x] = 0

import sys
sudoku = [list(map(int,sys.stdin.readline().split())) for _ in range(9)]
blank = []
for i in range(9):
    for j in range(9):
        if sudoku[i][j] == 0:
            blank.append([i,j])
find(0)