6 ms·

Fast pentomino puzzle solver ported from Forth to Python

65 points by benhoyt 9y ago

periodontal 9y ago
This is a specific example of an Exact cover problem: https://en.wikipedia.org/wiki/Exact_cover 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.
- denfromufa 9y ago
  wow, this is insightful generalization
- jxramos 9y ago
  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 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.
- kybernetikos 9y ago
  My JS implementation is http://dancing-links.herokuapp.com/ http://dancing-links.herokuapp.com/ It includes a sudoku (also exact cover) and pentonimo solver.
  - carapace 9y ago
    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 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.
    - kybernetikos 9y ago
      That's really fun.
ericfrederich 9y ago
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.
- zem 9y ago
  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 :)
denfromufa 9y ago
I have a jupyter notebook about a similar game "Penguins on Ice", solved with rotation of numpy arrays: https://nbviewer.jupyter.org/gist/denfromufa/9a5e1fdeaf611dc60ea8 https://nbviewer.jupyter.org/gist/denfromufa/9a5e1fdeaf611dc...
- ethereal_int 9y ago
  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=perfect http://harddrop.com/forums/index.php?showtopic=7792&hl=perfe...
  - denfromufa 9y ago
    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 ;)
raymondh 9y ago
Thank you. This was a nice Rosetta Stone language comparison using an interesting problem with beautiful diagrams.
Asooka 9y ago
> 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)
zmonx 9y ago
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.
deleted 9y ago
[deleted]

65 points by benhoyt 9y ago

This is a specific example of an Exact cover problem: https://en.wikipedia.org/wiki/Exact_cover 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.

denfromufa 9y ago
wow, this is insightful generalization
jxramos 9y ago
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 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.
kybernetikos 9y ago
My JS implementation is http://dancing-links.herokuapp.com/ http://dancing-links.herokuapp.com/ It includes a sudoku (also exact cover) and pentonimo solver.
- carapace 9y ago
  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 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.
  - kybernetikos 9y ago
    That's really fun.

ericfrederich 9y ago

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.

zem 9y ago
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 :)

denfromufa 9y ago

I have a jupyter notebook about a similar game "Penguins on Ice", solved with rotation of numpy arrays: https://nbviewer.jupyter.org/gist/denfromufa/9a5e1fdeaf611dc60ea8 https://nbviewer.jupyter.org/gist/denfromufa/9a5e1fdeaf611dc...

ethereal_int 9y ago
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=perfect http://harddrop.com/forums/index.php?showtopic=7792&hl=perfe...
- denfromufa 9y ago
  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 ;)

raymondh 9y ago

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

Asooka 9y ago

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

zmonx 9y ago

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.

deleted 9y ago

[deleted]