Friday, July 04, 2014

[mvoghuaz] One-dimensional puzzle generator

Here is a one-dimensional jigsaw puzzle generator implemented in Haskell, creating one-dimensional instances of the exact cover problem.

For generation purposes, the one-dimensional field is divided into n blocks each of size b.  Each of the n pieces is roughly centered on a unique block and spans at most p blocks.  The arguments to the program are b p n.

Each generated piece is specified by a list of coordinates offset from its leftmost coordinate.  Each individual piece is typically not contiguous; that would make the puzzle trivial to solve. Solve the puzzle by finding the offset of each piece in the field so that the field is exactly covered by all the pieces.

There is a "edge effect" flaw such that pieces near the edge tend to span less than p blocks.

Example run with parameters 10 5 10:
Pieces are:
(0,[0,5,12,15,19,29])
(1,[0,1,5,6,7,12,16,17,22,23,25,27,29,30,31,32])
(2,[0,1,6,7,8,11,22,32,38,40,44,45])
(3,[0,4,5,21,23,24,26,33,37])
(4,[0,5,14,16,30,35,38,39])
(5,[0,12,25,28,30,32])
(6,[0,1,7,10,12,21,23,25,27,30,31,34,37,42,43,44,45])
(7,[0,5,8,18,27,29,33,34,35])
(8,[0,10,13,17,28,29,30,35,36])
(9,[0,2,12,20,24,25,26,27])

Solution is the concatenation of:
[0,1,1,2,2,0,1,1,1,2]
[2,2,0,1,2,0,3,1,1,0]
[3,3,4,1,1,2,1,4,1,0]
[1,1,1,1,5,2,4,3,4,3]
[3,2,3,2,6,6,5,2,2,3]
[7,6,4,3,6,7,6,4,7,5]
[4,4,5,8,5,6,5,6,7,6]
[9,6,9,8,6,6,8,7,6,7]
[8,6,9,7,7,7,6,6,6,6]
[9,8,8,8,9,9,9,9,8,8]

Motivation is to generate random inputs to Knuth's Dancing Links DLX algorithm.  What puzzle parameters generate difficult puzzles?

No comments: