Back in January, I created a framework<\/a> to solve these types of puzzles. At the time, I wrote in the conclusion: <\/p>\n It still needs some work, and the proof of a framework isn\u00e2\u20ac\u2122t in the first application that uses it, but in the third, so I am not crowing about it too much yet.<\/p><\/blockquote>\n Well, eight months later, I am one step closer to that, having used the framework to tackle the Circuit Game puzzle<\/a> – the second application to use it.<\/p>\n The key part to using the framework, is working out how the puzzle can be decomposed into individual objects. <\/p>\n Typically, these objects store a small amount of local state and references to the neighbourhood other similar objects they interact with. They also maintain a set of possible solution values. They are in charge of enforcing a simple set of constraints, whittling down the set of possible values until only one remains. Finally, they are responsible for letting their neighbours know about changes in their state, so the neighbours can correspondingly re-apply their constraints.<\/p>\n Thus, the constraints are propagated across neighbourhoods, peer-to-peer, with little or no oversight from over-arching objects.<\/p>\n In this puzzle, each square (or cell) represented a game object.<\/p>\n Each cell was responsible for maintaining its shape (e.g. Tee, Corner, etc.) This was implemented through a class hierarchy. <\/p>\n Each cell was responsible for tracking its four neighbours.<\/p>\n Each cell was also responsible for maintaining a list of compass directions and its disposition on whether or not a wire was exiting the cell in that direction. For each direction, the disposition could be that a wire must<\/em>, must not<\/em> or might<\/em> be leaving the cell in that direction. Below, I describe how this was calculated.<\/p>\n For the subset of shapes that could be rotated (e.g. Corner, Line, Bulb, and Tee cells, but not Cross or Empty cells), each shape was responsible for maintaining the list of valid orientations. <\/p>\n By iterating through each of the valid orientations, and examining the resulting directions that the wires pointed, it was possible to mark the disposition of each compass direction. If all remaining orientations had a wire pointing up, then the disposition was must<\/em>. If none of them did, it was must not<\/em>. If some did, and some didn’t, it was might<\/em>.<\/p>\n Each of the rotatable shapes were also responsible for maintaining the key constraint in the puzzle – that this cell’s disposition of a wire, was compatible with its neighbour’s disposition of the same wire.<\/p>\n For example, if my neighbour to the left thinks that there must<\/em> be a wire pointing to its right (e.g. back to me), then I must<\/em> have a wire pointing to my left. Any orientation of my shape that doesn’t correspond to that can be eliminated from consideration.<\/p>\n To simplify the bounds-checking, I surrounded the entire puzzle in a border of Empty Cells. These cells never contacted their neighbours, so they didn’t peer past the limit of the grid. That isn’t the most sophisticated of solutions for dealing with boundary conditions, but it worked.<\/p>\n As it stands, this only enforces the rules in Rotate2<\/sup> (See the original article<\/a> for the differences.)<\/p>\n I expected that I would need to implement a global property to enforce that there should be no cycles. This supports the concept of power cells.<\/p>\n I even had a comment in the code pointing out where such functionality would go.<\/p>\n In practice, I found that it wasn’t required to solve the puzzles that were posed by the web-sites.<\/p>\n In theory, there could exist a puzzle that this engine couldn’t solve, because it would see two possible ambiguous solutions (one false solution containing a cycle, and one without). In practice, I haven’t seen one. It remains an open challenge to come up with such a puzzle.<\/p>\n [Stop Press<\/strong>: It is no longer open<\/a>]<\/p>\n I mentioned in the original article that these puzzles didn’t seem to have the complexity of Slitherlinks and the like. This was borne out in the run-time; these test puzzles I encoded were all solved by the engine in sub-second timeframes, even with basic graphical animation.<\/p>\n This is an example of a solved puzzle; this puzzle is the one shown in my original Circuit Puzzle<\/a> article.<\/p>\n These puzzles can be crossed off the list as beaten.<\/p>\n I initially used the same version of the framework as the Alphametics puzzle<\/a>. I found a couple of trivial bugs, with single character corrections, and made no changes to the interface.<\/p>\n I found it took me a little while to remember the concepts; I need to add some documentation to give me clues to get my head back into the right context to use it.<\/p>\n Related to that, I found that when I missed a tiny piece of necessary plumbing that my game objects were responsible for including, the whole object model just sat there. I couldn’t work out why nothing at all was happening – the framework couldn’t see that there was any work to do. I eventually added the missing line in, and the whole thing jumped to life.<\/p>\nThe Game Objects<\/h4>\n
Game Objects in the Circuit Game<\/h4>\n
Power\/Cycles<\/h4>\n
Did it work?<\/h4>\n
![\"Example](\"http:\/\/www.somethinkodd.com\/oddthinking\/wp-content\/uploads\/2008\/09\/circuitpuzzlesolution_example-300x206.jpg\" "\\"Example")
<\/a><\/p>\nHow did the framework go?<\/h4>\n