Sudoku Puzzle con cajas que contienen números cuadrados

Hace dos días, recibí un problema de sudoku que intenté resolver con Python 3. Me informaron que existe una solución, pero no estoy seguro de si existen múltiples soluciones.

El problema es el siguiente: una cuadrícula de sudoku de 9x9 está completamente vacía. Sin embargo, contiene cuadros de colores , y dentro de estos cuadros, la suma de los números tiene que ser un número cuadrado . Aparte de eso, se aplican las reglas normales de sudoku .

El problema aquí no es resolver un rompecabezas de sudoku, sino generar un rompecabezas viable que satisfaga las reglas de las cajas de colores .

Mi estrategia

Utilizando matrices numpy, he dividido la cuadrícula en 81 índices, que se pueden reorganizar a una cuadrícula de 9x9.

import numpy as np
print(np.array([i for i in range(81)]).reshape((9, 9)))

->
[[ 0  1  2  3  4  5  6  7  8]
 [ 9 10 11 12 13 14 15 16 17]
 [18 19 20 21 22 23 24 25 26]
 [27 28 29 30 31 32 33 34 35]
 [36 37 38 39 40 41 42 43 44]
 [45 46 47 48 49 50 51 52 53]
 [54 55 56 57 58 59 60 61 62]
 [63 64 65 66 67 68 69 70 71]
 [72 73 74 75 76 77 78 79 80]]

Aquí hay una lista que contiene todos los bloques de índices.

boxes = [[44, 43, 42, 53],[46, 47, 38],[61, 60],[69, 70],[71, 62],
         [0, 9, 18],[1, 10, 11, 20],[2, 3, 12],[4, 13, 14],[5, 6],
         [7, 8],[17, 26, 35],[21, 22, 23],[15, 16, 24, 25, 34],
         [27, 36, 37],[19, 28, 29],[45, 54],[55, 56],[63, 64, 65],
         [72, 73, 74],[57, 66, 75 ],[58, 59, 67, 68],[76, 77],[78, 79, 80]]

Como puede ver en la imagen , o en la matriz de arriba, las cajas se organizan en bloques de 2, 3, 4 o 5 (8, 12, 3, 3, 4). También he notado que una caja puede contener múltiples números sin romper ninguna regla de sudoku, pero solo es posible 2 de un número. Dada esa información, el cuadrado más grande posible sería 36, ​​ya que 9 + 9 + 8 + 7 + 6 = 39, y por lo tanto ninguna suma de un bloque podría llegar a 49. Para averiguar si la suma de una lista contiene un número cuadrado , Hice la siguiente función:

def isSquare(array):
    if np.sum(array) in [i**2 for i in range(1,7)]:
        return True
    else:
        return False

Para averiguar si una lista contiene la cantidad correcta de duplicados, es decir, más de un duplicado de un solo número, he realizado la siguiente función:

def twice(array):
    counter = [0]*9
    for i in range(len(array)):
        counter[array[i]-1]+=1
        if 3 in counter:
            return False
    if counter.count(2)>1:
        return False
    return True

Ahora, dados los dígitos 1-9, hay formas limitadas de soluciones a una lista, si la lista tiene que sumar un número cuadrado. Usando itertools , pude encontrar las soluciones, dividiéndolas en una matriz, donde el índice 0 contiene bloques de dos, el índice 1 contiene bloques de tres, y así sucesivamente.

from itertools combinations_with_replacement
solutions = []
for k in range(2, 6):
    solutions.append([list(i) for i in combinations_with_replacement(np.arange(1, 10), k) if 
    isSquare(i) and twice(i)])

Sin embargo, cualquier permutación de estas listas son soluciones viables para el "problema cuadrado". Usando itertools nuevamente, la cantidad total de cuadros posibles (sin las reglas de sudoku) suma 8782.

from itertools import permutations

def find_squares():
    solutions = []
    for k in range(2, 6):
        solutions.append([list(i) for i in combinations_with_replacement(np.arange(1, 10), k) if 
            isSquare(i) and twice(i)])
    s = []
    for item in solutions:
        d=[]
        for arr in item:
            for k in permutations(arr):
                d.append(list(k))
        s.append(d)
    return s # 4-dimensional array, max 2 of each

solutions = find_squares()

total = sum([len(i) for i in solutions])
print(total)
-> 8782

Esto debería ser suficiente para implementar una funcionalidad que decida si un tablero es legal, es decir, las filas, columnas y cuadros solo contienen uno de cada uno de los dígitos 1-9. Mi implementacion:

def legal_row(arr):
    for k in range(len(arr)):
        values = []
        for i in range(len(arr[k])):
            if (arr[k][i] != 0):
                if (arr[k][i] in values):
                    return False
                else:
                    values.append(arr[k][i])
    return True

def legal_column(arr):
    return legal_row(np.array(arr, dtype=int).T)


def legal_box(arr):
    return legal_row(arr.reshape(3,3,3,3).swapaxes(1,2).reshape(9,9))


