Given a partially filled 9×9 2D array, the goal is to assign digits (from 1 to 9) to the empty cells so that every row, column, and subgrid of size 3×3 contains exactly one instance of the digits from 1 to 9 (https://www.geeksforgeeks.org/backtracking-set-7-suduku/)

Backtracking : Sudoku Solver.py

#!/usr/bin/env python3


"""
Sudoku Solver

guesses:
	1-9

grid:
	3x3 3x3 3x3
	3x3 3x3 3x3
	3x3 3x3 3x3

default grid:
   [[0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0]]

outputs:
	easy:
		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

	difficult:
		2 3 7 6 5 8 9 1 4
		4 6 9 1 7 3 2 8 5
		8 5 1 9 2 4 3 6 7
		1 2 3 5 6 7 8 4 9
		7 8 4 2 3 9 1 5 6
		6 9 5 4 8 1 7 3 2
		5 1 6 8 9 2 4 7 3
		3 4 2 7 1 5 6 9 8
		9 7 8 3 4 6 5 2 1
"""


def is_guess_possible_in_box(guess, row, col, board):
	# top-left point of each 3x3 box
	x_base = col // 3 * 3
	y_base = row // 3 * 3

	# check with each element in 3x3 grid
	for y in range(3):
		for x in range(3):
			if board[y_base + y][x_base + x] == guess:
				return False

	return True


def is_guess_possible_in_row(guess, row, col, board):
	for x in range(9):
		if board[row][x] == guess:
			return False

	return True


def is_guess_possible_in_col(guess, row, col, board):
	for y in range(9):
		if board[y][col] == guess:
			return False

	return True


def is_safe(guess, row, col, board):
	if is_guess_possible_in_box(guess, row, col, board) and is_guess_possible_in_row(guess, row, col, board) and is_guess_possible_in_col(guess, row, col, board):
		return True
	else:
		return False


def solve_sudoku(board):
	for y in range(9):
		for x in range(9):
			if board[y][x] == 0:
				for num in range(1, 10):
					if is_safe(num, y, x, board):
						board[y][x] = num
						if solve_sudoku(board):
							return True
						board[y][x] = 0
				return False
	return True


def main():
	# easy
	grid = [[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, 3, 0, 1, 0, 0, 8, 0],
	        [9, 0, 0, 8, 6, 3, 0, 0, 5],
	        [0, 5, 0, 0, 9, 0, 6, 0, 0],
	        [1, 3, 0, 0, 0, 0, 2, 5, 0],
	        [0, 0, 0, 0, 0, 0, 0, 7, 4],
	        [0, 0, 5, 2, 0, 6, 3, 0, 0]]

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

	solve_sudoku(grid)

	for row in grid:
		print(*row)


if __name__ == '__main__':
	main()