Résoudre un Sudoku 4×4 par backtracking

Énoncé

Le programme lit une grille 4×4 de Sudoku sur l'entrée standard : 4 lignes de 4 chiffres séparés par des espaces, où 0 représente une case vide. Il affiche la grille résolue dans le même format. La grille d'entrée est garantie avoir une solution unique. L'algorithme de backtracking essaie chaque valeur possible pour chaque case vide et revient en arrière en cas de conflit.

Contraintes

• La grille est exactement 4×4.
• Les valeurs connues sont des entiers entre 1 et 4 ; les cases vides sont codées 0.
• Chaque ligne, colonne et bloc 2×2 (en-haut-gauche, en-haut-droite, en-bas-gauche, en-bas-droite) doit contenir exactement les valeurs 1, 2, 3, 4.
• La grille d'entrée a une solution unique.
• Solution réalisable dans tout langage généraliste avec sa seule bibliothèque standard.

Exemple

CopierEntrée :
1 0 0 2
0 0 1 0
0 2 0 0
3 0 0 4

Sortie :
1 3 4 2
2 4 1 3
4 2 3 1
3 1 2 4