Klotski

Klotski est un casse-tête à blocs coulissants dans lequel le joueur doit amener un grand bloc 2x2 vers une position de sortie désignée en le faisant glisser, ainsi que d’autres blocs, à l’intérieur d’un plateau fermé. Le plateau comporte généralement 4 colonnes et 5 lignes et contient des blocs de différentes tailles — un bloc 2x2, plusieurs blocs 2x1 (horizontaux ou verticaux) et des blocs 1x1 — ainsi que deux cases vides exactement qui permettent de déplacer les blocs. Le défi consiste à faire passer le grand bloc à travers le plateau encombré pour atteindre la sortie, généralement située en bas au centre.

Règles

1. Le plateau est un plateau de 4x5 cases contenant des blocs de différentes tailles et deux cases vides.
2. Les blocs peuvent être déplacés horizontalement ou verticalement vers un espace vide adjacent, mais ne peuvent pas être soulevés, pivotés ni placés au-dessus d’autres blocs.
3. Le but est de déplacer le grand bloc 2x2 vers une position cible (généralement le centre inférieur du plateau, qui comporte une ouverture).
4. Tous les autres blocs sont des obstacles qu’il faut réorganiser afin de créer un chemin pour le grand bloc.

Types de blocs (configuration classique)

• 1 grand bloc (2x2) — celui que vous devez libérer
• 1 bloc haut (1x2 vertical)
• 4 blocs moyens (2x1 horizontaux ou 1x2 verticaux, selon la configuration)
• 4 petits blocs (1x1)
• 2 cases vides

Stratégies

• Visualisez le chemin de sortie : le bloc 2x2 a besoin d’un passage dégagé de 2 cases de large entre sa position actuelle et la sortie. Votre tâche consiste à créer ce passage.
• Déplacez d’abord les petits blocs : les petits blocs 1x1 sont les plus polyvalents. Utilisez-les pour créer un espace temporaire permettant de déplacer les blocs plus grands.
• Évitez les déplacements circulaires : il est facile d’annuler accidentellement les progrès réalisés. Réfléchissez bien à chaque déplacement et essayez de suivre la direction générale du grand bloc.
• Commencez par la sortie : dégagez d’abord l’espace près de la sortie, puis remontez progressivement pour créer un chemin permettant au gros bloc de descendre.
• Utilisez des zones de stationnement : déplacez les blocs obstacles vers des zones où ils n’auront plus besoin d’être déplacés. Les coins constituent souvent de bons emplacements de stationnement.
• Défi du nombre minimum de coups : la configuration classique (« Pennant Puzzle » ou « Daughter in the Box ») nécessite au minimum 81 coups. Tenter de s’approcher de ce minimum ajoute une difficulté supplémentaire.

Les origines du Klotski sont quelque peu floues, plusieurs personnes revendiquant sa création. Ce casse-tête semble être apparu au début du XXe siècle, indépendamment les uns des autres, dans plusieurs pays. Des variantes de casse-têtes à blocs coulissants ont été brevetées aux États-Unis et en Europe entre 1900 et 1930. Le nom « Klotski » vient du mot polonais « klocki », qui signifie « blocs ».

La configuration la plus célèbre de ce casse-tête est connue en Chine sous le nom de « Hua Rong Dao » (华容道), d’après un col légendaire tiré du roman classique chinois « Le Roman des Trois Royaumes ». Dans cette histoire, le seigneur de guerre Cao Cao doit s’échapper par le col de Huarong après sa défaite lors de la bataille des Falaises Rouges (208 apr. J.-C.). Dans le casse-tête, le grand bloc représente Cao Cao, tandis que les autres blocs représentent les généraux qui lui barrent la route. Ce cadre narratif a rendu le casse-tête extrêmement populaire en Chine, où il fait partie intégrante de la culture depuis plus d’un siècle.

En Occident, ce casse-tête est apparu sous divers noms : « Pennant Puzzle » (commercialisé par la société Embossing Company dans les années 1930), « Dad's Puzzle » et simplement « Sliding Block Puzzle ». Martin Gardner a présenté les casse-têtes à blocs coulissants dans sa chronique du Scientific American, les faisant ainsi découvrir à un large public de mathématiciens. Les informaticiens ont utilisé le Klotski et ses variantes comme problèmes de référence pour les algorithmes de recherche et la planification en intelligence artificielle.

L’analyse mathématique du Klotski est très poussée. Il a été démontré que ce casse-tête est PSPACE-complet dans sa forme générale, ce qui signifie qu’il figure parmi les problèmes les plus difficiles pouvant être résolus avec un espace polynomial. La configuration classique a fait l’objet d’une analyse exhaustive par ordinateur, confirmant la solution optimale en 81 coups (ou 116 si l’on compte chaque déplacement d’une seule case comme un coup). Il existe de nombreuses variantes de configurations présentant différents niveaux de difficulté, et la conception de nouvelles configurations intéressantes reste un domaine d’activité dynamique dans la conception de casse-têtes.