Bienvenue sur le site de Jean-Marc

Jeu Sokosol

Version personnelle du jeu Sokoban

Origine

Le jeu Sokoban a été inventé en 1982 par le japonais Hiroyuki Imabashi. La société Thinking Rabbit a diffusé et détient les droits des 50 tableaux originaux.

Principe

Un magasinier doit ranger des caisses à des emplacements définis, et ne peut pour cela que les pousser, une seule à la fois.
Si le but est de ranger toutes les caisses, il faut évidemment le faire dans un minimum de mouvements.
Il est également possible de rechercher le minimum de poussées, qui ne correspond pas nécessairement au minimum de mouvements.

Le solveur

Intéressé par ce jeu qui mérite le qualificatif de "casse tête", j'ai voulu réaliser un programme permettant d'en résoudre les tableaux de façon automatique.
J'ai opté pour une recherche exhaustive, sachant bien qu'au-delà d'une certaine taille ou d'une certaine complexité ma machine ne permettra jamais d'obtenir le résultat.
J'ai donc placé dans le programme des moyens de limiter la recherche ou de l'arrêter proprement, afin de ne pas être bloqué.
Aujourd'hui, parmi les quelque 21389 tableaux trouvés sur internet et importé dans le format compatible avec mon solveur (sans compter une collection de 10000 tableaux, dont l'import ne me parait pas utile, puisque ces tableaux sont de taille un peu trop grande), j'en ai résolu environ 3000, et ce nombre progresse, lentement, mais sûrement (je ne fais quand même pas que cela).
Je précise que le solveur recherche uniquement le nombre de mouvements optimal, ce qui veut dire qu'il est tout à fait possible de trouver une solution avec moins de poussées.

Bien que le solveur tourne sous Windows et sous Linux, je ne l'utilise que sous Linux pour des raisons de rapidité.
En effet, des essais ont mis en évidence que la version Linux, bien que compilée à partir du même code Pascal Objet avec Lazarus/FPC, est environ quatre fois plus rapide que sous Windows.
Maintenant, utilisant FpGUI, compilé également avec FPC, me permet de diviser à nouveau les temps d'exécution de manière significative. Une version Delphi donnait les mêmes résultats qu'avec Lazarus sous Windows.
Je ne tenterai pas une version C ou C++, qui n'apporterait rien de plus hormis un code beaucoup moins lisible.

Le jeu

Bien évidemment, pour réaliser un solveur, il m'a fallu programmer une version du jeu.
J'ai donc décidé de diffuser cette version personnelle.
Cette version ne se voulant pas concurrente des versions déjà disponibles sur internet, je la propose en libre téléchargement, ainsi qu'un certain nombre de tableaux, au format compatible, et qui sont par ailleurs libres de droits.
Je précise que je n'ai créé aucun tableau, et j'ai fourni le nom des auteurs.
Il m'est arrivé de trouver des doublons de tableaux provenant d'auteurs différents, et de n'utiliser qu'un nom, arbitrairement et sans moyen de vérification.

Une petite aide jointe au jeu vous apportera des détails sur les fonctionnalité additionnelles.

Un tableau des résultats trouvés à l'aide du solveur est disponible.

Les versions