Técnica del árbol del pensamiento (ToT)

# 4x4 Sudoku puzzle generator and solver
import numpy as np
import random

def is_safe(grid, row, col, num):
    """
    Check if it's safe to place a number in a given position.
    """
    # Check if we find the same num in the similar row
    for x in range(4):
        if grid[row][x] == num:
            return False

    # Check if we find the same num in the similar column
    for x in range(4):
        if grid[x][col] == num:
            return False

    # Check if we find the same num in the particular 2x2 matrix
    start_row = row - row % 2
    start_col = col - col % 2
    for i in range(2):
        for j in range(2):
            if grid[i + start_row][j + start_col] == num:
                return False
    return True


def solve_sudoku(grid, row, col):
    """
    Solving the puzzle using backtracking
    """
    # Check if we have reached the 4x4 matrix end
    if row == 3 and col == 4:
        return True
    
    # Check if column value becomes 4, we move to next row
    if col == 4:
        row += 1
        col = 0

    # Check if the current position is filled
    if grid[row][col] > 0:
        return solve_sudoku(grid, row, col + 1)

    for num in range(1, 5):
        # Check if it is safe to place the num
        if is_safe(grid, row, col, num):
            grid[row][col] = num

            # Checking for next possibility with next column
            if solve_sudoku(grid, row, col + 1):
                return True

        # Removing the assigned num
        grid[row][col] = 0
    return False


def generate_sudoku():
    """
    Generate a 4x4 sudoku puzzle
    """
    grid = np.zeros((4,4), dtype=int)

    # Filling the diagonal 2x2 matrices
    for i in range(0, 4, 2):
        num = 1
        for j in range(i, i+2):
            for k in range(i, i+2):
                grid[j][k] = num
                num += 1

    # Removing random numbers to create the puzzle
    for i in range(4):
        remove = random.randint(1,2)  # Number of digits to remove from each row
        while remove > 0:
            col = random.randint(0,3)
            if grid[i][col] != 0:
                grid[i][col] = 0
                remove -= 1

    return grid

# Generate a 4x4 sudoku puzzle
puzzle = generate_sudoku()
puzzle_original = np.copy(puzzle)
# Solve the puzzle
solve_sudoku(puzzle, 0, 0)
puzzle, puzzle_original

# Function to find the next empty cell in the sudoku grid
def find_empty_location(grid):
    for row in range(4):
        for col in range(4):
            if grid[row][col] == 0:
                return row, col
    return -1, -1

# Function to check if a number can be placed in a specific cell
def is_valid(grid, row, col, num):
    # Row check
    if num in grid[row]:
        return False

    # Column check
    if num in [grid[i][col] for i in range(4)]:
        return False

    # 2x2 square check
    start_row, start_col = 2 * (row // 2), 2 * (col // 2)
    for i in range(start_row, start_row + 2):
        for j in range(start_col, start_col + 2):
            if grid[i][j] == num:
                return False

    return True

# Function to solve the sudoku using backtracking
def solve_sudoku_step_by_step(grid, step=0):
    row, col = find_empty_location(grid)
    
    # If there is no empty location, we are done
    if row == -1:
        return True, grid, step

    for num in range(1, 5):
        if is_valid(grid, row, col, num):
            grid[row][col] = num
            solved, final_grid, next_step = solve_sudoku_step_by_step(grid, step + 1)
            
            if solved:
                return True, final_grid, next_step

            # Undo the current cell for backtracking
            grid[row][col] = 0

    return False, grid, step

# Generate a 4x4 sudoku puzzle with some empty spaces
sudoku_puzzle = np.array([
    [1, 0, 0, 0],
    [0, 0, 0, 0],
    [0, 0, 0, 2],
    [0, 0, 0, 0]
])

# Solve the sudoku step by step
solved, final_sudoku, steps = solve_sudoku_step_by_step(sudoku_puzzle)
final_sudoku, steps