Sudoku Generation

Over two years ago, I wrote a basic 3×3-sudoku solver which uses both fundamental rule-based elimination and guessing to arrive at the solution. Revisiting the topic of computer-aided sudoku manipulation, I wrote a generalized sudoku generator (sudoku.hs).

    | 4  
  3 |    
  2 | 1  
  4 |    

./sudoku 5 2

Continue reading


Foam Cube Puzzle

After having solved the puzzle shown below a few times by combining six foam pieces to construct a hollow cube, I wondered if it had a unique solution. A simple brute-force search reveals it does. Source code:

Foam Cube Puzzle
All six foam pieces.

As a first step I digitalized all pieces seen above. Having an internal representation, I wrote a script which tries all possible rotations and reflections (as three-dimensional rotations can imply two-dimensional reflection) to try and construct a three-dimensional cube from the given pieces. Using short-circuit evaluation to not bother with already impossible solutions, the search space is narrow enough to not require any considerable computing time. The resulting unique solution modulo rotation is shown above; the top face is placed on the bottom right.

Slitherlink Solver

Slitherlink is a neat puzzle in which you are presented with a number matrix and the goal is to draw one connected, not interlooping line in between the cells. The number in each cell determines exactly how many line segments must be drawn around each cell (0, 1, 2 or 3). When a cell does not contain any number, the number of line segments adjacent to this cell are unrestricted.

*  *  *  *  *  *          *--*  *  *--*--*
     2  1  3              |  | 2  1| 3   |
*  *  *  *  *  *          *  *--*  *--*  *
        2  2  2           |     | 2  2| 2|
*  *  *  *  *  *          *--*  *--*  *  *
     2              ->       | 2   |  |  |
*  *  *  *  *  *          *  *--*  *--*  *
  1  3  1     1             1  3| 1     1|
*  *  *  *  *  *          *--*--*  *--*  *
  3     2     3           | 3     2|  | 3|
*  *  *  *  *  *          *--*--*--*  *--*

A sample 5x5 Slitherlink with solution.

Slitherlink was invented by the Japanese publisher Nikoli in 1989. It has many other names than ‘Slitherlink’, yet I prefer this descriptive name. Imagining a snake slithering along the board, seeking to link up with itself is a bit charming.

As with most of these puzzles that have simple rules and are fairly easy to work out by hand — on small scales that is –, writing a solver for them can prove to be more difficult than one may expect.

The first solving strategy I tried out was to brute force the problem. Using the Slitherlink from above as an example, there would be 5 \cdot 5 = 25 different cells with 2 \cdot 5 \cdot 5 + 5 + 5 = 60 line segments. With each line segment either being drawn or not, there are 2^{60} = 1.15 \cdot 10^{18} different boards to check. With one board being checked per nanosecond the solver would take \frac{2^{60}}{10^9} = 1.15 \cdot 10^9 seconds or 36.56 years. Brute force is definitely not a viable way to conquer Slitherlink.

After this harsh discovery, I needed a better way to approach solving a given Slitherlink puzzle. Doing some research, I even discovered that Slitherlink is an NP-complete problem (see this paper by Stefan Herting), whereby it — assuming \text{P} \neq \text{NP} — is not even possible to write a solving algorithm which takes polynomial time.
However, solving small Slitherlink puzzles is fortunately possible in a reasonable time frame.

The strategy I used in the solver consists of pre-programmed rules — figured out by humans — which determine parts of the board based on special arrangements and enforcing the puzzle’s rules (such as that there must only be one line). Using those clues, the solver partly solves a given Slitherlink until there are no more known rules to advance. At that point the solver guesses for a given line segment to be either crossed (marking it cannot be drawn) or drawn, building a tree.
Conflicting attempts (where the solver wrongly guessed, then later — through applying the given rules — determines the attempt as flawed) are thrown away, only leaving possible solved scenarios. Because each Slitherlink has one unique solution, this process ultimately results in one surviving attempt, which then is checked for correctness and printed out as the solution.
A list of Slitherlink rules can be found in this Wikipedia article.

Using the above described method, my solver takes roughly 0.05 seconds on an Intel Core i7 (4.00 GHz) to solve the example 5×5 Slitherlink. A 10×10 Slitherlink takes around 1.6 seconds whereas it takes 32 seconds to solve a 15×15 Slitherlink. The non-polynomial time is clearly recognisable.

My solver best runs in a bash shell, as it uses ANSI escape sequences to give the solved line a vivid blue and is entirely written in Python as well as fully text-based. The source code is listed below.

Other people also have written solvers, including puzzle generators, such as kakuro-online or appspot. The latter even supports different polygons as the Slitherlink base.

# Python 2.7.7 Code
# Jonathan Frech, 22nd of December 2016
# edited 23rd, 24th, 25th, 26th, 27th, 29th, 30th, 31st of December 2016
# edited 1st, 2nd, 3rd, 5th, 8th of January 2017
# edited 10th of February 2017

Continue reading