A heuristic algorithm to solve Sudoku puzzles

This project is an exploration of solving Sudoku puzzles using a heuristic approach that mimics human strategies. A common computer science principle used to solve Sudoku is backtracking. When confronted with two options, pick one and see if it could result in a solution; if not, backtrack to where you made the split. For a human, this is really annoying because if that branch “fails”—i.e., you arrive at a contradiction—you have to revert to the point where you branched out. I like to solve my Sudoku puzzles in one shot.

In this repository, we approach it in a simpler manner where we solve each sudoku as a human would, by putting a digit down only if no other digits can go in this cell or if that digit can only go here.

The code involves representing the Sudoku board as a Table class, where each individual cell is an instance of the Cell class. I did this project as a way to make a long flight interesting, so the goal was to have fun with a puzzle that has fascinated me since I was a kid while applying and practicing principles of good software engineering.

The whole code revolves around a Cell class representing a cell in the Sudoku board. Once you have this, you just need to keep track of candidate values, and it solves itself!

class Cell:
    def __init__(self, pos, value=0):
        """_summary_

        Args:
            pos (Tuple): Position of the Cell in the sudoku table.
            value (int, optional): Value in the cell. Defaults to 0 if the cell is unknown.
            candidate_values (set): Possible values in that cell. If the cell is already set to
            non-0. Then It is empty.

        Raises:
            RuntimeError: _description_
        """
        self.pos = pos
        self.value = int(value)
        self.candidate_values = set()

    def __str__(self):
        return str(self.value)

    def __eq__(self, other):
        if isinstance(other, int):
            return self.value == other
        return self.value == other.value and self.value == other.value

    def is_known(self):
        return self.value is not None

    def get_value(self):
        return self.value

    def set_value(self, value):
        self.value = value
        self.candidate_values = set()

    def get_candidate_values(self):
        return self.candidate_values

    def get_prohibited_values(self):
        prohibited_values = sorted(
            set([i for i in range(1, 10)]) - self.candidate_values
        )
        return prohibited_values

If you liked this post, you should check out my repo.