About the project
Nonogram is a logic puzzle, in which cells of a grid has to be painted, according to numbers written on the side of the board. This is a popular game which appears in daily newspapers.
While puzzles which are designed to be solved by humans are relatively easy in most cases, the general problem is hard – it is NP-Complete (Ueda, Nobuhisa; Nagao, Tadaaki (1996), NP-completeness results for NONOGRAM via Parsimonious Reductions)
In our project, we try to develop different search heuristics in order to solve hard puzzles in a reasonable time. We’re also interested in Board Validation: given a Nonogram board, we try to quickly determine if it does not have a solution.
The project is a 3rd year undergraduate project at the computer science department, Ben Gurion University, Israel.
Our team is: Dolev Pomeranz, Ben Raziel and Ronen Rabani. Our academic advisors are Prof. Daniel Berend and Dr. Mayer Goldberg.
Current version is: 1.0.2
You can download the latest version of our solver in a runnable JAR format, which should be easy to run. If you wish, you may also download the source code, and compile it yourself using GCJ (instructions below).
You may also export puzzles in NIN format from the webpbn export page.
About our solver
Solving a nonogram puzzle consists of two main parts: Line Solving and search heuristics.
Line Solving – given a partially solved nonogram board, find all cells that must be black or white, and set their color. This is similar to how humans solve a puzzle – go over each line, and try to find cells that must be black/white.
Searching – While line solving might solve easy Nonogram boards, in harder instances it will get “stuck” – after line solving has been completed, some cells’ colors are still undetermined. When this happens, we have to try and guess a cell's color in order to advance.
One simple way is searching for contradictions (We also refer to this method as “Probing”): we take a cell, and guess its color. Then, we run the line solver. If the line solver tells us that there are no solutions to the puzzle, it means our guess was wrong – and therefore, the cell must be of the opposite color. This way, we gain information and can continue solving the puzzle without really “guessing”.
In some cases, searching for contradictions is not enough. When this happens, we have to choose a cell, guess it’s color and continue searching our game tree. Most solvers do it by using some version of a DFS search.
Our line solver uses a dynamic programming algorithm. It receives a partially solved line, and find all cells that must be black or white. It runs in O(NK) time, where N is the row's length, and K is the number of blocks next to that line.
After we solve a line, we put its solution in a hash table. Whenever we solve a line, we first check if its solution already exists in the hash table – if it does, we do not need to solve this line again (we simply take the solution from the hash table).
Each time our line solver gets stuck, we try to find a contradiction. We want to find a contradiction as quickly as possible, since each test attempt requires us to run the line solver – which is expensive.
In order to
do so, we probe the cells according to “levels”:
1. Probe the neighboring cells of the cell selected in the last iteration.
2. Probe the neighboring cells of cells that were changed (i.e: their value was determined "black" or "white") in the last iteration.
3. Probe cells which have 2 or more known neighbors. (Known = we’ve already determined their color)
4. Probe cells which have 1 known neighbor
We go over the cells in each level looking for contradictions. If a contradiction is found – we stop, and set the cell’s color. Once we finished probing cells in a level, we go to the next.
If we haven’t found a contradiction in any level, we guess the cell according to the following heuristic: We choose that cell that, when we guessed its color an employed the line solver, determined the most cells to be “black” or “white”. For example: We start with an empty board. We guess the color of cell (1,1) to be black, and employ the line solver. After the line solver was employed, the color of 4 more cells is determined – so the score of (1,1) is 4.
We use a tree-based search in to keep track of our guesses, and backtrack whenever we hit a contradiction. Our search method can find all possible solutions to a board (unless we explicitly set a solution limit to stop after).
The easy way to run the solver is by downloading the runnable jar, and running it using java –jar bgusolver.jar. We got faster run times by running with –server flag on, so you might be interested in trying that.
The other way, is to compile the java code using gcj (the GNU Java compiler – a frontend to gcc). Download the source code, run make (a makefile is included) and run the application (bgusolver). Only the command line version may be compiled in this fashion.
Compiling with gcj makes the solver solve easy puzzles much faster. On the other hand, it had a slight negative impact on the run times of hard puzzles.
Running the solver
There are two
ways to run the solver. Command Line mode, and GUI mode. In order to run in
command line mode, use the following flags:
-file <filename>: solve board from file. board should be in NIN format.
-maxsolutions <number>: maximum solutions to search for. default is 2
-timeout <time in seconds>: maximum number of seconds before stopping the search.
-shortinfo: prints solution information in a shorter form.
For example: java -jar bgusolver.jar -file c:\nono.nin -maxsolutions 2
In order to run the GUI mode, just run the program without any flags (java -jar bgusolver.jar). You can edit puzzles there, and try to solve the board using different solvers.