Recursion issue in sudoku solver-CodePudding

I'm getting an error that I've exceeded the maximum number of errors in the method recuSolve. I'm using recursion to find the correct value for each sudoku box 1 by 1. ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎

import numpy as np

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

def printBoard(board): #prints the board
    horLine = '-'*22
    board_str = board.astype(str)
    for num in range(9):
        if num%3==0 and num!=0:
            print(horLine)
        row=board_str[num]
        print(' '.join(row[0:3]) ' | ' ' '.join(row[3:6]) ' | ' ' '.join(row[6:]))

def nextSpace(board): # returns the next open space
    for r in range(9):
        for c in range(9):
            if board[r][c] == 0:
                return (r,c)
    return -1

def check(board,row,col,num): #checks if a value(num) works as a solution to an open spot
    for x in range(9):
        if board[row][x]==num and x!=row:
            return False
        if board[x][col]==num and x!=col:
            return False
    ro=row//3*3
    co=col//3*3
    for r in range(ro,ro 3):
        for c in range(co,co 3):
            if board[r][c]==num and (row,col)!=(r,c):
                return False
    return True

def recuSolve(board): # this is where I think I'm messing up
    space = nextSpace(board)
    if space == -1:
        printBoard(board)
        return True
    row, col = space
    for x in range(9):
        if check(board, row, col, x 1):
            board[row][col]=x 1
    return recuSolve(board)


recuSolve(grid)

CodePudding user response：

For completeness, I removed the import of numpy, which you weren't using, and made these few changes:

def printBoard(board): #prints the board
    horLine = '-'*22
    for num in range(9):
        if num%3==0 and num!=0:
            print(horLine)
        row = list(map(str, board[num]))
        print(' '.join(row[0:3]) ' | ' ' '.join(row[3:6]) ' | ' ' '.join(row[6:]))

and

def recuSolve(board):
    space = nextSpace(board)
    if space == -1:
        printBoard(board)
        return True
    row, col = space
    for x in range(9):
        if check(board, row, col, x 1):
            board[row][col]=x 1
            if recuSolve(board):
                return True
    board[row][col] = 0
    return False

recuSolve(grid)

CodePudding user response：

Apart from the changes that Tim mentioned above, there was a bug (unnecessary row, column confusion) in check() method, that caused wrong answers.
Fixing that as well, below is the complete program.

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

def printBoard(board): #prints the board
    horLine = '-'*22
    for num in range(9):
        if num%3==0 and num!=0:
            print(horLine)
        row = list(map(str, board[num]))
        print(' '.join(row[0:3]) ' | ' ' '.join(row[3:6]) ' | ' ' '.join(row[6:]))


def nextSpace(board): # returns the next open space
    for r in range(9):
        for c in range(9):
            if board[r][c] == 0:
                return (r,c)
    return -1

def check(board,row,col,num): #checks if a value(num) works as a solution to an open spot
    for x in range(9):
        if board[row][x]==num:
            return False
        if board[x][col]==num:
            return False
    ro=row//3*3
    co=col//3*3
    for r in range(ro,ro 3):
        for c in range(co,co 3):
            if board[r][c]==num and (row,col)!=(r,c):
                return False
    return True

def recuSolve(board): # this is where I think I'm messing up
    space = nextSpace(board)
    if space == -1:
        printBoard(board)
        return True
    row, col = space
    for x in range(9):
        if check(board, row, col, x 1):
            board[row][col]=x 1
            if recuSolve(board):
                return True
    board[row][col]=0
    return False


recuSolve(grid)

Output:

2 5 8 | 7 3 6 | 9 4 1
6 1 9 | 8 2 4 | 3 5 7
4 3 7 | 9 1 5 | 2 6 8
----------------------
3 9 5 | 2 7 1 | 4 8 6
7 6 2 | 4 9 8 | 1 3 5
8 4 1 | 6 5 3 | 7 2 9
----------------------
1 8 4 | 3 6 9 | 5 7 2
5 7 6 | 1 4 2 | 8 9 3
9 2 3 | 5 8 7 | 6 1 4