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

AndyAinscow
AndyAinscow used Ask the Experts™
on
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.
Comment
Watch Question

Do more with

Expert Office
EXPERT OFFICE® is a registered trademark of EXPERTS EXCHANGE®
Most Valuable Expert 2013

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.
AndyAinscowFreelance programmer / Consultant

Author

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
Most Valuable Expert 2013
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
Most Valuable Expert 2013

Commented:
If you want pre-generated puzzles http://www.menneske.no/hashi/eng/
AndyAinscowFreelance programmer / Consultant

Author

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.
AndyAinscowFreelance programmer / Consultant

Author

Commented:
Thanks.  Looks like there isn't a nice algorithm.  (Makes me wonder then how one determines if easy/hard... to solve)
Most Valuable Expert 2013

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.

Do more with

Expert Office
Submit tech questions to Ask the Experts™ at any time to receive solutions, advice, and new ideas from leading industry professionals.

Start 7-Day Free Trial