Made with TED Notepad, free text editor! Copyright (c) 2001-2013, Juraj Simlovic.
Contact: griddlersjsimlo.sk. All rights reserved.
Request took: 0.0208.
Copyright (c) 2001-2013, Juraj Simlovic.
Site made with TED Notepad, free notepad alternative!
To explain my algorithm..
This page describes the algorithms and architecture of my solving engine. Hopefully, it will help you understand my idea and perhaps also help you develop your own solving engine. The main reason why my source code is not available is simple: to encourage you to write your own piece. It is indeed an appealing chalenge.
The main idea (the keystone of my engine) is called "achievable by human logic". Well, the puzzle itself was invented (by Non Ishida and Tetsuya Nishio) to entertain and tease our brains.. Every good puzzle must be thus solvable by common human logic. And so here we are, examining how the humans would engage this task. Whatever my engine does, it does exactly as human being would do.
Note: This article describes an object-oriented approach. Basics of object-oriented programming techniques might be necessary to understand this article.
To begin with, I have two important types of objects in the engine: A Field and a Row.
A Row is a set of cells, clues, and lot of important runtime info, which is gathered and used during the solving process. All these are always related to a single row or column of the puzzle. Note that there is no need to distinguish between rows and columns here.
A Field is a set of rows and columns represented by Row objects. While a single Row is always responsible for a single row/column, a Field is responsible for putting all rows/columns together into one puzzle.
Note: From now on, when I say "row" I mean "row or column". They share the same concept.
In the engine, I defined method Solve(). This is actually a very simple method. It is the main and only entry-point to the engine. It receives the puzzle (the cells and the clues) and initializes the engine. It creates one Field object from the given puzzle and then instructs the Field to solve itself. When solving is done, this method cleans up and returns the solved puzzle. All real solving is thus done within the Field object as described below.
The Field object define method SolveField(), that is supposed to solve the entire field. This method calls all known field-solving methods in a neverending loop. The loop is actually not infinite although written as one. There are three terminating conditions in the loop: when the entire puzzle is solved; when an error is found in the solution; or when no further progress can be made towards the final solution.
In other words, the SolveField() method ensures that all field-solving methods get called over and over again as long as necessary and reasonable. When one field-solving method fails to produce new results, another one is yoked to continue the work. In the end, hopefully, the entire field gets solved.
Close description of field methods will follow below in the field-solving methods section.
Currently I define two field-solving methods: SweepField() method and BruteforceField() method. I believe that a third method, something like TiltField(), could enhance the engine, but I have not implemented it yet.
The SweepField() method chooses unsolved or partially solved rows in a big neverending loop and instructs them to solve themselves. It uses several heuristic approaches to give more priority to those rows that promise to yield more results. After a handful of loops in this method, either a solution is reached, or a conclusion is developed that this method is of no use right now.
Note that this is how human would proceed in solving. One takes a single row; ties to determine as much as possible; then leaves the row for a while, taking a look at other rows.
Most of the puzzles can be solved using the SweepField() field-solving method only. However, for some more difficult puzzles, the SweepField() method may come to an unpleasant conclusion that there is nothing useful to be discovered this way anymore. In such cases, other and more time-consuming field-solving methods must take place. Close description of these methods will follow below in the recursion section.
The Row object define method SolveRow(), that is supposed to solve the given row. This method calls all known row-solving methods in a neverending heuristic loop. The loop is actually not infinite although written as one. There are again three terminating conditions in the loop: when the entire row is solved; when an error is found in the solution; or when no further progress can be made towards the final solution.
This is actually the most important part of the entire engine. If this method is weak, the entire engine is slow. If this method is incapable of producing results, the entire engine is incapable of solving more difficult puzzles. However, if this method is clever and fast, the entire engine can be quick and effective.
Note that this is how human would proceed in solving. One takes a single row; ties to determine as much as possible; then leaves the row for a while, taking a look at other rows.
Note: Although humans tend to forget runtime info from one row while solving other rows, we keep it. Gathering it over and over again would only waste computing time. My engine thus emulates a human being with very good memory, e.g. Sheldon Cooper.
Close description of row methods will follow below in the row-solving methods section.
Currently I define five row-solving methods. These methods alone does not produce the entire solution and their results are slightly different, but when combined in a heuristic loop, they do their job effectively. The combined goal is to discover as much cells and runtime info as possible and as soon as possible. Although usually only a few rows can be fully solved in the first run, solving a row partially helps a lot in the future.
The first four row-solving methods use direct computations on the row; considering the runtime info, the clues and the cells. Some of them are just updating the runtime info, others determine new cells from the runtime info, others do both. All of them are applicable by human logic. Although the computing approach might be a bit different from the one employed by a human brain, the results are always the same. This is the main reason why my engine works the same way as humans do. Whenever the engine discovers a new cell, common human logic can recognize, why this cell.
There is one important thing here: searching for errors and reporting them. All solving methods and sub-methods search for errors as well as for the solution itself. An example of an error is a row, where the clues can no longer be satisfied. This error reporting will be very important while searching for contradictions, as described later. It is very important to discover errors sooner rather than later. Contradiction searches, which rely on error reporting, are very slow already, therefore, clever error reporting speeds things up noticeably.
The fifth row-solving method is a bit different than the rest. It guesses one possible cell value and then utilizes the error reporting of the above four row-solving methods to search for so-called contradictions. This technique is of course also applicable by human logic, though it requires more teasing.
Note: All my tests show that there is no need for any deeper row-level recursion. The first level is always sufficient. Therefore, the fifth row-solving method is not actually a recursion, since it never calls itself. It does create a copy of the original row though and calls the above four row-solving methods to prove a contradiction on this copy. Thus, from memory point of view, it could be called a one-level recursion perhaps.
If you are interested in the above four row-solving methods, contact me by e-mail. This is the main fun about the entire engine. To write these row-solving methods. They need to be simple, quick, effective. Why? Because their code is what the CPU dishes up over and over again. More then 80% of the solving time is spent within the contents of the SolveRow() method. No kidding.
About the recursion: Yes, it can be powerful, but also very slow. Which is why I tried to limit its usage and limit its levels. No puzzle, which is also solvable by a human brain, does need more than one level of recursion. To support this idea, I have added the second level to the bruteforce method, and up to this point, I have found only one puzzle, which requires this second level in order to be solved. Though I believe this puzzle can be solved by adding more skilful field method anyway and thus the second level should become unnecessary.
Right now, the only recursive method, called BruteforceField(), tries to use several heuristic approaches to choose, which undetermined cells are worth to prioritize. Then, for each such cell, it tries to reach a contradiction by exploring both possibilities thru recursion.
When both possibilities come to a nothing fancy conclusion, then there is nothing useful about that cell right now. But if one of the possibilities returns with an error, a direct contradiction is discovered, and the other possibility is the right choice.
Note: If both possibilities reach a fully solved puzzle, then the puzzle has multiple solutions. This is because there is a specific cell that may contain any of the two possibilities.
Note: If both possibilities reach an error, then the puzzle have contained an error before the BruteforceField() was called. This can be reported and utilized further to perform deper recursions. My engine never allows to go more that two levels deep, because I have never seen anyone (a real human being) who could do that. Furthermore, the second level of the recursion may take hours or days to complete. And finally, I have not found a puzzle yet, also solvable by human, that would require deeper recursion. Have you?
Note: More recursive field-solving methods shall come in the future. At least there is one specific in my mind already, which could, by the way, replace the BruteforceField() method completely.
Regarding the required memory ussage..
While the solving engine is running, it stores and uses one Field object, which consist of rows and columns. In my engine, there is a static limit of 100x100 cells; this is only because I wanted to avoid dynamic arrays. The size of the Field is thus constant, and depends on the initial number of columns and rows. One Row object is created for each row and each column of the puzzle. Note that although rows and columns share cells, they do not share clues and runtime info.
When a row recursion takes place, the Row is copied into two childs, one for each possibility. Since there is only one level of row recursion, only two extra Row objects exist per one Field in any given time.
When a field recursion takes place, the Field is copied into two childs, one for each possibility. All field rows and comlumns are copied along with the field. Each level of recursion results in two more copies of the Field, so there is upto " 1 + 2 * level " Fields in the memory; upto " (1 + 2 * level) * fieldRowCount " Rows within those fields; plus upto two extra Rows. While the recursion is limited to second level and puzzle size is limited to 100x100 cells, the total count of Fields is 5; the total count of Rows is 5*100*100; plus two extra Rows at any given time.