스도쿠 (2580번) - 백준 (BOJ)

https://www.acmicpc.net/problem/2580

2580번: 스도쿠

 

 

백준 - 스도쿠 (2580번)

 

난이도 : Gold 4

알고리즘&자료구조 : Backtracking (백트래킹)

 

 

class Sudoku():
    def __init__(self):
        self.board = [list(map(int, input().split())) for _ in range(9)]
        self.init_memo()
        self.backtrack(0)
        
        
    def init_memo(self):
        board = self.board
        rmemo = [[False]*10 for _ in range(9)]
        cmemo = [[False]*10 for _ in range(9)]
        bmemo = [[False]*10 for _ in range(9)]
        es = []
        for r in range(9):
            for c in range(9):
                cur = board[r][c]
                if cur:
                    rmemo[r][cur] = True
                    cmemo[c][cur] = True
                    bmemo[(r//3)*3 + (c//3)][cur] = True
                else:
                    es.append((r, c))
        self.rmemo, self.cmemo, self.bmemo = rmemo, cmemo, bmemo
        self.es, self.esl = es, len(es)

    
    def backtrack(self, i):
        if i == self.esl:
            return True
        r, c = self.es[i]
        for x in range(1, 10):
            if not self.rmemo[r][x] and not self.cmemo[c][x] and not self.bmemo[(r//3)*3 + (c//3)][x]:
                self.board[r][c] = x
                self.rmemo[r][x] = self.cmemo[c][x] = self.bmemo[(r//3)*3 + (c//3)][x] = True
                if self.backtrack(i+1):
                    return True
                self.rmemo[r][x] = self.cmemo[c][x] = self.bmemo[(r//3)*3 + (c//3)][x] = False
                self.board[r][c] = 0
                

if __name__ == '__main__':
    sudoku = Sudoku()
    print('\n'.join(' '.join(map(str, row)) for row in sudoku.board))

 

 

스도쿠 문제를 백트래킹으로 풀면 된다.

 

---

 

▶ 어떤 숫자가 특정 위치에 들어가기 위해서는,

해당 행 / 열 / 3*3 박스 안에 그 숫자가 들어있으면 안된다.

 

따라서, 이를 확인하기 위한 rmemo, cmemo, bmemo 를 만들어줬다.

 

 

▶ 0으로 표시된 빈 칸의 좌표를 es 에 담아두고,

백트래킹을 통해 숫자를 하나씩 넣어보면서,

모든 빈 칸이 채워질 때, 그 상태를 반환하면 그것이 정답이 된다.