Futoshiki
Le Futoshiki (不等式, futōshiki), qui veut dire "non égal" en japonais est un casse-tête japonais arrivé en Europe à partir de la fin 2006, rappelant le Sudoku.
Règles
Il est fondé sur une grille carrée dans laquelle sont inscrits des nombres suivant quelques règles simples. Sur une grille de 5x5, les nombres de un à cinq doivent être placés dans chaque ligne et chaque colonne, sans aucune répétition. Les signes "plus grand que" ou "plus petit que" entre les cases sont des indices qui doivent obligatoirement être respectés. Chaque grille possède une solution unique.
Techniques simples de résolution
La résolution d'un puzzle suppose le recours à plusieurs types de techniques logiques[1]. Les nombres présents dans chaque ligne et colonne, de même que les inégalités, restreignent les nombres possibles dans les autres cases de la même ligne et colonne.
La technique des sous-ensembles (paires, triplets, etc.), nus ou cachés, familière aux joueurs de Sudoku, se transpose aisément au Futoshiki. Contrairement au Sudoku, il n'y a toutefois pas de sous-ensembles liés aux blocs 3x3.
Comme un Sudoku, un Futoshiki résolu est un cas particulier de carré latin.
Techniques avancées de résolution
Comme dans le cas du Sudoku, les puzzles de Futoshiki plus durs exigent de recourir à divers types de chaînes.
Un livre récent en anglais Pattern-Based Constraint Satisfaction and Logic Puzzles[2] montre que les techniques développées pour le Sudoku dans un livre plus ancien du même auteur The Hidden Logic of Sudoku[3] se généralisent à n'importe quel problème fini de Satisfaction de Contraintes. Cela inclut les chaînes xy, les fouets (whips) et les tresses (braids). Ce livre montre aussi en détail comment appliquer ces chaînes au Futoshiki.
Ces techniques sont implémentés directement sous forme de règles dans la partie FutoRules du logiciel général de satisfaction de contraintes CSP-Rules, désormais disponible sur la plate-forme GitHub : https://github.com/denis-berthier/CSP-Rules-V2.1
Références
- (en) Denis Berthier, Pattern-Based Constraint Satisfaction and Logic Puzzles, Paris, Lulu, , 492 p. (ISBN 978-1-291-20339-4, lire en ligne)
- (en) « What strategy tips will help me solve Futoshiki puzzles? »
- (en) Denis Berthier, « Pattern-Based Constraint Satisfaction and Logic Puzzles », Lulu Publishers, (ISBN 978-1-291-20339-4), (lire en ligne, consulté le )
- (en) Denis Berthier, « The Hidden Logic of Sudoku », Lulu Publishers, (ISBN 978-1-84753-472-9), (lire en ligne, consulté le )