백준 2580 스도쿠

문제 : 2580

풀이 point

백트래킹을 통해 푸는 문제이다. 1~9까지의 값을 넣어 행, 열, 3x3 정사각형까지 같은 값이 있는지 체크한다.

정사각형은 다음과 같은 식으로 판별할 수 있다.

grid[x//3 * 3 + i][y//3 * 3 + j]

풀이 방법

rowCheck, colCheck, 3x3 check를 통해 값이 들어가도 되는지 안되는지 True, False로 판단한다.

풀이 코드

#백준 2580, 스도쿠

import sys
input = sys.stdin.readline

def back(depth):
    if depth == len(zero):
        for num in grid:
            print(*num)
        exit()

    x, y = zero[depth]

    for i in range(1, 10):
        if rowCheck(x, i) and colCheck(y, i) and threeBy(x, y, i):
            grid[x][y] = i
            back(depth+1)
            grid[x][y] = 0

def rowCheck(x, n):
    return n not in grid[x]

def colCheck(y, n):
    for i in range(9):
        if n == grid[i][y]:
            return False
    return True

def threeBy(x, y, n):
    for i in range(3):
        for j in range(3):
            if n == grid[x//3 * 3 + i][y//3 * 3 + j]:
                return False
    return True

grid = [list(map(int, input().rstrip().split())) for _ in range(9)]
zero = []

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

back(0)