backtracking.sudoku

Given a partially filled 9x9 2D array, the objective is to fill a 9x9 square grid with digits numbered 1 to 9, so that every row, column, and and each of the nine 3x3 sub-grids contains all of the digits.

This can be solved using Backtracking and is similar to n-queens. We check to see if a cell is safe or not and recursively call the function on the next column to see if it returns True. if yes, we have solved the puzzle. else, we backtrack and place another number in that cell and repeat this process.

Attributes

Matrix

initial_grid

no_solution

solution

Functions

find_empty_location(→ tuple[int, int] | None)

This function finds an empty location so that we can assign a number

is_safe(→ bool)

This function checks the grid to see if each row,

print_solution(→ None)

A function to print the solution in the form

sudoku(→ Matrix | None)

Takes a partially filled-in grid and attempts to assign values to

Module Contents

backtracking.sudoku.find_empty_location(grid: Matrix) → tuple[int, int] | None

This function finds an empty location so that we can assign a number for that particular row and column.

backtracking.sudoku.is_safe(grid: Matrix, row: int, column: int, n: int) → bool

This function checks the grid to see if each row, column, and the 3x3 subgrids contain the digit ‘n’. It returns False if it is not ‘safe’ (a duplicate digit is found) else returns True if it is ‘safe’

backtracking.sudoku.print_solution(grid: Matrix) → None

A function to print the solution in the form of a 9x9 grid

backtracking.sudoku.sudoku(grid: Matrix) → Matrix | None

Takes a partially filled-in grid and attempts to assign values to all unassigned locations in such a way to meet the requirements for Sudoku solution (non-duplication across rows, columns, and boxes)

>>> sudoku(initial_grid)  
[[3, 1, 6, 5, 7, 8, 4, 9, 2],
 [5, 2, 9, 1, 3, 4, 7, 6, 8],
 [4, 8, 7, 6, 2, 9, 5, 3, 1],
 [2, 6, 3, 4, 1, 5, 9, 8, 7],
 [9, 7, 4, 8, 6, 3, 1, 2, 5],
 [8, 5, 1, 7, 9, 2, 6, 4, 3],
 [1, 3, 8, 9, 4, 7, 2, 5, 6],
 [6, 9, 2, 3, 5, 1, 8, 7, 4],
 [7, 4, 5, 2, 8, 6, 3, 1, 9]]
 >>> sudoku(no_solution) is None
 True
backtracking.sudoku.Matrix
backtracking.sudoku.initial_grid: Matrix = [[3, 0, 6, 5, 0, 8, 4, 0, 0], [5, 2, 0, 0, 0, 0, 0, 0, 0], [0, 8, 7, 0, 0, 0, 0, 3, 1], [0, 0,...
backtracking.sudoku.no_solution: Matrix = [[5, 0, 6, 5, 0, 8, 4, 0, 3], [5, 2, 0, 0, 0, 0, 0, 0, 2], [1, 8, 7, 0, 0, 0, 0, 3, 1], [0, 0,...
backtracking.sudoku.solution = [[3, 0, 6, 5, 0, 8, 4, 0, 0], [5, 2, 0, 0, 0, 0, 0, 0, 0], [0, 8, 7, 0, 0, 0, 0, 3, 1], [0, 0,...