37. Sudoku Solver

https://leetcode.com/problems/sudoku-solver/description/?envType=featured-list&envId=top-google-questions

input :

• board

output :

• 현재 주어진 스도쿠를 해결하시오.

조건 :

• 반환 값 없이 주어진 board 변수를 변화하시오.

---

Solution explain : Solution1

idea

• 우선적으로 생각한 아이디어
• 숫자를 넣어야 하는 빈칸들을 찾는다.
• 해당 위치에 넣을 수 있는 숫자들을 찾는다. (행, 열, 작은 사각형의 모든 숫자들을 체크하면서)
• 넣을 수 있는 숫자들을 하나씩 넣어보며 다른 위치에서도 위의 행동을 수행한다.
  
  
• Base case를 만드는 것이 복잡 했던 것 같다.
• 정답 base case : 더 이상 비어 있는 위치가 없다.
• valid가 False : 현재 위치에 넣었던 값을 초기화 하고 다시 넣을 수 있는 숫자를 넣기.
  
  
• 수도 코드 순서
• 비어 있는 공간을 찾는다.
• 넣을 수 있는 숫자 범위인 1 ~ 9까지를 다 넣어본다.
• 스도쿠 규칙에 적절하다면 해당 값을 넣고 답을 찾는 재귀를 수행한다.
• 모든 재귀가 다 돌았다면 True를 반환한다.
• 그렇지 않다면 해당 값을 초기화 하고 다시 숫자를 넣어본다.

주의

• 시간 초과 : 재귀 함수의 base case를 잘 작성했는지가 문제일 것
• 메모리 초과 : 재귀함수의 파라미터를 사용했다면 그것이 문제일 것
• 답이 언제나 1개는 존재하니까 위의 코드를 수행하면 된다.

from typing import List


class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        def check_valid(x, y, target):
            # row check
            for i in range(9):
                value = board[x][i]
                if value == target:
                    return False

            # col check
            for i in range(9):
                value = board[i][y]
                if value == target:
                    return False

            start_x = (x // 3) * 3
            start_y = (y // 3) * 3
            for dx in range(3):
                for dy in range(3):
                    value = board[start_x + dx][start_y + dy]
                    if value == target:
                        return False
            return True

        def vacant():
            for x in range(9):
                for y in range(9):
                    if board[x][y] == ".":
                        return x, y
            return -1, -1
        def recursive():
            x, y = vacant()
            if x == -1 and y == -1:
                return True

            for item in range(1, 10):
                if check_valid(x, y, f"{item}"):
                    board[x][y] = f"{item}"
                    if recursive():
                        return True
                board[x][y] = "."

        recursive()

s = Solution()
print(s.solveSudoku([["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"]]))