[알고리즘] Valid Sudoku && Sudoku Solver

포인트

• 오늘은 스도쿠 문제를 관련해서 풀어보았습니다. 스도쿠가 제대로 맞는지 증명을 하는 방법과 스도쿠가 비어있을 때, 스도쿠를 채울 수 있는 그런 방법의 문제입니다. 
• 특히, 재귀하는 방식을 이해하시면 도움이 되실 것 같습니다.
  비어있는 칸 찾아서 -> 숫자 채워보고 -> 아니면 돌아와서 -> 다시 비어두고 -> 숫자 채워보고

🧶문서는 항상 수정될 수 있습니다. 비판은 환영합니다. 

python

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        seen = set()
        for row in range(9):
            for col in range(9):
                number = board[row][col]
                if number != '.':
                    if((str(number)+" row " + str(row)) in seen):
                        return False
                    seen.add(str(number)+" row " + str(row))

                    if((str(number)+" col " + str(col)) in seen):
                        return False
                    seen.add(str(number)+" col " + str(col))

                    if((str(number)+" block " + str(row//3)+"-"+str(col//3)) in seen):
                        return False
                    seen.add(str(number)+" block " + str(row//3)+"-"+str(col//3))
                    
        return True

python

class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        if board is None or len(board) == 0:
            return
        # 재귀
        self.solve(board)

    def solve(self, board: List[List[str]]) -> None:
        for row in range(len(board)):
            for col in range(len(board[0])):
                # 2차원을 돈다
                if board[row][col] == '.':
                    for num in range(1, 10):
                        if self.valid(board, row, col, str(num)):
                            board[row][col] = str(num)

                            if self.solve(board):
                                return True
                            else:
                                board[row][col] = '.'

                    return False
        return True

    def valid(self, board: List[List[str]], row: int, col: int, char: str) -> bool:
        for i in range(9):
            if board[row][i] == char:
                return False
            if board[i][col] == char:
                return False
            if board[3 * (row // 3) + i // 3][3 * (col // 3) + i % 3] != '.' and board[3 * (row // 3) + i // 3][3 * (col // 3) + i % 3] == char:
            	# 이런 부분이 다시 채워지는 것을 확인하는 것이 좋다.
                return False
        return True