Le solveur de Sudoku en one-liner d’Arthur Whitney (2011)

 (dfns.dyalog.com)
1 points par GN⁺ 2024-10-07 | 1 commentaires | Partager sur WhatsApp
  • Dans Dyalog APL, sudoku renvoie toutes les matrices solution possibles à partir d’une matrice de puzzle où les cases vides valent 0, et le même problème est implémenté de plusieurs façons dans le style APL/K
  • La cible de base est un Sudoku 9×9, dans lequel chaque bloc 3×3, ligne et colonne doit contenir les chiffres de 1 à 9 sans répétition
  • L’entrée prob contient les valeurs 1-9 dans les cases remplies et 0 dans les cases vides, et l’argument gauche optionnel shape permet aussi de définir des blocs non carrés comme 2×3 ou 3×4
  • L’algorithme de résolution de Veli-Matti Jantunen vectorise la matrice, construit des index de lignes, colonnes et blocs, puis réduit progressivement les candidats en développant d’abord le groupe le plus contraint
  • Les exemples s33 et s22 ont chacun 3 solutions, et 3 4 sudoku s34 en a 2 ; le one-liner en K 5 d’Arthur Whitney et plusieurs réimplémentations APL sont également présentés

Entrée Sudoku et résultat de la fonction sudoku

  • Un puzzle Sudoku est une grille où des blocs 3×3 sont disposés en 3×3 ; chaque case est vide ou contient un chiffre de 1 à 9
  • Une solution doit satisfaire les trois contraintes d’absence de doublons
    • chaque bloc 3×3 contient les chiffres de 1 à 9 sans répétition
    • chaque ligne de 9 cases contient les chiffres de 1 à 9 sans répétition
    • chaque colonne de 9 cases contient les chiffres de 1 à 9 sans répétition
  • La matrice prob utilise les chiffres 1-9 pour les cases remplies et 0 pour les cases vides
  • L’argument gauche optionnel shape spécifie la forme des blocs pour les puzzles qui ne suivent pas la forme carrée par défaut
    • pour une matrice 6×6 dont les sous-zones sont en 2×3, on appelle la fonction sous la forme 2 3 sudoku mat
  • Le résultat est un vecteur contenant toutes les matrices solution
    • s’il n’existe aucune solution, la fonction renvoie ⍬
    • les situations d’erreur peuvent être représentées par '' ; la documentation indique « cela ne devrait pas arriver, mais peut se produire si le nombre de résultats devient énorme »

Déroulement de la solution de Veli-Matti Jantunen

  • L’algorithme traite la matrice Sudoku comme un vecteur et représente séparément les lignes, colonnes et zones Sudoku par des vecteurs d’index
  • Après les vérifications de base, il examine les alternatives une à une dans la liste des candidats
  • À chaque étape, il filtre les éléments possibles de toutes les cases
    • si au moins une case n’a aucune valeur possible, le candidat de solution est éliminé
    • si une case a deux chiffres candidats ou plus, l’algorithme choisit une case dans le groupe le plus contraint et ajoute les combinaisons candidates de cette case à la liste
    • si toutes les cases n’ont plus qu’un seul chiffre possible, la grille est traitée comme une solution et l’algorithme passe au candidat suivant
  • La même section inclut aussi une fonction Shuffle qui mélange une grille Sudoku existante pour en produire une autre

Le one-liner d’Arthur Whitney et les implémentations alternatives

  • L’implémentation alternative de sudoku par David Crossley prend en entrée une configuration N×N et vise les cas où la taille de bloc N*÷2 est entière
    • l’entrée doit être une disposition valide dans laquelle certaines cases contiennent des chiffres de 1 à N et les autres 0
    • dans le résultat, chaque ligne, colonne et bloc doit contenir tous les chiffres de 1 à N
    • l’implémentation s’appuie en interne sur des fonctions auxiliaires comme valid, search, rules, sole, singles, uniques, matches, NinN et setup
  • La solution en K 5 d’Arthur Whitney est présentée sous forme de code sur une seule ligne
