Python Sudoku Solver goes into an infinite loop, How could I limit the amount of loops within the function?

Question

I have the following code that enters an infinite loop as the puzzle has many solutions.

However, I am struggling to understand how I could limit the amount of solutions printed out without affecting how the function iterates.

I tried using a while loop inside the solve() function but that didn't work.

import numpy as np

# Add the puzzle you want to solve here:
grid = [[0, 0, 0, 3, 0, 4],
        [0, 0, 0, 0, 6, 5],
        [0, 2, 0, 0, 0, 1],
        [3, 0, 0, 0, 4, 0],
        [2, 4, 0, 0, 0, 0],
        [6, 0, 5, 0, 0, 0]
        ]


def possible(y, x, n):
    global grid
    for i in range(0, 6):
        if grid[y][i] == n:
            return False

    for i in range(0, 6):
        if grid[i][x] == n:
            return False

    x0 = (x//3)*3
    y0 = (y//3)*3

    for i in range(0, 3):
        for j in range(0, 3):
            if grid[y0+i][x0+j] == n:
                return False

    return True


print(np.matrix(grid))


def solve():
    global grid
    for y in range(6):
        for x in range(6):
            if grid[y][x] == 0:
                for n in range(1, 10):
                    if possible(y, x, n):
                        grid[y][x] = n
                        solve()
                        grid[y][x] = 0
                return
    print(np.matrix(grid))

`for n in range(1, 10)` does not seem to fit with a 6x6 puzzle. Maybe you want `range(1, 7)` here. — BeS, Oct 17 '20 at 12:45
Does your solution need to be recursive or can it also be iterative? — flabons, Oct 17 '20 at 13:11
I think I have misunderstood the problem, the algorithm was first written to solve a 9x9 sudoku and not 6x6. I might have to rewrite it. But I do have a question... but im struggling to understand the function of `x0` and `y0` — Gillytron, Oct 17 '20 at 21:32

MoeNeuron · Answer 1 · 2020-10-17T13:12:51.850

I will try here to help with reasoning for a possible approach.

I can't say much about the correctness of possible() (which is very important that it works correctly otherwise it could be a never terminating algorithm). On the other hand, it seems to me while assuming possible() is correct that the algorithm has an upper bound (thanks to the loops with range()) and since a given sudoku (even with no clues) has always a finite solution set, then your algorithm should always terminate. So, better you have expectation of time complexity you are OK with for certain input sets.

A possible way is to limit your recursion depth (see more here) or pass a parameter to i.e. solve(limit=1000) that you decrement every time you go deeper in recursion and combine it with a boolean condition, say, a (partial) solution(s) found or so (in the general sense of such a problem, solution verification is the easiest part).

score 0 · Answer 2 · answered Oct 17 '20 at 12:51

Each time you call solve() it will start from the very first box i,j = 0,0. So, if your possible function returns False for some coordinates, you never change the value to be different from 0 and will be stuck at that particular box forever.

If, you would like to still implement a recursive function, you will at least need to pass the coordinates i and j as parameters.

Python Sudoku Solver goes into an infinite loop, How could I limit the amount of loops within the function?

2 Answers2