Sudoku

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

 

[Ulrich Eckhardt]

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

 

[Damien Wyart]

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

 

[Dave Angel]

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.
 

 

[Eric Parry]

Thank you all for your help and suggestions.

Eric

 

[Eric Parry]

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 aparticular 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 forexcel which would enable any puzzle to be entered directly.
Your comments are a big help especially the double negative aspect.
Eric.

 

[Dave Angel]

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

 

[Eric Parry]

<SNIP the double-spaced garbage that GoogleGroups put in - see

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









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.

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.

 

[Eric Parry]

<SNIP the double-spaced garbage that GoogleGroups put in - see

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









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.

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.

 

[Chris Angelico]

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

 

[Dave Angel]

On Thursday, March 28, 2013 3:06:02 PM UTC+10:30, Dave Angel 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.
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

 

[Eric Parry]

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

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

 

[Eric Parry]

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

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

 

[Eric Parry]

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

 

[Eric Parry]

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

 

[Dave Angel]

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.

 

[Eric Parry]

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.

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

 

[Eric Parry]

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.

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

 

[Dave Angel]

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.

 

[Eric Parry]

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.






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.

I think in the original it was exit(a). That did not work either.
I'll try the others.
Eric.