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 1 of 2  [1] 2  Next page →

#41979 — Sudoku

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?
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.
 

[toc] | [next] | [standalone]

#41985

Am 27.03.2013 06:44, schrieb Eric Parry:
> 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.


In simple terms, it is using a depth-first search and backtracking. If 
you really want to understand this, get a book on algorithms and graphs 
(or locate an online source). I can try to give you an idea though.


 > It seems to go backwards and forwards at random. Can anyone explain
 > how it works in simple terms?

I think your interpretation of what it does is wrong or at least flawed. 
It does try different combinations, but some don't lead to a solution. 
In that case, it goes back to a previous solution and tries the next one.


I'll try to document the program to make it easier to understand...

> 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):
      # find an empty cell
      # If no empty cells are found, we have a solution that we print
      # and then terminate.
>    i = a.find('0')
>    if i == -1:
>      print a
>      exit(a)

      # find excluded numbers
      # Some numbers are blocked because they are already used in
      # the current column, row or block. This means they can't
      # possibly be used for the current empty cell.
>    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])

      # create possible solutions
      # Try all possibly numbers for the current empty cell in turn.
      # With the resulting modifications to the sodoku, use
      # recursion to find a full solution.
>    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:])

      # no solution found
      # If we come here, there was no solution for the input data.
      # We return to the caller (should be the recursion above),
      # which will try a different solution instead.
      return


Note:

  * The program is not ideal. It makes sense to find the cell with the 
least amount of possible numbers you could fill in, i.e. the most 
restricted cell. This is called "pruning" and should be explained in any 
good book, too.

  * The style is a bit confusing. Instead of the excluded numbers, use a 
set with the possible numbers (starting with 1-9) and then remove those 
that are excluded. Then, iterate over the remaining elements with "for m 
in possible_numbers". This double negation and also using exit() in the 
middle isn't really nice.


Good luck!

Uli

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

#42075

On Wednesday, March 27, 2013 6:28:01 PM UTC+10:30, Ulrich Eckhardt wrote:
> Am 27.03.2013 06:44, schrieb Eric Parry:
> 
> > 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.
> 
> 
> 
> 
> 
> In simple terms, it is using a depth-first search and backtracking. If 
> 
> you really want to understand this, get a book on algorithms and graphs 
> 
> (or locate an online source). I can try to give you an idea though.
> 
> 
> 
> 
> 
>  > It seems to go backwards and forwards at random. Can anyone explain
> 
>  > how it works in simple terms?
> 
> 
> 
> I think your interpretation of what it does is wrong or at least flawed. 
> 
> It does try different combinations, but some don't lead to a solution. 
> 
> In that case, it goes back to a previous solution and tries the next one.
> 
> 
> 
> 
> 
> I'll try to document the program to make it easier to understand...
> 
> 
> 
> > 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):
> 
>       # find an empty cell
> 
>       # If no empty cells are found, we have a solution that we print
> 
>       # and then terminate.
> 
> >    i = a.find('0')
> 
> >    if i == -1:
> 
> >      print a
> 
> >      exit(a)
> 
> 
> 
>       # find excluded numbers
> 
>       # Some numbers are blocked because they are already used in
> 
>       # the current column, row or block. This means they can't
> 
>       # possibly be used for the current empty cell.
> 
> >    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])
> 
> 
> 
>       # create possible solutions
> 
>       # Try all possibly numbers for the current empty cell in turn.
> 
>       # With the resulting modifications to the sodoku, use
> 
>       # recursion to find a full solution.
> 
> >    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:])
> 
> 
> 
>       # no solution found
> 
>       # If we come here, there was no solution for the input data.
> 
>       # We return to the caller (should be the recursion above),
> 
>       # which will try a different solution instead.
> 
>       return
> 
> 
> 
> 
> 
> Note:
> 
> 
> 
>   * The program is not ideal. It makes sense to find the cell with the 
> 
> least amount of possible numbers you could fill in, i.e. the most 
> 
> restricted cell. This is called "pruning" and should be explained in any 
> 
> good book, too.
> 
> 
> 
>   * The style is a bit confusing. Instead of the excluded numbers, use a 
> 
> set with the possible numbers (starting with 1-9) and then remove those 
> 
> that are excluded. Then, iterate over the remaining elements with "for m 
> 
> in possible_numbers". This double negation and also using exit() in the 
> 
> middle isn't really nice.
> 
> 
> 
> 
> 
> Good luck!
> 
> 
> 
> Uli

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.
Eric.

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

