import time
import numpy as np
from scipy import stats
import matplotlib.pyplot as plt
# Backtracking Sudoku naïf (déterministe)
def _valid(g, r, c, n):
for i in range(9):
if g[r][i] == n or g[i][c] == n:
return False
br, bc = 3 * (r // 3), 3 * (c // 3)
for i in range(3):
for j in range(3):
if g[br + i][bc + j] == n:
return False
return True
def solve_naive(g):
for r in range(9):
for c in range(9):
if g[r][c] == 0:
for n in range(1, 10):
if _valid(g, r, c, n):
g[r][c] = n
if solve_naive(g):
return True
g[r][c] = 0
return False
return True
# Solution complète valide (pour générer des puzzles reproductibles)
_SOLUTION = [[5,3,4,6,7,8,9,1,2],[6,7,2,1,9,5,3,4,8],[1,9,8,3,4,2,5,6,7],
[8,5,9,7,6,1,4,2,3],[4,2,6,8,5,3,7,9,1],[7,1,3,9,2,4,8,5,6],
[9,6,1,5,3,7,2,8,4],[2,8,7,4,1,9,6,3,5],[3,4,5,2,8,6,1,7,9]]
# Un puzzle (37 clues, reproductible) en masquant 44 cellules
def make_puzzle(seed, k_remove=44):
rng = np.random.default_rng(seed)
g = [row[:] for row in _SOLUTION]
for m in rng.choice(81, size=k_remove, replace=False):
r, c = divmod(int(m), 9)
g[r][c] = 0
return g
puzzle_A = make_puzzle(seed=1000)
# 30 exécutions du MÊME puzzle par le MÊME solveur déterministe
times_A = []
for _ in range(30):
g = [row[:] for row in puzzle_A]
t0 = time.perf_counter()
solve_naive(g)
times_A.append(time.perf_counter() - t0)
times_A = np.array(times_A) * 1000 # en millisecondes
print(f"30 runs du meme puzzle, solveur deterministe :")
print(f" min={times_A.min():.3f} ms max={times_A.max():.3f} ms "
f"moyenne={times_A.mean():.3f} ms ecart-type={times_A.std():.3f} ms")
print(f" coefficient de variation = {times_A.std()/times_A.mean()*100:.0f} %")
print(f" ratio max/min = {times_A.max()/times_A.min():.1f}x")
fig, ax = plt.subplots(figsize=(7, 3.6))
ax.hist(times_A, bins=15, color="#9ecae1", edgecolor="white", linewidth=0.4)
ax.axvline(times_A.mean(), color="#d62728", lw=2, label=f"moyenne = {times_A.mean():.3f} ms")
ax.set_xlabel("Temps d'exécution (ms)")
ax.set_ylabel("Nombre de runs (sur 30)")
ax.set_title("Bruit du système : 30 runs d'un solveur déterministe sur 1 puzzle")
ax.legend(fontsize=9)
plt.tight_layout()
plt.show()
print("\nLecture : meme en déterministe, le temps varie d'un facteur non négligeable.")
print("Un seul chronométrage n'est PAS une mesure fiable.")
