백준 4056번 - 스-스-스도쿠

 

4056번: 스-스-스도쿠

 - 문제 설명 - 

 

스-스-스도쿠 문제는  백트래킹을 활용하여 스도쿠를 풀어내는 문제입니다. 

 

백준 2580번 문제와 비슷하지만, 스도쿠가 만들어질 수 있는 경우만 만들어지는 2580번 스도쿠 문제와는 다르게 스-스-스도쿠는 스도쿠를 만들지 못하는 경우도 생깁니다.

 

스도쿠를 만드는 백트래킹 코드를 먼저 작성하고, 스도쿠를 만들지 못 할 경우를 조건으로 추가로 달아주면 되는 문제였습니다.

 

 

 복습할 문제 선정 이유 :

• 스도쿠를 만들지 못 할 경우를 체크했다고 생각하여 계속 틀린 답을 선택하게 되었습니다. 
• 처음에는 스도쿠를 푸는 로직을 백트래킹으로 수월하게 푸는 방법을 복습하려고 하였으나, 틀린 경우를 생각하는 습관도 기르고자 복습할 문제로 선정하였습니다.

** 코드는 더보기 칸을 눌러서 확인해주세요 **

 

1. 스도쿠를 풀어내는 로직 만들기

• 스도쿠의 빈 칸을 채워넣기 위해선 그 자리의 행과, 열과, 작은 사각형에 해당 칸의 값이 들어가지 않는 경우에 넣을 수 있습니다. 행, 열, 작은 사각형의 숫자들을 체크할 리스트를 만듭니다.

# 1. 9개 행의 숫자 입력받기
    sudoku = [list(map(int, input())) for _ in range(9)]
# 스도쿠에서 체크해야할 세가지
    r_check = [[False] * 10 for _ in range(9)]  # 가로 안에 들어갈 수 있는 숫자 체크하기 0~8번줄에 1~9까지의 숫자
    c_check = [[False] * 10 for _ in range(9)]  # 세로 안에 들어갈 수 있는 숫자 체크하기
    s_check = [[False] * 10 for _ in range(9)]  # 작은 사각형 안에 들어갈 수 있는 숫자 체크하기

 

• 스도쿠를 한 바퀴 돌면서 0이 아닌 숫자가 있는 경우 해당 칸의 행, 열, 작은 사각형에 숫자가 있다고 체크를 해줍니다. 이왕 한 번 반복하는김에 0인 경우도 나중에 백트래킹 처리를 위해 스택에 값을 넣어줍니다.