#42095

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

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

#42198

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]

#42203

On 03/28/2013 06:11 PM, Eric Parry wrote:
> On Thursday, March 28, 2013 3:06:02 PM UTC+10:30, Dave Angel wrote:


    <SNIP>
>>
>>
>> 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.
>>
       <SNIP>
>
> 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.
>

Recursion is not limited to Python.  It's a general programming term, 
and indeed applies in other situations as well.  Suppose you wanted to 
explain what the -r switch meant in the cp command.  "r" stands for 
recursion.

(example is from Linux.  But if you're more familiar with Windows, it's 
the /s switch in the DIR command.)

The cp command copies all the matching files in one directory to another 
one.  If the -r switch is specified, it then does the same thing to each 
subdirectory.

Notice we did NOT have to specify sub-subdirectories, since they're 
recursively implied by the first description.


Closer to the current problem, suppose you defined factorial in the 
following way:  factorial(0) is 1, by definition.  And for all n>0, 
factorial(n) is n*factorial(n-1).

So to directly translate this definition to code, you write a function 
factorial() which takes an integer and returns an integer.  If the 
parameter is zero, return one.  If the parameter is bigger than zero, 
then the function calls itself with a smaller integer, building up the 
answer as needed  (untested).

def  factorial(n):
     if n==0:
         return 1
     val = n *factorial(n-1)
     return val




-- 
DaveA

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

#42223

On Friday, March 29, 2013 9:58:27 AM UTC+10:30, Dave Angel wrote:
> On 03/28/2013 06:11 PM, Eric Parry wrote:
> 
> > On Thursday, March 28, 2013 3:06:02 PM UTC+10:30, Dave Angel wrote:
> 
> 
> 
> 
> 
>     <SNIP>
> 
> >>
> 
> >>
> 
> >> 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.
> 
> >>
> 
>        <SNIP>
> 
> >
> 
> > 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.
> 
> >
> 
> 
> 
> Recursion is not limited to Python.  It's a general programming term, 
> 
> and indeed applies in other situations as well.  Suppose you wanted to 
> 
> explain what the -r switch meant in the cp command.  "r" stands for 
> 
> recursion.
> 
> 
> 
> (example is from Linux.  But if you're more familiar with Windows, it's 
> 
> the /s switch in the DIR command.)
> 
> 
> 
> The cp command copies all the matching files in one directory to another 
> 
> one.  If the -r switch is specified, it then does the same thing to each 
> 
> subdirectory.
> 
> 
> 
> Notice we did NOT have to specify sub-subdirectories, since they're 
> 
> recursively implied by the first description.
> 
> 
> 
> 
> 
> Closer to the current problem, suppose you defined factorial in the 
> 
> following way:  factorial(0) is 1, by definition.  And for all n>0, 
> 
> factorial(n) is n*factorial(n-1).
> 
> 
> 
> So to directly translate this definition to code, you write a function 
> 
> factorial() which takes an integer and returns an integer.  If the 
> 
> parameter is zero, return one.  If the parameter is bigger than zero, 
> 
> then the function calls itself with a smaller integer, building up the 
> 
> answer as needed  (untested).
> 
> 
> 
> def  factorial(n):
> 
>      if n==0:
> 
>          return 1
> 
>      val = n *factorial(n-1)
> 
>      return val
> 
> 
> 
> 
> 
> 
> 
> 
> 
> -- 
> 
> DaveA

Thank you for that Dave, I've started writing the VBA code.
Eric.

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

#42225

