Fast pentomino puzzle solver ported from Forth to Python | Hacker News Reader

Fast pentomino puzzle solver ported from Forth to Python

benhoyt.com

65 pointsbenhoyt14 comments

This is a specific example of an Exact cover problem: https://en.wikipedia.org/wiki/Exact_cover

If you haven't seen Knuth's Dancing Links implementation of Algorithm X, I highly recommend it. It's based on the observation that updating a doubly-linked list in-place preserves enough information to make backtracking easy.

wow, this is insightful generalization

I feel like I may be missing something in comprehending that first up mathematical definition in the Exact cover wiki. How is it different from a partition of a set? (https://en.wikipedia.org/wiki/Partition_of_a_set).

UPDATE: think I may see it, sounds like in terms of partitions an exact cover is a subset of a set's partition.

My JS implementation is http://dancing-links.herokuapp.com/

It includes a sudoku (also exact cover) and pentonimo solver.

This make me want to dig up a version I did in Python (for Sudoku as it happens.) The algorithm is a bad fit for Python because attributes are not pointers, but have a look at this:

http://www.cs.mcgill.ca/~aassaf9/python/algorithm_x.html

> One day I decided to write Algorithm X in Python, and I came up with a very interesting variation on Dancing Links.

That's really fun.

> for example, an innocent board[pos] access will look up __getitem__ in board.__dict__ and call the result

Pedantic note: Special methods aren't looked up in __dict__, they're members of the C struct describing the type. "board[pos]" will look up the type of board, then call the tp_getitem function pointer in that struct. That can be a bit surprising to people:

    class A:
        def __getitem__(self, key):
            print("A.__getitem__({})".format(key))

        def foo(self, x):
            print("A.foo({})".format(x))

    a = A()
    a["special"]
    a.foo("ordinary")
    a.__getitem__ = lambda key: print("Overriden __getitem__({})".format(key))
    a.foo = lambda x: print("Overriden foo({})".format(x))
    a["special"]
    a.foo("ordinary")

Outputs:

    A.__getitem__(special)
    A.foo(ordinary)
    A.__getitem__(special)
    Overriden foo(ordinary)

I have a jupyter notebook about a similar game "Penguins on Ice", solved with rotation of numpy arrays:

https://nbviewer.jupyter.org/gist/denfromufa/9a5e1fdeaf611dc...

Wow, hacker news is incredible sometimes :) , I was/am just looking over your notebook a week ago. Vacation is starting in a couple days and i was gonna try and solve if infinite play is possible in Tetris with just perfect clears. People have been at the problem for a few years now, and your notebook is pretty cool :D http://harddrop.com/forums/index.php?showtopic=7792&hl=perfe...

I was really surprised how efficient numpy arrays were at finding all combinations of the pieces. The backtracking is not using recursion, but instead a stack. This makes it more verbose to code and read, but easier to understand. I would like to make this notebook more interactive with ipywidgets and Unicode characters, so stay tuned ;)

I wonder what a solution in prolog would look like. That language always seemed geared to solve riddles. You describe the solution and it can tell you how to arrive there.

when i was in college i decided to pick up a bit of prolog by writing a pentomino solver. i have no idea what i did wrong but three days later it still hadn't found a solution :)

The declarative programming language Prolog is very well suited for solving such tasks, because it ships with built-in backtracking and several methods such as constraints that help to significantly prune the search space. Here is a Prolog solution:

First, let us describe the possible tiles as 0/1 matrices, where 0 means an empty cell:

    tile([[1],
          [1],
          [1],
          [1],
          [1]]).

    tile([[0,1,1],
          [1,1,0],
          [0,1,0]]).

    tile([[1,1,0],
          [0,1,1],
          [0,1,0]]).

    etc. (remaining facts left as an exercise)

Before we continue, let us run two brief validity checks over this data. First, how many tiles did we define:

    ?- findall(., tile(T), Ts),
       length(Ts, L).

The system answers with:

    L = 18.

