파이썬과 백트래킹 알고리즘을 이용한 스도쿠 구현

 

개요

 

이번 시간에는 백 트래킹 알고리즘에 대해서 알아보도록 하겠습니다.

 

 

또한, 백 트래킹 알고리즘을 이용해서 스도쿠 퍼즐을 만드는 프로그램을 작성 해보도록 하겠습니다.

 

 

백 트래킹(Back Tracking)?

 

 

백 트래킹(Back Tracking)은 단어 뜻 그대로, 되 추적이라는 다시 되돌아가서 되돌아간 자리에서 시작한다는 말입니다.

 

 

어릴 적에 "경우의 수" 문제나, "확률과 통계" 문제를 풀 때를 떠올려 봅시다.

문제를 맨 처음 풀 때, 우리는 종이에 수형도 라고 부르는 나뭇가지를 처음부터 하나씩 그려서 갯수를 전부 세었습니다.

 

 

아니면, 길 찾기 문제를 풀 때 에도, 종이에 거의 모든 경우의 수를 그려서 직접 세서 풀었던 것을 기억 하실겁니다.

 

사실은 모든 경우의 수를 전부 세서 그렸다고 생각을 하고는 있지만,

 

실제로는 문제에서 절대로 안될것 같은 부분을 마주쳤을때, 그 부분은 제외하고(즉, 가지치기를 하고)

다시 수형도를 그렸던 것을 떠올리실 수 있습니다.

 

 

이러한 방식을 백 트래킹(Back Tracking) 이라고 합니다.

 

여기서 핵심은 절대로 안될것 같은 부분을 가지치기 하는것입니다.

이를 통해, 일반적인 무식하게 모든 경우의 수를 다 해보는 알고리즘과는 다르게 꽤 많은 불필요한 중복 탐색을 제거합니다.

 

 

따라서, 상대적으로 모든 경우의 수를 무식하게 다 하는 경우 보다는 빠릅니다.

 

 

보통 백트래킹을 이용해서 N-Queen 문제나, 스도쿠 퍼즐 과 같은 문제를 풀 수 있습니다.

이번 포스팅에서는 백 트래킹 예제로, 파이썬으로 스도쿠 퍼즐을 생성하는 예제를 구현 할 것입니다.

 

 

백 트래킹을 이용한 스도쿠(Sudoku) 생성 프로그램 구현

 

 

해당 예제에서는, 가지치기 방식으로, 각 행/열, 및 3*3 사각형에,

1~9 까지의 숫자가 단 1개씩만 들어있는지를 체크 하는 방식으로 가지치기를 구현하게 됩니다.

 

 

이를 위해, row,col,diag 라는 2차원 리스트를 생성하였고,

이를 통해 각 행/열 및 3*3 사각형에 어떤 숫자가 들어있는지를 바로 파악 할 수가 있게 됩니다.

 

 

 

 

아래는 파이썬으로 백 트래킹 알고리즘을 이용 해서, 스도쿠 퍼즐을 생성 하는 프로그램을 구현한 코드 입니다.

 

import random

origin_board = [[0 for j in range(0,9)] for i in range(0,9)]
board = [[0 for j in range(0,9)] for i in range(0,9)]
row = [[0 for j in range(0,10)] for i in range(0,10)]
col = [[0 for j in range(0,10)] for i in range(0,10)]
diag = [[0 for j in range(0,10)] for i in range(0,10)]

terminate_flag = False

def board_init():
    seq_diag = [0,4,8]
    for offset in range(0,9,3):
        seq = [i for i in range(1,10)]
        random.shuffle(seq)
        for idx in range(0,9):
            i,j = idx//3,idx%3
            row[offset+i][seq[idx]] = 1
            col[offset+j][seq[idx]] = 1
            k = seq_diag[offset//3]
            diag[k][seq[idx]] = 1
            origin_board[offset+i][offset+j] = seq[idx]

def make_sudoku(k):

    global terminate_flag
    global board

    if terminate_flag == True:
        return True

    if k > 80:
        for i in range(0,9):
            for j in range(0,9):
                board[i][j] = origin_board[i][j]
        terminate_flag = True
        return True

    i,j = k//9,k%9
    start_num = random.randint(1,9)

    if origin_board[i][j] != 0:
        make_sudoku(k+1)

    for m in range(1,10):
        m = 1 + (m + start_num)%9
        d = (i//3)*3 + (j//3)
        if row[i][m] == 0 and col[j][m] == 0 and diag[d][m] == 0:
            row[i][m],col[j][m],diag[d][m] = 1,1,1
            origin_board[i][j] = m
            make_sudoku(k+1)
            row[i][m],col[j][m],diag[d][m] = 0,0,0
            origin_board[i][j] = 0

board_init()
make_sudoku(0)

for i in range(0,9):
    print(board[i])

 

 

출력 결과는 아래와 같습니다.

(생성 때마다, 결과가 달라 집니다.)

 

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