Algorithm to create a puzzle for the game bridges (NOT the card game bridge).

A question about making puzzles for bridges (also known as Hashiwokakero or Hashi).  https://en.wikipedia.org/wiki/Hashiwokakero

Is there an algorithm to generate a puzzle given the size of grid?  Please provide algorithm or link to one if it exists.
LVL 45
AndyAinscowFreelance programmer / ConsultantAsked:
Who is Participating?
 
☠ MASQ ☠Commented:
Nice :)

Here's an nice outline paper from a  Univ. Leiden student which covers some of the programmatic requirements and then realises why generation is such a pain!
http://liacs.leidenuniv.nl/assets/Bachelorscripties/2009-11TimoMorsink.pdf
0
 
☠ MASQ ☠Commented:
It's a great question Andy

It's so much easier to write an algorithm to solve Hashi than it is to create simply because not all combinations can be solved.  This means any Hashi generator must by definition use recursion to check that a valid grid has been created and this in turn means as you increase the dimensions of the grid the odds on being unable to link all the islands in accordance with the rules becomes smaller and the validation process longer.

There are some good math texts on the theory but apart from very small scale grids I don't know of anything online.  Solvers you'll find everywhere as it's a standard math/basic coding exercise for students.

I'd also be interested to see what gets found here.
0
 
AndyAinscowFreelance programmer / ConsultantAuthor Commented:
I agree, solving is often simpler.  I could write something to solve bridges but it is a real pain to type in the grid contents.
I did a suite of articles on EE about solving sudoku quite some time ago, starts here:  https://www.experts-exchange.com/articles/3707/Sudoku-a-complete-MFC-application-Part-1.html
1
Introducing Cloud Class® training courses

Tech changes fast. You can learn faster. That’s why we’re bringing professional training courses to Experts Exchange. With a subscription, you can access all the Cloud Class® courses to expand your education, prep for certifications, and get top-notch instructions.

 
☠ MASQ ☠Commented:
If you want pre-generated puzzles http://www.menneske.no/hashi/eng/
0
 
AndyAinscowFreelance programmer / ConsultantAuthor Commented:
Thanks.  I've found numbers of online sites for either playing online or downloading the preprepared puzzles.  (Search for Krazydad to find loads).
The thesis looks interesting.  I've had a quick scan through but the section on generating is pretty spartan.  More or less what I had thought of myself - but there might be a much better way of doing it hence the question.  
I'll wait and see if anyone else knows some interesting ideas / code / algorithms about this.
0
 
AndyAinscowFreelance programmer / ConsultantAuthor Commented:
Thanks.  Looks like there isn't a nice algorithm.  (Makes me wonder then how one determines if easy/hard... to solve)
0
 
☠ MASQ ☠Commented:
Suspect that's based on a ratio of nodes with double bridges vs. those without - that's how I'd probably grade them anyway.
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.