백트랙킹(Sudoku)

백트랙킹을 이용하여 스도쿠 퍼즐을 푸는 문제이다.

 

# Title : Sudoku 풀이
# Chapter : Backtracking
# Link :
# ChapterLink :
# 문제 : 주어진 sudoku를 풀어라 (inplace로서 input object에 답을 넣어라)

# [['. ','5','1','3','. ','9','. ','. ','6'],
# ['. ','2','. ','8','7','1','3','4','5'],
# ['. ','. ','. ','2','. ','. ','. ','. ','. '],
# ['2','1','9','7','6','4','. ','3','. '],
# ['. ','. ','. ','1','3','. ','. ','. ','. '],
# ['7','3','. ','. ','. ','8','. ','6','2'],
# ['5','. ','. ','4','2','. ','. ','. ','3'],
# ['. ','. ','. ','9','1','5','. ','. ','7'],
# ['1','9','. ','. ','. ','. ','2','. ','. ']]

# 답:
# ['8', '5', '1', '3', '4', '9', '7', '2', '6']
# ['9', '2', '6', '8', '7', '1', '3', '4', '5']
# ['4', '7', '3', '2', '5', '6', '8', '9', '1']
# ['2', '1', '9', '7', '6', '4', '5', '3', '8']
# ['6', '8', '5', '1', '3', '2', '4', '7', '9']
# ['7', '3', '4', '5', '9', '8', '1', '6', '2']
# ['5', '6', '8', '4', '2', '7', '9', '1', '3']
# ['3', '4', '2', '9', '1', '5', '6', '8', '7']
# ['1', '9', '7', '6', '8', '3', '2', '5', '4']\

from typing import List

class SudokuSolver:
    def solve(self, sudoku_board : List[List[str]]) -> None:
        self._board = sudoku_board

        next_row, next_col = self.__find_next_empty()
        for i in range(1, 10):
            self.__bt(next_row, next_col, str(i))

    def __check_row(self, row:int, num:str) -> bool:
        for x in range(0, 9):
            if self._board[row][x] == num:
                return False
        return True

    def __check_col(self, col:int, num:str) -> bool:
        for y in range(0, 9):
            if self._board[y][col] == num:
                return False
        return True

    def __check_33(self, row: int, col:int, num:str) ->bool:
        box_x = int(col / 3) *3
        box_y = int(row / 3) *3

        for y in range(box_y, box_y + 3):
            for x in range(box_x, box_x + 3):
                if self._board[y][x] == num:
                    return False
        return True

    def __find_next_empty(self):
        for y in range(0, 9):
            for x in range(0, 9):
                if self._board[y][x] == '.':
                    return [y, x]
        return [9, 9]


    def __bt(self, row: int, col:int, num:str) -> bool:
        if not self.__check_row(row, num):
            return False
        if not self.__check_col(col, num):
            return False
        if not self.__check_33(row, col, num):
            return False

        self._board[row][col] = num
        next_row, next_col = self.__find_next_empty()
        if next_row == 9 and next_col == 9:
            return True
        
        for i in range(1, 10):
            if self.__bt(next_row,next_col, str(i)):
                return True
        
        self._board[next_row][next_col] = '.'
        return False

solver = SudokuSolver()

sudoku_quiz = \
[['.','5','1','3','.','9','.','.','6'],\
['.','2','.','8','7','1','3','4','5'],\
['.','.','.','2','.','.','.','.','.'],\
['2','1','9','7','6','4','.','3','.'],\
['.','.','.','1','3','.','.','.','.'],\
['7','3','.','.','.','8','.','6','2'],\
['5','.','.','4','2','.','.','.','3'],\
['.','.','.','9','1','5','.','.','7'],\
['1','9','.','.','.','.','2','.','.']]
solver.solve(sudoku_quiz)

for row in range ( 0, 9):
  print(sudoku_quiz[row])

 

참조 : (3) 코딩테스트, 상급, 스도쿠 풀기 Sudoku - YouTube