On Friday, March 29, 2013 9:58:27 AM UTC+10:30, Dave Angel wrote:
> On 03/28/2013 06:11 PM, Eric Parry wrote:
> 
> > On Thursday, March 28, 2013 3:06:02 PM UTC+10:30, Dave Angel wrote:
> 
> 
> 
> 
> 
>     <SNIP>
> 
> >>
> 
> >>
> 
> >> 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.
> 
> >>
> 
>        <SNIP>
> 
> >
> 
> > 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.
> 
> >
> 
> 
> 
> Recursion is not limited to Python.  It's a general programming term, 
> 
> and indeed applies in other situations as well.  Suppose you wanted to 
> 
> explain what the -r switch meant in the cp command.  "r" stands for 
> 
> recursion.
> 
> 
> 
> (example is from Linux.  But if you're more familiar with Windows, it's 
> 
> the /s switch in the DIR command.)
> 
> 
> 
> The cp command copies all the matching files in one directory to another 
> 
> one.  If the -r switch is specified, it then does the same thing to each 
> 
> subdirectory.
> 
> 
> 
> Notice we did NOT have to specify sub-subdirectories, since they're 
> 
> recursively implied by the first description.
> 
> 
> 
> 
> 
> Closer to the current problem, suppose you defined factorial in the 
> 
> following way:  factorial(0) is 1, by definition.  And for all n>0, 
> 
> factorial(n) is n*factorial(n-1).
> 
> 
> 
> So to directly translate this definition to code, you write a function 
> 
> factorial() which takes an integer and returns an integer.  If the 
> 
> parameter is zero, return one.  If the parameter is bigger than zero, 
> 
> then the function calls itself with a smaller integer, building up the 
> 
> answer as needed  (untested).
> 
> 
> 
> def  factorial(n):
> 
>      if n==0:
> 
>          return 1
> 
>      val = n *factorial(n-1)
> 
>      return val
> 
> 
> 
> 
> 
> 
> 
> 
> 
> -- 
> 
> DaveA

Thank you for that Dave, I've started writing the VBA code.
Eric.

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

#42235

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

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

#42283

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]

#42286

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

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

#42351

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]

#42353

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

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

#42423

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.

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

#42432

On 03/31/2013 06:03 PM, Eric Parry wrote:
>
>>  <SNIP>
>>
>
> I think in the original it was exit(a). That did not work either.

There you go again.  "Did not work" tells us very little.  With my 
Python 2.7.2, exit(something) with something being a string prints the 
string and then exits.  Nowhere have I seen that documented, and I 
thought it either took an int or nothing.

So please be much more specific.  Did it give some exception, or did it 
not print the right result (I don't see any print statement in the 
code), or what?


-- 
DaveA

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

#42434

On 31 March 2013 23:34, Dave Angel <davea@davea.name> wrote:
>[...]  With my Python
> 2.7.2, exit(something) with something being a string prints the string and
> then exits.  Nowhere have I seen that documented, and I thought it either
> took an int or nothing.

It is documented, just not exactly where you'd expect it (exit is a
constant, not a function):

    http://docs.python.org/2/library/constants.html#constants-added-by-the-site-module

As for the behaviour when you pass a string, it's documented here:

    http://docs.python.org/2/library/exceptions.html#exceptions.SystemExit

-- 
Arnaud

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

#42426

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.

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

#42427

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]

#42433

On Mon, Apr 1, 2013 at 9:27 AM, Eric Parry <joan4eric@gmail.com> wrote:
> [ chomp 128 lines of quoted text ]
>
> 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.

You have just spammed us with, and I counted them, one hundred and
twenty-eight lines of quoted text. And you posted to both
comp.lang.python and python-list, so some of us will have seen those
lines twice. Please don't do this. If you MUST use Google Groups,
check out this page, and try to adjust your posts to be more
courteous.

http://wiki.python.org/moin/GoogleGroupsPython

Thanks!

ChrisA

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

#42438

Sorry.
Won't happen again.
signing off this topic.
Eric.

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

Page 1 of 2  [1] 2  Next page →

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

csiph-web