Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #41979 > unrolled thread

Sudoku

Back to article view | Back to comp.lang.python

Contents

  Sudoku Eric Parry <joan4eric@gmail.com> - 2013-03-26 22:44 -0700
    Re: Sudoku Ulrich Eckhardt <ulrich.eckhardt@dominolaser.com> - 2013-03-27 08:58 +0100
      Re: Sudoku Eric Parry <joan4eric@gmail.com> - 2013-03-27 20:00 -0700
        Re: Sudoku Dave Angel <davea@davea.name> - 2013-03-28 00:36 -0400
          Re: Sudoku Eric Parry <joan4eric@gmail.com> - 2013-03-28 15:11 -0700
            Re: Sudoku Dave Angel <davea@davea.name> - 2013-03-28 19:28 -0400
              Re: Sudoku Eric Parry <joan4eric@gmail.com> - 2013-03-28 22:07 -0700
              Re: Sudoku Eric Parry <joan4eric@gmail.com> - 2013-03-28 22:07 -0700
            Re: Sudoku Chris Angelico <rosuav@gmail.com> - 2013-03-29 09:45 +1100
              Re: Sudoku Eric Parry <joan4eric@gmail.com> - 2013-03-29 14:47 -0700
                Re: Sudoku Dave Angel <davea@davea.name> - 2013-03-29 18:11 -0400
                  Re: Sudoku Eric Parry <joan4eric@gmail.com> - 2013-03-30 15:06 -0700
                    Re: Sudoku Dave Angel <davea@davea.name> - 2013-03-30 19:15 -0400
                      Re: Sudoku Eric Parry <joan4eric@gmail.com> - 2013-03-31 15:03 -0700
                        Re: Sudoku Dave Angel <davea@davea.name> - 2013-03-31 18:34 -0400
                        Re: Sudoku Arnaud Delobelle <arnodel@gmail.com> - 2013-03-31 23:59 +0100
                      Re: Sudoku Eric Parry <joan4eric@gmail.com> - 2013-03-31 15:03 -0700
                        Re: Sudoku Eric Parry <joan4eric@gmail.com> - 2013-03-31 15:27 -0700
                          Re: Sudoku Chris Angelico <rosuav@gmail.com> - 2013-04-01 09:35 +1100
                            Re: Sudoku Eric Parry <joan4eric@gmail.com> - 2013-03-31 20:58 -0700
                        Re: Sudoku Eric Parry <joan4eric@gmail.com> - 2013-03-31 15:27 -0700
                  Re: Sudoku Eric Parry <joan4eric@gmail.com> - 2013-03-30 15:06 -0700
              Re: Sudoku Eric Parry <joan4eric@gmail.com> - 2013-03-29 14:47 -0700
          Re: Sudoku Eric Parry <joan4eric@gmail.com> - 2013-03-28 15:11 -0700
    Re: Sudoku Damien Wyart <damien.wyart@free.fr> - 2013-03-27 09:49 +0100
    Re: Sudoku Dave Angel <davea@davea.name> - 2013-03-27 05:38 -0400
    Re: Sudoku Eric Parry <joan4eric@gmail.com> - 2013-03-27 19:49 -0700

Page 2 of 2 — ← Prev page 1 [2]

#42428

On Monday, April 1, 2013 8:33:47 AM UTC+10:30, Eric Parry wrote:
> On Sunday, March 31, 2013 9:45:36 AM UTC+10:30, Dave Angel wrote:
> 
> > On 03/30/2013 06:06 PM, Eric Parry wrote:
> 
> > 
> 
> > > On Saturday, March 30, 2013 8:41:08 AM UTC+10:30, Dave Angel wrote:
> 
> > 
> 
> > >> On 03/29/2013 05:47 PM, Eric Parry wrote:
> 
> > 
> 
> > >>
> 
> > 
> 
> > >>>  <SNIP>
> 
> > 
> 
> > >>
> 
> > 
> 
> > >> Sometimes a bug in such a function will cause it to run indefinitely,
> 
> > 
> 
> > >>
> 
> > 
> 
> > >> and/or to overflow the stack.  I don't see such a bug in this function.
> 
> > 
> 
> > >>
> 
> > 
> 
> > >>
> 
> > 
> 
> > >>
> 
> > 
> 
> > >>
> 
> > 
> 
> > >>
> 
> > 
> 
> > >> --
> 
> > 
> 
> > >>
> 
> > 
> 
> > >> DaveA
> 
> > 
> 
> > >
> 
> > 
> 
> > > The exit() did not work.
> 
> > 
> 
> > 
> 
> > 
> 
> > Would you like to elaborate?  exit() is supposed to take an int 
> 
> > 
> 
> > parameter, but the author apparently didn't notice that.  So perhaps you 
> 
> > 
> 
> > got an exception of some sort.  Change it to exit() or exit(0) and it 
> 
> > 
> 
> > might solve the problem, depending on what the problem was.
> 
> > 
> 
> > 
> 
> > 
> 
> > > I replaced it with return = 0, and that does work.
> 
> > 
> 
> > 
> 
> > 
> 
> > No it doesn't.  return = 0 is a syntax error in both Python 2.x and 3.x
> 
> > 
> 
> > 
> 
> > 
> 
> > But if you changed it to a valid return statement, then that's why it 
> 
> > 
> 
> > doesn't stop on the first solution.
> 
> > 
> 
> > 
> 
> > 
> 
> > 
> 
> > 
> 
> > -- 
> 
> > 
> 
> > DaveA
> 
> 
> 
> I think in the original it was exit(a). That did not work either.
> 
> I'll try the others.
> 
> Eric.