x(,/{@[x;y;]'(!10)^x*|/p[;y]=p,:,3/:-3!p:!9 9}')/&~* x
  • Phil Last propose une implémentation sudoku qui transpose le code de Whitney en D-function
  • La réécriture de Morten Kromberg définit explicitement certains composants de K pour rester plus proche de l’original
    • comme la version K, elle prend en entrée et renvoie un vecteur de 81 éléments plutôt qu’une matrice
  • L’implémentation Sudoku de Roger Hui est plus généralisée et traite aussi les puzzles à blocs non carrés
    • svec construit le vecteur solution, et pvex ainsi que pvec développent les placements possibles
    • avl construit la liste des chiffres possibles, et emt trouve les index de ligne et de colonne des cases vides
    • rcb, box, cmap et CMAP construisent les relations de conflit entre lignes, colonnes et blocs

Puzzles d’exemple et nombre de solutions

  • s33 est un exemple 9×9, et le résultat de sudoku s33 comporte 3 solutions
  • La fonction sbox découpe les blocs internes afin d’afficher la grille Sudoku plus lisiblement
    • les 0 sont affichés sous forme de points (·)
    • la sortie prend la forme d’une matrice de caractères avec tracé des frontières entre blocs
  • s22 est un exemple 4×4, et le résultat de sbox¨ sudoku s22 comporte 3 solutions
  • s34 est un exemple utilisant des blocs 3×4
    • 3 4 sbox s34 affiche le puzzle avec séparation visuelle des blocs
    • le résultat de 3 4 sudoku s34 comporte 2 solutions

Liens de référence et éléments associés

À lire aussi

1 commentaires

 
GN⁺ 2024-10-07
Avis sur Hacker News

  • Cette ligne est écrite en K. K est un langage créé par Arthur Whitney à partir d’APL et de Scheme
    x(,/{@[x;y;]'(!10)^x*|/p[;y]=p,:,3/:-3!p:!9 9}')/&~*x

  • J’évalue parfois la complexité d’un code en comparant son nombre de lignes au résultat de la commande suivante
    tar -cf - . | gzip | base64 | wc -l
    Autrement dit, je regarde « à quel point ça se compresse bien ». Quand je vois de l’APL, ça me rappelle les fois où l’on envoie par erreur la sortie de gzip dans le terminal
    p←{(↑⍵)∘{(⍺∨.=⍵)/⍳n×n∘}¨,⍵},(n*÷2){⍵,⍺⊥⌊⍵÷⍺}'⍳n n←⍴⍵
    C’est impressionnant qu’il y ait même des gens capables de suivre ce genre de code en se demandant « peut-on y trouver un bug ? ». On dirait des données binaires compressées dont tout le monde posséderait déjà le même dictionnaire

    • Je me demande sincèrement comment les programmeurs APL envisagent la maintenabilité et la lisibilité. Peut-être commentent-ils le code de façon très détaillée, ou le documentent-ils séparément
    • Si la question est « peut-on y trouver un bug ? », on en voit tout de suite quelques-uns. Il y a des erreurs de syntaxe, comme une apostrophe non fermée et un ∘ sans opérande droit, et n n←⍴⍵ semble indiquer que n est affecté deux fois et que l’on s’attend à ce que ⍵ soit bidimensionnel, mais selon l’intention, _ n←⍴⍵ ou n←⊃⌽⍴⍵ serait plus naturel
      De plus, ⊥ provoque une erreur si ⍴⍵ n’est ni un entier unique ni un vecteur vide, si bien qu’au final ce n’est pas vraiment différent de n←⍴⍵, ce qui rend la chose encore plus déroutante. Plusieurs , redondants et ↑⍵ peuvent aussi être supprimés, et toute l’expression revient en fait presque à p←(n+1)⍴⊂⍳n×n←⍴⍵, une structure qui produit n+1 vecteurs 1..n²
      Malgré son apparence étrange, une fois qu’on apprend les symboles et les opérations de base, APL est étonnamment linéaire. Il faut toutefois du temps pour devenir à l’aise, et quand on y arrive, cela donne l’impression d’avoir un super-pouvoir
    • Quand on pense que des milliards de personnes lisent et écrivent des caractères qui ne sont pas anglais, je ne sais pas si le fait que des gens lisent l’APL est si particulier ou surprenant

  • Il est vrai que les défenseurs du langage mettent en avant sa vitesse, la facilité du traitement de tableaux et sa syntaxe expressive
    https://en.m.wikipedia.org/wiki/K_(programming_language)

    • En revanche, je ne sais pas si la maintenabilité fait partie de ses atouts

  • Le nombre de lignes de code est un mauvais indicateur, car chaque langage a sa propre manière d’utiliser les lignes
    Une meilleure mesure pourrait consister à compter le nombre de nœuds de l’arbre syntaxique correspondant à des symboles non terminaux significatifs, comme les « constantes » ou les « appels de fonction ». Mieux encore, on pourrait aussi tenir compte de la profondeur de cet arbre et de son facteur de branchement

    • J’ai du mal à accepter l’idée selon laquelle seule la sémantique compterait. L’expérience utilisateur du langage, sa clarté, sa manière de structurer la pensée et son expressivité comptent aussi, et la taille visuelle du code influence tout cela
      Une solution en une ligne n’occupe presque pas d’espace à l’écran, ce qui est un gros avantage quand on traite des problèmes complexes. Déplacer les yeux dans l’écran demande beaucoup moins d’effort que passer d’un fichier à l’autre en faisant défiler, et la charge cognitive compte
      Même sans connaître K, voir les constantes alignées donne l’impression d’utiliser une représentation directe des données du problème. Si la culture de K encourage ce genre de code et oriente la pensée vers la directeté et la simplicité, j’aimerais bien introduire cette sauce spéciale dans une équipe
    • Les fonctions intégrées et les API des bibliothèques système faussent ce genre de mesure. Par exemple, HQ9+ se débrouille plutôt bien pour afficher « Hello, world! »
      https://cliffle.com/esoterica/hq9plus/
    • La mesure que je préfère pour la quantité d’information est simplement le nombre de bits, comme en théorie algorithmique de l’information
      https://en.wikipedia.org/wiki/Algorithmic_information_theory
    • Ce one-liner a clairement été fait pour s’amuser, et personne ne prétend raisonnablement qu’il s’agit de code facile à lire. Discuter des définitions ici passe à côté de l’essentiel. Le point important est que « K permet d’écrire du code extrêmement dense »

  • Je me suis souvent demandé si l’utilisation de langages comme APL/K permet réellement aux programmeurs de penser les problèmes plus efficacement

    • En tant que programmeur kdb+/Q, je dirais que cela dépend du type de problème. Quand on manipule des tableaux de données, il est clairement plus simple de penser et d’écrire l’opération consistant à additionner deux tableaux puis à en prendre la moyenne sous la forme avg a+b
      Dans un langage non centré sur les tableaux, il faudrait probablement des vérifications de bornes, une grosse boucle for, des variables temporaires pour la somme et le nombre d’éléments, etc. Ce qui prendrait environ 6 lignes dans un langage comme C se fait en 6 caractères en Q
      Cela dit, chaque langage possède des fonctionnalités qui aident à raisonner sur certains problèmes. Les langages fonctionnels avec types algébriques et filtrage par motif, comme OCaml ou F#, sont meilleurs qu’un gros switch ou une chaîne de if-else-if, et les langages avec du sucre syntaxique comme async/await sont avantagés pour gérer la concurrence
    • Pour les familles de problèmes qui se vectorisent facilement, les langages centrés sur les tableaux rendent la réflexion et les solutions plus efficaces. Ils permettent d’abstraire les détails des structures de données et des itérations
      Quand je travaillais comme quant, j’ai beaucoup utilisé kdb+/q pendant plus de cinq ans pour des stratégies de moyenne fréquence, mais lorsque je suis passé au trading haute fréquence, avec des calculs sur carnet d’ordres difficiles ou peu efficaces à vectoriser, continuer à utiliser un langage centré sur les tableaux rendait au contraire le raisonnement plus complexe
    • Dans une présentation sur Dyalog, un langage moderne de la famille APL, j’ai entendu l’argument selon lequel cette notation permet de reconnaître plus facilement certains idiomes
      https://youtu.be/PlM9BXfu7UY?si=ORtwI1qmfmzhJGZX&t=3598
      Le passage concerné s’inscrivait dans le contexte d’un compilateur, mais l’ensemble de la présentation traite Dyalog et APL comme un système de notation mathématique. L’idée centrale est qu’il peut être plus facile d’optimiser des expressions mathématiques que du code ordinaire
    • Hillel Wayne aborde parfois ce sujet dans sa newsletter. Il m’a convaincu qu’il réfléchit effectivement mieux à certains problèmes dans des langages de tableaux, mais j’ai encore du mal à imaginer ce que cette expérience peut faire ressentir
    • Ce qui est appréciable dans le style des langages de tableaux, c’est que lorsqu’on discute de variantes d’algorithmes, les fragments de code pertinents ne font que quelques caractères et peuvent être intégrés directement dans le texte. Dans les langages verticaux traditionnels, où il faut plusieurs lignes, voire des dizaines de lignes, pour dire la même chose, il faut sans cesse alterner entre blocs de code et explications

  • L’un des points les plus importants ici est que le générateur de problèmes en haut est très clair. C’est ce qui distingue les langages notationnels à la Iverson, y compris J et K, des autres langages.
    Il n’a pas l’élégance ni la puissance de la solution en une ligne, mais il est très propre et compréhensible même sans commentaires stricts. Cela dit, je ne pense pas que lamp soit un bon symbole de commentaire.
    La solution en une ligne est étonnante, et la programmation tacite est à vous retourner le cerveau. L’idée d’utiliser la concision particulière des langages à glyphes pour expliquer et pratiquer la programmation fonctionnelle, puis de l’appliquer à des tableaux entiers, relève du génie.
    https://www.jsoftware.com/papers/fork.htm

    • Ce n’est pas parce qu’on peut tout écrire sur une seule ligne sans espaces qu’il faut forcément le faire.
      Bien sûr, si l’on retire cette possibilité, on peut forcer l’écriture d’un code plus verbeux, mais cela réduit fortement leur intérêt comme outils interactifs. Les langages à la Iverson permettent d’écrire du code très court, ce qui les rend utiles pour le travail interactif. Dans ce contexte, le code n’est même pas enregistré, c’est donc vraiment du code write-only.
      Quand on écrit du code destiné à aller dans un fichier, on choisit le style que l’on veut, et dans ce cas je recommande d’écrire de façon moins compacte. Même ainsi, les langages à la Iverson produisent, dans un style verbeux, un code bien plus court que la plupart des langages.

  • La plupart des gens sont rebutés par les symboles, mais ce n’était pas mon problème.
    J’aime APL et les langages de tableaux, et ce que j’ai appris m’a beaucoup aidé dans d’autres langages. Mais ils ne sont pas devenus mes outils du quotidien ; pas à cause des symboles, plutôt parce qu’après 3 ou 4 ans d’utilisation intermittente, je me suis heurté à un mur que je n’ai pas réussi à franchir.
    Dans les autres langages, il existe généralement une approche générale qui permet de résoudre un problème, même grossièrement, puis, quand on découvre le « truc » propre à ce problème, on peut le rendre plus élégant et plus efficace. Avec APL, j’avais l’impression qu’il n’y avait pas ce genre de détour provisoire : soit on connaît le truc, soit on ne le connaît pas.
    Je ne sais pas vraiment si c’est effectivement le cas, si l’on développe une intuition de résolution de problèmes en apprenant suffisamment de trucs, si cela reste jusqu’au bout une affaire de trucs, ou si je suis simplement passé à côté du document décrivant les stratégies essentielles.

    • Cette impression n’est pas fausse. Quand on apprend les langages de tableaux, il est très facile de ressentir cela. Quelqu’un qui les utilise depuis longtemps peut voir un problème et dire : « Pourquoi as-tu fait si compliqué, il suffisait d’utiliser ⍸⍣¯1 », alors qu’il est fort possible que personne ne vous ait jamais dit que ⍸ avait une opération inverse ni comment l’utiliser.
      Même après des années à utiliser ces langages, les murs de code que produisent certains programmeurs de tableaux restent un peu intimidants. Je comprends pourquoi ils écrivent ainsi, mais personnellement je préfère qu’il y ait un peu d’espace dans le code.
      Je suis en train de créer un langage de tableaux basé sur APL, et l’un de mes objectifs initiaux était de faire du style impératif un citoyen de première classe, sans punir les débutants qui utilisent des choses comme des instructions if. Je vois ce style comme un entre-deux entre l’APL pur et les langages impératifs classiques.
      https://codeberg.org/loke/array/src/branch/master/array/standard-lib/output3.kap
    • Le mur que tu décris est un vrai problème dans les parcours actuels d’initiation à APL. J’ai même fait une présentation précisément sur ce sujet l’an dernier, et ce n’est absolument pas une faute personnelle.
      Cela ne signifie pas non plus que ce soit une limite du langage lui-même. D’après mon expérience, franchir ce mur correspond justement au moment où le paradigme se met en place. Ce n’est qu’après avoir bricolé pendant environ 500 heures sur un prototype de parseur YAML pendant un an que les pièces ont commencé à s’assembler.
      Le cœur du sujet me semble être une combinaison de principes de conception pilotée par les données, de l’usage concret des propriétés iversoniennes d’une bonne notation dans l’architecture logicielle, et de la familiarité avec les idiomes ainsi qu’avec la manière dont ils expriment les concepts du domaine.
      https://dyalog.tv/Dyalog23/?v=J4cg6SV92C4
      https://www.jsoftware.com/papers/tot.htm

  • Il existe une vidéo sur ce sujet.
    https://www.youtube.com/watch?v=DmT80OseAGs
    On peut essayer la solution directement sur https://tryapl.org/.

  • Il pourrait être intéressant de comparer cette ligne unique aux solutions de code golf dans plusieurs langages de programmation.
    https://codegolf.stackexchange.com/questions/tagged/sudoku?tab=Votes

    • Fait amusant, pour ce problème précis — résoudre un sudoku par force brute — la solution arrivée en tête est justement un fragment de K. La deuxième est une solution en J inspirée de la solution en K.
      https://codegolf.stackexchange.com/a/5030