[Python] 스도쿠 만들기 (다른 방식)

저번 코드는 처음부터 하나하나 다 만들어야해서 많은 시도를 해야했습니다.

하지만 이번에는 미리 정해진 수를 집어넣어봤습니다.

 

from random import *
import sys

sys.setrecursionlimit(100000000)

board = [[0 for i in range(9)] for i in range(9)] # 9 x 9 크기
row = [[0 for i in range(10)] for i in range(9)] # 편의성을 위해 0번째는 사용 x
col = [[0 for i in range(10)] for i in range(9)]
diag = [[0 for i in range(10)] for i in range(9)]
end = False

def board_init():
    nums = [i for i in range(1, 10)]
    shuffle(nums)
    idx = 0
    for i in range(0, 9, 3):
        for j in range(0, 9, 3):
            board[i][j] = nums[idx]
            row[i][nums[idx]] = 1
            col[j][nums[idx]] = 1
            diag[(i // 3) * 3 + (j // 3)][nums[idx]] = 1
            idx += 1

def fill_board(k):
    global end

    if k >= 81:
        end = True
        return

    i, j = k // 9, k % 9
    if board[i][j] != 0:
        fill_board(k+1)
        return
    
    for n in range(1, 10):
        if row[i][n] == 0 and col[j][n] == 0 and diag[(i // 3) * 3 + (j // 3)][n] == 0:
            board[i][j] = n
            row[i][n], col[j][n], diag[(i // 3) * 3 + (j // 3)][n] = 1, 1, 1
            fill_board(k+1)
            if end:
                return
            board[i][j] = 0
            row[i][n], col[j][n], diag[(i // 3) * 3 + (j // 3)][n] = 0, 0, 0
            
board_init()
fill_board(0)

for row in board:
    print(row)

 

저번 코드와 비교해보겠습니다.

저번 코드의 1000번 반복 결과 나온 반복 횟수의 평균값입니다.

이번 코드의 1000번 반복 결과 나온 반복 횟수의 평균값입니다.

 

의외로 저번 코드가 훨씬 효율이 좋군요.

제 생각으로는 저번 코드에서는 한 줄을 천천히 메워나가는 방식으로 오류의 발생과 미리 섞어놓고 이를 배열하는 것 뿐이라서 적었다고 생각이 드네요.

이번 코드는 정말 사소한 부분때문에 시간이 많이 걸렸던 것 같습니다.

그래도 재밌는 프로젝트였습니다.