I tried all those things. The program keeps running after the solution in every case. Never mind. It won't do that in VBA when I finish it.
Eric.

[toc] | [prev] | [next] | [standalone]

#42352

On Saturday, March 30, 2013 8:41:08 AM UTC+10:30, Dave Angel wrote:
> On 03/29/2013 05:47 PM, Eric Parry wrote:
> 
> >
> 
> >>   <SNIP>
> 
> >>
> 
> > That explains why the program keeps running after a solution is found.
> 
> 
> 
> A recursive function can be designed to find all solutions, in which 
> 
> case it would (as you say) keep running.
> 
> 
> 
> The function you posted in the first place uses exit() to avoid keeping 
> 
> running.  It stops as soon as a solution is found.
> 
> 
> 
> Sometimes a problem cannot be solved in the number of stack entries 
> 
> supplied by Python.  So even though such a function will terminate, it 
> 
> may crash first if the problem is too big.  Example, the factorial 
> 
> problem I described earlier, if you pass it 2000 as a parameter.  If 
> 
> this is a problem, one can tell the Python to give you more stack entries.
> 
> 
> 
> Given a 9x9 matrix, and at least some of them filled in, the maximum 
> 
> depth your code can use is less than 81.  So it won't get a stack 
> 
> overflow in any implementation of Python I've seen.  Perhaps in an 8051.
> 
> 
> 
> Sometimes a bug in such a function will cause it to run indefinitely, 
> 
> and/or to overflow the stack.  I don't see such a bug in this function.
> 
> 
> 
> 
> 
> -- 
> 
> DaveA

The exit() did not work.
I replaced it with return = 0, and that does work.
Eric.

[toc] | [prev] | [next] | [standalone]

#42284

On Friday, March 29, 2013 9:15:36 AM UTC+10:30, Chris Angelico wrote:
> On Fri, Mar 29, 2013 at 9:11 AM, Eric Parry <joan4eric@gmail.com> wrote:
> 
> > Thank you for that explanation.
> 
> > No, I do not understand recursion. It is missing from my Python manual. I would be pleased to receive further explanation from anyone.
> 
> 
> 
> If you already know what recursion is, just remember the answer.
> 
> Otherwise, find someone who is standing closer to Douglas Hofstadter
> 
> than you are; then ask him or her what recursion is.
> 
> 
> 
> :)
> 
> 
> 
> Recursion is a form of self-referential code. Take this simple, and
> 
> rather silly, means of calculating the sum of numbers in a list (like
> 
> the sum() function):
> 
> 
> 
> # The sum of numbers in an empty list is 0.
> 
> # Otherwise it is the first number plus the sum of the rest of the list.
> 
> def list_sum(lst):
> 
>     if not lst: return 0
> 
>     return lst[0] + list_sum(lst[1:])
> 
> 
> 
> >>> list_sum([1,2,3,4,5,6])
> 
> 21
> 
> 
> 
> Note how the function calls itself - but not always. That's critical
> 
> to recursion - a termination condition. In this case, it's quite
> 
> obvious that the list will eventually have nothing left in it, so the
> 
> function will terminate. Sometimes it's less obvious. Sometimes a bug
> 
> results in infinite recursion... and:
> 
> 
> 
> RuntimeError: maximum recursion depth exceeded in comparison
> 
> 
> 
> Hope that helps!
> 
> 
> 
> ChrisA

Thank you for that example Chris.
That explains why the program keeps running after a solution is found.
Eric

