심심해서 만들어본 스도쿠입니다.
만들고나서 다른 풀이를 찾아보면서 백트래킹(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
작심삼주 오블완 챌린지
오늘 블로그 완료! 21일 동안 매일 블로그에 글 쓰고 글력을 키워보세요.
www.tistory.com
'게임 개발' 카테고리의 다른 글
[유니티] 크기 조절할 때 중심 고정하는 법 (0) | 2025.01.27 |
---|---|
[Web] 스도쿠 구현하기 마지막 (0) | 2024.11.15 |
[Web] 스도쿠 구현하기 (4) | 2024.11.14 |
[Python] 스도쿠 만들기 (다른 방식) (1) | 2024.11.12 |
게임 개발 일지 # 1 Pygame (3) | 2024.03.13 |