stack = []
# 스도쿠 돌면서 체크리스트 채워주기
    for i in range(9):
        for j in range(9):
            val = sudoku[i][j]
            if val != 0 :
                    r_check[i][val] = True  # i행 숫자 체크
                    c_check[j][val] = True  # j열 숫자도 체크
                    # 작은 사각형은 i//3*3 + j//3 번째 사각형이 된다
                    s_check[i // 3 * 3 + j // 3][val] = True
            else : # 0이 아닌 경우 백트래킹을 돌려야하므로 스택에 넣어준다
                stack.append((i, j))

 

• 스도쿠의 0인 칸들을 돌면서 백트래킹 실행 만약 True값 하나 찾았으면 다른 값들을 찾을 필요가 없는 backtracking을 만듭니다.
• 0이 존재하는 칸에 1~9를 넣어봅니다. 이 때 1~9까지 가능한 지 체크하기 위해서 이전에 만들어두었던 값들을 활용합니다.
• 스도쿠를 완성하지 못해 되돌아 왔을 경우, 넣어봤던 수들의 행, 열, 작은사각형 체크들은 다시 False로 바꿔주어야 한다는 것을 잊지 않습니다.

def backtracking(level):
    # 1. 종료조건
    if level == len(stack):
        return True
    else:
        for j in range(1, 10):  # 1~9까지의 숫자 넣어보기
            r, c = stack[level]  # r번째행 c번째 열에 있는 0 채워주기
            if not r_check[r][j] and not c_check[c][j] and not s_check[r//3*3 + c//3][j]:
                sudoku[r][c] = j  # 0 채워넣고
                r_check[r][j] = True  # 모든 행과 열과 작은사각형 방문처리 해준 뒤
                c_check[c][j] = True
                s_check[r // 3 * 3 + c // 3][j] = True
                if backtracking(level + 1):  # 다음 0 찾기(만약 찾아서 True 를 반환했으면 return True
                    return True
                else:  # 만약 다음 0을 못 찾고 돌아왔으면 다음 값을 넣어야하므로 모두 초기화
                    sudoku[r][c] = 0
                    r_check[r][j] = False
                    c_check[c][j] = False
                    s_check[r // 3 * 3 + c // 3][j] = False
    return False

 

 

 

2. 스도쿠가 가능하지 않은 경우 체크해주기

• 스도쿠가 불가능한 경우는 backtracking에서 True값을 반환하지 못하는 경우입니다. 

if backtracking(0) :
        for i in sudoku :
            print("".join(map(str, i)))
else :
    print("Could not complete this grid.")
print()

• 이렇게 처리해주고 다 풀었다~ 생각하면서 제출을 하면 틀렸습니다! 라는 문구를 볼 수 있어요.

• 스도쿠가 불가능 한 경우는 이렇게 넣을 수 있는 숫자가 없는 경우도 있지만, 문제 자체가 잘못 됐을 경우에도 스도쿠를 만들 수 없다는 것을 간과했습니다.
• 주어진 스도쿠 문제를 반복문으로 돌릴 때, 해당 열, 행, 작은 사각형에 숫자를 체크해주고, True로 바꿔주었습니다. 백트래킹을 할 때와 마찬가지로 처음에 보드에 스도쿠 문제로 주어진 숫자를 채워줄 때도, 숫자가 들어갈 수 있는지 체크를 해주어야합니다.
• 스도쿠 문제를 만들기 전에 조건을 걸어두어 불가능 한 경우 check 값을 추가해줍니다.

if not r_check[i][val] or not c_check[j][val] or not s_check[i // 3 * 3 + j // 3][val] :
                check = False
                break

 

 

최종 코드 

 

def backtracking(level):
    # 1. 종료조건
    if level == len(stack):
        return True
    else:
        for j in range(1, 10):  # 1~9까지의 숫자 넣어보기
            r, c = stack[level]  # r번째행 c번째 열에 있는 0 채워주기
            if not r_check[r][j] and not c_check[c][j] and not s_check[r//3*3 + c//3][j]:
                sudoku[r][c] = j  # 0 채워넣고
                r_check[r][j] = True  # 모든 행과 열과 작은사각형 방문처리 해준 뒤
                c_check[c][j] = True
                s_check[r // 3 * 3 + c // 3][j] = True
                if backtracking(level + 1):  # 다음 0 찾기(만약 찾아서 True 를 반환했으면 return True
                    return True
                else:  # 만약 다음 0을 못 찾고 돌아왔으면 다음 값을 넣어야하므로 모두 초기화
                    sudoku[r][c] = 0
                    r_check[r][j] = False
                    c_check[c][j] = False
                    s_check[r // 3 * 3 + c // 3][j] = False
    return False


T = int(input())

for tc in range(1, T + 1):
    # 1. 9개 행의 숫자 입력받기
    sudoku = [list(map(int, input())) for _ in range(9)]

    # 스도쿠에서 체크해야할 세가지
    r_check = [[False] * 10 for _ in range(9)]  # 가로 안에 들어갈 수 있는 숫자 체크하기 0~8번줄에 1~9까지의 숫자
    c_check = [[False] * 10 for _ in range(9)]  # 세로 안에 들어갈 수 있는 숫자 체크하기
    s_check = [[False] * 10 for _ in range(9)]  # 작은 사각형 안에 들어갈 수 있는 숫자 체크하기
    # 스도쿠에서 0인 곳 체크하기
    stack = []
    check = True
    # 스도쿠 돌면서 체크리스트 채워주기
    for i in range(9):
        for j in range(9):
            val = sudoku[i][j]
            if r_check[i][val] == True or c_check[j][val] == True or s_check[i // 3 * 3 + j // 3][val] == True :
                check = False
                break
            if val != 0 :
                r_check[i][val] = True  # i행 숫자 체크
                c_check[j][val] = True  # j열 숫자도 체크
                # 작은 사각형은 i//3*3 + j//3 번째 사각형이 된다
                s_check[i // 3 * 3 + j // 3][val] = True
            else:  # 0이면 스택에 넣어주기
                stack.append((i, j))
    if backtracking(0) and check :
        for i in sudoku :
            print("".join(map(str, i)))
    else :
        print("Could not complete this grid.")
    print()