Skip to content
Advertisement

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

Advertisement

Answer

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]))
User contributions licensed under: CC BY-SA
6 People found this is helpful
Advertisement