[Python] 스도쿠 만들기

심심해서 만들어본 스도쿠입니다.

만들고나서 다른 풀이를 찾아보면서 백트래킹(Backtracking)에 대해 알게되었는데

간단히 설명하자면 무조건 불가능한 경우의 수들을 없에 무작정 모든 경우의 수를 다루는 것보단 빠르게 하는 알고리즘입니다. 스도쿠나 다른 경우의 수를 다루는 것에서 많이 쓰이니 한번씩 알고가시면 좋을 듯 합니다.

 

from random import sample
import sys

sys.setrecursionlimit(2000)

map = [[0 for _ in range(9)] for _ in range(9)]

def is_safe(map, row, col, num):
    if map[row].count(num) > 0:
        return False
    if [row[col] for row in map].count(num) > 0:
        return False # 행
    s_row = 3 * (row // 3)
    s_col = 3 * (col // 3)
    for i in range(3):
        for j in range(3):
            if map[s_row + i][s_col + j] == num:
                return False
    return True
tries = 0
def fill_col(row):
        global tries
        nums = sample(range(1, 10), 9) # 1 ~ 9 숫자 섞은 리스트
        for col in range(9):
            tries += 1
            index = 0
            try:
                while not is_safe(map, row, col, nums[index]):
                    index += 1
                map[row][col] = nums[index]
                del nums[index]
            except:
                map[row] = [0 for _ in range(9)] # 오류 시 초기화
                fill_col(row) # 재귀
                break
        return map

# 3가지 조건으로 한 칸씩 배치 1. 열에 1개밖에 없는가? 2. 행에 1개밖에 없는가? 3. 3x3크기에서 1개밖에 없는가?
for row in range(9):
    a = fill_col(row) # 확인용
    print("\n")
    for line in a:
        print(line)

print(f"\nresult | tries : {tries}\n")
for row in map:
    print(row)

https://www.tistory.com/event/write-challenge-2024

작심삼주 오블완 챌린지