Hashi:Linkdoku Bridges Puzzle

À Hashiwokakero, vous êtes le roi des îles et votre travail consiste à relier les îles en fonction de leur population - les petites îles n'ont besoin que d'un seul pont (il est indiqué 1 sur l'île), et les grandes îles ont besoin de plus de ponts (le nombre dans l'île ). Alors rappelez-vous que tout cela est un seul royaume, le vôtre, vous devez donc permettre à tous les citoyens de voyager entre toutes les îles. Aussi connu sous le nom de ponts/baguettes

RÈGLES:

1. Connectez les îles (les cercles avec des chiffres) avec autant de ponts que le nombre dans l'île.

2. Il ne peut y avoir plus de deux ponts entre deux îles.

3. Les ponts ne peuvent pas traverser des îles ou d'autres ponts.

4. Les ponts formeront un lien continu entre toutes les îles.

Caractéristiques:

* 720 puzzles de hashi classiques gratuits

* 480 puzzles bonus supplémentaires publiés gratuitement chaque mois

* Plusieurs tailles, de 6x9 à 14x21

* Indice d'île connectable

* Met en évidence les îles connectées

* Défaire refaire

* Enregistré automatiquement

* Instantanés pour des puzzles complexes

* Sauvegardez et restaurez la progression du puzzle dans le Cloud

* Plusieurs beaux thèmes

* Prise en charge de plusieurs langues

* Minuterie

Méthodes de résolution :

Résoudre un puzzle Hashiwokakero est une question de force procédurale : après avoir déterminé où un pont doit être placé, le placer là peut éliminer d'autres endroits possibles pour les ponts, forcer le placement d'un autre pont, etc.

Une île affichant '3' dans un coin, '5' le long du bord extérieur ou '7' n'importe où doit avoir au moins un pont rayonnant dans chaque direction valide, car si une direction n'avait pas de pont, même si toutes d'autres directions arboraient deux ponts, pas assez auront été placés. Un '4' dans un coin, un '6' le long de la frontière ou un '8' n'importe où doit avoir deux ponts dans chaque direction. Cela peut être généralisé car des ponts ajoutés obstruent les routes : un « 3 » qui ne peut être parcouru que verticalement doit avoir au moins un pont chacun pour monter et descendre, par exemple.

Il est courant de rayer ou de remplir les îles dont le quota de pont a été atteint. En plus de réduire les erreurs, cela peut également aider à localiser les "courts-circuits" potentiels : en gardant à l'esprit que toutes les îles doivent être reliées par un réseau de ponts, un pont qui créerait un réseau fermé auquel aucun autre pont ne pourrait être ajouté ne peut que être autorisé s'il donne immédiatement la solution au puzzle complet. L'exemple le plus simple de ceci est deux îles montrant '1' alignées l'une avec l'autre; à moins qu'elles ne soient les deux seules îles du puzzle, elles ne peuvent pas être reliées par un pont, car cela compléterait un réseau auquel on ne peut pas ajouter, et obligerait donc ces deux îles à être inaccessibles par d'autres.

Tout pont qui isolerait complètement un groupe d'îles d'un autre groupe ne serait pas autorisé, car on aurait alors deux groupes d'îles qui ne pourraient pas se connecter. Cette déduction, cependant, n'est pas très courante dans les puzzles Hashiwokakero.

Déterminer si un puzzle Hashiwokakero a une solution est NP-complet, par une réduction de la recherche de cycles hamiltoniens dans des graphiques de distance unitaire à coordonnées entières. Il existe une solution utilisant la programmation linéaire entière dans les exemples MathProg inclus dans GLPK. Une bibliothèque de puzzles comptant jusqu'à 400 îles ainsi que des résultats de programmation linéaire entière sont également rapportés.