Sudoku

import numpy as np

class Sudoku:
    def __init__(self, grid):
        # grid is a np array
        self.grid = grid
        
    def is_finished(self):
        return np.all(self.grid != 0)
    
    def possible_values(self, i, j):
        """
        Lists possible values for square (i, j)
        """
        values_rows = self.grid[i,:]
        values_columns = self.grid[:,j]
        c1 = i//3
        c2 = j//3
        values_3x3_squares = self.grid[c1*3:(c1+1)*3, c2*3:(c2+1)*3].reshape(-1)
        excluded_values = np.hstack([values_rows, values_columns, values_3x3_squares])
        possible_values = [i for i in range(1, 10) if i not in excluded_values]
        return possible_values
        
    def solve(self):
        ## PART 1: fill in the easy values
        has_changed = True
        while has_changed:
            has_changed = False
            for i in range(9):
                for j in range(9):
                    if self.grid[i,j] == 0:
                        possible_values = self.possible_values(i, j)
                        if len(possible_values) == 1:
                            self.grid[i,j] = possible_values[0]
                            has_changed = True
                        elif len(possible_values) == 0: # sudoku not solvable, no possible value for this square
                            return False
        
        if self.is_finished():
            return True
        
        ## PART 2: explore paths
        # a) find square with minimum amount of possibilities
        min_possible_values = 10
        for i in range(9):
            for j in range(9):
                if self.grid[i,j] == 0:
                    possible_values = self.possible_values(i, j)
                    if len(possible_values) < min_possible_values:
                        min_i = i
                        min_j = j
                        min_possible_values = len(possible_values)

        # b) Loop through possibilities for that square
        possible_values = self.possible_values(min_i, min_j)
        for r in possible_values:
            sudoku_r = self.grid.copy()
            sudoku_r[min_i, min_j] = r
            sudoku_r = Sudoku(sudoku_r)
            res = sudoku_r.solve()
            if res:
                self.grid = sudoku_r.grid
                return True

import numpy as np

def load_sudokus(file):
    with open(file, 'r') as f:
        sudokus = []
        sudoku = []
        for line in f:
            if 'Grid' in line:
                if len(sudoku) > 0:
                    sudokus.append(np.array(sudoku))
                    sudoku = []
            else:
                sudoku.append([int(k) for k in list(line.strip())])
    return sudokus

sudokus = load_sudokus("p096_sudoku.txt")
answer = 0
for i in range(len(sudokus)):
    s = Sudoku(sudokus[i])
    res = s.solve()
    if res:
        answer += int(str(s.grid[0,0]) + str(s.grid[0,1]) + str(s.grid[0,2]))
print(answer)