Solving edge-match puzzles with Arc and backtracking

arcfn.com

14 pointskens3 comments

Cute little puzzle. Is "backtracking" just a depth-first search?

I've always thought solving small puzzles like this was a nice way to get a feel for a new language. I recently worked on a similar solver for one of those triangle peg jumping games (http://www.gabedurazo.com/blog/?p=86) to get the hang of C a bit. Arc, here, looks nice.

Yes, backtracking is similar to depth-first search, except backtracking stop going down a branch as soon as you realize it's not going to work. Depth-first search on the other hand normally visits all the nodes in the graph. Applied to the puzzle, depth-first search would try every possible combination of tiles and check each one to see if it works or not, which would be very inefficient.

Your peg-jumping puzzle would be harder to solve efficiently with backtracking, because it's not obvious until the end that you're on the wrong path. If you're interested in the mathematics of peg-jumping puzzles, see "Winning Ways for your mathematical plays, Vol 2", by Berlekamp, Conway, and Guy, which discusses the mathematics of the plus-shaped peg-jumping puzzle in detail.

Thanks for the recommendation, I'll check it out!

Reply on news.ycombinator.com