I need explanation in this Sudoku python code

Question

I tried this Sudoku solver written in Python https://freepythontips.wordpress.com/2013/09/01/sudoku-solver-in-python/ The code works fine. This is the full code:

import sys

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:
    sys.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:
        r(a[:i]+m+a[i+1:])

r('100070030830600000002900608600004907090000050307500004203009100000002043040080009')

I dont understand this loop:

for m in '123456789':
        if m not in excluded_numbers:
            r(a[:i]+m+a[i+1:])

Please someone explain the algorithm of this code. Thanks

Edit: I was asking about logic of that loop and now I understand the logic and I checked Peter Novig's Sudoku solver.

It's a _recursive_ algorithm. I think a good answer needs to explain that. — RemcoGerlich, Oct 26 '14 at 07:05

score 2 · Accepted Answer · edited May 23 '17 at 11:49

At the beginning of the code, you set i to the index of the first field that is still not yet filled. Next, you make excluded_numbers the set of all the numbers that are not allowed on this position, since they are already present in the same row, column or block as i.

In the for you loop you ask about, you loop over all the possible numbers, guessing that position i has the number m. You first check if m is not one of the forbidden numbers, and if not, recursively call the function r again with the empty spot replaced by the guess m. This is done by concatenating all the fields up to position i (a[:i]), the guess m, and all the fields after position i (a[i+1:]). Getting the parts before and after the position i is done by slicing into the long string that represents the whole board.

The function r() as a whole works by finding the first unfilled position, fill it with a valid number and then recursively calling itself again. If at some point, there are no more numbers to fill at a certain position (since you made the wrong guess), the function simply exits. When the function finally finds a complete solution (no 0 left), it prints the solution and exits. Note that this is not a very efficient way of solving a Sudoku. A much better algorithm is explained by Peter Norvig, who is head of Google research.

"excluded_numbers is a set of all the numbers that this are not allowed on this position" - not true. "excluded_numbers" are all the excluded throughout the board. — Nir Alfasi, Oct 26 '14 at 06:57
I edited the sentence for clarity, but I still think it is true. — Bas Swinckels, Oct 26 '14 at 07:05
excluded_numbers is all the numbers that are already on the board, in the same row, column or block. So all the numbers that are excluded for location 'i'. — RemcoGerlich, Oct 26 '14 at 07:05

Nir Alfasi · Answer 2 · 2014-10-26T07:15:55.863

def r(a):
  i = a.find('0')  #  find the next "missing" item
  if i == -1:  # if there is none, we have a winner - print it on exit
    sys.exit(a)

  excluded_numbers = set()  #  build a set of excluded numbers, the range is [0,9] (though '0' is not meaningful)
  for j in range(81):  #  we have 9 mini 3X3 boards which combined to one sudoku board
    if same_row(i,j) or same_col(i,j) or same_block(i,j):  #  if i and j are on the same row/column/block - we'll exclude the item on a[j] because i cannot contain the same number - according to sudoku rules
        excluded_numbers.add(a[j])

for m in '123456789':  #  for each one of the candidates m in [1,2,3,...9] (though it's being read as a string)
    if m not in excluded_numbers:  #  if m was not excluded in the previous step 
        r(a[:i]+m+a[i+1:])  #  replace the i-th item with m and continue (recursively)

on the last line we have a recursive call that tries to "guess" the solution using each one of the ms that were not excluded. Assuming that the board has at least one solution - at least one of the calls should reach the condition if i == -1 and the first recursive branch that will get there will print itself and exit (ignoring other possible solutions that "come later" as one of the leafs on the tree of all the other possibilities).

I need explanation in this Sudoku python code

2 Answers2