Le solveur de Sudoku en une ligne d'Arthur Whitney (2011)

Algorithme de résolution de Sudoku

• Description du problème de Sudoku

  • Une grille de Sudoku est composée de carrés 3×3 formant une grille 3×3, et chaque cellule est soit vide, soit contient un chiffre de 1 à 9.
  • Chacun des carrés 3×3, des 9 lignes et des 9 colonnes doit contenir les 9 chiffres sans doublon.
  • Un exemple de problème et une méthode de résolution sont fournis.

• Vue d'ensemble de l'algorithme

  • La matrice est traitée comme un vecteur, avec les lignes, les colonnes et les zones du Sudoku représentées par des vecteurs d'index.
  • L'algorithme effectue les vérifications de base du puzzle et trouve une solution en filtrant les éléments possibles.
  • Si une cellule est vide, il passe à la liste suivante, et si une cellule contient plusieurs chiffres possibles, il choisit dans le groupe le plus contraint pour l'ajouter à la liste.
  • Lorsque toutes les cellules ne contiennent plus qu'un seul chiffre, la solution est trouvée.

• Notes techniques

  • Solution fournie par Veli-Matti Jantunen, avec la possibilité d'utiliser ⍺ pour représenter des rectangles de Sudoku.
  • Le résultat renvoie un vecteur de toutes les solutions, ⍬ s'il n'y en a aucune, et '' en cas d'erreur.
  • L'algorithme est simple : il traite la matrice comme un vecteur et cherche la solution en filtrant les éléments possibles.

• Autres approches

  • Des implémentations alternatives de David Crossley et Arthur Whitney sont proposées.
  • Différents styles de codage et approches sont présentés.

• Exemples et usages

  • Divers exemples de résolution de Sudoku sont fournis.
  • Une fonction est également proposée pour séparer les carrés internes afin de rendre les grilles plus lisibles.

Résumé de GN⁺

• Divers algorithmes et styles de codage pour résoudre des Sudoku sont présentés.
• Les puzzles Sudoku sont utiles pour améliorer la pensée logique et les capacités de résolution de problèmes.
• La variété des approches permet de gagner en flexibilité dans la résolution.
• Parmi les puzzles aux mécaniques proches, Kakuro et KenKen sont recommandés.

[GN⁺]

Avis sur Hacker News

• Le langage K a été créé par Arthur Whitney à partir d’APL et de Scheme, avec un accent sur la vitesse, le traitement des tableaux et une syntaxe expressive
• Lorsqu’on mesure la complexité du code, on compare le nombre de lignes de code et le degré de compression
  • Le code APL donne l’impression de données binaires compressées, et cela impressionne ceux qui sont capables de le comprendre
• Le nombre de lignes de code n’est pas un bon critère de mesure, car il est utilisé différemment selon les langages
  • Une meilleure méthode consiste à prendre en compte le nombre de nœuds de l’arbre syntaxique, sa profondeur et les facteurs de branchement
• La clarté du problème est importante, et les langages iversoniens (dont J et K) se distinguent des autres langages
  • Une solution en une ligne est surprenante et utile pour décrire et exécuter efficacement des tableaux
• Certains estiment qu’un programme K devrait se terminer par QED, et s’interrogent sur le lien avec KQED
  • KQED est un partenaire PBS de la Bay Area
• Certains se demandent si des langages comme APL/k permettent de penser les problèmes plus efficacement
• Apprendre APL et les langages de tableaux a aidé avec d’autres langages, mais on finit par ne plus les utiliser au quotidien
  • Avec APL, il est difficile de résoudre un problème si l’on ne connaît pas déjà une méthode spécifique
• Il existe de meilleures solutions que certaines solutions inefficaces vues dans des handbooks de conception d’algorithmes
  • Un billet de blog a été écrit à ce sujet en 2015
• Une solution Sudoku avec Scryer Prolog est lisible et puissante, avec d’excellentes capacités de résolution de contraintes
  • Scryer Prolog est un Prolog moderne, performant et conforme à l’ISO