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 46
AndyAinscowFreelance programmer / ConsultantAsked:
Who is Participating?

[Product update] Infrastructure Analysis Tool is now available with Business Accounts.Learn More

x
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

☠ 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
☠ 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

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
PMI ACP® Project Management

Prepare for the PMI Agile Certified Practitioner (PMI-ACP)® exam, which formally recognizes your knowledge of agile principles and your skill with agile techniques.

☠ 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
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
Game Programming

From novice to tech pro — start learning today.