[Puzzler-users] duplicate puzzler solutions for "polyiamonds" puzzles
Brought to you by:
goodger
Menu
▾
▴
[Puzzler-users] duplicate puzzler solutions for "polyiamonds" puzzles
|
From: Dave C. <dav...@gm...> - 2014-09-23 21:48:36
|
This is the second time I'm sending this message. The first attempt contained an attachment ( __init__.py ). In the Puzzler-users archive on sourceforge.net I *only* see the attachment - not the message itself. Now I am sending the message again, this time without the attachment. Refer to the earlier message for the attachment. Original message follows: -------------------------------------- Original Message Below --------------------------------------------------- I happened to notice that some of the puzzler "polyiamonds" solutions were showing duplicate answers. For example, solution 9 and solution 10 (shown below) from http://puzzler.sourceforge.net/solutions/iamonds/polyiamonds-12345-elongated-hexagon-9x1.txt are identical. Actually *most* of the solutions shown in that output file are duplicated - I just noticed 9 & 10 first. It turns out that this happens because there are duplicate rows in the exact cover problem formulation. Specifically, some of the rows corresponding to the T1 piece are duplicated. I didn't try to figure out the cause of this row duplication but I'm attaching a version of puzzler/puzzler/__init__.py that contains code that detects and removes duplicate rows (thus eliminating the duplicate solutions in the output). The attached __init__.py is based off of the trunk version from sourceforge . After the duplicate solutions shown in this e-mail, you can see a diff that shows the duplicate removal code. ------------------------------------------ duplicate solutions below -------------------------------------------- solution 9 (392 searches): 1,0,0 1,0,1 1,1,0 2,0,0 2,0,1 P5 0,0,1 0,1,0 0,1,1 I3 1,1,1 2,1,0 D2 2,1,1 3,0,0 3,0,1 3,1,0 C4 4,0,0 4,0,1 4,1,0 5,0,0 T4 3,1,1 T1 4,1,1 5,0,1 5,1,0 6,0,0 6,0,1 L5 5,1,1 6,1,0 6,1,1 7,1,0 7,1,1 I5 7,0,0 7,0,1 8,0,0 8,0,1 I4 8,1,0 8,1,1 9,0,0 9,0,1 9,1,0 C5 ____________________________________ / /\ \ \ /\ \ / \ / / \___\ \/ \ \________/___ \ \ / / / \ / / / \/_______/___/______\____/_______/___/ solution 10 (403 searches): 1,0,0 1,0,1 1,1,0 2,0,0 2,0,1 P5 0,0,1 0,1,0 0,1,1 I3 1,1,1 2,1,0 D2 2,1,1 3,0,0 3,0,1 3,1,0 C4 4,0,0 4,0,1 4,1,0 5,0,0 T4 3,1,1 T1 4,1,1 5,0,1 5,1,0 6,0,0 6,0,1 L5 5,1,1 6,1,0 6,1,1 7,1,0 7,1,1 I5 7,0,0 7,0,1 8,0,0 8,0,1 I4 8,1,0 8,1,1 9,0,0 9,0,1 9,1,0 C5 ____________________________________ / /\ \ \ /\ \ / \ / / \___\ \/ \ \________/___ \ \ / / / \ / / / \/_______/___/______\____/_______/___/ ------------------------------ ------------ duplicate removal code below -------------------------------------------- --- a/puzzler/puzzler/__init__.py +++ b/puzzler/puzzler/__init__.py @@ -203,6 +203,25 @@ def solve(puzzle_class, output_stream, settings): # initially (and memory) with multi-part puzzles puzzles.append(component()) for puzzle in puzzles: + # check for and eliminate duplicate rows + unique_rows = [] + for row in puzzle.matrix[1:]: + if row not in unique_rows: + unique_rows.append(row) + else: + print >>output_stream, "duplicate row: ", + for i, item in enumerate(row): + if item: + print >>output_stream, item, + print >>output_stream + original_row_count = len(puzzle.matrix[1:]) + unique_row_count = len(unique_rows) + if original_row_count != unique_row_count: + print >>output_stream, ( + '\nEliminating %s duplicate rows leaving %s total rows.\n' + % (original_row_count - unique_row_count, + unique_row_count)) + puzzle.matrix[1:] = unique_rows matrices.append((puzzle.matrix, puzzle.secondary_columns)) state.init_periodic_save(solver) last_solutions = state.last_solutions |
