백준 22.01.30. 2580번 - 스도쿠

sudoku = []
blank = []

for i in range(9):
    sudoku.append(list(map(int, input().strip().split())))

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


def CheckRow(x, val):
    for i in range(9):
        if sudoku[x][i] == val:
            return False
    return True


def CheckCol(y, val):
    for i in range(9):
        if sudoku[i][y] == val:
            return False
    return True


def CheckSquare(x, y, val):
    startX = x // 3 * 3
    startY = y // 3 * 3
    for i in range(3):
        for j in range(3):
            if sudoku[startX + i][startY + j] == val:
                return False
    return True


def DFS(idx):
    if idx == len(blank):
        for i in range(9):
            print(*sudoku[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 CheckSquare(x, y, i):
            sudoku[x][y] = i
            DFS(idx + 1)
            sudoku[x][y] = 0


DFS(0)

• 스도쿠의 규칙은 1~9의 숫자가 같은 행, 열, 3x3 정사각형 안에 중복되지 않으면 됩니다
• 스도쿠의 경우엔 이차원 배열인 좌표(x, y)에 값(value)이 주어집니다.
• sudoku[1][3] = 7 과 같은 형식입니다.
• 따라서 CheckCol, CheckRow, CheckSquare 함수를 생성하여 중복여부를 판단했습니다.
• CheckSquare의 startX, strartY는 3x3인 정사각형의 리스트 내에서의 인덱스를 고려하여 도출해낸 인덱스입니다.
• 이어서 for반복문에 따라 스도쿠의 빈칸에 1~9의 수를 넣어가며 Col, Row, Square중복여부를 판단하고 적합하다면 재귀로 다음 칸의 값 탐색을 시작합니다.
• 알고리즘이 틀렸을 때를 위해 재귀 이후에는 검색했던 칸의 값을 다시 0으로 초기화시켜줍니다.