This matches what the article states. Next, let us ask Prolog: Have we accidentally introduced a typo somewhere, i.e., is there a tile that is not a pentomino?

   ?- tile(T),
      L #\= 5,
      append(T, Ls),
      include(=(1), Ls, Ones),
      length(Ones, L).

The system answers: No. Thus, we can proceed.

I am now posting a full solution, using CLP(FD) constraints:

    polyominoes(M, N, Rows, Vs) :-
            matrix(M, N, Rows),
            same_length(Rows, Vs),
            Vs ins 0..1,
            transpose(Rows, Cols),
            phrase(all_cardinalities(Cols, Vs), Cs),
            maplist(call, Cs).

    all_cardinalities([], _) --> [].
    all_cardinalities([Col|Cols], Vs) -->
            { pairs_keys_values(Pairs0, Col, Vs),
              include(key_one, Pairs0, Pairs),
              pairs_values(Pairs, Cs) },
            [sum(Cs,#=,1)],
            all_cardinalities(Cols, Vs).

    key_one(1-_).


    matrix(M, N, Ms) :-
            Squares #= M*N,
            length(Ls, Squares),
            findall(Ls, line(N,Ls), Ms0),
            sort(Ms0, Ms).


    line(N, Ls) :-
            tile(Ts),
            length(Ls, Max),
            phrase((zeros(0,P0),tile_(Ts,N,Max,P0,P1),zeros(P1,_)), Ls).

    tile_([], _, _, P, P) --> [].
    tile_([T|Ts], N, Max, P0, P) -->
            tile_part(T, N, P0, P1),
            { (P1 - 1) mod N #>= P0 mod N,
              P2 #= min(P0 + N, Max) },
            zeros(P1, P2),
            tile_(Ts, N, Max, P2, P).

    tile_part([], _, P, P) --> [].
    tile_part([L|Ls], N, P0, P) --> [L],
            { P1 #= P0 + 1 },
            tile_part(Ls, N, P1, P).

    zeros(P, P) --> [].
    zeros(P0, P) --> [0],
            { P1 #= P0 + 1 },
            zeros(P1, P).

As pointed out in the sibling, this models the task as an exact cover problem.

For a 6x10 puzzle, you can see what the rows look like with the following query:

    ?- polyominoes(6, 10, Rows, Vs),
       maplist(portray_clause, Rows).

Here are the first few lines emitted by the query:

    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1].
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0].
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0].
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0].
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0].

Each line describes a possible placement of one of the tiles, where 1 denotes which of the cells are covered. Note that each element of the rows above represents one of the positions of the whole board. Therefore, each list has 6x10 = 60 elements. The exact cover problem states that each of these cells is covered exactly once. Therefore, the essential constraint in this puzzle is:

    sum(Cs, #=, 1)

This is a CLP(FD) constraint that constrains the sum of all integers in Cs to 1.

Now, let us use Prolog to generate solutions. For this, we use label/1 to trigger the built-in backtracking:

    ?- polyominoes(6, 10, _, Vs),
       label(Vs).

This yields, in at most a few seconds:

    Vs = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0] .

It shows which of the placements need to be picked to cover the whole board. Further solutions can be generated on backtracking.

To display solutions in a more meaningful way, we can use the following query:

    ?- polyominoes(6, 10, Rows, Vs),
       label(Vs),
       pairs_keys_values(Pairs0, Vs, Rows),
       include(key_one, Pairs0, Pairs1),
       pairs_values(Pairs1, Selected),
       maplist(portray_clause, Selected).

Here is the exact cover, i.e., the first solution:

    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0].
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0].
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1].
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0].
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0].
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0].
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0].
    [0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0].
    [0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0].
    [0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0].
    [0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0].
    [1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0].

Note that if you sum columns, the sum of each column is 1, i.e., each cell is covered exactly once.

Thank you. This was a nice Rosetta Stone language comparison using an interesting problem with beautiful diagrams.

Reply on news.ycombinator.com