News for hackers. Stuff that matters.
Re:Fast pentomino puzzle solver ported from Forth to Python by periodontal on Wednesday July 19, 2017 @01:19PM (#14805961)
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.

Re:Fast pentomino puzzle solver ported from Forth to Python by kybernetikos on Wednesday July 19, 2017 @05:47PM (#14808283)
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 by carapace on Thursday July 20, 2017 @03:47AM (#14810710)
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.

Re:Fast pentomino puzzle solver ported from Forth to Python by kybernetikos on Thursday July 20, 2017 @04:44AM (#14810900)
That's really fun.
Re:Fast pentomino puzzle solver ported from Forth to Python by jxramos on Wednesday July 19, 2017 @04:14PM (#14807500)
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 by denfromufa on Wednesday July 19, 2017 @03:43PM (#14807280)
wow, this is insightful generalization