4
\$\begingroup\$

I have recently gotten back into writing python and i decided to take up a project of writing a backtracking algorithm in python to solve Sudoku puzzles

How it Works

A matrix is declared to represent the Sudoku grid the blank spaces on the Sudoku grid are represented by zero A function is declared that checks for all the zeros in the grid, another function is the declared to check the answers are valid by checking against a variable declared as Row_Values it also checks against a variable declared as column_values then another function is declared which calls the first function to locate where it can make guesses it returns none if all the spaces are filled, it inputs a number between 1 and 9 in a valid place and then checks it doesn't conflict it then uses recursion to call the function it repeatedly checks if anything is invalid if it becomes invalid it uses backtracking to try new number(s) it returns false if the puzzle is invalid

Code

import numpy as np
import time

start_time = time.time()

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

print (np.matrix(grid))

def find_empty_box(sudoku): 
    for x in range(9):
        for y in range(9):
            if sudoku[x][y] == 0:
                return x, y 
    
    return None, None

def Answer_Valid(sudoku, guess, row, col): 
    row_values = sudoku[row]    
    if guess in row_values:
        return False

    column_values = [sudoku[i][col]for i in range(9)]
    if guess in column_values:
        return False

    row_start = (row // 3) * 3
    col_start = (col // 3) * 3 

    for x in range(row_start, row_start + 3):
        for y in range(col_start, col_start + 3):
            if sudoku[x][y] == guess:
                return False

        return True

def Solver(sudoku):
    row, col = find_empty_box(sudoku)

    if row is None:
        return True

    for guess in range(1,10):
        if Answer_Valid(sudoku, guess, row, col):
            sudoku[row][col] = guess

            if Solver(sudoku):
                return True

        sudoku[row][col] = 0

    return False

print(Solver(grid))

print(np.matrix(grid))

print("%s seconds " % (time.time() - start_time))
New contributor
HiddenSquid123 is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
\$\endgroup\$

Your Answer

HiddenSquid123 is a new contributor. Be nice, and check out our Code of Conduct.

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.