Leetcode 21th August

Sudoku Solver

이 문제는 9x9 배열의 sudoku 문제 주워지고 그 빈값에 알맞은 답을 적용하는 방식입니다.

This is the problem that return matrix that set correct value

이 경우에도 저는 grid 한 방식으로 9X9 배열을 돌면서 값이 없을 경우 1~9까지의 숫자를 돌면서 해당 답이 valid 할 경우 다음 row, col에 값을 대입하는 형태로 문제를 풀었습니다.

i use previous way for solving this problem, so looping matrix then if the value is empty, i found a correct value from 1 ~9

Python

class Solution:
    N = 9
    def is_valid(self, board, row, col, num):
	    """
	    This function is for checking this board is valid or not
	    :return: boolean
	    """
        # TODO: checking row is valid
        for x in range(9):
            if board[row][x] == num:
                return False
        # TODO: chcking colum in valid
        for x in range(9):
            if board[x][col] == num:
                return False

        # TODO: checking box is valid
        startRow = row - row % 3
        startCol = col - col % 3
        for i in range(3):
            for j in range(3):
                if board[i + startRow][j + startCol] == num:
                    return False
        return True
    def solve(self, board, row, col):
	    """
	    This is the function set correct sudoku value
		"""
        N = self.N
        if row == N -1 and col == N:
            return True

        # if col is same as end of line change col = 0 and row += 1
        if col == N:
            row += 1
            col = 0

        # if has a value in board[row][col] go to next col
        if board[row][col] != '.':
            return self.solve(board, row, col + 1)

        for num in range(1, N + 1):
            num = str(num)
            if self.is_valid(board, row, col, num):
                board[row][col] = num
                if self.solve(board, row, col + 1):
                    return True
            board[row][col] = '.'
        return False
    
    def solveSudoku(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        self.solve(board, 0, 0)