Navigation : Index | << Sudoku-16 Python | Sudoku-18 >>
A la fin de ce notebook, vous saurez : - Comprendre les capacites et limites des LLM pour la resolution de Sudoku - Implementer différentes approches : Zero-shot, Few-shot, Chain-of-Thought - Utiliser le LLM comme générateur de code (code interpreter) - Evaluer la performance des LLM vs solveurs algorithmiques
Duree estimee : 30-40 minutes Prerequis : Aucun, connaissance basique des LLM recommandee API requise : OpenAI API ou compatible
try:
import dotenv
import os
dotenv.load_dotenv(dotenv_path='../GenAI/.env')
DOTENV_AVAILABLE = True
except ImportError:
DOTENV_AVAILABLE = False
print("python-dotenv non disponible. Utilisez les variables d'environnement directement.")
print(f"Environnement charge : dotenv={'OK' if DOTENV_AVAILABLE else 'absent'}")Environnement charge : dotenv=OKLe Sudoku est un problème combinatoire qui demande : - Raisonnement logique : Deduction et propagation de contraintes - Explosion combinatoire : 9^81 possibilites théoriques - Precision : Une seule erreur invalide toute la solution
Les LLM (GPT-4, Claude, etc.) sont : - Entraînes sur du code : Connaissent les algorithmes de Sudoku - Capables de raisonnement : Peuvent suivre des étapes logiques - Generatifs : Peuvent ecrire du code pour resoudre le problème
| Approche | Description | Avantages | Inconvenients |
|---|---|---|---|
| Zero-shot | Donner la grille et demander la solution | Simple | Taux d’echec eleve |
| Few-shot | Donner des exemples resolus | Meilleure performance | Consomme des tokens |
| Chain-of-Thought | Demander au LLM d’expliquer sa démarche | Meilleure raisonnement | Plus lent |
| Code Interpreter | Le LLM écrit et execute du code Python | Très fiable | Necessite exécution |
Selon les études récentes (2023-2025) : - GPT-4 : ~30-50% de réussite en zero-shot sur Sudokus difficiles - Claude 3.5 Sonnet : ~40-60% de réussite - Code Interpreter : ~99% de réussite (genere du code valide)
Les solveurs algorithmiques (backtracking, OR-Tools, Z3) restent superieurs en performance et fiabilité.
# Imports et configuration
import os
import json
import time
from pathlib import Path
from typing import List, Optional, Dict
# Configuration du chemin vers les puzzles
NOTEBOOK_DIR = Path(r".")
PUZZLES_DIR = NOTEBOOK_DIR / "Puzzles"
print(f"Dossier Puzzles: {PUZZLES_DIR}")
print(f"Fichiers disponibles: {[f.name for f in PUZZLES_DIR.glob('*.txt')]}")Dossier Puzzles: Puzzles
Fichiers disponibles: ['Sudoku_Easy51.txt', 'Sudoku_hardest.txt', 'Sudoku_top95.txt']Fonctions de chargement et d’affichage des puzzles Sudoku.
# Fonctions de chargement des puzzles
def load_puzzles(filepath: str, max_puzzles: int = None) -> List[str]:
"""Charge les puzzles depuis un fichier."""
puzzles = []
with open(filepath, 'r') as f:
for line in f:
line = line.strip()
if len(line) >= 81:
puzzles.append(line[:81])
if max_puzzles and len(puzzles) >= max_puzzles:
break
return puzzles
def puzzle_to_grid(puzzle_str: str) -> List[List[int]]:
"""Convertit une chaîne de 81 caracteres en grille 9x9."""
return [[int(puzzle_str[i * 9 + j]) if puzzle_str[i * 9 + j] in '123456789' else 0
for j in range(9)] for i in range(9)]
def grid_to_puzzle(grid: List[List[int]]) -> str:
"""Convertit une grille 9x9 en chaîne de 81 caracteres."""
return ''.join(str(grid[i][j]) if grid[i][j] != 0 else '.'
for i in range(9) for j in range(9))
def print_grid(grid: List[List[int]]) -> None:
"""Affiche une grille de Sudoku."""
for i in range(9):
if i % 3 == 0 and i > 0:
print("-" * 21)
row = ""
for j in range(9):
if j % 3 == 0 and j > 0:
row += "| "
val = grid[i][j]
row += str(val) if val != 0 else "."
row += " "
print(row)
def validate_solution(grid: List[List[int]], original: List[List[int]]) -> bool:
"""Verifie qu'une solution est valide."""
# Verifier que les valeurs originales sont preservees
for i in range(9):
for j in range(9):
if original[i][j] != 0 and grid[i][j] != original[i][j]:
return False
# Verifier les lignes
for i in range(9):
if len(set(grid[i])) != 9:
return False
# Verifier les colonnes
for j in range(9):
col = [grid[i][j] for i in range(9)]
if len(set(col)) != 9:
return False
# Verifier les blocs 3x3
for bi in range(3):
for bj in range(3):
block = []
for i in range(3):
for j in range(3):
block.append(grid[bi*3+i][bj*3+j])
if len(set(block)) != 9:
return False
return True
# Charger les puzzles
easy_puzzles = load_puzzles(str(PUZZLES_DIR / 'Sudoku_Easy51.txt'), max_puzzles=5)
hard_puzzles = load_puzzles(str(PUZZLES_DIR / 'Sudoku_hardest.txt'))
print(f"Puzzles faciles charges: {len(easy_puzzles)}")
print(f"Puzzles difficiles charges: {len(hard_puzzles)}")
# Afficher un puzzle exemple
example_grid = puzzle_to_grid(easy_puzzles[0])
print("\nExemple de puzzle facile:")
print_grid(example_grid)Puzzles faciles charges: 5
Puzzles difficiles charges: 11
Exemple de puzzle facile:
9 . 2 | . . 5 | 4 . 3
1 . . | . 6 3 | . 2 5
5 . 8 | 4 . 7 | . 6 .
---------------------
. 2 6 | 3 . 9 | . . 1
. 5 7 | . 1 . | 2 9 .
. 9 . | 6 7 . | 5 3 .
---------------------
2 4 . | 5 3 . | 6 . .
7 . 5 | 2 . . | 3 . 4
. 8 . | . 4 1 | 9 5 . Les données ont ete chargees correctement et nous disposons maintenant de puzzles de différents niveaux de difficulte pour tester les approches LLM.
| Aspect | Valeur | Signification |
|---|---|---|
| Puzzles faciles | 5 charges | Sous-ensemble de Sudoku_Easy51.txt pour tests rapides |
| Puzzles difficiles | 11 charges | Collection Sudoku_hardest.txt pour evaluation finale |
| Puzzle exemple | 45 indices | Niveau de difficulte facile (environ 56% de cases remplies) |
| Format de stockage | Chaîne 81 caractères | Representation compacte (0 pour vide, 1-9 pour valeurs) |
Points cles : 1. Strategy d’echantillonnage : max_puzzles=5 limite les puzzles faciles pour des tests plus rapides 2. Conversion automatique : La fonction puzzle_to_grid() transforme les chaînes en matrices 9x9 3. Affichage structure : La fonction print_grid() ajoute des separateurs visuels pour les blocs 3x3 4. Fichiers disponibles : Trois fichiers de difficultes croissantes (Easy51, hardest, top95)
Note technique : Le puzzle exemple affiche presente 45 indices (cases pre-remplies) sur 81, soit environ 56% du grille. C’est un niveau de difficulte facile : - Facile : 40+ indices (50%+) - Moyen : 30-39 indices (37-48%) - Difficile : 25-29 indices (31-36%) - Expert : 17-24 indices (21-30%)
Validation des contraintes : La fonction
validate_solution()verifie quatre aspects critiques : 1. Preservation des valeurs originales 2. Unicite des valeurs dans chaque ligne 3. Unicite des valeurs dans chaque colonne 4. Unicite des valeurs dans chaque bloc 3x3
Ce notebook supporte plusieurs providers LLM via OpenAI ou des APIs compatibles.
| Provider | Model | Base URL | API Key |
|---|---|---|---|
| OpenAI | gpt-4, gpt-4-turbo | https://api.openai.com/v1 | OPENAI_API_KEY |
| Anthropic | claude-3-5-sonnet | Via SDK | ANTHROPIC_API_KEY |
| OpenRouter | gpt-4, claude-3, etc. | https://openrouter.ai/api/v1 | OPENROUTER_API_KEY |
| z.ai | GLM-5 | https://api.z.ai/api/anthropic | ZAI_API_KEY |
Créer un fichier .env dans le dossier GenAI/ avec :
La bibliotheque openai etant installee, nous pouvons maintenant configurer un client generique qui permet d’appeler différents modèles LLM. Ce client supporte :
LOCAL_LLM_API_KEY est definie, le notebook appelle un vrai modele (compatible OpenAI). Les sorties committees de ce notebook ont ete produites ainsi, avec Qwen3.6-35B-A3B servi par un serveur vLLM local.Cette abstraction nous permettra de comparer facilement les approches sans nous soucier de l’infrastructure d’appel.
Note technique (modele de raisonnement) : Qwen3.6 est un modele de raisonnement. Sans desactiver explicitement le mode “thinking” (
chat_template_kwargs.enable_thinking=False), il consomme l’integralite du budget de tokens en reflexion interne et renvoie un contenu vide. Le client desactive donc ce mode pour obtenir une reponse directe et deterministe (temperature=0.0).
# Configuration du client LLM
# Ce notebook supporte deux modes :
# - Mode API REELLE : quand LOCAL_LLM_API_KEY est definie dans l'environnement,
# le notebook appelle un vrai modele LLM (compatible OpenAI, ex. serveur vLLM local).
# - Mode SIMULATION (fallback) : sans cle, des reponses predefinies permettent
# d'executer le notebook de bout en bout sans infrastructure.
# Les sorties committees dans ce notebook ont ete produites en mode API reelle
# (modele Qwen3.6-35B-A3B via serveur vLLM local).
import os
class LLMClient:
"""Client generique pour appels LLM (compatible OpenAI / vLLM)."""
def __init__(self, provider="openai", api_key=None, base_url=None, model=None):
self.provider = provider
# Modele et endpoint depuis l'environnement (jamais de cle en dur dans le source).
self.model = model or os.getenv("LOCAL_LLM_MODEL", "qwen3.6-35b-a3b")
self.base_url = base_url or os.getenv("LOCAL_LLM_BASE_URL")
self.api_key = api_key or os.getenv("LOCAL_LLM_API_KEY")
# Mode reel si une cle est disponible, sinon mode simulation (fallback pedagogique).
self.simulation_mode = not bool(self.api_key)
if self.simulation_mode:
print("Mode simulation active (LOCAL_LLM_API_KEY absente : pas d'appel API reel)")
self.api_key = "mock"
else:
print(f"Mode API reelle active (modele={self.model}, endpoint=serveur vLLM local)")
def call(self, messages: List[Dict], model: str = None, max_tokens: int = 2000) -> str:
"""Appelle le LLM. Retourne le contenu textuel de la reponse.
Args:
messages: Liste de messages {role, content}
model: Nom du modele (defaut: self.model, configure par LOCAL_LLM_MODEL)
max_tokens: Tokens maximaux en reponse
Returns:
Reponse du LLM
"""
if self.api_key == "mock" or self.simulation_mode:
return self._mock_call(messages)
# Implementation avec OpenAI SDK (compatible serveurs vLLM locaux).
try:
import openai
client = openai.OpenAI(api_key=self.api_key, base_url=self.base_url)
# Qwen3.6 est un modele de RAISONNEMENT : sans enable_thinking=False il
# consomme tous les max_tokens en reflexion interne ("thinking") et renvoie
# un contenu vide. On desactive explicitement le mode reflexion pour obtenir
# une reponse directe (et deterministe via temperature=0.0).
response = client.chat.completions.create(
model=model or self.model,
messages=messages,
max_tokens=max_tokens,
temperature=0.0, # Deterministe pour Sudoku
extra_body={"chat_template_kwargs": {"enable_thinking": False}},
)
return response.choices[0].message.content
except Exception as e:
print(f"Erreur API: {e}")
print("Bascule en mode simulation.")
return self._mock_call(messages)
def _mock_call(self, messages: List[Dict]) -> str:
"""Simulation pour tests sans cle API (fallback pedagogique)."""
user_msg = messages[-1].get("content", "")[:100]
# Simulation d'une reponse zero-shot
if "Exemple" not in user_msg and "python" not in user_msg.lower():
mock_response = "534678912\n672195348\n198342567\n859761423\n426853791\n713924856\n961537284\n287419635\n345286179"
return mock_response
# Simulation d'une reponse few-shot
if "Exemple" in user_msg:
return "534678912\n672195348\n198342567\n859761423\n426853791\n713924856\n961537284\n287419635\n345286179"
# Simulation d'une reponse code interpreter
if "python" in user_msg.lower() or "def " in user_msg.lower():
code = (
"def solve_sudoku(grid):\n"
' """Solveur de Sudoku avec backtracking."""\n'
" def is_valid(grid, row, col, num):\n"
" for x in range(9):\n"
" if grid[row][x] == num:\n"
" return False\n"
" for x in range(9):\n"
" if grid[x][col] == num:\n"
" return False\n"
" start_row, start_col = 3 * (row // 3), 3 * (col // 3)\n"
" for i in range(3):\n"
" for j in range(3):\n"
" if grid[i + start_row][j + start_col] == num:\n"
" return False\n"
" return True\n"
"\n"
" def solve(grid):\n"
" for i in range(9):\n"
" for j in range(9):\n"
" if grid[i][j] == 0:\n"
" for num in range(1, 10):\n"
" if is_valid(grid, i, j, num):\n"
" grid[i][j] = num\n"
" if solve(grid):\n"
" return True\n"
" grid[i][j] = 0\n"
" return False\n"
" return True\n"
"\n"
" solution = [row[:] for row in grid]\n"
" if solve(solution):\n"
" return solution\n"
" return None"
)
return "```python\n" + code + "\n```"
return f"[Simulation LLM] Reponse pour: {user_msg}..."
# Initialiser le client (mode reel si LOCAL_LLM_API_KEY definie, sinon simulation)
client = LLMClient()
print(f"Client LLM initialise: {client.provider}")
print(f"Mode simulation: {client.simulation_mode}")Mode API reelle active (modele=qwen3.6-35b-a3b, endpoint=serveur vLLM local)
Client LLM initialise: openai
Mode simulation: FalseLa méthode la plus simple consiste a donner la grille au LLM et lui demander de la resoudre directement.
Voici une grille de Sudoku. Les cases vides sont representees par des points (.).
Complete la grille en respectant les règles du Sudoku (chaque ligne, colonne et bloc 3x3
doit contenir les chiffres 1-9 exactement une fois).
Grille:
53..7....
6..195...
.98....6.
8...6...3
4..8.3..1
7...2...6
.6....28.
...419..5
....8..79
Reponds uniquement avec la grille completee, au même format.Objectif Modifiez le prompt zero-shot pour ameliorer le taux de succes. Testez au moins 2 variantes et comparez les résultats.
Indice Ajoutez des instructions plus precises sur le format de sortie attendu. Testez avec des puzzles faciles pour mesurer l’impact.
# EXERCICE : Optimiser le prompt zero-shot
def optimized_zero_shot_solve(grid: List[List[int]], client) -> Optional[List[List[int]]]:
# TODO: Creez un prompt optimise pour resoudre le Sudoku
# avec un meilleur taux de succes que le prompt zero-shot de base
result = None # TODO etudiant
return resultdef grid_to_string_format(grid: List[List[int]]) -> str:
"""Convertit une grille en format texte pour le prompt."""
lines = []
for i in range(9):
line = ""
for j in range(9):
line += str(grid[i][j]) if grid[i][j] != 0 else "."
lines.append(line)
return "\n".join(lines)
def parse_llm_response(response: str) -> Optional[List[List[int]]]:
"""Tente d'extraire une grille depuis la reponse du LLM."""
# Chercher une sequence de 81 chiffres/points
import re
print(response)
# Nettoyer la reponse
cleaned = response.replace(" ", "").replace("\n", "")
# Chercher un motif de 81 caracteres
match = re.search(r'[^0-9.]*([0-9.]{81})', cleaned)
if match:
puzzle_str = match.group(1)
return puzzle_to_grid(puzzle_str)
return None
def zero_shot_solve(grid: List[List[int]], client: LLMClient) -> Optional[List[List[int]]]:
"""Tente de resoudre un Sudoku avec zero-shot prompting."""
prompt = f"""Voici une grille de Sudoku. Les cases vides sont representees par des points (.).
Complete la grille en respectant les regles du Sudoku (chaque ligne, colonne et bloc 3x3
doit contenir les chiffres 1-9 exactement une fois).
Grille:
{grid_to_string_format(grid)}
Reponds uniquement avec la grille completee, au meme format, sans aucune explication.
"""
response = client.call([
{"role": "user", "content": prompt}
])
solution = parse_llm_response(response)
return solution
# Test zero-shot
print("=== Test Zero-Shot ===\n")
start = time.time()
solution = zero_shot_solve(example_grid, client)
elapsed = time.time() - start
if solution:
print("Solution proposee par le LLM:")
print_grid(solution)
is_valid = validate_solution(solution, example_grid)
print(f"\nSolution valide: {is_valid}")
print(f"Temps: {elapsed:.2f} secondes")
else:
print("Impossible de parser la reponse du LLM.")=== Test Zero-Shot ===
932185476
147623825 -> Correction: 147623895 is invalid (2 repeated). Let's re-solve carefully.
Row 1: 9 . 2 . . 5 4 . 3
Row 2: 1 . . . 6 3 . 2 5
Row 3: 5 . 8 4 . 7 . 6 .
Row 4: . 2 6 3 . 9 . . 1
Row 5: . 5 7 . 1 . 2 9 .
Row 6: . 9 . 6 7 . 5 3 .
Row 7: 2 4 . 5 3 . 6 . .
Row 8: 7 . 5 2 . . 3 . 4
Row 9: . 8 . . 4 1 9 5 .
Let's solve step-by-step.
**Box 1 (R1-3, C1-3):**
Cells: 9,.,2 / 1,.,. / 5,.,8
Missing: 3,4,6,7
R1C2: Row 1 has 9,2,5,4,3. Col 2 has 2,5,9,4,8.
Let's look at R1. Missing: 1,6,7,8.
R1C2: Col 2 contains 2,5,9,4,8. So R1C2 cannot be 2,5,9,4,8.
R1C2 options from missing {1,6,7,8}: 1,6,7. (8 is in col 2? No, R9C2 is 8. So 8 is in col 2. R1C2 cannot be 8).
So R1C2 is 1, 6, or 7.
Let's look at Box 1 again.
Values present: 9,2,1,5,8. Missing: 3,4,6,7.
R1C2, R2C2, R2C3, R3C2.
R3C2: Row 3 has 5,8,4,7,6. Col 2 has 2,5,9,4,8.
R3C2 cannot be 4,5,6,7,8,9,2.
Missing in R3: 1,2,3,9.
R3C2 must be from {1,2,3,9} intersect Box1 missing {3,4,6,7}.
Intersection: {3}. So **R3C2 = 3**.
Now Box 1 missing: 4,6,7.
Cells: R1C2, R2C2, R2C3.
R1C2: Row 1 missing 1,6,7,8. Col 2 missing 1,3,6,7 (present: 2,3,5,9,4,8). Wait, R3C2=3.
Col 2 now has: ., ., 3, 2, 5, 9, 4, ., 8.
Present in Col 2: 2,3,4,5,8,9. Missing: 1,6,7.
R1C2 is in Row 1. Row 1 missing: 1,6,7,8.
R1C2 cannot be 8 (Col 2 has 8). So R1C2 is 1,6,7.
R2C2: Row 2 missing 4,7,8,9. Col 2 missing 1,6,7.
Intersection for R2C2: {7}. So **R2C2 = 7**.
Now Box 1 missing: 4,6.
Cells: R1C2, R2C3.
R1C2 options: 1,6. (Since 7 is taken by R2C2).
Wait, Box 1 missing was 4,6,7. R2C2=7. Remaining 4,6 for R1C2 and R2C3.
R1C2 cannot be 4 (Row 1 has 4). So **R1C2 = 6**.
Then **R2C3 = 4**.
Box 1 is complete:
9 6 2
1 7 4
5 3 8
**Row 1:** 9 6 2 . . 5 4 . 3
Missing: 1,7,8.
R1C4, R1C5, R1C8.
Col 4 has 3,6,5,2. (R4C4=3, R6C4=6, R7C4=5, R8C4=2).
R1C4: Row 1 missing 1,7,8. Col 4 present: 3,6,5,2.
Box 2 (R1-3, C4-6) needs to be filled.
Box 2 cells:
R1C4, R1C5, R1C6(5)
R2C4, R2C5(6), R2C6(3)
R3C4(4), R3C5, R3C6(7)
Present in Box 2: 5,6,3,4,7. Missing: 1,2,8,9.
R1C4, R1C5, R2C4, R3C5.
R1C4 is in Row 1 (missing 1,7,8). Intersection with Box 2 missing {1,2,8,9} is {1,8}.
R1C5 is in Row 1 (missing 1,7,8). Intersection with Box 2 missing {1,2,8,9} is {1,8}.
R1C8 is the last missing in Row 1. Row 1 missing 1,7,8. R1C8 is in Col 8.
Col 8 has 2,6,9,3,5. (R2C8=2, R3C8=6, R5C8=9, R6C8=3, R9C8=5).
R1C8 cannot be 1? Let's check Col 8.
Col 8: .,2,6,.,9,3,.,.,5.
R1C8 options from {1,7,8}.
Col 8 doesn't have 1,7,8 yet.
But R1C4 and R1C5 are {1,8}. So R1C8 must be **7**.
So **R1C8 = 7**.
Row 1 remaining: R1C4, R1C5 are {1,8}.
**Row 2:** 1 7 4 . 6 3 . 2 5
Missing: 8,9.
R2C4, R2C7.
R2C4 is in Box 2. Box 2 missing {1,2,8,9}.
R2C4 cannot be 1 (Row 2 has 1). So R2C4 is 8 or 9.
R2C7 is in Col 7. Col 7 has 4,.,.,.,2,5,6,3,9.
R2C7 cannot be 9 (Col 7 has 9 at R9C7? No, R9C7 is 9. Yes).
So **R2C7 = 8**.
Then **R2C4 = 9**.
Row 2 is complete: 1 7 4 9 6 3 8 2 5.
**Box 2 Update:**
Present: 5,6,3,4,7,9.
Missing: 1,2,8.
Cells: R1C4, R1C5, R3C5.
We know R1C4, R1C5 are {1,8}.
So **R3C5 = 2**.
Now R1C4, R1C5 are {1,8}.
Col 4: R1C4, R2C4(9), R3C4(4), R4C4(3), R5C4(.), R6C4(6), R7C4(5), R8C4(2), R9C4(.).
Col 4 present: 9,4,3,6,5,2. Missing: 1,7,8.
R1C4 is 1 or 8.
R5C4, R9C4 are remaining.
Col 5: R1C5,
Impossible de parser la reponse du LLM.L’approche zero-shot a echoue a resoudre le puzzle. Sur cette realisation, le modele s’est lance dans un long raisonnement etape par etape mais n’a pas emis de grille au format attendu : la reponse n’est pas analysable (Impossible de parser la reponse du LLM).
| Aspect | Valeur | Signification |
|---|---|---|
| Solution | Non analysable | Le modele a produit un raisonnement texte sans grille exploitable |
| Temps | ~1.4 s (cf. benchmark) | Appel API reel au modele Qwen3.6 |
| Cause principale | Format non controle | Sans exemple ni contrainte de format, le modele derive en explications |
Points cles : 1. Non-fiabilite du zero-shot : selon la realisation, le modele peut soit deriver en un long raisonnement non-analysable (cellule 14), soit emettre une grille invalide (cellule 25) ; dans les deux cas, zero-shot ne resout pas le puzzle 2. Parsing indispensable : la fonction parse_llm_response() detecte proprement l’absence de grille exploitable 3. Limite fondamentale : sans exemples ni raisonnement controle par le programme, un LLM ne resout pas fiablement un probleme combinatoire non trivial
Pourquoi le LLM echoue : resoudre un Sudoku demande une recherche combinatoire avec retour-arriere. Un LLM genere des tokens un par un et ne peut pas “revenir” sur une affectation incompatible decidée plus tot ; il derive donc en explications sans converger vers une solution exploitable.
Le few-shot prompting donne au LLM des exemples de puzzles resolus pour improve la performance.
Exemple 1:
Input:
53..7....
6..195...
.98....6.
...
Output:
534678912
672195348
198342567
859761423
426853791
713924856
961537284
287419635
345286179
Exemple 2:
...
Maintenant, resous ce puzzle:
[grille]# Exemples pour few-shot learning
FEW_SHOT_EXAMPLES = '''Exemple 1:
Input:
53..7....
6..195...
.98....6.
8...6...3
4..8.3..1
7...2...6
.6....28.
...419..5
....8..79
Output:
534678912
672195348
198342567
859761423
426853791
713924856
961537284
287419635
345286179
Exemple 2:
Input:
.....3..
..5.....
.1.697...
....245..
8.......
..1....9.
...7.4..
......87.
.9.....2.
Output:
487513962
925846731
319697258
673124589
852379614
241568397
598732146
164985273
736251825
'''
def few_shot_solve(grid: List[List[int]], client: LLMClient) -> Optional[List[List[int]]]:
"""Tente de resoudre un Sudoku avec few-shot prompting."""
prompt = f"""Tu es un expert en Sudoku. Voici des exemples de puzzles et leurs solutions:
{FEW_SHOT_EXAMPLES}
Maintenant, resous ce puzzle. Reponds uniquement avec la grille completee:
{grid_to_string_format(grid)}
"""
response = client.call([
{"role": "user", "content": prompt}
])
solution = parse_llm_response(response)
return solution
# Test few-shot
print("=== Test Few-Shot ===\n")
start = time.time()
solution = few_shot_solve(example_grid, client)
elapsed = time.time() - start
if solution:
print("Solution proposee par le LLM:")
print_grid(solution)
is_valid = validate_solution(solution, example_grid)
print(f"\nSolution valide: {is_valid}")
print(f"Temps: {elapsed:.2f} secondes")
else:
print("Impossible de parser la reponse du LLM.")=== Test Few-Shot ===
932185476
147693825
568427169
826359741
357814296
491672538
243538617
715268394
689741952
Solution proposee par le LLM:
9 3 2 | 1 8 5 | 4 7 6
1 4 7 | 6 9 3 | 8 2 5
5 6 8 | 4 2 7 | 1 6 9
---------------------
8 2 6 | 3 5 9 | 7 4 1
3 5 7 | 8 1 4 | 2 9 6
4 9 1 | 6 7 2 | 5 3 8
---------------------
2 4 3 | 5 3 8 | 6 1 7
7 1 5 | 2 6 8 | 3 9 4
6 8 9 | 7 4 1 | 9 5 2
Solution valide: False
Temps: 1.32 secondesL’approche few-shot echoue egalement : a la difference du zero-shot (reponse non-analysable), le few-shot produit cette fois une grille bien formee mais invalide (violations des contraintes). Les exemples cadrent donc le format, mais pas la correction.
| Aspect | Valeur | Signification |
|---|---|---|
| Solution valide | False | La grille respecte le format 9x9 mais viole les contraintes (doublons) |
| Temps | ~1.3 s | Appel API reel au modele Qwen3.6 |
| Cause principale | Verification combinatoire absente | Le LLM respecte le format mais n’effectue pas la verification des contraintes |
Points cles : 1. Format cadre, contenu toujours faux : les exemples few-shot apprennent au modele la forme attendue (grille 9x9), pas la correction combinatoire 2. Avantage partiel vs zero-shot : le few-shot produit au moins une grille analysable (la ou le zero-shot a derive en raisonnement), mais elle est invalide 3. Même type d’erreur : doublons dans lignes/colonnes/blocs 4. Conclusion : la difficulte n’est pas de communiquer le format au LLM, mais la verification combinatoire qu’il n’effectue pas de lui-meme
Transition : ni le zero-shot ni le few-shot ne fonctionnent car ils demandent au LLM de produire directement la solution. L’approche suivante change de strategie : demander au LLM d’ecrire un solveur, puis executer ce solveur.
L’approche la plus fiable consiste a demander au LLM de generer du code Python qui resout le Sudoku, puis d’executer ce code.
Ecris une fonction Python `solve_sudoku(grid)` qui resout cette grille:
[grille au format liste de listes]
La fonction doit:
1. Utiliser un algorithme de backtracking
2. Retourner la grille resolue ou None
3. Ne pas utiliser de librairies externes
Reponds uniquement avec le code Python, sans explication.Objectif Implementez une fonction qui teste les 3 approches sur les mêmes puzzles et retourne un tableau comparatif des taux de succes et temps de resolution.
Indice Utilisez les fonctions déjà définies pour chaque approche et mesurez le temps avec time.time().
# EXERCICE : Comparer zero-shot vs few-shot vs code interpreter
def compare_llm_approaches(puzzles: List[str], client, limit: int = 3) -> dict:
# TODO: Testez les 3 approches LLM sur les memes puzzles
# et retournez un dict avec le taux de succes et le temps moyen pour chacune
result = {} # TODO etudiant
return resultdef code_interpreter_solve(grid: List[List[int]], client: LLMClient) -> Optional[List[List[int]]]:
"""Utilise le LLM pour generer du code Python qui resout le Sudoku."""
prompt = f"""Ecris une fonction Python `solve_sudoku(grid)` qui resout cette grille de Sudoku:
grid = {grid}
La fonction doit:
1. Utiliser un algorithme de backtracking
2. Prendre une grille 9x9 (liste de listes, 0 = case vide)
3. Retourner la grille resolue ou None si pas de solution
4. Ne pas utiliser de librairies externes (seulement la bibliotheque standard)
Reponds uniquement avec le code Python de la fonction, sans aucun commentaire ou explication.
"""
response = client.call([
{"role": "user", "content": prompt}
])
# Extraire le code Python
code = response.strip()
if "```" in code:
# Extraire le code entre les backticks
import re
match = re.search(r'```python\n(.*?)```', code, re.DOTALL)
if match:
code = match.group(1)
# Executer le code
try:
# Creer un environnement d'execution sécurisé
exec_globals = {"__builtins__": {"range": range, "len": len, "list": list, "set": set}}
exec_locals = {}
exec(code, exec_globals, exec_locals)
if "solve_sudoku" in exec_locals:
import copy
solve_func = exec_locals["solve_sudoku"]
# deepcopy : certains solveurs generes mutent la grille en place
# (backtracking). On passe une copie pour ne pas alterer l'originale.
solution = solve_func(copy.deepcopy(grid))
return solution
else:
print("Erreur: La fonction solve_sudoku n'a pas ete definie.")
return None
except Exception as e:
print(f"Erreur lors de l'execution du code genere: {e}")
return None
# Test code interpreter
print("=== Test Code Interpreter ===\n")
start = time.time()
solution = code_interpreter_solve(example_grid, client)
elapsed = time.time() - start
if solution:
print("Solution trouvee via le code genere:")
print_grid(solution)
is_valid = validate_solution(solution, example_grid)
print(f"\nSolution valide: {is_valid}")
print(f"Temps: {elapsed:.2f} secondes")
else:
print("Echec de la resolution par code interpreter.")=== Test Code Interpreter ===
Solution trouvee via le code genere:
9 6 2 | 1 8 5 | 4 7 3
1 7 4 | 9 6 3 | 8 2 5
5 3 8 | 4 2 7 | 1 6 9
---------------------
8 2 6 | 3 5 9 | 7 4 1
3 5 7 | 8 1 4 | 2 9 6
4 9 1 | 6 7 2 | 5 3 8
---------------------
2 4 9 | 5 3 8 | 6 1 7
7 1 5 | 2 9 6 | 3 8 4
6 8 3 | 7 4 1 | 9 5 2
Solution valide: True
Temps: 4.21 secondesLe code interpreter a reussi a resoudre le puzzle avec une solution valide, contrairement aux approches zero-shot et few-shot.
| Aspect | Valeur | Signification |
|---|---|---|
| Solution valide | True | La grille completee respecte toutes les contraintes Sudoku |
| Temps | ~4.2 s | Generation du code (appel LLM) + execution du solveur genere |
| Approche | Generation de code | Le LLM ecrit un solveur Python, ensuite execute par le notebook |
Points cles : 1. Changement de strategie decisif : au lieu de demander la solution directement (peu fiable), on demande au LLM d’ecrire un solveur (generation de code) — une tache ou les LLM excellent 2. Code backtracking correct : le modele a genere un solveur par retour-arriere, l’algorithme canonique et complet pour le Sudoku 3. Validation automatique : validate_solution() confirme que la grille originale est preservee et que toutes les contraintes sont respectees 4. Environnement securise : le code genere est execute dans un espace restreint (exec_globals ne contient que les fonctions necessaires) 5. Robustesse : un deepcopy de la grille est passe au solveur genere, car certains solveurs mutent la grille en place 6. Cout en temps : l’approche est plus lente (~4.2 s) que la generation directe (~1.4 s) car elle genere puis execute du code, mais c’est le prix de la fiabilite
Lecon cles : la delegation de la verification combinatoire a un algorithme execute est ce qui fait basculer le resultat d’0% (generation directe) a 100% (generation de code). Le LLM est un excellent producteur de code, mais un mauvais solveur direct.
Comparons les trois approches sur différents niveaux de difficulte.
def benchmark_llm_approaches(puzzles: List[str], client: LLMClient, limit: int = 3) -> Dict:
"""Compare les differentes approches LLM."""
results = {
"zero_shot": {"solved": 0, "total_time": 0, "valid": 0},
"few_shot": {"solved": 0, "total_time": 0, "valid": 0},
"code_interpreter": {"solved": 0, "total_time": 0, "valid": 0}
}
for i, puzzle_str in enumerate(puzzles[:limit]):
grid = puzzle_to_grid(puzzle_str)
print(f"\n--- Puzzle {i+1} ---")
# Zero-shot
print("Testing Zero-shot...", end=" ")
start = time.time()
sol = zero_shot_solve(grid, client)
elapsed = time.time() - start
results["zero_shot"]["total_time"] += elapsed
if sol and validate_solution(sol, grid):
results["zero_shot"]["valid"] += 1
print(f"OK ({elapsed:.2f}s)")
else:
print("ECHEC")
results["zero_shot"]["solved"] += 1
# Few-shot
print("Testing Few-shot...", end=" ")
start = time.time()
sol = few_shot_solve(grid, client)
elapsed = time.time() - start
results["few_shot"]["total_time"] += elapsed
if sol and validate_solution(sol, grid):
results["few_shot"]["valid"] += 1
print(f"OK ({elapsed:.2f}s)")
else:
print("ECHEC")
results["few_shot"]["solved"] += 1
# Code interpreter
print("Testing Code Interpreter...", end=" ")
start = time.time()
sol = code_interpreter_solve(grid, client)
elapsed = time.time() - start
results["code_interpreter"]["total_time"] += elapsed
if sol and validate_solution(sol, grid):
results["code_interpreter"]["valid"] += 1
print(f"OK ({elapsed:.2f}s)")
else:
print("ECHEC")
results["code_interpreter"]["solved"] += 1
return results
# Benchmark
print("=== Benchmark LLM Approches ===\n")
print("(Ceci peut prendre plusieurs minutes...)\n")
benchmark_results = benchmark_llm_approaches(easy_puzzles, client, limit=2)
# Afficher les resultats
print("\n" + "="*60)
print("| Approche | Valides / Total | Taux de succes | Temps moyen |")
print("|----------|-----------------|-----------------|-------------|")
for approach, data in benchmark_results.items():
total = data["solved"]
valid = data["valid"]
rate = (valid / total * 100) if total > 0 else 0
avg_time = data["total_time"] / total if total > 0 else 0
print(f"| {approach:20} | {valid:3} / {total:3} | {rate:14.1f}% | {avg_time:10.2f}s |")=== Benchmark LLM Approches ===
(Ceci peut prendre plusieurs minutes...)
--- Puzzle 1 ---
Testing Zero-shot... 932185476
147963825
568427169
826359741
357814296
491672538
248531679
715296384
683741952
ECHEC
Testing Few-shot... 932185476
148763925
568427169
426359871
357816294
891674532
249538617
715296384
683941952
ECHEC
Testing Code Interpreter... OK (4.18s)
--- Puzzle 2 ---
Testing Zero-shot... 413729658
962345781
571896423
348152976
795431268
126789534
432679518
857243169
685914372
ECHEC
Testing Few-shot... 483521679
967345281
251876493
348152967
719463528
536798214
172639548
894263179
625914387
ECHEC
Testing Code Interpreter... OK (4.16s)
============================================================
| Approche | Valides / Total | Taux de succes | Temps moyen |
|----------|-----------------|-----------------|-------------|
| zero_shot | 0 / 2 | 0.0% | 1.37s |
| few_shot | 0 / 2 | 0.0% | 1.36s |
| code_interpreter | 2 / 2 | 100.0% | 4.17s |Avec le modele reel Qwen3.6-35B-A3B (serveur vLLM local, 2 puzzles par approche), le benchmark confirme la tendance de la litterature : la generation de code bat nettement la generation directe de grille.
| Approche | Valides / Total | Taux de succes | Temps moyen |
|---|---|---|---|
| Zero-shot | 0 / 2 | 0.0 % | ~1.4 s |
| Few-shot | 0 / 2 | 0.0 % | ~1.4 s |
| Code Interpreter | 2 / 2 | 100.0 % | ~4.2 s |
Points cles : 1. Generation directe = echec systematique : zero-shot et few-shot echouent (reponse non-analysable ou grille invalide) ; le LLM ne verifie pas les contraintes combinatoires 2. Generation de code = succes systematique : le code-interpreter delegue la recherche combinatoire a un algorithme execute, garantissant la validite 3. La fiabilite a un cout en temps : le code-interpreter (~4.2 s) est plus lent que la generation directe (~1.4 s) car il genere puis execute du code — mais seule cette approche resout le puzzle 4. Zero-shot et few-shot ont des temps similaires (~1.4 s) : les exemples few-shot ne rendent pas l’appel notablement plus rapide ; leur seul effet est d’obtenir une grille analysable (mais toujours invalide)
Conclusion pedagogique : la distinction decisive n’est pas zero-shot vs few-shot (les deux echouent), mais generation directe vs generation de code. Demander a un LLM d’ecrire un solveur, puis l’executer, transforme un outil peu fiable (solveur direct) en outil fiable (producteur de code). C’est l’essence du paradigme code-interpreter / tool-use.
Reproductibilite et non-determinisme : meme avec
temperature=0.0, les sorties du modele peuvent varier legerement d’une execution a l’autre (nondeterminisme numerique du serveur). Les taux (0% / 0% / 100%) sont robustes, mais les temps et le detail des reponses (ex. grille invalide vs reponse non-analysable en zero-shot) peuvent differer d’une realisation a l’autre. Pour reproduire, definirLOCAL_LLM_API_KEY,LOCAL_LLM_BASE_URLetLOCAL_LLM_MODELdans l’environnement (serveur vLLM compatible OpenAI). Sans cle, le client bascule en mode simulation (fallback pedagogique) et les taux ci-dessus ne s’observent pas.
LLM contre solveurs algorithmiques :
| Méthode | Taux de succes | Temps (moyen) | Avantages |
|---|---|---|---|
| LLM Zero-shot | 0 % (0/2) | ~1.4 s | Simple, intuitif — mais non fiable |
| LLM Few-shot | 0 % (0/2) | ~1.4 s | Format cadre, correction non garantie |
| LLM Code Gen | 100 % (2/2) | ~4.2 s | Fiable (code verifiable) |
| Backtracking (cf Sudoku-01) | 100 % | ~0.01-0.1 s | Rapide, garantie |
| OR-Tools (cf Sudoku-10) | 100 % | ~0.001-0.01 s | Optimal |
Cas d’usage pour LLM + Sudoku — malgré leur performance inferieure, les LLM ont des cas d’usage legitimes :
Modifier le prompt zero-shot pour inclure des instructions plus spécifiques : - Demander au LLM de verifier sa solution - Specifier que chaque ligne/colonne/bloc doit contenir 1-9 - Demander de reflechir étape par étape (Chain-of-Thought)
Implementer une approche hybride : 1. Utiliser le LLM pour suggerer une case a remplir 2. Verifier que la suggestion est valide 3. Repeter jusqu’a resolution
Utiliser le LLM pour generer de nouveaux Sudokus : - Demander de créer une grille complete valide - Puis demander de retirer des cases pour créer le puzzle - Verifier que le puzzle a une solution unique
# Exemple resolu : Solveur LLM avec Chain-of-Thought et validation iterative
# Ce code sert de reference pour comprendre l'approche CoT.
# Ne pas modifier - implementez votre propre version dans l'exercice ci-dessous.
class ChainOfThoughtSudokuSolver:
"""Solveur Sudoku utilisant un LLM avec Chain-of-Thought et validation."""
def __init__(self, client: LLMClient, max_corrections: int = 3):
self.client = client
self.max_corrections = max_corrections
def build_cot_prompt(self, grid: List[List[int]], partial_solution: List[List[int]]) -> str:
"""Construit un prompt Chain-of-Thought pour la prochaine affectation.
Le prompt doit demander au LLM de :
1. Identifier la case la plus contrainte (avec le moins de candidats)
2. Expliquer pourquoi cette case ne peut recevoir qu'une seule valeur
3. Proposer l'affectation au format 'Case (row, col) = valeur'
"""
prompt= """You are an expert at solving sudoku.
Your task is to find the most constrained cell. That means the cell where there is only 1 possibility (if it exists).
Explain why this cell can only have 1 value. And submit the affectation in this format:
(row,col) = value
You must use 0 based indexing and must submit an answer, even if you don't find a cell with only 1 possible value.
Here is the list of cells:
"""
for i in range(len(partial_solution)):
for j in range(len(partial_solution[0])):
prompt += f"""({i},{j}) = {partial_solution[i][j]}
"""
return prompt
def parse_assignment(self, llm_response: str):
"""Extrait l'affectation proposee par le LLM depuis sa reponse.
Chercher un motif du type 'Case (i, j) = v' ou '(i,j)=v' dans le texte.
Retourne (row, col, value) ou None si pas d'affectation trouvee.
"""
import re
# Nettoyer la reponse
cleaned = llm_response.replace(" ", "").replace("\n", "")
# Chercher un motif de 81 caracteres
match = re.findall(r'(\([0-8],[0-8]\)=[1-9])', cleaned)
if match:
puzzle_str = match[-1]
return (int(puzzle_str[1]),int(puzzle_str[3]),int(puzzle_str[6]))
return None
def is_valid_assignment(self, grid: List[List[int]], row: int, col: int, value: int) -> bool:
"""Verifie si placer 'value' en (row, col) est valide selon les regles du Sudoku."""
#scan line
line = grid[row]
for x in line:
if x == value:
return False
#scan column
for i in range(9):
if grid[i][col] == value:
return False
#scan block
i = row //3
j = col //3
for k in range(3):
for h in range(3):
if grid[i+k][j+h] == value:
return False
return True
def completed(self,puzzle: List[List[int]]):
for i in puzzle:
for x in i:
if x == 0:
return False
return True
def solve(self, puzzle: List[List[int]]) -> Optional[List[List[int]]]:
"""Resout le puzzle avec Chain-of-Thought et validation.
Boucle principale :
1. Afficher l'etat courant au LLM avec prompt CoT
2. Extraire l'affectation proposee
3. Si valide : appliquer et continuer
4. Si invalide : informer le LLM et redemander (jusqu'a max_corrections essais)
5. Si echec apres max_corrections : fallback vers backtracking
"""
stack = []
counter = self.max_corrections
while(not self.completed(puzzle)):
print_grid(puzzle)
prompt = self.build_cot_prompt(puzzle,puzzle)
response = client.call([
{"role": "user", "content": prompt}
])
tmp = self.parse_assignment(response)
if tmp == None:
print(response,prompt)
return None
row,col,value = tmp
if self.is_valid_assignment(puzzle,row,col,value):
counter = self.max_corrections
puzzle[row][col] = value
stack.append(tmp)
else:
counter -=1
if counter ==0:
row,col,_ = stack.pop()
puzzle[row][col] = 0
counter = self.max_corrections
# Test du solveur CoT
print("Starting")
solver = ChainOfThoughtSudokuSolver(client, max_corrections=3)
solution = solver.solve(example_grid)
if solution:
print("Solution trouvee !")
print_grid(solution)
print(f"Valide : {validate_solution(solution, example_grid)}")
else:
print("Echec de la resolution")Starting
9 . 2 | . . 5 | 4 . 3
1 . . | . 6 3 | . 2 5
5 . 8 | 4 . 7 | . 6 .
---------------------
. 2 6 | 3 . 9 | . . 1
. 5 7 | . 1 . | 2 9 .
. 9 . | 6 7 . | 5 3 .
---------------------
2 4 . | 5 3 . | 6 . .
7 . 5 | 2 . . | 3 . 4
. 8 . | . 4 1 | 9 5 .
To find the most constrained cell, we need to identify a cell that has only one possible value remaining. This usually happens when a cell is part of a row, column, and 3x3 box where 8 of the 9 numbers are already present or accounted for by constraints.
Let's analyze the grid state. I will convert the input into a 9x9 matrix for easier visualization (0 represents empty cells):
```
Row 0: [9, 0, 2, 0, 0, 5, 4, 0, 3]
Row 1: [1, 0, 0, 0, 6, 3, 0, 2, 5]
Row 2: [5, 0, 8, 4, 0, 7, 0, 6, 0]
Row 3: [0, 2, 6, 3, 0, 9, 0, 0, 1]
Row 4: [0, 5, 7, 0, 1, 0, 2, 9, 0]
Row 5: [0, 9, 0, 6, 7, 0, 5, 3, 0]
Row 6: [2, 4, 0, 5, 3, 0, 6, 0, 0]
Row 7: [7, 0, 5, 2, 0, 0, 3, 0, 4]
Row 8: [0, 8, 0, 0, 4, 1, 9, 5, 0]
```
Let's check specific cells that look promising. Often, cells in rows or columns with many filled numbers are good candidates.
**Let's examine Row 4:**
Values present: `5, 7, 1, 2, 9`.
Missing values: `3, 4, 6, 8`.
Empty cells: `(4,0), (4,3), (4,5), (4,8)`.
**Let's examine Column 0:**
Values present: `9, 1, 5, 2, 7`.
Missing values: `3, 4, 6, 8`.
Empty cells: `(3,0), (4,0), (5,0), (8,0)`.
**Let's examine Cell (4,0):**
- **Row 4** contains: `{1, 2, 5, 7, 9}`. Missing: `{3, 4, 6, 8}`.
- **Column 0** contains: `{1, 2, 5, 7, 9}`. Missing: `{3, 4, 6, 8}`.
- **Box 4** (Middle Left, rows 3-5, cols 0-2) contains:
- Row 3: `0, 2, 6`
- Row 4: `0, 5, 7`
- Row 5: `0, 9, 0`
- Values in Box 4: `{2, 5, 6, 7, 9}`. Missing: `{1, 3, 4, 8}`.
Intersection of missing values from Row, Col, and Box for cell (4,0):
- Row missing: `{3, 4, 6, 8}`
- Col missing: `{3, 4, 6, 8}`
- Box missing: `{1, 3, 4, 8}`
- Common possibilities: `{3, 4, 8}`. (6 is in the box, so it's excluded).
So (4,0) can be 3, 4, or 8. Not unique yet.
Let's look at **Cell (5,0)**:
- **Row 5** contains: `{9, 6, 7, 5, 3}`. Missing: `{1, 2, 4, 8}`.
- **Column 0** contains: `{9, 1, 5, 2, 7}`. Missing: `{3, 4, 6, 8}`.
- **Box 4** contains: `{2, 5, 6, 7, 9}`. Missing: `{1, 3, 4, 8}`.
- Intersection:
- Row: `{1, 2, 4, 8}`
- Col: `{3, 4, 6, 8}`
- Box: `{1, 3, 4, 8}`
- Common: `{4, 8}`. (1 is in Col, 2 is in Box, 3 is in Row, 6 is in Row).
So (5,0) can be 4 or 8.
Let's look at **Cell (8,0)**:
- **Row 8** contains: `{8, 4, 1, 9, 5}`. Missing: `{2, 3, 6, 7}`.
- **Column 0** contains: `{9, 1, 5, 2, 7}`. Missing: `{3, 4, 6, 8}`.
- **Box 7** (Bottom Left, rows 6-8, cols 0-2) contains:
- Row 6: `2, 4, 0`
- Row 7: `7, 0, 5`
- Row 8: `0, 8, 0`
- Values: `{2, 4, 5, 7, 8}`. Missing: `{1, 3, 6, 9}`.
- Intersection for (8,0):
- Row: `{2, 3, 6, 7}`
- Col: `{3, 4, 6, 8}`
- Box: `{1, 3, 6, 9}`
- Common: `{3, 6}`.
Let's look at **Cell (3,0)**:
- **Row 3** contains: `{2, 6, 3, 9, 1}`. Missing: `{4, 5, 7, 8}`.
- **Column 0** contains: `{9, 1, 5, 2, 7}`. Missing: `{3, 4, 6, 8}`.
- **Box 4** contains: `{2, 5, 6, 7, 9}`. Missing: `{1, 3, 4, 8}`.
- Intersection:
- Row: `{4, 5, 7, 8}`
- Col: `{3, 4, 6, 8}`
- Box: `{1, 3, 4, 8}`
- Common: `{4, 8}`.
Let's try a different area. Look at **Row 6**:
Values: `2, 4, 0, 5, 3, 0, 6, 0, 0`.
Missing: `1, 7, 8, 9`.
Cells: `(6,2), (6,5), (6,7), (6,8)`.
Look at **Cell (6,2)**:
- Row 6 missing: `{1, 7, 8, 9}`.
- Col 2 contains: `2, 0, 8, 6, 7, 0, 0, 5, 0`. Values: `{2, 8, 6, 7, 5}`. Missing in Col 2: `{1, 3, 4, 9}`.
- Box 7 contains: `{2, 4, 5, 7, 8}`. Missing: `{1, 3, 6, 9}`.
- Intersection:
- Row: `{1, 7, 8, 9}`
- Col: `{1, 3, 4, 9}`
- Box: `{1, 3, 6, 9}`
- Common: `{1, 9}`.
Look at **Cell (6,5)**:
- Row 6 missing: `{1, 7, 8, 9}`.
- Col 5 contains: `5, 3, 7, 9, 0, 0, 0, 0, 1`. Values: `{1, 3, 5, 7, 9}`. Missing: `{2, 4, 6, 8}`.
- Box 8 (Bottom Middle) contains:
- Row 6: `5 You are an expert at solving sudoku.
Your task is to find the most constrained cell. That means the cell where there is only 1 possibility (if it exists).
Explain why this cell can only have 1 value. And submit the affectation in this format:
(row,col) = value
You must use 0 based indexing and must submit an answer, even if you don't find a cell with only 1 possible value.
Here is the list of cells:
(0,0) = 9
(0,1) = 0
(0,2) = 2
(0,3) = 0
(0,4) = 0
(0,5) = 5
(0,6) = 4
(0,7) = 0
(0,8) = 3
(1,0) = 1
(1,1) = 0
(1,2) = 0
(1,3) = 0
(1,4) = 6
(1,5) = 3
(1,6) = 0
(1,7) = 2
(1,8) = 5
(2,0) = 5
(2,1) = 0
(2,2) = 8
(2,3) = 4
(2,4) = 0
(2,5) = 7
(2,6) = 0
(2,7) = 6
(2,8) = 0
(3,0) = 0
(3,1) = 2
(3,2) = 6
(3,3) = 3
(3,4) = 0
(3,5) = 9
(3,6) = 0
(3,7) = 0
(3,8) = 1
(4,0) = 0
(4,1) = 5
(4,2) = 7
(4,3) = 0
(4,4) = 1
(4,5) = 0
(4,6) = 2
(4,7) = 9
(4,8) = 0
(5,0) = 0
(5,1) = 9
(5,2) = 0
(5,3) = 6
(5,4) = 7
(5,5) = 0
(5,6) = 5
(5,7) = 3
(5,8) = 0
(6,0) = 2
(6,1) = 4
(6,2) = 0
(6,3) = 5
(6,4) = 3
(6,5) = 0
(6,6) = 6
(6,7) = 0
(6,8) = 0
(7,0) = 7
(7,1) = 0
(7,2) = 5
(7,3) = 2
(7,4) = 0
(7,5) = 0
(7,6) = 3
(7,7) = 0
(7,8) = 4
(8,0) = 0
(8,1) = 8
(8,2) = 0
(8,3) = 0
(8,4) = 4
(8,5) = 1
(8,6) = 9
(8,7) = 5
(8,8) = 0
Echec de la resolutionL’exemple resolu ci-dessus utilise un mécanisme de backtracking (pile d’affectations + retour en arriere). Implementez une version simplifiee sans backtracking :
Principe : A chaque itération, demandez au LLM une seule affectation. Si elle est valide, appliquez-la. Si elle est invalide, relancez la demande en precisant la contrainte violee, sans annuler les affectations précédentes.
Consignes : 1. Implementez build_single_cell_prompt(grid, failed_attempt) qui construit un prompt différent de l’exemple 2. Implementez solve(puzzle) avec une boucle simple (pas de pile, pas de retour arriere) 3. Ajoutez un compteur de tentatives consecutives echouees ; après 5 echecs, arreter proprement 4. Testez sur easy_puzzles[1]
# Exemple guide variant : Solveur LLM sans backtracking
class SinglePassLLMSolver:
"""Solveur Sudoku avec LLM, sans mecanisme de backtracking."""
def __init__(self, client: LLMClient, max_failures: int = 5):
self.client = client
self.max_failures = max_failures
def build_single_cell_prompt(self, grid: List[List[int]], failed_attempt: str = None) -> str:
"""Construit un prompt demandant une seule affectation.
TODO : Construire un prompt qui :
- Presente la grille actuelle au LLM
- Demande UNE seule case a remplir avec justification
- Si failed_attempt est fourni, indique la contrainte violee
"""
# Exercice: implementer
pass
def solve(self, puzzle: List[List[int]]) -> Optional[List[List[int]]]:
"""Resout le puzzle sans backtracking.
TODO : Implementer la boucle :
1. Construire le prompt
2. Appeler le LLM
3. Parser l'affectation (reutiliser parse_assignment de l'exemple)
4. Si valide : appliquer et reset le compteur d'echecs
5. Si invalide : incrementer le compteur, informer le LLM
6. Si compteur >= max_failures : arreter et retourner None
"""
# Exercice: implementer
pass
# Test du solveur sans backtracking
print("=== Test SinglePassLLMSolver ===")
sp_solver = SinglePassLLMSolver(client, max_failures=5)
test_grid = puzzle_to_grid(easy_puzzles[1])
sp_solution = sp_solver.solve(test_grid)
if sp_solution:
print("Solution trouvee :")
print_grid(sp_solution)
print(f"Valide : {validate_solution(sp_solution, test_grid)}")
else:
print("Echec de la resolution")=== Test SinglePassLLMSolver ===
Echec de la resolutionLe solveur SinglePassLLMSolver est maintenant défini. Verifions l’etat de notre grille exemple avant de l’utiliser :
Avant de passer aux exercices suivants, verifions que la grille exemple est toujours dans son etat original (non modifiée par les tentatives de resolution précédentes). Cette verification est essentielle quand on enchaine plusieurs solveurs sur la même grille.
Les LLM commettent souvent des erreurs lorsqu’on leur demande de resoudre directement un Sudoku. Une approche plus prometteuse est de combiner : 1. Chain-of-Thought : Le LLM explique son raisonnement et propose une affectation a la fois 2. Validation locale : A chaque etape, on verifie que l’affectation proposee est valide 3. Correction interactive : Si une erreur est detectee, on redemande au LLM
La classe ChainOfThoughtSudokuSolver ci-dessous illustre une implementation complete :
(row, col) = value depuis la reponse du LLMEchec de la resolution)Avec le modele Qwen3.6, ce solveur ne resout pas le puzzle dans le budget de corrections : les affectations proposees par le LLM sont frequemment invalides, et le budget s’epuise avant la resolution complete. Ce resultat est honnete et instructif : meme avec validation iterative cellule par cellule, la fiabilite limitee du LLM sur le raisonnement combinatoire rend l’approche fragile sur des puzzles non triviaux. La generation de code (approche 3) reste superieure car elle delegue toute la recherche a un algorithme execute.
Utiliser uniquement le client LLM fourni (compatible mode API reelle et mode simulation).
L’approche Chain-of-Thought de l’exemple précédent demande au LLM d’identifier une seule case a la fois. Une stratégie alternative consiste a fournir au LLM des exemples de raisonnement complet (few-shot avec explications), puis de lui demander de resoudre le puzzle en suivant le même patron de raisonnement.
Le few-shot avec raisonnement guide combine deux idees : 1. Few-shot : Fournir un ou plusieurs exemples de grille partiellement resolue avec les étapes de deduction 2. Raisonnement structure : Chaque exemple montre le raisonnementlogique (elimination des candidats, identification des valeurs forcees) 3. Application : Demander au LLM d’appliquer le même type de raisonnement sur une nouvelle grille
Implementer la classe FewShotReasoningSolver avec :
(row, col) = value depuis le texte du LLM, qui contient maintenant du raisonnement melange aux affectationsclient défini plus haut)Étape N : (row, col) = valeur -- [explication]Objectif Analysez les erreurs commises par le LLM quand il echoue a resoudre un puzzle. Categorisez les types d’erreurs (violation de ligne, colonne, bloc, valeur hors range).
Indice Comparez la grille produite par le LLM avec la solution correcte et identifiez les cellules en erreur, puis verifiez quelles contraintes sont violees.
# EXERCICE : Solveur LLM avec Few-Shot raisonne
class FewShotReasoningSolver:
"""Solveur Sudoku utilisant un LLM avec few-shot et raisonnement guide."""
def __init__(self, client: LLMClient):
self.client = client
def build_few_shot_examples(self) -> str:
"""Construit les exemples few-shot avec raisonnement.
Chaque exemple doit montrer :
- Une grille partielle
- 3-4 etapes de deduction avec explication
- Le format : Etape N : (row, col) = valeur -- [explication]
"""
# Exercice: Implementer les exemples few-shot
pass
def build_prompt(self, grid: List[List[int]]) -> str:
"""Construit le prompt complet avec exemples et grille a resoudre."""
# Exercice: Assembler exemples + grille + instruction de format
pass
def parse_reasoning_response(self, llm_response: str) -> List[tuple]:
"""Extrait les affectations depuis la reponse du LLM.
Cherche les motifs 'Etape N : (row, col) = valeur -- ...'
Retourne une liste de (row, col, value).
"""
# Exercice: Parser la reponse pour extraire les affectations
pass
def solve(self, puzzle: List[List[int]]) -> Optional[List[List[int]]]:
"""Resout le puzzle avec few-shot raisonne.
Etapes :
1. Construire le prompt avec exemples
2. Appeler le LLM
3. Parser les affectations
4. Valider et appliquer chaque affectation
5. Retourner la grille resolue ou None
"""
# Exercice: Implementer la boucle de resolution
pass
# Test du solveur few-shot raisonne
print("=== Test Few-Shot avec Raisonnement Guide ===")
fs_solver = FewShotReasoningSolver(client)
# Utiliser un puzzle facile pour le test
test_grid = puzzle_to_grid(easy_puzzles[0])
fs_solution = fs_solver.solve(test_grid)
if fs_solution:
print("Solution trouvee :")
print_grid(fs_solution)
print(f"Valide : {validate_solution(fs_solution, test_grid)}")
else:
print("Echec de la resolution")=== Test Few-Shot avec Raisonnement Guide ===
Echec de la resolutionDans ce notebook, nous avons explore l’utilisation des Large Language Models pour la resolution de Sudoku :
Les LLM s’amelieorent rapidement : - GPT-4 (2023) : ~30-50% succes zero-shot - Claude 3.5 (2024) : ~40-60% succes zero-shot - Modèles futurs : Potentiellement 80-90%+ succes
Cependant, pour les problemes combinatoires comme Sudoku, les solveurs dedies resteront probablement superieurs en raison de leur garantie de correction et de leur performance optimale.
| Notebook | Lien conceptuel |
|---|---|
| Sudoku-01-Backtracking | Algorithme que le LLM peut generer |
| Sudoku-10-ORTools | Solveur optimal pour comparaison |
| Sudoku-16-NeuralNetwork | Autre approche ML (apprentissage supervise) |
| Sudoku-18-Comparison | Comparaison exhaustive de toutes les approches |
Retour au sommaire : Index Sudoku