백준 2580번 스도쿠

백준 2580번 스도쿠 문제이다.

스도쿠에 대한 규칙은 일반 스도쿠와 동일한 것으로 보인다. 

 

빈칸을 0으로 표시하고 있다. 빈칸에 숫자를 하나씩 넣어가면서 확인해주는 백트래킹 방식이다. 

이번에도 하나씩 넣어가는 solve 함수와 다음 빈칸에 숫자를 넣으러 넘어갈지를 판단해주는 promise 함수로 이루어져 있다.

promise 함수에서는 가로 세로, 포함된 3x3 칸에 숫자가 있는지 확인하여 있다면 false를 리턴하여 다음으로 넘어가지 않도록 하였다.

여기서 3x3칸을 확인할 때에는 가로 세로 값인 i 와 j를 3으로 나눈 몫을 확인하여 0, 1, 2 값으로 3구역으로 나뉘기 때문에

어느 3x3 구역인지 확인하도록 하였다. 

import sys

def promise(i, j, k):
    for m in range(9):
        if k in sudoku[i]:
            return False
        elif sudoku[m][j] == k:
            return False
    
    for l in range(3):
        for o in range(3):
            if sudoku[i // 3 * 3 + l][j // 3 * 3 + o] == k:
                return False 
    return True

def solve(cnt):
    if cnt == n:
        for i in range(9):
            for j in range(9):
                print(sudoku[i][j], end = ' ')
            print()
        sys.exit(0)
    else:
        for k in range(1,10):
            i = zero[cnt][0]
            j = zero[cnt][1]
            if promise(i, j, k):
                sudoku[i][j] = k
                solve(cnt+1)
                sudoku[i][j] = 0


n = 0
flag = 0
sudoku = [[int(x) for x in input().split()]for y in range(9)]
zero = [(i, j) for i in range(9) for j in range(9) if sudoku[i][j] == 0]
n = len(zero)
solve(0)

언어는 Python을 사용하였다.

성공!