In article <87iodoakft@elektro.pacujo.net>,
Marko Rauhamaa wrote:
>Ian Kelly :
>
>> The test puzzle that you posted has 23 values already filled in. How
>> does it perform on harder puzzles with only 17 clues (the proven
>> minimum)? One would expect it to be around a million times slower.
>
On 29/03/2015 08:57, Christian Gollwitzer wrote:
Am 29.03.15 um 05:06 schrieb Steven D'Aprano:
[OT: Competing with compiled C code]
I'm not one of those people who think that C is by definition the fastest
language conceivable. (People who believe this sometimes make an
exception
for hand-cra
mr.smit...@gmail.com:
> You say "neater implementation"
> I'll send you to the code-golf site:
> http://codegolf.stackexchange.com/a/446/38632 this is brute force.
> There are some really good implementations in other languages that
> arent brute force.
It ain't neater if it don't fit in your pos
Ian Kelly :
> On Mon, Mar 30, 2015 at 1:13 AM, Christian Gollwitzer
> wrote:
>> Am 30.03.15 um 08:50 schrieb Ian Kelly:
>>>
>>> On Sun, Mar 29, 2015 at 12:03 PM, Marko Rauhamaa
>>> wrote:
Be careful with the benchmark comparisons. Ian's example can be
solved with the identical alg
On Mon, Mar 30, 2015 at 7:57 PM, Ian Kelly wrote:
> On Mon, Mar 30, 2015 at 2:16 AM, Dave Angel wrote:
>> 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 an
On Mon, Mar 30, 2015 at 2:16 AM, Dave Angel wrote:
> 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 c
On 03/30/2015 03:29 AM, Ian Kelly wrote:
On Mon, Mar 30, 2015 at 1:13 AM, Christian Gollwitzer wrote:
Am 30.03.15 um 08:50 schrieb Ian Kelly:
On Sun, Mar 29, 2015 at 12:03 PM, Marko Rauhamaa wrote:
Be careful with the benchmark comparisons. Ian's example can be solved
with the identical al
On Mon, Mar 30, 2015 at 1:13 AM, Christian Gollwitzer wrote:
> Am 30.03.15 um 08:50 schrieb Ian Kelly:
>>
>> On Sun, Mar 29, 2015 at 12:03 PM, Marko Rauhamaa wrote:
>>>
>>> Be careful with the benchmark comparisons. Ian's example can be solved
>>> with the identical algorithm in eight different w
Am 30.03.15 um 08:50 schrieb Ian Kelly:
On Sun, Mar 29, 2015 at 12:03 PM, Marko Rauhamaa 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 solv
On Sun, Mar 29, 2015 at 12:03 PM, Marko Rauhamaa wrote:
> BartC :
>
>> As Chris mentioned, when I say 'faster than C', I mean X running my
>> algorithm was faster then C running Marko's algoritim (on Ian's data).
>> This was just an illustration of algorithm being more important than
>> language.
On Sun, 29 Mar 2015 23:17:23 +0100, BartC wrote:
>On 29/03/2015 22:21, Mark Lawrence wrote:
>> On 28/03/2015 23:50, BartC wrote:
>>> On 28/03/2015 03:39, Sayth wrote:
Good test for pypy to see where it's speed sits between C and Python.
>
>>> Python 3.1: 1700 seconds (normal Python i
On Wednesday, March 25, 2015 at 4:39:40 AM UTC-7, Marko Rauhamaa wrote:
> A lot of discussion was generated by the good, old fibonacci sequence. I
> have yet to find practical use for fibonacci numbers. However, the
> technique behind a sudoku solver come up every now and again in
> practical situa
On 29/03/2015 22:21, Mark Lawrence wrote:
On 28/03/2015 23:50, BartC wrote:
On 28/03/2015 03:39, Sayth wrote:
Good test for pypy to see where it's speed sits between C and Python.
Python 3.1: 1700 seconds (normal Python interpreter)
PyPy: 93 seconds
C unoptimised: 17 secon
On 29/03/2015 22:19, Mark Lawrence wrote:
On 29/03/2015 21:59, BartC wrote:
On 29/03/2015 00:12, Chris Angelico wrote:
On Sun, Mar 29, 2015 at 10:50 AM, BartC wrote:
Using the OP's algorithm, and testing with the 'hard' puzzle posted
by Ian
Kelly, I got these approximate results:
Python 3.1:
On 28/03/2015 23:50, BartC wrote:
On 28/03/2015 03:39, Sayth wrote:
Good test for pypy to see where it's speed sits between C and Python.
I've spent the last hour or so doing such tests.
Using the OP's algorithm, and testing with the 'hard' puzzle posted by
Ian Kelly, I got these approximate
On 29/03/2015 21:59, BartC wrote:
On 29/03/2015 00:12, Chris Angelico wrote:
On Sun, Mar 29, 2015 at 10:50 AM, BartC wrote:
Using the OP's algorithm, and testing with the 'hard' puzzle posted
by Ian
Kelly, I got these approximate results:
Python 3.1: 1700 seconds (normal Python interp
On 29/03/2015 19:03, Marko Rauhamaa wrote:
BartC :
As Chris mentioned, when I say 'faster than C', I mean X running my
algorithm was faster then C running Marko's algoritim (on Ian's data).
This was just an illustration of algorithm being more important than
language.
Be careful with the benc
On 29/03/2015 00:12, Chris Angelico wrote:
On Sun, Mar 29, 2015 at 10:50 AM, BartC wrote:
Using the OP's algorithm, and testing with the 'hard' puzzle posted by Ian
Kelly, I got these approximate results:
Python 3.1: 1700 seconds (normal Python interpreter)
PyPy: 93 seconds
C
Mark Lawrence :
> One thing I have come to rely on over the years is never, ever trust
> your gut instincts about Python performance, you're almost inevitably
> wrong. When I first came across the Norvig solver I made a change,
> purely for fun, to replace two calls to len() with a single call and
On 29/03/2015 19:03, Marko Rauhamaa wrote:
BartC :
As Chris mentioned, when I say 'faster than C', I mean X running my
algorithm was faster then C running Marko's algoritim (on Ian's data).
This was just an illustration of algorithm being more important than
language.
Be careful with the benc
BartC :
> As Chris mentioned, when I say 'faster than C', I mean X running my
> algorithm was faster then C running Marko's algoritim (on Ian's data).
> This was just an illustration of algorithm being more important than
> language.
Be careful with the benchmark comparisons. Ian's example can be
On 29/03/2015 13:01, BartC wrote:
On 29/03/2015 11:35, Steven D'Aprano wrote:
Anyway, we don't really know where the confusion lies. Perhaps the
description is misleading, or I'm just confused, or Bart's idea of brute
force is not the same as my idea of brute force, or perhaps he really
is a
s
On 29/03/2015 11:35, Steven D'Aprano wrote:
That's why I can't help but feel that, *given the description we've seen*,
perhaps Bart's brute force code doesn't actually solve the problem, and
that's why it is so fast. I'm reminded of the recent thread where somebody
claimed to have a significant
On 29/03/2015 04:06, Steven D'Aprano wrote:
On Sun, 29 Mar 2015 10:50 am, BartC wrote:
But using X *and* my own brute-force algorithm, the same puzzle took 2
seconds to solve - faster than C!
But, when you tell me that your very own personal interpreted language,
which I assume nobody else
On Sun, Mar 29, 2015 at 9:35 PM, Steven D'Aprano
wrote:
> Anyway, we don't really know where the confusion lies. Perhaps the
> description is misleading, or I'm just confused, or Bart's idea of brute
> force is not the same as my idea of brute force, or perhaps he really is a
> super-genius who ha
On Sun, 29 Mar 2015 03:10 pm, Chris Angelico wrote:
> On Sun, Mar 29, 2015 at 2:06 PM, Steven D'Aprano
> wrote:
>> On Sun, 29 Mar 2015 10:50 am, BartC wrote:
>>
>>> (X is my own interpreted language, which is where my interest in this
>>> is. This had been generally faster than Python until PyPy
Am 29.03.15 um 05:06 schrieb Steven D'Aprano:
I'm not one of those people who think that C is by definition the fastest
language conceivable. (People who believe this sometimes make an exception
for hand-crafted assembly, which is ironic since these days the best C
optimizing compilers can genera
On Sun, Mar 29, 2015 at 2:06 PM, Steven D'Aprano
wrote:
> On Sun, 29 Mar 2015 10:50 am, BartC wrote:
>
>> (X is my own interpreted language, which is where my interest in this
>> is. This had been generally faster than Python until PyPy came along. It
>> does however use a pure byte-code interpret
On Sun, 29 Mar 2015 10:50 am, BartC wrote:
> (X is my own interpreted language, which is where my interest in this
> is. This had been generally faster than Python until PyPy came along. It
> does however use a pure byte-code interpreter, so the result is not too
> bad.
>
> But using X *and* my
On Sun, Mar 29, 2015 at 10:50 AM, BartC wrote:
> Using the OP's algorithm, and testing with the 'hard' puzzle posted by Ian
> Kelly, I got these approximate results:
>
> Python 3.1: 1700 seconds (normal Python interpreter)
> PyPy: 93 seconds
> C unoptimised: 17 seconds (gc
On 28/03/2015 03:39, Sayth wrote:
Good test for pypy to see where it's speed sits between C and Python.
I've spent the last hour or so doing such tests.
Using the OP's algorithm, and testing with the 'hard' puzzle posted by
Ian Kelly, I got these approximate results:
Python 3.1: 1700 se
On 27-Mar-2015 15:09, Dave Angel wrote:
On 03/27/2015 09:56 AM, Marko Rauhamaa wrote:
"Frank Millman" :
So what I am talking about is called a "satisfactory" puzzle, which is
a subset of a "proper" puzzle.
That is impossible to define, though, because some people are mental
acrobats and can
On Fri, Mar 27, 2015 at 7:40 PM, Steven D'Aprano
wrote:
> Excluding that, the consensus seems to be that Perl's regexes are stronger
> than Chomsky regular expressions, but nobody quite knows how much stronger.
> It's likely that they are at least as powerful as context-free grammars,
> but not as
Good test for pypy to see where it's speed sits between C and Python.
--
https://mail.python.org/mailman/listinfo/python-list
On Sat, 28 Mar 2015 05:18 am, sohcahto...@gmail.com wrote:
> On Friday, March 27, 2015 at 7:10:54 AM UTC-7, Dave Angel wrote:
>> I know, let's use "regular expressions"
>>
>>
>> --
>> DaveA
>
> You jest, but...
>
> http://www.perlmonks.org/?node_id=471168
I'm not a Perl expert, but I call
On Sat, 28 Mar 2015 01:19 am, Chris Angelico wrote:
> Part of me is quaking in fear... the other part looking on in morbid
> fascination. Can you build a regexp that proves a Sudoku grid
> solvable?
Perl's regular expressions can run arbitrary code using ?{...} which
technically makes them Turin
Chris Angelico wrote:
Part of me is quaking in fear... the other part looking on in morbid
fascination. Can you build a regexp that proves a Sudoku grid
solvable?
Well, it's *theoretically* possible, since there are a finite
number of possible sudoku puzzles, so if nothing else you
could just u
On 03/27/2015 07:09 AM, Dave Angel wrote:
[snip]
I know, let's use "regular expressions"
This is totally OT, but...
There was a recent (2015-03-23) item on The Daily WTF web site concerning
regular expressions.
Take a look at http://thedailywtf.com/articles/regularly-expressing-hate
On 26/03/2015 00:07, Ian Kelly wrote:
On Wed, Mar 25, 2015 at 2:31 PM, Marko Rauhamaa wrote:
It takes about 2 seconds for my Python program to find the answer but it
spends a total of 110 seconds to exhaust the problem space.
The analogous C program finished the whole thing in 200 millisecon
On Friday, March 27, 2015 at 7:10:54 AM UTC-7, Dave Angel wrote:
> On 03/27/2015 09:56 AM, Marko Rauhamaa wrote:
> > "Frank Millman" :
> >
> >> So what I am talking about is called a "satisfactory" puzzle, which is
> >> a subset of a "proper" puzzle.
> >
> > That is impossible to define, though, be
On 27/03/2015 14:09, Dave Angel wrote:
On 03/27/2015 09:56 AM, Marko Rauhamaa wrote:
"Frank Millman" :
So what I am talking about is called a "satisfactory" puzzle, which is
a subset of a "proper" puzzle.
That is impossible to define, though, because some people are mental
acrobats and can d
On Sat, Mar 28, 2015 at 1:09 AM, Dave Angel wrote:
> On 03/27/2015 09:56 AM, Marko Rauhamaa wrote:
>>
>> "Frank Millman" :
>>
>>> So what I am talking about is called a "satisfactory" puzzle, which is
>>> a subset of a "proper" puzzle.
>>
>>
>> That is impossible to define, though, because some pe
On 03/27/2015 09:56 AM, Marko Rauhamaa wrote:
"Frank Millman" :
So what I am talking about is called a "satisfactory" puzzle, which is
a subset of a "proper" puzzle.
That is impossible to define, though, because some people are mental
acrobats and can do a lot of deep analysis in their heads.
On Sat, Mar 28, 2015 at 12:56 AM, Marko Rauhamaa wrote:
> "Frank Millman" :
>
>> So what I am talking about is called a "satisfactory" puzzle, which is
>> a subset of a "proper" puzzle.
>
> That is impossible to define, though, because some people are mental
> acrobats and can do a lot of deep ana
On Sat, Mar 28, 2015 at 12:48 AM, Dave Angel wrote:
> On the other hand, I play some "games" which I can only solve with the aid
> of a computer. Is that "cheating"? Not for some games. I have some
> challenges for which I need/prefer to use a wrench, or a screwdriver, or a
> lawnmower. That d
"Frank Millman" :
> So what I am talking about is called a "satisfactory" puzzle, which is
> a subset of a "proper" puzzle.
That is impossible to define, though, because some people are mental
acrobats and can do a lot of deep analysis in their heads. What's
satisfactory to you may not be satisfa
On 03/27/2015 09:35 AM, Frank Millman wrote:
"Dave Angel" wrote in message
news:551557b3.5090...@davea.name...
But now I have to disagree about "true Sudoku puzzle." As we said
earlier, it might make sense to say that puzzles that cannot be solved
that way are not reasonable ones to put in a
On 03/27/2015 09:25 AM, Chris Angelico wrote:
On Sat, Mar 28, 2015 at 12:14 AM, Dave Angel wrote:
But now I have to disagree about "true Sudoku puzzle." As we said earlier,
it might make sense to say that puzzles that cannot be solved that way are
not reasonable ones to put in a human Sudoku b
"Dave Angel" wrote in message
news:551557b3.5090...@davea.name...
>
> But now I have to disagree about "true Sudoku puzzle." As we said
> earlier, it might make sense to say that puzzles that cannot be solved
> that way are not reasonable ones to put in a human Sudoku book. But why
> isn't
On Sat, Mar 28, 2015 at 12:14 AM, Dave Angel wrote:
> But now I have to disagree about "true Sudoku puzzle." As we said earlier,
> it might make sense to say that puzzles that cannot be solved that way are
> not reasonable ones to put in a human Sudoku book. But why isn't it a "true
> Sudoku puz
On 03/27/2015 05:25 AM, Chris Angelico wrote:
On Fri, Mar 27, 2015 at 8:07 PM, Frank Millman wrote:
There seems to be disagreement over the use of the term 'trial and error'.
How about this for a revised wording -
"It should be possible to reach that solution by a sequence of logical
deduction
On Fri, Mar 27, 2015 at 8:07 PM, Frank Millman wrote:
> There seems to be disagreement over the use of the term 'trial and error'.
> How about this for a revised wording -
>
> "It should be possible to reach that solution by a sequence of logical
> deductions. Each step in the sequence must unique
"Marko Rauhamaa" wrote in message
news:87fv8sndw1@elektro.pacujo.net...
> "Frank Millman" :
>
>> Here is another python-based sudoku solver -
>>
>> http://www.ics.uci.edu/~eppstein/PADS/Sudoku.py
>>
>>>From its docstring -
>>
>> "A proper Sudoku puzzle must have a unique solution, and it sho
Am 26.03.15 um 00:04 schrieb Mark Lawrence:
On 25/03/2015 22:50, Steven D'Aprano wrote:
On Wed, 25 Mar 2015 10:39 pm, Marko Rauhamaa wrote:
I have yet to find practical use for fibonacci numbers.
Many people have failed to find practical uses for many things from
mathematics. Doesn't mean th
Here's my Python sudoku solver which I wrote about 10 years ago.
http://petef.22web.org/sudoku/
It works by applying the solving techniques I came up with. No trial and
error or backtracking is used, so it is not up to cracking the very
hardest puzzles. Run time is 15 ms to 45 ms on a 2009 MacBoo
Ian Kelly :
> On Thu, Mar 26, 2015 at 9:48 AM, Marko Rauhamaa wrote:
>> In fact, the "trial-and-error" technique is used in automated theorem
>> proving:
>>
>> Lean provers are generally implemented in Prolog, and make proficient
>> use of the backtracking engine and logic variables of that l
On Thu, Mar 26, 2015 at 9:48 AM, Marko Rauhamaa wrote:
> Ian Kelly :
>
>> On Thu, Mar 26, 2015 at 8:23 AM, Marko Rauhamaa wrote:
>>> That's trial and error, aka, reductio ad absurdum.
>>
>> Okay, I've probably used single-lookahead trial and error in my
>> reasoning at some point. But the example
Ian Kelly :
> On Thu, Mar 26, 2015 at 8:23 AM, Marko Rauhamaa wrote:
>> That's trial and error, aka, reductio ad absurdum.
>
> Okay, I've probably used single-lookahead trial and error in my
> reasoning at some point. But the example you give is equivalent to the
> deductive process "That can't b
Dave Angel :
> When in a playful mood, I wonder if all the Sudoku puzzles out there
> are just permutations of a few hundred written by Will Shortz.
A sudoku solver can be trivially turned into a puzzle generator:
$ ./sudok
On Fri, Mar 27, 2015 at 2:03 AM, Dave Angel wrote:
> On 03/26/2015 10:41 AM, Chris Angelico wrote:
> that's already been proven. So, that's why I would avoid guessing.
>>
>>
>> I've written a lot of solvers for various puzzles. Minesweeper,
>> Sudoku, a binary Sudoku-like puzzle that I don't real
On Thu, Mar 26, 2015 at 8:23 AM, Marko Rauhamaa wrote:
> Ian Kelly :
>
>> I don't think that I have used trial and error, in my head or
>> otherwise, in any sudoku I have ever solved.
>
> Of course you have. "This here can't be a 2 because if it were a 2, that
> there would have to be a 5, which i
On 03/26/2015 10:41 AM, Chris Angelico wrote:
that's already been proven. So, that's why I would avoid guessing.
I've written a lot of solvers for various puzzles. Minesweeper,
Sudoku, a binary Sudoku-like puzzle that I don't really have a good
name for, several others. Every time, I've tried t
On Fri, Mar 27, 2015 at 1:14 AM, Dave Angel wrote:
> On 03/26/2015 08:37 AM, Chris Angelico wrote:
>> Nothing. And solving a Sudoku puzzle - or any other puzzle - should
>> require no guessing. It should be possible to solve purely by logic.
>> Same goes for every other kind of puzzle out there; i
Ian Kelly :
> I don't think that I have used trial and error, in my head or
> otherwise, in any sudoku I have ever solved.
Of course you have. "This here can't be a 2 because if it were a 2, that
there would have to be a 5, which is impossible. Thus, the only
remaining alternative is 3, so I mark
Marko Rauhamaa :
> I have optimized my solution slightly:
>
> 1. precalculated integer division operations (big savings)
>
> 2. interned integers (little savings)
>
> The example above now finishes in 41 minutes on my computer. (The C
> version finishes in 13 seconds).
Any considered harmfull
On 03/26/2015 08:37 AM, Chris Angelico wrote:
On Thu, Mar 26, 2015 at 11:26 PM, Marko Rauhamaa wrote:
"Frank Millman" :
Here is another python-based sudoku solver -
http://www.ics.uci.edu/~eppstein/PADS/Sudoku.py
>From its docstring -
"A proper Sudoku puzzle must have a unique solution, an
On Mar 26, 2015 6:31 AM, "Marko Rauhamaa" wrote:
>
> "Frank Millman" :
>
> > Here is another python-based sudoku solver -
> >
> > http://www.ics.uci.edu/~eppstein/PADS/Sudoku.py
> >
> >>From its docstring -
> >
> > "A proper Sudoku puzzle must have a unique solution, and it should be
> > possible
On Thu, Mar 26, 2015 at 11:26 PM, Marko Rauhamaa wrote:
> "Frank Millman" :
>
>> Here is another python-based sudoku solver -
>>
>> http://www.ics.uci.edu/~eppstein/PADS/Sudoku.py
>>
>>>From its docstring -
>>
>> "A proper Sudoku puzzle must have a unique solution, and it should be
>> possible to
"Frank Millman" :
> Here is another python-based sudoku solver -
>
> http://www.ics.uci.edu/~eppstein/PADS/Sudoku.py
>
>>From its docstring -
>
> "A proper Sudoku puzzle must have a unique solution, and it should be
> possible to reach that solution by a sequence of logical deductions
> without tr
Abhiram R :
> On Thu, Mar 26, 2015 at 8:54 AM, Ian Kelly wrote:
>> On Wed, Mar 25, 2015 at 8:56 PM, Abhiram R wrote:
>>> On Mar 26, 2015 5:39 AM, "Ian Kelly" wrote:
$ cat sudoku2.dat
. . . 7 . . . . .
1 . . . . . . . .
. . . 4 3 . 2 . .
. . . . . . . . 6
. . . 5 .
"Marko Rauhamaa" wrote in message
news:87r3sdnw5t@elektro.pacujo.net...
>
>
> I post below a sudoku solver. I eagerly await neater implementations (as
> well as bug reports).
>
Here is another python-based sudoku solver -
http://www.ics.uci.edu/~eppstein/PADS/Sudoku.py
>From its docstring
On Thu, Mar 26, 2015 at 8:54 AM, Ian Kelly wrote:
> On Wed, Mar 25, 2015 at 8:56 PM, Abhiram R wrote:
>>
>> On Mar 26, 2015 5:39 AM, "Ian Kelly" wrote:
>>>
>>
>>> "Hard" for a human doesn't necessarily mean "hard" for a programmatic
>>> solver in this case. Try your solver on this one:
>>>
>>> $
On Wed, Mar 25, 2015 at 8:56 PM, Abhiram R wrote:
>
> On Mar 26, 2015 5:39 AM, "Ian Kelly" wrote:
>>
>
>> "Hard" for a human doesn't necessarily mean "hard" for a programmatic
>> solver in this case. Try your solver on this one:
>>
>> $ cat sudoku2.dat
>> . . . 7 . . . . .
>> 1 . . . . . . . .
>>
On Mar 26, 2015 5:39 AM, "Ian Kelly" wrote:
>
> "Hard" for a human doesn't necessarily mean "hard" for a programmatic
> solver in this case. Try your solver on this one:
>
> $ cat sudoku2.dat
> . . . 7 . . . . .
> 1 . . . . . . . .
> . . . 4 3 . 2 . .
> . . . . . . . . 6
> . . . 5 . 9 . . .
> . .
On Wed, Mar 25, 2015 at 2:31 PM, Marko Rauhamaa wrote:
> Ian Kelly :
>
>> The test puzzle that you posted has 23 values already filled in. How
>> does it perform on harder puzzles with only 17 clues (the proven
>> minimum)? One would expect it to be around a million times slower.
>
> Just try it.
On 25/03/2015 22:50, Steven D'Aprano wrote:
On Wed, 25 Mar 2015 10:39 pm, Marko Rauhamaa wrote:
I have yet to find practical use for fibonacci numbers.
Many people have failed to find practical uses for many things from
mathematics. Doesn't mean they don't exist:
http://en.wikipedia.org/wiki
On Wed, 25 Mar 2015 10:39 pm, Marko Rauhamaa wrote:
> I have yet to find practical use for fibonacci numbers.
Many people have failed to find practical uses for many things from
mathematics. Doesn't mean they don't exist:
http://en.wikipedia.org/wiki/Fibonacci_number#Applications
--
Steven
On Thu, Mar 26, 2015 at 7:31 AM, Marko Rauhamaa wrote:
> Ian Kelly :
>
>> The test puzzle that you posted has 23 values already filled in. How
>> does it perform on harder puzzles with only 17 clues (the proven
>> minimum)? One would expect it to be around a million times slower.
>
> Just try it.
Ian Kelly :
> The test puzzle that you posted has 23 values already filled in. How
> does it perform on harder puzzles with only 17 clues (the proven
> minimum)? One would expect it to be around a million times slower.
Just try it. The example had a minimum of clues (drop one clue and
you'll get
On Wed, Mar 25, 2015 at 1:37 PM, Marko Rauhamaa wrote:
> John Ladasky :
>
>> On Wednesday, March 25, 2015 at 4:39:40 AM UTC-7, Marko Rauhamaa wrote:
>>
>>> I post below a sudoku solver. I eagerly await neater implementations (as
>>> well as bug reports).
>>
>> So, it's a brute-force, recursive sol
John Ladasky :
> On Wednesday, March 25, 2015 at 4:39:40 AM UTC-7, Marko Rauhamaa wrote:
>
>> I post below a sudoku solver. I eagerly await neater implementations (as
>> well as bug reports).
>
> So, it's a brute-force, recursive solver? The code is nice and short.
> But I bet it takes a long time
On Wed, Mar 25, 2015 at 12:44 PM, John Ladasky
wrote:
> On Wednesday, March 25, 2015 at 4:39:40 AM UTC-7, Marko Rauhamaa wrote:
>
>> I post below a sudoku solver. I eagerly await neater implementations (as
>> well as bug reports).
>
> So, it's a brute-force, recursive solver? The code is nice and
On Wednesday, March 25, 2015 at 4:39:40 AM UTC-7, Marko Rauhamaa wrote:
> I post below a sudoku solver. I eagerly await neater implementations (as
> well as bug reports).
So, it's a brute-force, recursive solver? The code is nice and short. But I
bet it takes a long time to run.
I and a stude
>> http://norvig.com/sudoku.html
(...)
> Below is the "winner" of my hacking for an as fast as
> possible 110% pure python (no imports at all!) comprehensive sudoku
> solver under 50 LOCs, back in 2006. Performance is comparable to the
> solver you advertize - numbers are slightly better, but
On Thu, 24 Jan 2008 21:09:42 +0100
Thomas Thiel <[EMAIL PROTECTED]> wrote:
> Neither fast nor user friendly, but very concise:
This is a bit faster:
options = set([str(i) for i in range(1, 10)])
def allow(puzzle,i):
exclude = set(x if i//9 == j//9 or i%9 == j%9
or i//27 == j//27 an
On Wed, 23 Jan 2008 19:02:01 -0800 (PST), Derek Marshall wrote:
> This is just for fun, in case someone would be interested and because
> I haven't had the pleasure of posting anything here in many years ...
>
> http://derek.marshall.googlepages.com/pythonsudokusolver
>
> Appreciate any fee
Shawn Milochik wrote:
> On Jan 23, 2008, at 10:02 PM, Derek Marshall wrote:
>
>> This is just for fun, in case someone would be interested and because
>> I haven't had the pleasure of posting anything here in many years ...
>>
>> http://derek.marshall.googlepages.com/pythonsudokusolver
>>
>> A
Derek Marshall <[EMAIL PROTECTED]> wrote:
>This is just for fun, in case someone would be interested and because
>I haven't had the pleasure of posting anything here in many years ...
>
> http://derek.marshall.googlepages.com/pythonsudokusolver
>
>Appreciate any feedback anyone who takes the
On Jan 23, 2008, at 10:02 PM, Derek Marshall wrote:
> This is just for fun, in case someone would be interested and because
> I haven't had the pleasure of posting anything here in many years ...
>
> http://derek.marshall.googlepages.com/pythonsudokusolver
>
> Appreciate any feedback anyone w
ago wrote:
[Something I mostly agree with]
> According to Anton the number of possible solutions can be reduced
> using 1) number swapping, 2) mirroring, 3) blocks/rows/columns
> swapping. All those operations create equivalent matrices. For a 9X9
> grid, this should give a reduction factor = (9
> Do you think it is possible to reduce the set of all possible solutions
> to a small enough set? I personally doubt it, but IF that was the case
> an efficient solver could be easily created.
To expand on the concept, assume for the argument sake that the
universe of possible solutions can be re
ago wrote:
> Do you think it is possible to reduce the set of all possible solutions
> to a small enough set? I personally doubt it, but IF that was the case
> an efficient solver could be easily created.
No I don't think so, but it's a great idea :-) . Iff we would have some
ultimate symmetry de
>Your reduction-first approach makes short work of
> them, though. On the other hand, my version probably didn't take as long
> to write!
Well, I started from the reduction-only algorithm so by the time I
implemented the brute force solver I already had the code. Anyway the
full code is just above
Anton,
Do you think it is possible to reduce the set of all possible solutions
to a small enough set? I personally doubt it, but IF that was the case
an efficient solver could be easily created.
In reducing the set of all solutions for instance you could always swap
the numbers (3rd axis) so that
ago wrote:
>> But to inflate my ego beyond the known universe, here is my solver
>>(that solves the avove mentioned grid reasonably fast). I suppose the
>>only difference is that is uses 3, rather than 2, rules to simplify
>>before starting tree-like search.
>
>
> Thanks for the nice problem and
ago wrote:
> You can see my amended code in the link above.
Thanks, I will look into it sometime. At the moment I'm at a library
computer, which severely limits my Python options. Meanwhile I have
been thinking about the sudoku problem, maybe it will prompt you, me or
someone else to make some ki
> But to inflate my ego beyond the known universe, here is my solver
> (that solves the avove mentioned grid reasonably fast). I suppose the
> only difference is that is uses 3, rather than 2, rules to simplify
> before starting tree-like search.
Thanks for the nice problem and the nice post.
Th
There is more in this thread:
http://groups.google.com/group/comp.lang.python/browse_frm/thread/479c1dc768f740a3/9252dab14e8ecabb?q=sudoku&rnum=2#9252dab14e8ecabb
Enjoy,
Bas
--
http://mail.python.org/mailman/listinfo/python-list
ago wrote:
> Inspired by some recent readings on LinuxJournal and an ASPN recipe, I
> decided to revamp my old python hack... The new code is a combination
> of (2) reduction methods and brute force and it is quite faster than
> the
> ASPN program. If anyone is interested I attached the code in
> h
ago wrote:
> Inspired by some recent readings on LinuxJournal and an ASPN recipe, I
> decided to revamp my old python hack... The new code is a combination
> of (2) reduction methods and brute force and it is quite faster than
> the
> ASPN program. If anyone is interested I attached the code in
> h
1 - 100 of 101 matches
Mail list logo
