Fast pentomino puzzle solver ported from Forth to Python
1–10 of 16 posts
Re: Fast pentomino puzzle solver ported from Forth to Python
#2This 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.
Re: Fast pentomino puzzle solver ported from Forth to Python
#3I 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.
Re: Fast pentomino puzzle solver ported from Forth to Python
#4I have a jupyter notebook about a similar game "Penguins on Ice", solved with rotation of numpy arrays:
https://nbviewer.jupyter.org/gist/denfromufa/9a5e1fdeaf611dc...
Re: Fast pentomino puzzle solver ported from Forth to Python
#5Thank you. This was a nice Rosetta Stone language comparison using an interesting problem with beautiful diagrams.
Re: Fast pentomino puzzle solver ported from Forth to Python
#6This 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
Re: Fast pentomino puzzle solver ported from Forth to Python
#7This 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 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.
Re: Fast pentomino puzzle solver ported from Forth to Python
#8> 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")
A.__getitem__(special)
A.foo(ordinary)
A.__getitem__(special)
Overriden foo(ordinary)Re: Fast pentomino puzzle solver ported from Forth to Python
#9This 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.
My JS implementation is http://dancing-links.herokuapp.com/
It includes a sudoku (also exact cover) and pentonimo solver.
Re: Fast pentomino puzzle solver ported from Forth to Python
#10I 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 :)