Path: csiph.com!usenet.pasdenom.info!weretis.net!feeder1.news.weretis.net!feeder.erje.net!eu.feeder.erje.net!bcyclone04.am1.xlned.com!bcyclone04.am1.xlned.com!newsfeed.xs4all.nl!newsfeed4a.news.xs4all.nl!xs4all!post.news.xs4all.nl!not-for-mail
Date: Mon, 30 Mar 2015 04:16:58 -0400
From: Dave Angel <davea@davea.name>
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:31.0) Gecko/20100101 Thunderbird/31.5.0
MIME-Version: 1.0
To: python-list@python.org
Subject: Re: Sudoku solver
References: <87r3sdnw5t.fsf@elektro.pacujo.net> <4e81bdb9-52db-46e6-b449-d4241cb2a3f2@googlegroups.com> <87twx8amww.fsf@elektro.pacujo.net> <82e7c5b9-2f0f-405b-859c-b74916c475e0@googlegroups.com> <R6HRw.1255136$4b6.945049@fx44.am4> <55176c2c$0$13009$c3e8da3$5496439d@news.astraweb.com> <ziRRw.1732061$BB2.522910@fx35.am4> <87619j7kbu.fsf@elektro.pacujo.net> <mailman.334.1427698246.10327.python-list@python.org> <mfat14$v08$1@dont-email.me> <CALwzid=zoDano9ZQ7vkk_uVG8kLSBs2822YaTTR4MYNfGmzu8g@mail.gmail.com>
In-Reply-To: <CALwzid=zoDano9ZQ7vkk_uVG8kLSBs2822YaTTR4MYNfGmzu8g@mail.gmail.com>
Content-Type: text/plain; charset=windows-1252; format=flowed
Content-Transfer-Encoding: 7bit
Precedence: list
Newsgroups: comp.lang.python
Message-ID: <mailman.337.1427703431.10327.python-list@python.org>
Lines: 67
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python:88323

On 03/30/2015 03:29 AM, Ian Kelly wrote:
> On Mon, Mar 30, 2015 at 1:13 AM, Christian Gollwitzer <auriocus@gmx.de> wrote:
>> Am 30.03.15 um 08:50 schrieb Ian Kelly:
>>>
>>> On Sun, Mar 29, 2015 at 12:03 PM, Marko Rauhamaa <marko@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