Leetcode 37. Sudoku Solver with Python

문제

Write a program to solve a Sudoku puzzle by filling the empty cells.

주어진 스도쿠를 해결하는 코드를 작성하세요

예시

Input: board = [
["5","3",".",".","7",".",".",".","."],
["6",".",".","1","9","5",".",".","."],
[".","9","8",".",".",".",".","6","."],
["8",".",".",".","6",".",".",".","3"],
["4",".",".","8",".","3",".",".","1"],
["7",".",".",".","2",".",".",".","6"],
[".","6",".",".",".",".","2","8","."],
[".",".",".","4","1","9",".",".","5"],
[".",".",".",".","8",".",".","7","9"]]
Output: [
["5","3","4","6","7","8","9","1","2"],
["6","7","2","1","9","5","3","4","8"],
["1","9","8","3","4","2","5","6","7"],
["8","5","9","7","6","1","4","2","3"],
["4","2","6","8","5","3","7","9","1"],
["7","1","3","9","2","4","8","5","6"],
["9","6","1","5","3","7","2","8","4"],
["2","8","7","4","1","9","6","3","5"],
["3","4","5","2","8","6","1","7","9"]]

제한

• board.length == 9
• board[i].length == 9
• board[i][j] is a digit or '.'
• 정답은 단 한개만 존재한다.

풀이

백트래킹을 사용한다.

비어있는 숫자들의 위치를 전부 저장 한뒤

1 ~ 9 까지 집어 넣어보고

그중 하나가 되면, 다음 숫자를 보는데

만약 1부터 9까지 아무것도 안된다면 그 칸은 비우고

이전 칸으로 되돌아가 이전칸의 숫자에서 다시 1씩 늘려 이전 칸의 숫자를 바꾼 뒤

다시 돌아와 1부터 9까지 확인한다.

def checkcorrect(board: List[List[str]], row, col):
    c = set()
    r = set()
    b = set()
    for i in board[row]:
        if i == '.': continue
        if i in r: return False
        r.add(i)
    for j in range(9):
        if board[j][col] == '.': continue
        if board[j][col] in c: return False
        c.add(board[j][col])
    trow = (row // 3) * 3
    tcol = (col // 3) * 3
    for i in range(trow, trow + 3):
        for j in range(tcol, tcol + 3):
            if board[i][j] == '.': continue
            if board[i][j] in b: return False
            b.add(board[i][j])
    return True

def sudoku(board: List[List[str]], empty, n):
    if n >= len(empty): 
        return 1
    for i in range(1, 10):
        board[empty[n][0]][empty[n][1]] = str(i)
        if checkcorrect(board, empty[n][0], empty[n][1]):
            x = sudoku(board, empty, n+1)
            if x == 1: return 1
        board[empty[n][0]][empty[n][1]] = '.'



class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        empty = list()
        for i in range(9):
            for j in range(9):
                if board[i][j] == '.':
                    empty.append([i, j])
        sudoku(board, empty, 0)