[ BOJ ] 2955 : 스도쿠 풀기 ( GOLD 2 ) / Python

 

문제

스도쿠는 가로 9칸, 세로 9칸으로 이루어져 있는 표에 1부터 9까지의 숫자를 채워 넣는 퍼즐이다. 퍼즐을 푸는 방법은 각 가로줄과 세로줄에 1에서 9까지의 숫자를 한 번만 넣고, 3*3칸의 작은 격자에도 1에서 9까지의 숫자를 겹치지 않게 넣어야 한다.

스도쿠를 푸는 방법에는 여러 가지 방법이 있다. 그 중 한가지 방법은 Cross-hatching이다.

Cross-hatching방법을 이용할 때는, 먼저 숫자를 하나 골라야 한다. 그런 뒤에, 그 숫자가 등장하는 가로줄이나 세로줄 또는 3*3 박스에 선을 긋는다. 이렇게 선을 그었을 때, 3*3박스에 고른 숫자가 들어갈 수 있는 칸이 한 칸일 때, 그 숫자를 채우는 것이다.

아래 그림 중 왼쪽 그림은 매우 조금만 숫자가 채워진 스도쿠이고, 오른쪽 그림은 cross-hatching 방법을 이용해서 4가 들어갈 수 있는 곳을 찾은 한가지 예이다.

 

부분적으로 숫자가 채워진 스도쿠 퍼즐이 주어졌을 때, cross-hatching방법만을 이용해서 스도쿠를 푸는 프로그램을 작성하시오. 더이상 이 방법을 이용해서 풀 수 없을 때 까지 스도쿠를 풀어야 한다. 다른 방법을 이용하면 안 된다.

입력으로 주어지는 스도쿠 퍼즐이 규칙을 지키지 않는 경우가 입력으로 주어질 수 있다. (예, 한 가로줄에 1이 2개 있는 경우, 숫자 1이 어떤 가로줄, 3*3박스, 세로줄에 있을 수 있는 곳이 전혀 없는 경우) 이런 경우도 판별해야 한다.

입력

입력은 9개줄로 이루어지며, 각 줄은 9개 문자로 이루어져 있다. 문자는 1~9 숫자 또는 '.'이다. 마침표는 빈 칸을 나타낸다.

출력

올바른 스도쿠 퍼즐이고, 모순이 일어나지 않는다면, 입력과 같은 형식으로 cross-hatching만을 이용해서 푼 결과를 출력한다. 그렇지 않다면 "ERROR"를 출력한다. (쌍따옴표는 출력하지 않는다)

풀이 과정

1. 세로, 가로, 블럭 단위로 이미 사용된 숫자를 기록하고, 만약 같은 숫자가 다중으로 입력된다면 오류로 판정한다.

2. 가로, 세로, 블럭 단위로 이미 사용된 숫자를 제외한 사용할 수 있는 숫자를 메모하고, 블럭 단위에서 만약 채워야 하는 숫자 (쓰지 않은 숫자) 를 쓸 수 없을 때는 오류로 판정하고, 무조건 한 곳에 특정 숫자를 적을 수 있을 때 적는다.

3. 만약 한 턴에 아무것도 적지 않았다면 더 이상 숫자를 채울 수 없다고 판단하여 종료한다.

import sys
input = sys.stdin.readline

maps = [list(input().rstrip()) for _ in range(9)]

while True:
    mosoon = 0
    # Sero - Already Existed
    sero_already = [[] for _ in range(9)]
    for ja in range(9):
        for ia in range(9):
            if maps[ia][ja] != '.':
                if maps[ia][ja] not in sero_already[ja]:
                    sero_already[ja].append(maps[ia][ja])
                else:
                    mosoon = 1

    # Garo - Already Existed
    garo_already = [[] for _ in range(9)]
    for ia in range(9):
        for ja in range(9):
            if maps[ia][ja] != '.':
                if maps[ia][ja] not in garo_already[ia]:
                    garo_already[ia].append(maps[ia][ja])
                else:
                    mosoon = 1

    # Block - Already Existed
    block_already = [[[] for j in range(3)] for i in range(3)]
    for bi in range(3):
        for bj in range(3):
            for ai in range(3):
                for aj in range(3):
                    if maps[bi*3+ai][bj*3+aj] != '.':
                        if maps[bi*3+ai][bj*3+aj] not in block_already[bi][bj]:
                            block_already[bi][bj].append(maps[bi*3+ai][bj*3+aj])
                        else:
                            mosoon = 1

    if mosoon == 1: # if the certain number is already existed
        print('ERROR')
        break

    else:
        # Memo
        memo = [[[] for j in range(9)] for i in range(9)]

        # memo available numbers in sero, garo
        for sero_block in range(3):
            for garo_block in range(3):
                y = sero_block * 3
                x = garo_block * 3

                for block_i in range(3):
                    for block_j in range(3):
                        ny = y + block_i
                        nx = x + block_j

                        if maps[ny][nx] == '.':
                            for num in range(1, 9 + 1):
                                if (str(num) not in sero_already[nx]) and (str(num) not in garo_already[ny]) and (str(num) not in block_already[sero_block][garo_block]):
                                    memo[ny][nx].append(str(num))

        # find available numbers in block with memo
        change_cnt = 0
        for sero_block in range(3):
            for garo_block in range(3):
                block_count = { '1':[0, []], '2':[0, []], '3':[0, []],
                                '4':[0, []], '5':[0, []], '6':[0, []],
                                '7':[0, []], '8':[0, []], '9':[0, []], }
                y = sero_block * 3
                x = garo_block * 3

                for block_i in range(3):
                    for block_j in range(3):
                        ny = y + block_i
                        nx = x + block_j

                        for m in memo[ny][nx]:
                            block_count[m][0] += 1
                            block_count[m][1].append([ny, nx])
                
                for bc in block_count.keys():
                    if bc not in block_already[sero_block][garo_block]:
                        if block_count[bc][0] == 0: # not available number
                            mosoon = 1
                            break
                        elif block_count[bc][0] == 1: # available number ( only 1 ) 
                            maps[block_count[bc][1][0][0]][block_count[bc][1][0][1]] = bc
                            change_cnt += 1
            
                if mosoon == 1: break
            if mosoon == 1: break
        if mosoon == 1:
            print('ERROR')
            break
        else:
            # end ( does not fill )
            if change_cnt == 0:
                for m in maps:
                    print(''.join(m))
                break