CODEWITHSUNDEEP
pythonpython-3.xrecursionreturn
1TACHI
1TACHI

Reputation: 3

How to stop Recursion and return answer?

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

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

  2. 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:)

Upvotes: 0

Views: 120

Answers (2)

furas
furas

Reputation: 142794

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]))

Upvotes: 0

wjandrea
wjandrea

Reputation: 33107

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):

Upvotes: 1

Related Questions