Fast pentomino puzzle solver ported from Forth to Python (benhoyt.com)

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.

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.

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...

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

> 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)

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. N...