A szúdoku egy logikai játék, melyben megadott szabályok szerint számjegyeket kell elhelyezni egy táblázatban.
Legközönségesebb változatában egy 9×9-es táblázat van 3×3 = 9 darab 3×3-as résztáblázatra felosztva, és minden résztáblázatot az 1, 2, 3, 4, 5, 6, 7, 8, 9 számokkal kell kitölteni úgy, hogy az egész 9×9-es táblázat minden sorában és minden oszlopában az 1...9 számok mindegyike egyszer forduljon elő.
A rejtvény készítője a megoldhatóság érdekében előre ki szokta tölteni néhány szükséges számmal a 9×9-es táblázat bizonyos celláit – általában úgy, hogy csak egy megoldása (kitöltése) létezzen a rejtvénynek.
A rejtvényfejtő feladata kitölteni a maradék cellákat a fentebb írt feltételeknek megfelelően. (source: https://hu.wikipedia.org/wiki/Sz%C3%BAdoku)
Szabálya
import numpy as np
def generate_sudoku(mask_rate=0.5):
while True:
n = 9
m = np.zeros((n, n), np.int)
rg = np.arange(1, n + 1)
m[0, :] = np.random.choice(rg, n, replace=False)
try:
for r in range(1, n):
for c in range(n):
col_rest = np.setdiff1d(rg, m[:r, c])
row_rest = np.setdiff1d(rg, m[r, :c])
avb1 = np.intersect1d(col_rest, row_rest)
sub_r, sub_c = r//3, c//3
avb2 = np.setdiff1d(np.arange(0, n+1), m[sub_r*3:(sub_r+1)*3, sub_c*3:(sub_c+1)*3].ravel())
avb = np.intersect1d(avb1, avb2)
m[r, c] = np.random.choice(avb, size=1)
break
except ValueError:
pass
print("Answer:\n", m)
mm = m.copy()
mm[np.random.choice([True, False], size=m.shape, p=[mask_rate, 1 - mask_rate])] = 0
print("\nMasked anwser:\n", mm)
np.savetxt("./puzzle.csv", mm, "%d", delimiter=",")
return mm
def solve(m):
if isinstance(m, list):
m = np.array(m)
elif isinstance(m, str):
m = np.loadtxt(m, dtype=np.int, delimiter=",")
rg = np.arange(m.shape[0]+1)
while True:
mt = m.copy()
while True:
d = []
d_len = []
for i in range(m.shape[0]):
for j in range(m.shape[1]):
if mt[i, j] == 0:
possibles = np.setdiff1d(rg, np.union1d(np.union1d(mt[i, :], mt[:, j]), mt[3*(i//3):3*(i//3+1), 3*(j//3):3*(j//3+1)]))
d.append([i, j, possibles])
d_len.append(len(possibles))
if len(d) == 0:
break
idx = np.argmin(d_len)
i, j, p = d[idx]
if len(p) > 0:
num = np.random.choice(p)
else:
break
mt[i, j] = num
if len(d) == 0:
break
if np.all(mt != 0):
break
print("\nTrail:\n", mt)
return mt
def check_solution(m):
if isinstance(m, list):
m = np.array(m)
elif isinstance(m, str):
m = np.loadtxt(m, dtype=np.int, delimiter=",")
set_rg = set(np.arange(1, m.shape[0] + 1))
no_good = False
for i in range(m.shape[0]):
for j in range(m.shape[1]):
r1 = set(m[3 * (i // 3):3 * (i // 3 + 1), 3 * (j // 3):3 * (j // 3 + 1)].ravel()) == set_rg
r2 = set(m[i, :]) == set_rg
r3 = set(m[:, j]) == set_rg
if not (r1 and r2 and r3):
no_good = True
break
if no_good:
break
if no_good:
print("\nChecked: not good")
else:
print("\nChecked: OK")
if __name__ == "__main__":
puzzle = generate_sudoku(mask_rate=0.7)
solved = solve(puzzle)
check_solution(solved)
print("\nSolve in code:")
solve([
[0, 5, 0, 0, 6, 7, 9, 0, 0],
[0, 2, 0, 0, 0, 8, 4, 0, 0],
[0, 3, 0, 9, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 2, 1, 0, 4],
[0, 0, 0, 6, 0, 9, 0, 0, 0],
[0, 0, 8, 5, 0, 0, 6, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 4, 9, 0, 0, 5, 0],
[2, 1, 3, 7, 0, 0, 0, 0, 0]
])
print("\nSolve in csv file:")
solve("puzzle.csv")
Answer: [[7 4 6 3 5 1 9 8 2] [5 8 1 7 9 2 3 4 6] [9 2 3 4 8 6 5 7 1] [3 7 9 2 1 5 8 6 4] [8 6 2 9 4 3 1 5 7] [1 5 4 6 7 8 2 3 9] [2 3 7 5 6 9 4 1 8] [4 9 8 1 3 7 6 2 5] [6 1 5 8 2 4 7 9 3]] Masked anwser: [[0 4 6 0 0 0 0 0 0] [0 0 0 0 0 2 0 4 6] [9 2 3 0 0 0 5 7 0] [0 7 0 2 1 5 8 0 0] [0 6 0 0 0 0 0 5 0] [0 0 0 0 0 8 0 0 0] [0 0 0 0 0 0 0 1 8] [0 9 8 0 3 0 6 0 0] [6 0 0 0 0 0 0 0 3]] Trail: [[7 4 6 3 5 1 2 8 9] [1 8 5 9 7 2 3 4 6] [9 2 3 8 4 6 5 7 1] [3 7 9 2 1 5 8 6 4] [8 6 4 7 9 3 1 5 2] [2 5 1 4 6 8 9 3 7] [5 3 7 6 2 9 4 1 8] [4 9 8 1 3 7 6 2 5] [6 1 2 5 8 4 7 9 3]] Checked: OK Solve in code: Trail: [[8 5 4 2 6 7 9 1 3] [9 2 7 1 3 8 4 6 5] [6 3 1 9 4 5 7 2 8] [5 6 9 3 7 2 1 8 4] [1 4 2 6 8 9 5 3 7] [3 7 8 5 1 4 6 9 2] [4 9 5 8 2 1 3 7 6] [7 8 6 4 9 3 2 5 1] [2 1 3 7 5 6 8 4 9]] Solve in csv file: Trail: [[5 4 6 1 7 3 9 8 2] [1 8 7 5 9 2 3 4 6] [9 2 3 4 8 6 5 7 1] [3 7 9 2 1 5 8 6 4] [8 6 1 3 4 7 2 5 9] [2 5 4 9 6 8 1 3 7] [7 3 5 6 2 9 4 1 8] [4 9 8 7 3 1 6 2 5] [6 1 2 8 5 4 7 9 3]]