In the past, I have blogged about a several projects to solve some puzzles with a common theme: Nonograms<\/a>, Kakuro<\/a>, Sudoku<\/a>, Solitaire Battleships<\/a> and Slitherlinks [in press].<\/p>\n My solutions shared a similar architecture – one that has been evolving over time.<\/p>\n The architecture is based on a common Artificial Intelligence approach of having a large number of different objects representing part of the puzzle (e.g. a coloured line or a square in the grid). Each object is trying to independently resolve some internal constraints. As they make progress and discover some information, they share the current information with their neighbours. Those neighbours use that to improve their situation, recursively, until, hopefully, a solution is found. The whole system is decentralised, with no master object driving the algorithm.<\/p>\n The area of the architecture that has changed the most is the message-passing mechanism.<\/p>\n This article focuses on that message-passing system and the variants I have tried. <\/p>\n The question I am trying to answer is: Each object knows about its direct neighbours. When it comes time to tell those neighbours some new information, how should it go about that?<\/p>\n The obvious solution is for the object simply to call each of the neighbours in turn, and have them check their constraints immediately, while the original object waits. If the constraints lead to new information, the neighbours recursively call their neighbours, until there is no new information to be shared, the stack unwinds and the original object completes.<\/p>\n This system is conceptually fairly straightforward, and it is easy to get the basic implementation working.<\/p>\n It is helpful in debugging, as the stack trace shows a complete history of how the information was passed around. (If you are debugging why a piece of wrong information was passed to an object, you can see who the culprit was.)<\/p>\n It is inefficient. For example, if the cell_1 object passes a message to line_1 and cell_2 objects, and then the line_1 object updates some data and passes another message to cell_2, then cell_2 is going to get two calls to its constraint checking. It will check its constraint twice rather than once.<\/p>\n Care must be taken to ensure that functions support re-entrance. An object’s methods may be called when it is half-way through a function. Its invariants must all be met before passing the message to its neighbours.<\/p>\n Animation hooks are a bit trickier. Many of these projects have an associated game board that is displayed to show progress. Rendering of these graphics are CPU-intensive. Typically, I would refresh the screen after every contraint check during early debugging but only after every 50-or-so constraint checks during the final runs. Having a recursive solution means putting calls to the animation system throughout the code for the object. It couples the algorithm to the rendering.<\/p>\n If the puzzle is solved before all the constraints are checked, it is difficult to finish early. Similar to the animation hooks, checks for puzzle-completeness are required throughout the code.<\/p>\n Another implementation of message passing is to use a “command queue”.<\/p>\n Rather than using the run-time stack to keep track of the neighbours, a separate queue is created.<\/p>\n Rather than calling the neighbours directly, a request is pushed on the command queue for each of the neighbours. Each constraint check is now a short (probably constant time) operation that is guaranteed to return quickly.<\/p>\n The calling software needs to pop the first command off the queue, execute it (which calls the appropriate object) and repeat until the queue is empty or the puzzle is solved.<\/p>\n Animation and puzzle-completeness hooks can be moved into the calling code. They can perform the updates\/checks after executing every command or every Coding can afford to be a bit sloppier, if you know you are using this technique. You can afford to trigger the call to the neighbour object even before you finish updating your local data to maintain the invariants. Code is not re-entrant.<\/p>\n While I haven’t tried it, I think this technique supports multi-threading better. The items in the queue can be distributed amongst different threads – perhaps based on some partition of the affected objects to minimise the amount of locking required. I’ve been meaning to try this.<\/p>\n Again, I haven’t tried this, but if you have computer-assisted solving of the puzzles and a slow algorithm (e.g. brute force), it allows an opportunity for the user to make an update before the entire algorithm has completed. So the human can play in real-time, with the computer just slowly adding information as it discovers it.<\/p>\n The effect of an update is divorced from its cause. During debugging, I have found incorrect information lined up in the command queue, and it has been difficult to back trace it to the code that incorrectly created it.<\/p>\n The system remains inefficient. The example above of cell_2 updating twice continues to apply.<\/p>\n The pureness of the bottom-up, decentralised nature of the implementation is tainted. There is now a centralised master object (i.e. the command queue) that every object needs to know about – either it is a global or it needs to passed around to almost every object in the system.<\/p>\n Some messages are more useful than others.<\/p>\n Consider two messages to a Sudoku cell. One says “Your value is not an 8. Please eliminate that from your list of possibilities.” The other says “Your value is a 3.” The latter message has more information content.<\/p>\n By giving each type of message a relative priority, and keeping the command queue sorted by that priority, you can ensure the more useful messages are processed first.<\/p>\n The less useful messages will either be abandoned (if the puzzle is solved before they are processed), ignored (once an object has resolved all of its own constraints using the more useful messages, it can discard further information quickly) or eventually processed (if the object is still looking for more information.)<\/p>\n I also used this technique where some objects had multi-stage initialisation (e.g. before and after their neighbours were associated) but I eventually moved this responsibility to the object that created them, because it was simpler.<\/p>\n Prioritised Command Queues are an optimisation that is only application in some situations. There is a small cost in keeping the queue sorted.<\/p>\n Looking at the command queue data reveals that there are generally many duplicate commands, like the cell_1 example, above.<\/p>\n Converting the command queue into a set can greatly reduce the number of redundant calls. Duplicates are simply discarded as they are added to the queue.<\/p>\n Note: Compare these two different styles of message-passing:<\/p>\n If fetching data from neighbours is expensive, the latter might be more efficient. However, if the evaluation of the data is the expensive part, the the former style, plus the command set design, can save a large number of constraint checks.<\/p>\n A Prioritised Command Set is also possible, combining the duplication-removal features of the set with the best-data first features of the prioritised queue.<\/p>\n During the Kakuro project, I made a gross simplification.<\/p>\n I dropped the message-passing between neighbours entirely. Instead, I had the calling program simply iterate repeatedly over every cell object, and tell it to check its constraints, whether its neighbours had changed or not.<\/p>\n This contained an inherent inefficiency: cells were called on to update even when their environment hadn’t changed in the meantime.<\/p>\n However, the code was much, much simpler.<\/p>\n If the neighbourhood connectivity is high compared to the number of objects, if it takes a large number of messages to an object before it can solve itself, and if there is only one message type, this is a worthwhile consideration.<\/p>\n I have experimented with a number of different designs. The Prioritised Command Set is the default that I reach for now. Now I can use this article to justify that decision to myself!<\/p>\n If I was ever hired to take these disposable prototypes and replace them with massively over-engineered production code, I could certainly see the opportunity for a puzzle-solving framework (including a Prioritised Command Set) to do most of the infrastructure work.<\/p>\nScope<\/h3>\n
Recursion<\/h3>\n
Advantages<\/h4>\n
Disadvantages<\/h4>\n
Command Queue<\/h3>\n
Advantages<\/h4>\n
n<\/code> commands, as desired.<\/p>\nDisadvantages<\/h4>\n
Prioritised Command Queue<\/h3>\n
Command Set<\/h3>\n
\n
Iteration<\/h3>\n
Conclusion<\/h3>\n