def legal(arr):
    return (legal_row(arr) and legal_column(arr) and legal_box(arr))

Dificultades con el tiempo de ejecución

Un enfoque directo sería verificar cada combinación de cada bloque. He hecho esto y he producido varios problemas viables, sin embargo, la complejidad de mi algoritmo hace que esto tome demasiado tiempo.

En cambio, traté de aleatorizar algunas de las propiedades: el orden de los bloques y el orden de las soluciones. Con esto, limité el número de intentos y verifiqué si una solución era viable:

attempts = 1000
correct = 0
possibleBoards = []
for i in range(1, attempts+1):
    board = np.zeros((9, 9), dtype=int)
    score = 0
    shapes = boxes
    np.random.shuffle(shapes)
    for block in shapes:
        new_board = board
        new_1d = board.reshape(81)
        all_sols = solutions[len(block)-2]
        np.random.shuffle(all_sols)
        for sols in all_sols:
            #print(len(sols))
            new_1d[block] = sols
            new_board = new_1d.reshape((9, 9))
            if legal(new_board):
                board = new_board
                score+=1
                break
    confirm = board.reshape(81)
    #solve(board) # Using my solve function, not important here
    # Note that without it, correct would always be 0 as the middle of the puzzle has no boxes
    confirm = board.reshape(81)
    if (i%1000==0 or i==1):
        print("Attempt",i)
    if 0 not in confirm:
        correct+=1
        print(correct)
        possibleBoards.append(board)

En el código anterior, la puntuación variable se refiere a cuántos bloques puede encontrar el algoritmo durante un intento. La variable correcta se refiere a cuántas de las tablas de sudoku generadas podrían completarse. Si está interesado en qué tan bien funcionó en 700 intentos, aquí hay algunas estadísticas (este es un historgrama, el eje x representa los puntajes y el eje y representa cuántos de cada puntaje estuvo presente durante estos 700 intentos).

En qué necesito ayuda

Estoy luchando por encontrar una manera factible de encontrar una solución a este problema, que realmente pueda ejecutarse en un tiempo finito. Agradecería mucho cualquier consejo sobre cómo hacer que algunos de mis códigos sean más rápidos o mejores, cualquier idea de un enfoque diferente del problema, cualquier solución al problema o algunos consejos útiles sobre Python / Numpy relevantes para este problema.

Aquí es donde usaría un solucionador SMT. Son mucho más poderosos de lo que la gente da crédito. Si el mejor algoritmo que se te ocurre es esencialmente fuerza bruta, prueba con un solucionador. Simplemente enumerando sus restricciones y ejecutándolas, obtendrá su respuesta única en un par de segundos:

278195436
695743128
134628975
549812763
386457291
721369854
913286547
862574319
457931682

El código utilizado (y la imagen de referencia para las coordenadas):

import z3

letters = "ABCDEFGHI"
numbers = "123456789"
boxes = """
A1 A2 A3
B1 B2 C2 C3
C1 D1 D2
E1 E2 F2
F1 G1
H1 I1
G2 H2 G3 H3 H4
I2 I3 I4
B3 B4 C4
D3 E3 F3
A4 A5 B5
C5 B6 C6
G5 H5 I5 I6
A6 A7
B7 C7
D7 D8 D9
E7 E8 F7 F8
G7 H7
I7 I8
A8 B8 C8
G8 H8
A9 B9 C9
E9 F9
G9 H9 I9
"""
positions = [letter + number
             for letter in letters
             for number in numbers]
S = {pos: z3.Int(pos) for pos in positions}

solver = z3.Solver()

# Every symbol must be a number from 1-9.
for symbol in S.values():
    solver.add(z3.Or([symbol == i for i in range(1, 10)]))

# Every row value must be unique.
for row in numbers:
    solver.add(z3.Distinct([S[col + row] for col in letters]))

# Every column value must be unique.
for col in letters:
    solver.add(z3.Distinct([S[col + row] for row in numbers]))

# Every block must contain every value.
for i in range(3):
    for j in range(3):
        solver.add(z3.Distinct([S[letters[m + i * 3] + numbers[n + j * 3]]
                                for m in range(3)
                                for n in range(3)]))

# Colored boxes.
for box in boxes.split("\n"):
    box = box.strip()
    if not box: continue
    boxsum = z3.Sum([S[pos] for pos in box.split()])
    solver.add(z3.Or([boxsum == 1, boxsum == 4, boxsum == 9,
                      boxsum == 16, boxsum == 25, boxsum == 36]))

# Print solutions.
while solver.check() == z3.sat:
    model = solver.model()
    for row in numbers:
        print("".join(model.evaluate(S[col+row]).as_string()
                    for col in letters))
    print()

    # Prevent next solution from being equivalent.
    solver.add(z3.Or([S[col+row] != model.evaluate(S[col+row])
                      for col in letters
                      for row in numbers]))