Sudoku solver implementation in Python

sudoku_solver.py

import copy


def peers(i, j):
    row = set([(i, x)   for x in range(9)])
    column = set([(x, j)    for x in range(9)])

    start_row = 3 * (i // 3)
    start_col = 3 * (j // 3)
    square = set([
        (r, c)
        for r in range(start_row, start_row + 3)
        for c in range(start_col, start_col + 3)
    ])

    return row.union(column).union(square).difference([(i, j)])

PEERS = { 
    (i, j): peers(i, j)   
    for i in range(9)
    for j in range(9) 
}

TRIPLETS = [(0,1,2), (3,4,5), (6,7,8)]
SQUARE_INDICES = [
    [(i, j) for i in t1 for j in t2] 
    for t1 in TRIPLETS 
    for t2 in TRIPLETS
]


class Cell:
    def __init__(self, value=0, possibilities="123456789"): 
        self.value = value 
        self.possibilities = possibilities

    def __repr__(self):
        return f"Cell<value: {self.value}, possibilities: '{self.possibilities}'>"


class Board:
    def __init__(self, raw_board):
        self.count = len([x for row in raw_board for x in row   if x != 0])
        self.board = self.make_board(raw_board)

        for i in range(9):
            for j in range(9):
                if self.value_at(i, j) != 0:
                    self.propagate_changes(i, j)

    
    def peers(self, i, j):
        return PEERS[(i, j)]

    
    def make_board(self, raw_board):
        board = {}
        for i in range(9):
            for j in range(9):
                value = raw_board[i][j]
                possibilities = "123456789" if value == 0 else ""
                board[(i, j)] = Cell(value, possibilities)

        return board


    def value_at(self, i, j):
        return self.board[(i, j)].value


    def possibilities_at(self, i, j):
        return [int(x)  for x in self.board[(i, j)].possibilities]


    def __repr__(self):
        rows = []
        rows.append(f"Count: {self.count}")

        for i in range(9):
            row = []
            for j in range(9):
                value = self.value_at(i, j)
                str_value = f"{ '·' if value == 0   else str(value)}" 
                row.append(str_value)
                
                if j % 3 == 2:
                    row.append(" ")
            
            rows.append(" ".join(row))
            if i % 3 == 2:
                rows.append("")

        return "\n".join(rows)


    def clone(self):
        new_board = copy.copy(self)
        new_board.board = copy.copy(self.board)
        return new_board


    def propagate_changes(self, i, j):
        peers = self.peers(i, j)
        str_value = str(self.value_at(i, j))

        for (r, c) in peers:
            peer_value = self.value_at(r, c)
            peer_possibilities = self.board[(r, c)].possibilities.replace(str_value, "")
            self.board[(r, c)] = Cell(value=peer_value, possibilities=peer_possibilities)


    def assign(self, i, j, value):
        new_board = self.clone()
        new_board.board[(i, j)] = Cell(value=value, possibilities="")
        new_board.propagate_changes(i, j)
        new_board.count += 1

        return new_board


    def next_position(self):
        min_len = 10
        result = None
        for position in self.board:
            cell = self.board[position]
            if cell.value == 0:
                length = len(cell.possibilities)
                if length < min_len:
                    min_len = length
                    result = position
        
        return result


    
    def raw_board(self):
        return [
            [self.value_at(i, j) for j in range(9)]
            for i in range(9)
        ]



def solve(raw_board):
    validate(raw_board)

    board = Board(raw_board)
    solutions = solve_board(board, [])

    if len(solutions) == 0:
        raise Exception("No solutions found!")

    elif len(solutions) == 1:
        print(solutions[0])

    else:
        raise Exception("More than one solution!")


def solve_board(board: Board, solutions):
    if board.count == 81:
        solutions.append(board)
        return solutions

    else:
        next_position = board.next_position()
        possible_values = board.possibilities_at(*next_position)
        
        for value in possible_values:
            new_board = board.assign(*next_position, value)
            solutions = solve_board(new_board, solutions)
            if len(solutions) > 1:
                return solutions

        return solutions


def validate(raw_board):
    for i in range(9):
        valid_row = validate_row(raw_board, i)
        if not valid_row:
            raise Exception(f"Invalid row: {i}")
    
    for j in range(9):
        valid_column = validate_column(raw_board, j)
        if not valid_column:
            raise Exception(f"Invalid column: {j}")

    for k in range(9):
        valid_square = validate_square(raw_board, k)
        if not valid_square:
            raise Exception(f"Invalid square: {k}")


def validate_row(raw_board, i):
    values = raw_board[i]
    return unique_values(values)


def validate_column(raw_board, j):
    values = [raw_board[i][j] for i in range(9)]
    return unique_values(values)


def validate_square(raw_board, k):
    values = [raw_board[i][j]   for (i, j) in SQUARE_INDICES[k]]
    return unique_values(values)


def unique_values(values):
    found = set([])
    for x in values:
        if x != 0:
            if x not in found:
                found.add(x)
            else:
                return False
    
    return True


if __name__ == "__main__":
    # Single solution
    raw_board_1 = [
        [9, 0, 0, 0, 8, 0, 0, 0, 1],
        [0, 0, 0, 4, 0, 6, 0, 0, 0],
        [0, 0, 5, 0, 7, 0, 3, 0, 0],
        [0, 6, 0, 0, 0, 0, 0, 4, 0],
        [4, 0, 1, 0, 6, 0, 5, 0, 8],
        [0, 9, 0, 0, 0, 0, 0, 2, 0],
        [0, 0, 7, 0, 3, 0, 2, 0, 0],
        [0, 0, 0, 7, 0, 5, 0, 0, 0],
        [1, 0, 0, 0, 4, 0, 0, 0, 7]]

    # Two solutions
    raw_board_2 = [
        [9, 0, 6, 0, 7, 0, 4, 0, 3],
        [0, 0, 0, 4, 0, 0, 2, 0, 0],
        [0, 7, 0, 0, 2, 3, 0, 1, 0],
        [5, 0, 0, 0, 0, 0, 1, 0, 0],
        [0, 4, 0, 2, 0, 8, 0, 6, 0],
        [0, 0, 3, 0, 0, 0, 0, 0, 5],
        [0, 3, 0, 7, 0, 0, 0, 5, 0],
        [0, 0, 7, 0, 0, 5, 0, 0, 0],
        [4, 0, 5, 0, 1, 0, 7, 0, 8]]

    # Many solutions
    raw_board_3 = [
        [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]]

    # No solutions (invalid board)
    raw_board_4 = [
        [9, 0, 0, 0, 8, 0, 0, 0, 1],
        [0, 9, 0, 4, 0, 6, 0, 0, 0],
        [0, 0, 5, 0, 7, 0, 3, 0, 0],
        [0, 6, 0, 0, 0, 0, 0, 4, 0],
        [4, 0, 1, 0, 6, 0, 5, 0, 8],
        [0, 9, 0, 0, 0, 0, 0, 2, 0],
        [0, 0, 7, 0, 3, 0, 2, 0, 0],
        [0, 0, 0, 7, 0, 5, 0, 0, 0],
        [1, 0, 0, 0, 4, 0, 0, 0, 7]]   


    # solve(raw_board_1)
    # solve(raw_board_2)
    # solve(raw_board_3)
    # solve(raw_board_4)