Bonjour à tous,
Nous avons développé un petit jeu de logique avec un ami et nous cherchons à dénombrer les grilles de jeu possibles. Je ne suis pas mathématicien et je tiens à m’excuser par avance au sujet d’éventuelles imprécisions. Le jeu revient à chercher un chemin Hamiltonien dans un graph avec des contraintes.
Le but est de retrouver un chemin de nombres consécutifs dans une grille dont les cases sont hexagonales. Certains nombres ainsi que des marques de passage du chemin sont déjà placés dans la grille de manière à ce que le puzzle n’ait qu’une seule solution. Une marque de passage de chemin est représentée par un petit symbole en forme de losange placé entre deux cases qui doivent contenir des nombres consécutifs.
Dans un premier temps, nous cherchons à dénombrer les solutions possibles pour une taille de grille donnée ce qui revient à dénombrer les chemins Hamiltoniens possibles dans la grille.
Pour des grilles de petites tailles (36 cases) j’ai pu estimer un minorant numériquement en étudiant le nombre de doublons obtenus sur un grand nombre de solutions produites par le générateur. Je trouve environ 100 millions pour ce minorant. Cette méthode peut difficilement être utilisée pour les grilles de plus grande taille à cause du temps de calcul et du grand nombre de solutions possibles.
Auriez-vous des idées sur la démarche à suivre pour faire un dénombrement plus rigoureux ?
Le jeu est publié en ligne sur www.rikudo.fr.
Bonne soirée,
Xavier
-----
