Leetcode 37 스도쿠 문제 풀이 정리

https://leetcode.com/problems/sudoku-solver/

Sudoku Solver - LeetCode

---

예전에 코딩테스트에서 만났다가 땅만 팠던 스도쿠 문제를 ㅜㅠㅜㅠ Leetcode에서 다시 만났습니다 

스도쿠의 규칙을 어떤 식으로 적용했는지를 중심으로 여러 풀이를 분석해보겠습니다

 

---

깔끔한 Back Tracking 풀이 )

class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        assert(self.backtrack(board, 0, 0))
        return
                    
    def backtrack(self, board: List[List[str]], r: int, c: int) -> bool:
        # Go to next empty space
        while board[r][c] != '.':
            c += 1
            if c == 9: c, r = 0, r+1
            if r == 9: return True
        # Try all options, backtracking if not work
        for k in range(1, 10):
            if self.isValidSudokuMove(board, r, c, str(k)):
                board[r][c] = str(k)
                if self.backtrack(board, r, c):
                    return True
        board[r][c] = '.'
        return False
    
    def isValidSudokuMove(self, board: List[List[str]], r: int, c: int, cand: int) -> bool:

        if any(board[r][j] == cand for j in range(9)): return False

        if any(board[i][c] == cand for i in range(9)): return False

        br, bc = 3*(r//3), 3*(c//3)
        if any(board[i][j] == cand for i in range(br, br+3) for j in range(bc, bc+3)): return False
        return True

 

어떻게 코드를 이렇게 깔끔하게 짰나 싶은 코드인데요

isValidSudokuMove에서 스도쿠의 규칙을 준수하는지를 확인하고 backtrack에서 규칙이 적용되는 경우에만

board를 채워나가도록 했습니다.

 

스도쿠 문제에서 가장 난감했던 9개칸(부분적인 사각형)을 점검하는 부분은

br = 3*(r//3) 으로 1-3, 3-6, 6-9 이렇게 3칸씩을 기준으로 분리되도록 했습니다.

그리고 부분적인 사각형내에서 중복되는 1-9까지의 숫자가 없도록 any 문 안에 2개의 for loop list comprehension을 통해서 점검을 했습니다.

 

가장 인상깊었던 부분이, isValidSudoku를 만족하는 board[r][c] = str(k)로 채워놓고 다시 스도쿠를 풀었을 때, 스도쿠의 규칙을 따를 수 없으면, 기존에 채웠던 board[r][c] = '.' 로 다시 공란으로 만들고 False를 반환하며 backtracking하도록 구성했습니다 !!