A puzzle I'd not seen before appeared in a recent copy of The Independent, called Slitherlink.
See http://en.wikipedia.org/wiki/Slitherlink and http://www.puzzle-loop.com/ To quote the rules verbatim: "Draw a single loop by connecting together the dots [on the grid] so that each numbered square has the specified number of adjacent line segments. Dots can only be joined by straight horizontal or vertical lines. The loop cannot cross or overlap itself in any way." Although fun to solve the puzzles manually, I've been wondering about possible approaches to solving the general case recently, too. Does anyone have hints or tips on how you might go about creating an algorithm to solve Slitherlink puzzles? I'd prefer not to be overly spoiled so I'd appreciate it if you didn't spell it out :) It seems quite challenging for a few reasons: Firstly, I've found representing the actual grid slightly awkward, as you care about the squares on the board and the lines between them, as well as the actual points - this is more of a programming challenge than algorithmic, however. Secondly, there are lots of degrees of freedom, so an exhaustive search is extremely expensive, as well as inelegant. Thirdly, I've found myself needing some fairly subtle assertions when solving manually - proving that various spaces on the grid are "closed systems"; knowing you're dealing with a single line segment from a set entry and exit point really reduces complexity. Fourthly, the standard path-finding algorithms don't (I think) deal well with the requirements of an non-intersecting loop. Also, A* would get confused by having different routes to a certain point yield different heuristic values, right? I thought the heuristic at any point had to be independent of the path taken to that point... Anyone got any ideas? --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
