kying18 / sudoku Goto Github PK

(Pdb) c
guess: 9
row: 0 , col: 8
> /Dev/sandbox/python_sudoku_solver/sudoku.py(77)solve_sudoku()
-> puzzle[row][col] = -1 # reset the guess
(Pdb) c
> /Dev/sandbox/python_sudoku_solver/sudoku.py(76)solve_sudoku()
-> breakpoint()
(Pdb) c
guess: 3
row: 0 , col: 7
> /Dev/sandbox/python_sudoku_solver/sudoku.py(77)solve_sudoku()
-> puzzle[row][col] = -1 # reset the guess

from pprint import pprint
def find_next_empty(puzzle):
    #finds next row, col on the puzzle that is not filled yet -->rep with -1
    for r in range (9):
        for c in range(9):
            if puzzle[r][c]==-1:
                return r, c
            else:
                continue
    return None, None

def is_valid(puzzle, guess, row, col):
    #Checks if the guess is valid by checking row, column and matrix.
    for r in range(9):#Check if there is the number guess already in the row (col is static)
        if puzzle[r][col]==guess:
            return False
    for c in range(9):#Check if there is the number guess already in the col (row is static)
        if puzzle[row][c]==guess:
            return False
        
    #I have also to check the 3x3 matrix for the same number
    #I can check row and col and use their index to determine the representative 3x3 Matrix
    #Representing them with CAPS
    ROW=None
    COL=None
    try:#This could be simplified, but I find it easier to read it in several if statements
        #Generates ROW
        if row in range(3):
            ROW=0
        elif row in range(3,6):
            ROW=1
        elif row in range(6,9):
            ROW=2
        else:
            print(f"{row} is not a valid input for row")
            raise ValueError
        
        #Generates COL
        if col in range(3):
            COL=0
        elif col in range(3,6):
            COL=1
        elif col in range(6,9):
            COL=2
        else:
            print(f"{col} is not a valid input for col")
            raise ValueError
    except ValueError:
        return False
    #I still have to check the matrix, but now I know which one I have to check
    #Generate the Matrix as a list and use a second variable to see if there is the guess
    #Making it a list because I do not need to know if it is lower, higer or left or right
    Mat=[]
    for r in range(3):
        for c in range(3):
            Mat.append(puzzle[ROW+r][COL+c])
    if guess in Mat:
        return False
        
        
    return True


def solve_sudoku(puzzle, i):
    #solve sudoku using backtracking!
    #puzzle is a list of lists, where each inner list represents a row in our puzzle
    #return whether a solution exists
    #mutates puzzle to be the solution (if solution exists)
    print(i)
    i+=1
    #step 1: choose somewhere on the puzzle to make a guess
    #Because we essentially brute force the puzzle, we can choose the first free entry in puzzle and start with 1
    row, col = find_next_empty(puzzle)
    #Step 1.1: if there is nowhere left, then we are done because we only allowed valid inputs
    if row is None:
        pprint(puzzle)#Printing the found solution
        return True
    #Step 2: if there is a place to put a number, then make a guess between 1 and 9
    for guess in range(1,10):
    #Step 3: Check if guess is valid
        if is_valid(puzzle, guess, row, col):
            puzzle[row][col]=guess
        #Now we have a modified puzzle which we will iterate
        #Step 4: Iterate
        if solve_sudoku(puzzle, i):
            return True
        #Step 5. Turns out that the guess was shit. So we count up and start again till we have no numbers left
        else:
            puzzle[row][col]=-1#reset the guess (should not be necessary, but just in case)
            continue
    
    #Step 6: If we have tried every combination and did not solve puzzle, then this solver was not able to solve it and will return false.
    #We can assume that this puzzle is not solveable
    return False                
            
if __name__=='__main__':
    import sys
    import threading
    print(sys.getrecursionlimit())
    i =1
    sys.setrecursionlimit(50000)
    threading.stack_size(10**8)
    example_board = [
        [3, 9, -1,   -1, 5, -1,   -1, -1, -1],
        [-1, -1, -1,   2, -1, -1,   -1, -1, 5],
        [-1, -1, -1,   7, 1, 9,   -1, 8, -1],

        [-1, 5, -1,   -1, 6, 8,   -1, -1, -1],
        [2, -1, 6,   -1, -1, 3,   -1, -1, -1],
        [-1, -1, -1,   -1, -1, -1,   -1, -1, 4],

        [5, -1, -1,   -1, -1, -1,   -1, -1, -1],
        [6, 7, -1,   1, -1, 5,   -1, 4, -1],
        [1, -1, 9,   -1, -1, -1,   2, -1, -1]
    ] 
    pprint(example_board)
    print(solve_sudoku(example_board, i))