[toc] | [prev] | [next] | [standalone]

#42199

On Thursday, March 28, 2013 3:06:02 PM UTC+10:30, Dave Angel wrote:
> On 03/27/2013 11:00 PM, Eric Parry wrote:
> 
> > On Wednesday, March 27, 2013 6:28:01 PM UTC+10:30, Ulrich Eckhardt wrote:
> 
> >>
> 
>       <SNIP the double-spaced garbage that GoogleGroups put in - see 
> 
> http://wiki.python.org/moin/GoogleGroupsPython >
> 
> >
> 
> > Thank you for your explanation.
> 
> > I noticed that in this particular puzzle when it ran out of candidates in a particular cycle, it then changed the last entry to the next one in line in the previous cycle. But I cannot find any code to do this.
> 
> > I was hoping to understand the logic so that I could re-write it in VBA for excel which would enable any puzzle to be entered directly.
> 
> > Your comments are a big help especially the double negative aspect.
> 
> >
> 
> 
> 
> Are you familiar with recursion?  Notice the last line in the function 
> 
> r() calls the function r() inside a for loop.
> 
> 
> 
> So when r() returns, you're back inside the next level up of the 
> 
> function, and doing a "backtrack."
> 
> 
> 
> When the function succeeds, it will be many levels of recursion deep. 
> 
> For example, if the original pattern had 30 nonzero items in it, or 51 
> 
> zeroes, you'll be 51 levels of recursion when you discover a solution.
> 
> 
> 
> If you don't already understand recursion at all, then say so, and one 
> 
> or more of us will try to explain it in more depth.
> 
> 
> 
> -- 
> 
> DaveA

Thank you for that explanation.
No, I do not understand recursion. It is missing from my Python manual. I would be pleased to receive further explanation from anyone.
Eric.

[toc] | [prev] | [next] | [standalone]

#41990

* Eric Parry <joan4eric@gmail.com> in comp.lang.python:
> I downloaded the following program from somewhere using a link from
> Wikipedia and inserted the “most difficult Sudoku puzzle ever” string
> into it and ran it. It worked fine and solved the puzzle in about
> 4 seconds. However I cannot understand how it works. It seems to go
> backwards and forwards at random. Can anyone explain how it works in
> simple terms?

You might also be interested in the following:

http://norvig.com/sudoku.html
http://norvig.com/sudopy.shtml

-- 
DW

[toc] | [prev] | [next] | [standalone]

#41999

On 03/27/2013 01:44 AM, Eric Parry wrote:
> I downloaded the following program from somewhere

It'd be good to show where you found it, and credit the apparent author. 
  Bill Barksdale posted this in 2008 at:
 
http://stackoverflow.com/questions/201461/shortest-sudoku-solver-in-python-how-does-it-work

I don't know if there are older ones somewhere, but I didn't find any. 
I did find places that quoted his code without attribution.

Another thing worth pointing out is that it's only valid for Python 2.x 
  (naturally, since I don't think Python 3 was out at that point)

using a link from Wikipedia and inserted the “most difficult Sudoku 
puzzle ever” string into it and ran it. It worked fine and solved the 
puzzle in about 4 seconds. However I cannot understand how it works. It 
seems to go backwards and forwards at random. Can anyone explain how it 
works in simple terms?
> Eric.
>
>
> def same_row(i,j): return (i/9 == j/9)
> def same_col(i,j): return (i-j) % 9 == 0
> def same_block(i,j): return (i/27 == j/27 and i%9/3 == j%9/3)
>
> def r(a):
>    i = a.find('0')
>    if i == -1:
>      print a
>      exit(a)
>
>    excluded_numbers = set()
>    for j in range(81):
>      if same_row(i,j) or same_col(i,j) or same_block(i,j):
>        excluded_numbers.add(a[j])
>
>    for m in '123456789':
>      if m not in excluded_numbers:
>        # At this point, m is not excluded by any row, column, or block, so let's place it and recurse
>        r(a[:i]+m+a[i+1:])
>
> r('800000000003600000070090200050007000000045700000100030001000068008500010090000400')
> Sudoku solver where the puzzle is an 81 character string representing the puzzle read left-to-right, top-to-bottom, and 0 is a blank.
>  
>


-- 
DaveA

[toc] | [prev] | [next] | [standalone]

#42072

Thank you all for your help and suggestions.

Eric

[toc] | [prev] | [standalone]

Page 2 of 2 — ← Prev page 1 [2]

Back to top | Article view | comp.lang.python

csiph-web