Jupyter-Puzzles

Ce dépôt contient des notebooks jupyter (fichiers d'extension ipynb), avec noyau python ou sage, ayant pour objet la résolution de puzzles, de problèmes logiques, etc.
Si vous clonez tout ou partie du dépôt, veillez à respecter l'arborescence des fichiers.

1 Python

Utilisation d'un noteboook jupyter xxx.ipynb avec un noyau Python

• Si Python, avec jupyter, est installé sur votre machine, utiliser la commande jupyter notebook dans un répertoire qui contient xxx.ipynb ou ouvrir le fichier dans VScode ;
• sinon, avec un compte Google, le plus simple est de téléverser les fichiers dans un sous répertoire de Mon Drive/Colab Notebooks/ dans Google Drive et d'ouvrir Mon Drive/Colab Notebooks/.../xxx.ipynb dans un navigateur. Noter que cela permet aussi de faire fonctionner Python sur un smartphone.

1.1 Permutations (permutations.ipynb)

Génération de toutes les permutations d'un ensemble (fini) par un joli algorithme et application à des petites énigmes.

1.2 Parcours de graphe (parcours.ipynb)

Fournit trois fonctions python utilisées par d'autres notebooks

• dfs parcours en profondeur, utilisé par solitaire.ipynb
• bfs parcours en largeur
• aStar algorithme A*, utilisé par sokoban.ipynb, 8-puzzle.ipynb et rush-hour.ipynb

1.3 Solitaire (solitaire.ipynb)

Utilisation du parcours en profondeur d'un graphe pour la résolution de solitaires, par exemple anglais, français ou allemand :

                 

1.4 Sokoban (sokoban.ipynb)

Utilisation de l'Algorithme A* pour trouver une solution optimale (nombre minimum de déplacements) d'un sokoban de pas trop grande dimension, par exemple, le microcosmos-31 de Aymeric du Peloux:

                 

1.5 8-puzzle (8-puzzle.ipynb)

Utilisation de l'Algorithme A* pour trouver une solution optimale (nombre minimum de déplacements) d'une version simplifiée (8 pièces au lieu de 15) du 15-puzzle

1.6 Rush Hour (rush-hour.ipynb)

Utilisation de l'Algorithme A* pour trouver une solution optimale

1.7 Marche du cavalier (cavalier.ipynb)

Application de la notion de cycle hamiltonien d'un graphe à la résolution du problème du cavalier :

        

1.8 Nonograms (nonogram.ipynb)

Résolution de nonograms pas trop difficiles et génération d'une suite d'images expliquant cette résolution pas à pas.

Un exemple simple :

Un autre plus compliqué. et quelques autres

1.9 Automates (automates.ipynb)

Applications de la théorie des automates à la résolution de problèmes de bouteilles et de de passage de rivière, ainsi que de l'énigme dite des 4 jetons ou du barman aveugle.

1.10 Deux problèmes de logique (logique.ipynb)

choisis parmi les plus beaux (selon moi) problèmes du type "je sais, je sais pas" : le problème de Freudenthal et le problème de Axel Born, Kor Hurkens et Gerhard Woeginger, tous deux référencés ici.

1.11 Mastermind (mastermind.ipynb)

Faire jouer à l'ordinateur le rôle du décodeur dans le jeu Mastermind. L'algorithme utilisé, dû à Donald Knuth, est nommé five-guess car il permet, dans le cas du mastermind classique ($4$ positions et $6$ couleurs), de trouver le code caché en au plus cinq propositions (cinq motifs proposés).
Une autre méthode (D. L. Greenwell) est proposée qui consiste à toujours proposer les 6 motifs suivants (dans 89 % des cas, les 5 premiers suffisent) :

        🔴🟢🟢🔴
        🟢🔵⚫🟡
        🔵🔵🔴🔴
        🟡⚫🟢🟡
        ⚫⚪⚫⚪
        ⚪⚪🟡🔵

1.12 Rubik's Cube 2x2x2 (rubikcube2x2x2.ipynb)

Utilisation de la notion de parcours en largeur d'un graphe pour calculer efficacement une solution optimale d'un Rubik's Cube 2x2x2.

Pour être complet, le notebook comprend aussi une interface avec l'excellent solveur de Victor Cabezas qui calcule en un temps très raisonable une solution presque optimale d'un Rubik's Cube classique 3x3x3. Pour l'utiliser : pip install rubik_solver

1.13 Snake Cube (snakecube.ipynb)

Calcul des solutions d'un cube serpent :

        

1.14 Fonction de Grundy et noyau d'un graphe acyclique (noyau-graphe.ipynb)

Application à quelques jeux impartiaux sans partie nulle : blackjack mathématique, Nim, Marienbad, Wythoff et Euclide.

2 Programmation par contraintes

Programmation par contraintes, Louis-Martin Rousseau et Gilles Pesant constitue une bonne introduction aux algorithmes utilisés en PPC (Programmation Par Contraintes) par les solveurs disponibles dans Python, comme OR-Tools, le solveur de Google .

2.1 Le problème SAT (SAT.ipynb)

Implémentation de l'algorithme de Davis–Putnam–Logemann–Loveland (DPLL) de résolution du problème de satisfiabilité d'une FNC.

On applique SAT à la résolution de petits problèmes de PPC comme la résolution du problème du zèbre, de sudokus et du problème des 8 reines.

2.2 Utilisation de cpmpy

Voir la documentation ; en voici un très court résumé.

Exemples (cpmpy-exemples.ipynb)

5 exemples d'applications du module CPMpy dont

Application de la théorie des graphes à la criminologie

Marche du fou :

2.3 Génération d'explications pour la résolution de problèmes de satisfaction de contraintes (explications.ipynb)

Notebook dont l'essentiel est issu de la page github de cpmy.

A lire en parallèle avec l'un des trois notebooks suivants :

Le problème du zèbre (zebre.ipynb)

Génération d'une suite d'explications pas à pas pour la résolution du problème du zèbre.

Sudoku (sudoku.ipynb)

Production d'une suite d'images expliquant la résolution case après case d'une grille de sudoku :

Mosaïque et Démineur (mosaic.ipynb)

Production d'une suite d'images expliquant la résolution pas à pas d'une grille de mosaïque ou de démineur :

Mosaïque :

...

Démineur :

...

3 Sage

3.1 Utilisation d'un noteboook jupyter xxx.ipynb avec un noyau SageMath

• si SageMath est installé sur votre machine, utiliser la commande sage -n jupyter dans un répertoire qui contient xxx.ipynb ou ouvrir le fichier dans VScode ;
• ou vous pouvez ouvrir un compte sage.syzygy.ca ou cocalc.

3.2 Rubik's Cube 3x3x3 (rubikcube.ipynb)

Interface avec les solveurs de Rubik's Cube fournis par Sage (si le package externe rubiks est installé ¹) et affichage graphique des solutions:

3.3 Rubik's Snake (rubiksnake.ipynb)

Etude d'un Rubik's Snake donné par son code, par exemple 000000220220220102202200 et aide à sa réalisation :

3.4 Problème de la couverture exacte (algorithmeX.ipynb)

L'algorithme X de Knuth est implémenté efficacement avec la méthode, incluse dans Sage, des liens dansants de Donald Knuth.

tests.ipynb

Résolution de sudokus et du problème des 8 reines

puzzles-carres.ipynb

Puzzles de polyominos :

puzzles-hexagones.ipynb

Puzzles de polyhexs :

puzzles-triangles.ipynb

Puzzles de polyiamonds :

puzzles-triangles.ipynb

Puzzles de polyiabolos :

puzzles-3D.ipynb

Puzzles de polycubes :

Footnotes

1. rubiks est pré-installé sur sage.syzygy.ca et cocalc ↩