Solving sudoku

sudoku_solver.py

import time

class Sudoku:
    def __init__(self, board):
        if not self.is_valid_input(board):
            raise ValueError("Board must be a 9x9 grid of integers from 0 to 9.")
        self.board = board
        self.steps = 0

    def is_valid_input(self, board):
        if len(board) != 9 or any(len(row) != 9 for row in board):
            return False
        return all(all(isinstance(num, int) and 0 <= num <= 9 for num in row) for row in board)

    def is_valid_move(self, row, col, num):
        # Check row, column, and 3x3 square
        for i in range(9):
            if self.board[row][i] == num or self.board[i][col] == num or \
               self.board[row - row % 3 + i // 3][col - col % 3 + i % 3] == num:
                return False
        return True

    def find_least_candidates_cell(self):
        min_candidates = 10
        cell = None
        for i in range(9):
            for j in range(9):
                if self.board[i][j] == 0:
                    candidates = sum(self.is_valid_move(i, j, num) for num in range(1, 10))
                    if candidates < min_candidates:
                        min_candidates = candidates
                        cell = (i, j)
        return cell

    def solve(self):
        self.steps += 1
        cell = self.find_least_candidates_cell()
        if not cell:
            return True

        row, col = cell

        for num in range(1, 10):
            if self.is_valid_move(row, col, num):
                self.board[row][col] = num
                if self.solve():
                    return True
                self.board[row][col] = 0

        return False

    def print_board(self):
        for i, row in enumerate(self.board):
            if i % 3 == 0 and i != 0:
                print("- - - - - - - - - - - -")
            print(" ".join(str(num) if num != 0 else '.' for num in row[:3]) + " | " +
                  " ".join(str(num) if num != 0 else '.' for num in row[3:6]) + " | " +
                  " ".join(str(num) if num != 0 else '.' for num in row[6:]))

    def print_steps(self):
        print(f"Total steps taken: {self.steps}")

# Example usage
board = [
    [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]
]
start = time.time()
sudoku = Sudoku(board)
if sudoku.solve():
    sudoku.print_board()
    sudoku.print_steps()
else:
    print("No solution exists")
print(time.time() - start)