How to stop Recursion and return answer?

Question

This is a sudoku solver function and I have 2 questions:

import numpy as np

def possible(y, x, n):
    global sudoku
    for i in range(9):
        if sudoku[y][i] == n:
            return False
    for i in range(9):
        if sudoku[i][x] == n:
            return False
    x0 = (x // 3) * 3
    y0 = (y // 3) * 3
    for i in range(3):
        for j in range(3):
            if sudoku[y0 + i][x0 + j] == n:
                return False
    return True


def solve():
    global sudoku
    for y in range(9):
        for x in range(9):
            if sudoku[y][x] == 0:
                for n in range(1, 10):
                    if possible(y, x, n):
                        sudoku[y][x] = n
                        solve()
                        sudoku[y][x] = 0
                return
    print("solution:\n", np.matrix(sudoku))
    return sudoku # (This is what I have trid)


sudoku = [[0, 0, 0, 0, 7, 0, 0, 0, 0],
          [0, 0, 6, 0, 0, 0, 7, 0, 0],
          [2, 0, 0, 8, 0, 3, 0, 0, 5],
          [0, 0, 8, 0, 0, 0, 5, 0, 0],
          [0, 2, 0, 4, 0, 9, 0, 3, 0],
          [9, 0, 0, 6, 0, 7, 0, 0, 2],
          [5, 0, 9, 0, 0, 0, 3, 0, 8],
          [0, 0, 3, 0, 0, 0, 9, 0, 0],
          [0, 7, 0, 9, 0, 4, 6, 5, 0]]
solve()
print("solution:\n", np.matrix(sudoku))

Why 2nd print print the original sudoku?

 # This is the 1st print:
 solution:
  [[3 5 4 1 7 6 2 8 9]
  [1 8 6 2 9 5 7 4 3]
  [2 9 7 8 4 3 1 6 5]
  [4 6 8 3 1 2 5 9 7]
  [7 2 1 4 5 9 8 3 6]
  [9 3 5 6 8 7 4 1 2]
  [5 4 9 7 6 1 3 2 8]
  [6 1 3 5 2 8 9 7 4]
  [8 7 2 9 3 4 6 5 1]]

 # This is the 2nd print:
 solution:
  [[0 0 0 0 7 0 0 0 0]
  [0 0 6 0 0 0 7 0 0]
  [2 0 0 8 0 3 0 0 5]
  [0 0 8 0 0 0 5 0 0]
  [0 2 0 4 0 9 0 3 0]
  [9 0 0 6 0 7 0 0 2]
  [5 0 9 0 0 0 3 0 8]
  [0 0 3 0 0 0 9 0 0]
  [0 7 0 9 0 4 6 5 0]]

How can I get the sudoku solution (not print it), because I want to reuse the solution. (I have tried using return sudoku but get None)

Thanks:)

What if there are multiple solutions? Do you only want the first one? — wjandrea, Apr 27 '21 at 02:05
you should use `return result` inside `solve()` to send it back to previous level - and `result = solve()` to get it in previous level and use this `result` to create new result which you will send to another previous level.. — furas, Apr 27 '21 at 02:09
you get original sudoku because inside `solve` you use `sudoku[y][x] = 0` to set it back to original value. You put values in place of `0` and later you put back `0` but you never check if you already filled all places and if they are correctly filled - so you never check if you resolved sudoku. And when you will check if you resolve sudoku then you should display solution or keep it in separated matrix (or list of all correct matrixes) — furas, Apr 27 '21 at 02:14
@wjandrea I update my output. Multiple solutions are also fine.( if I can reuse the solotions) Thanks — 1TACHI, Apr 27 '21 at 02:19
if you want (multi) solutions then you should create `deep copy` of solution in `sudoku` and put it on list with all solutions - `import copy ; solutions.append(copy.deepcopy(sudoku))`. Because code will still run and search other solutions and it will use table `sudoku` for this - so it will replace values in `sudoku`. — furas, Apr 27 '21 at 02:22
@1TACHI I ask because handling multiple solutions actually makes it more difficult. If you're not expecting to handle puzzles that have multiple solutions, then it's easier to not bother. — wjandrea, Apr 27 '21 at 02:24
@furas Thanks. I understand why I get original sudoku. But I tried 'return result' and 'result = solve()' still get "NoneType",can you please tell me where to change the code? — 1TACHI, Apr 27 '21 at 02:41
@wjandrea thanks. just 1st solution is OK. So how to get the 1st solution and quit the recursion. — 1TACHI, Apr 27 '21 at 02:45
`return` goes back only one level - and it goes to line before `sudoku[y][x] = 0` which removes value from `sudoku` - and `return sudoku` doesn't duplicate `sudoku` but it sends access to `sudoku` which is used in `sudoku[y][x] = 0` and you should use `deepcopy` to duplicate it and keep solution. — furas, Apr 27 '21 at 02:46

score 1 · Answer 1 · answered Apr 27 '21 at 03:02

The problem is that the recursion keeps going, which resets the puzzle due to the line sudoku[y][x] = 0.

To stop the recursion on the first solution, you need some sort of flag to indicate that the puzzle is solved. One way to do that is by returning True if so.

def solve():
    ...
    return True  # All cells are filled, so it's solved

Then you need to catch that from the recursive call and return there as well:

def solve():
    ...
        if possible(y, x, n):
            sudoku[y][x] = n
            solved = solve()
            if solved:
                return True  # Recursive return on first solution
            sudoku[y][x] = 0
    ...

Then you can remove the print() from inside solve(), and you'll get the right output from the print() outside.

BTW, this problem is similar to Why does my recursive function return None? except that you're mutating a global (sudoku).

Also BTW:

The global declarations are not needed since you never reassign sudoku, just mutate it.

You can remove the dependency on numpy by simply printing each row:

print("solution:")
for row in sudoku:
    print(*row)

solution:
3 5 4 1 7 6 2 8 9
1 8 6 2 9 5 7 4 3
2 9 7 8 4 3 1 6 5
4 6 8 3 1 2 5 9 7
7 2 1 4 5 9 8 3 6
9 3 5 6 8 7 4 1 2
5 4 9 7 6 1 3 2 8
6 1 3 5 2 8 9 7 4
8 7 2 9 3 4 6 5 1

You can collapse two nested-for-loops by using itertools.product, for example:
```
for y, x in product(range(9), repeat=2):
```

furas · Accepted Answer · 2022-08-04T12:21:09.907

Maybe it is not elegant but I use global list all_solutions and append duplicated solution

solution = copy.deepcopy(sudoku)
all_solutions.append(solution)

It works for your example. But I still not sure if your code is correct.

import numpy as np
import copy

def possible(y, x, n):

    for i in range(9):
        if sudoku[y][i] == n:
            return False
            
    for i in range(9):
        if sudoku[i][x] == n:
            return False
            
    x0 = (x // 3) * 3
    y0 = (y // 3) * 3
    
    for i in range(3):
        for j in range(3):
            if sudoku[y0 + i][x0 + j] == n:
                return False
                
    return True


def solve():
    
    for y in range(9):
        for x in range(9):
            if sudoku[y][x] == 0:
                for n in range(1, 10):
                    if possible(y, x, n):
                        sudoku[y][x] = n
                        solve()
                        sudoku[y][x] = 0
                return
                
    print("solution:\n", np.matrix(sudoku))

    solution = copy.deepcopy(sudoku)
    all_solutions.append(solution)

    return


sudoku = [[0, 0, 0, 0, 7, 0, 0, 0, 0],
          [0, 0, 6, 0, 0, 0, 7, 0, 0],
          [2, 0, 0, 8, 0, 3, 0, 0, 5],
          [0, 0, 8, 0, 0, 0, 5, 0, 0],
          [0, 2, 0, 4, 0, 9, 0, 3, 0],
          [9, 0, 0, 6, 0, 7, 0, 0, 2],
          [5, 0, 9, 0, 0, 0, 3, 0, 8],
          [0, 0, 3, 0, 0, 0, 9, 0, 0],
          [0, 7, 0, 9, 0, 4, 6, 5, 0]]

all_solutions = []
solve()
if all_solutions:
    print("solution:\n", np.matrix(all_solutions[0]))

The same using return instead of global variable.

Because solve() returns list of solutions so it has to also return [solution] as a list.

import numpy as np
import copy

def possible(y, x, n):

    for i in range(9):
        if sudoku[y][i] == n:
            return False
            
    for i in range(9):
        if sudoku[i][x] == n:
            return False
            
    x0 = (x // 3) * 3
    y0 = (y // 3) * 3
    
    for i in range(3):
        for j in range(3):
            if sudoku[y0 + i][x0 + j] == n:
                return False
                
    return True


def solve():
    
    all_solutions = []
    
    for y in range(9):
        for x in range(9):
            if sudoku[y][x] == 0:
                for n in range(1, 10):
                    if possible(y, x, n):
                        sudoku[y][x] = n
                        all_solutions += solve()
                        sudoku[y][x] = 0
                return all_solutions
                
    print("solution:\n", np.matrix(sudoku))

    solution = copy.deepcopy(sudoku)

    #return all_solutions + [solution]
    return [solution]


sudoku = [[0, 0, 0, 0, 7, 0, 0, 0, 0],
          [0, 0, 6, 0, 0, 0, 7, 0, 0],
          [2, 0, 0, 8, 0, 3, 0, 0, 5],
          [0, 0, 8, 0, 0, 0, 5, 0, 0],
          [0, 2, 0, 4, 0, 9, 0, 3, 0],
          [9, 0, 0, 6, 0, 7, 0, 0, 2],
          [5, 0, 9, 0, 0, 0, 3, 0, 8],
          [0, 0, 3, 0, 0, 0, 9, 0, 0],
          [0, 7, 0, 9, 0, 4, 6, 5, 0]]

all_solutions = solve()

if all_solutions:
    print("solution:\n", np.matrix(all_solutions[0]))

I added version which use `return` instead of global variable. — furas, Apr 27 '21 at 03:09

How to stop Recursion and return answer?

2 Answers2