On 03/30/2015 03:29 AM, Ian Kelly wrote:
On Mon, Mar 30, 2015 at 1:13 AM, Christian Gollwitzer <aurio...@gmx.de> wrote:
Am 30.03.15 um 08:50 schrieb Ian Kelly:
On Sun, Mar 29, 2015 at 12:03 PM, Marko Rauhamaa <ma...@pacujo.net> wrote:
Be careful with the benchmark comparisons. Ian's example can be solved
with the identical algorithm in eight different ways (four corners, left
or right). I ran the example with my recent Python solver and got these
times in the eight cases:
884 s
2.5 s
13 s
499 s
5.9 s
128 s
1360 s
36 s
That sounds to me like either a transcription error was made to the
puzzle at some point, or there's something wrong with your solver. The
whole point of that example was that it was a puzzle with the minimum
number of clues to specify a unique solution.
I think Marko meant, that if he creates symmetrically equivalent puzzles by
rotating / mirroring the grid, he gets vastly different execution times, but
ends up with the same solution.
That makes sense, but it is true for all puzzles that there are eight
possible orientations (since it's impossible for a puzzle solution to
be symmetric), and the wording made it sound like he was describing a
property specific to the puzzle that I posted.
But for some puzzles, the 8 timings may be much closer. Or maybe even
further apart.
Incidentally, there are many other variants of the same puzzle that
might matter, beyond those 8.
The digits can all be crypto'ed Like replace all 4 with 8, etc.
Probably won't matter for any realistic algorithm.
The columns can be reordered, in at least some ways. For example, if
the first and second columns are swapped, it's a new puzzle, equivalent.
Likewise certain rows.
The relationship between row, column and box can be rearranged. Some of
these are already covered by the rotations proposed earlier, where for a
90 degree rotate, row becomes column and column becomes row. But in a
similar way each box could become a column, and so on.
All of these rearrangeements will change the order that an algorithm
might choose to examine things, and thus affect timings (but not the
solution).
When I made my own solver years ago, I considered the puzzle to have 9
columns, 9 rows, and 9 boxes. So these 27 lists of 9 could be analyzed.
I just came up with a fast way to map those 243 cells back and forth
with the original 81. At that point, it no longer mattered which things
were rows and which were columns or boxes.
--
DaveA
--
https://mail.python.org/mailman/listinfo/python-list
