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