L'objet des exercices suivants est de résoudre par la force brute, en un minimum de lignes de code, quelques puzzles classiquement utilisés comme exercices de programmation.
On ne cherchera pas à écrire un algorithme optimal pour le cas général, mais simplement à écrire le plus rapidement et le plus simplement possible un programme donnant la solution du cas considéré.
Le problème consiste à placer 8 reines sur un échiquer sans que deux d'entre elles s'attaquent mutuellement. Il s'agit donc de les placer sur un carré 8×8 de manière à ce qu'il n'y en ait pas deux dans une même ligne, colonne ou diagonale.
La condition sur les lignes et les colonnes signifie que pour un placement correct, les numéros de colonne forment une permutation p de ceux des lignes. Les diagonales sont définies par i+j=constante et i-j=constante.
On sélectionnera donc les permutations p telles que les ensembles {i+p(i)} et {i-p(i)} soient tous deux de cardinal 8.
La généralisation à un échiquier n×n est immédiate.
Jusqu'à quelle valeur de n le programme répond-il en un temps acceptable ?
Un cryptarithme est une équation du type
SEND + MORE = MONEY (le premier du genre)
ou encore
MARS + SATURNE + NEPTUNE = PLANETES
Le jeu consiste à remplacer chaque lettre par un chiffre différent (entre 0 et 9) de manière à ce que l'équation soit vérifiée.
Pour le premier exemple, la seule solution est 9567 + 1085 = 10652 si on interdit les 0 initiaux, et pour le second, c'est 8724 + 4765290 + 9016590 = 13790604.
Ecrire un solveur de cryptarithmes (une dizaine de lignes pour la fonction solve).
On pourra lui passer un argument du type SEND + MORE == MONEY pour lui éviter une substitution
et permettre d'utiliser directement la fonction eval après substitution des chiffres aux lettres.
L'équation poura contenir n'importe quelle expression arithmétique, par exemple SIX * CINQ == TRENTE ou 3*MOT == TOM-1.
Recherchez quelques exemples intéressants sur le web et résolvez les.
La suite de Conway est une suite de chaines de digits dans laquelle chaque terme décrit le précédent. On commence avec '1'. On voit donc « un 1 » et on écrit '11'. On voit alors « deux 1s » et le terme suivant est '21'. Ensuite, '1211', '111221', etc. Utiliser itertools pour écrire une fonction engendrant les termes successifs de cette suite.
Ecrivez en Python l'algorithme de Heap pour engendrer les permutations.
Comparez les performances de votre code avec celles de la fonction permutations d'itertools.
En utilisant le modèle vu en cours, modifiez votre code en déclarant les types idoines (int n, cdef int i, cdef list A,c) dans un fichier .pyx et compilez le avec Cython. Refaites la comparaison avec itertools. Que faut-il en conclure ?