Quebra-cabeça Sudoku com caixas contendo números quadrados

Há dois dias, recebi um problema de sudoku que tentei resolver com o Python 3. Fui informado de que existe uma solução, mas não tenho certeza se existem várias soluções.

O problema é o seguinte: Uma grade 9x9 de sudoku está completamente vazia. No entanto, contém caixas coloridas e, dentro dessas caixas, a soma dos números deve ser um número quadrado . Fora isso, as regras normais do sudoku se aplicam.

A questão aqui não é resolver um quebra-cabeça sudoku, mas gerar um quebra-cabeça viável, que satisfaça as regras das caixas coloridas .

Minha estratégia

Usando matrizes numpy, dividi a grade em 81 índices, que podem ser reorganizados em uma grade 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]]

Aqui está uma lista contendo todos os blocos 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 você pode ver na figura , ou na matriz acima, as caixas são organizadas em blocos de 2, 3, 4 ou 5 (8 duplas, 12 três, 3 quatro, 1 quinto). Também notei que uma caixa pode conter vários números sem violar nenhuma regra de sudoku, mas apenas 2 de um número são possíveis. Dada essa informação, o maior quadrado possível seria 36, ​​pois 9 + 9 + 8 + 7 + 6 = 39 e, portanto, nenhuma soma de um bloco poderia chegar a 49. Para descobrir se a soma de uma lista contém um número quadrado , Eu fiz a seguinte função:

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

Para descobrir se uma lista contém a quantidade correta de duplicatas, ou seja, mais de uma duplicata de apenas um número, criei a seguinte função:

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

Agora, dados os dígitos de 1 a 9, existem maneiras limitadas de soluções para uma lista, se a lista precisar somar um número quadrado. Usando as ferramentas , eu poderia encontrar as soluções, dividindo-as em uma matriz, onde o índice 0 contém blocos de dois, o índice 1 contém blocos de três e assim por diante.

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)])

No entanto, qualquer permutação dessas listas é soluções viáveis ​​para o "problema do quadrado". Usando as ferramentas novamente, a quantidade total de caixas possíveis (sem as regras do sudoku) é 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

Isso deve ser suficiente para implementar a funcionalidade que decide se uma placa é legal, ou seja, linhas, colunas e caixas contém apenas um de cada um dos dígitos de 1 a 9. Minha implementação:

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))

Dificuldades com o tempo de execução

Uma abordagem direta seria verificar todas as combinações de todos os blocos. Eu fiz isso e produzi vários problemas viáveis, no entanto, a complexidade do meu algoritmo faz com que isso demore muito tempo.

Em vez disso, tentei aleatoriamente algumas das propriedades: A ordem dos blocos e a ordem das soluções. Usando isso, limitei o número de tentativas e verifiquei se uma solução era viável:

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)

No código acima, a pontuação da variável refere-se a quantos blocos o algoritmo pôde encontrar durante uma tentativa. A variável correta refere-se a quantas placas de sudoku geradas podem ser concluídas. Se você está interessado em saber como foi o desempenho em 700 tentativas, aqui estão algumas estatísticas (este é um historograma, o eixo x representa as pontuações e o eixo y representa quantos de cada pontuação estavam presentes nessas 700 tentativas).

Com o que preciso de ajuda

Estou lutando para encontrar uma maneira viável de encontrar uma solução para esse problema, que possa realmente ser executada em uma quantidade finita de tempo. Eu gostaria muito de receber dicas sobre como tornar alguns dos meus códigos mais rápidos ou melhores, idéias de uma abordagem diferente para o problema, soluções para o problema ou algumas dicas úteis sobre Python / Numpy relevantes para esse problema.

É aqui que eu usaria um solucionador SMT. Eles são muito mais poderosos do que as pessoas dão crédito. Se o melhor algoritmo em que você consegue pensar é essencialmente força bruta, tente um solucionador. Basta listar suas restrições e executá-las, fornecendo sua resposta exclusiva em alguns segundos:

278195436
695743128
134628975
549812763
386457291
721369854
913286547
862574319
457931682

O código usado (e imagem de referência para 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]))