[백준 2239번] 파이썬 - 스도쿠

http://www.acmicpc.net/problem/2239

2239번: 스도쿠

 

 

# 조건

• 스도쿠는 매우 간단한 숫자 퍼즐이다.
• 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다.
• 예를 들어 다음을 보자.

 

• 위 그림은 참 잘도 스도쿠 퍼즐을 푼 경우이다.
• 각 행에 1부터 9까지의 숫자가 중복 없이 나오고, 각 열에 1부터 9까지의 숫자가 중복 없이 나오고, 각 3×3짜리 사각형(9개이며, 위에서 색깔로 표시되었다)에 1부터 9까지의 숫자가 중복 없이 나오기 때문이다.
• 하다 만 스도쿠 퍼즐이 주어졌을 때, 마저 끝내는 프로그램을 작성하시오.

 

입력

• 9개의 줄에 9개의 숫자로 보드가 입력된다. 아직 숫자가 채워지지 않은 칸에는 0이 주어진다.

 

출력

• 9개의 줄에 9개의 숫자로 답을 출력한다. 답이 여러 개 있다면 그 중 사전식으로 앞서는 것을 출력한다. 즉, 81자리의 수가 제일 작은 경우를 출력한다.

 

# 접근 방법

• 모든 경우의 수를 dfs로 탐색한다면 시간 초과가 날 것
• 따라서, 백트래킹을 통하여 현재 입력한 경우가 스도쿠 퍼즐을 완성하지 못한다면 그만 두고 다른 경우의 수를 찾아본다.
• 우선, 0 -> 채워지지 않은 좌표들을 추출
• 해당 칸에 들어갈 수 있는 숫자 추출
• 후보 숫자들을 순서대로 대입하며 재귀를 돌린다.
• 이 때, 재귀의 깊이가 0의 개수보다 깊어진다면 문제가 풀렸다는 얘기이므로 스도쿠 판 출력 후 종료

 

pypy 통과

import sys
input = sys.stdin.readline


def puzzle(n):
    if n == len(empty):
        for i in sudoku:
            print(*i, sep="")
        sys.exit()

    x, y = empty[n]
    a, b = x // 3, y // 3
    number2 = number[:]


    # 3*3 박스 후보 숫자 골라주기
    for i in range(3*a, (a+1)*3):
        for j in range(3*b, (b+1)*3):
            if sudoku[i][j] in number2:
                number2.remove(sudoku[i][j])

    # 가로 세로
    for i in range(9):
        if sudoku[x][i] in number2:
            number2.remove(sudoku[x][i])
        if sudoku[i][y] in number2:
            number2.remove(sudoku[i][y])

    for i in number2:
        sudoku[x][y] = i
        puzzle(n+1)
    sudoku[x][y] = 0



sudoku = [[*map(int, list(input().rstrip()))] for _ in range(9)]
empty = [(i,j) for i in range(9) for j in range(9) if not sudoku[i][j]]
number = [i for i in range(1,10)]

puzzle(0)

 

python3 통과

 

• 각 빈 칸에 넣을 수 있는 숫자들을 간소화해주었다.
• boardRow, boardCol, boardSquare: 각 행, 각 열, 각 정사각형에 들어갈 수 있는 숫자를 표시하는 배열
  • 각 빈칸에서 위의 배열의 값이 모두 True인 숫자만 넣을 수 있다.

def getPromisingNums(r, c):  
    global boardRow, boardCol, boardSquare  
    return [n for n in range(1, 10) if boardRow[r][n] and boardCol[c][n] and boardSquare[(r // 3) * 3 + (c // 3)][n]]  
  
  
def backtracking(depth):  
    global board, blanks, isEnd, boardRow, boardCol, boardSquare  
  
    if isEnd:  
        return  
  
    if depth == len(blanks):  
        isEnd = True  
        for row in board:  
            for x in row:  
                print(x, end='')  
            print()  
        return  
  
    r, c = blanks[depth]  
    for n in getPromisingNums(r, c):  
        boardRow[r][n] = False  
        boardCol[c][n] = False  
        boardSquare[(r // 3) * 3 + (c // 3)][n] = False  
        board[r][c] = n  
        backtracking(depth + 1)  
        boardRow[r][n] = True  
        boardCol[c][n] = True  
        boardSquare[(r // 3) * 3 + (c // 3)][n] = True  
        board[r][c] = 0  
  
  
  
board = []  
blanks = []  
isEnd = False  
  
boardRow, boardCol, boardSquare = [[True] * 10 for _ in range(9)], [[True] * 10 for _ in range(9)], [[True] * 10 for  
                                                                                                     _ in range(9)]  
  
for i in range(9):  
    tmp = list(map(int, list(input())))  
    board.append(tmp)  
    for j in range(9):  
        here = tmp[j]  
        if here == 0:  
            blanks.append((i, j))  
        else:  
            boardRow[i][here] = False  
            boardCol[j][here] = False  
            boardSquare[(i // 3) * 3 + (j // 3)][here] = False  
  
backtracking(0)