Encontrar todos los factores posibles en KenKen rompecabezas de dominio 'multiplicar'

Question

Un rompecabezas KenKen es un dividido en dominios de borde conectados cuadrado latino: una sola célula, dos celdas adyacentes dentro de la misma fila o columna, tres celdas dispuestas en una fila o en una ell, etc. Cada dominio tiene una etiqueta que da un número de destino y una sola operación aritmética (+ - * /) que se va a aplicar a los números en las células del dominio para dar el número de destino. (Si el dominio tiene sólo una célula, no hay ningún operador dado, sólo un destino --- la plaza se resuelve para usted Si el operador -. O /, entonces hay sólo dos células en el dominio.) El objetivo de rompecabezas es (re) construcción de la plaza consistente con los límites y las etiquetas de los dominios América. (Creo que he visto un rompecabezas con una solución no única sólo una vez.)

El número en una celda puede variar desde 1 a la anchura (altura) del rompecabezas; comúnmente, puzzles son 4 o 6 células en un lado, pero consideran rompecabezas de cualquier tamaño. Los dominios en los puzzles publicados (4x4 o 6x6) por lo general no tienen más de 5 células, pero, de nuevo, esto no parece ser un límite duro. (Sin embargo, si el rompecabezas tenía sólo un dominio, no habría tantas soluciones como hay cuadrados latinos de esa dimensión ...)

Un primer paso para escribir un solucionador KenKen sería tener rutinas que pueden producir las posibles combinaciones de números en cualquier dominio, a descuidar primera geometría del dominio. (. Un dominio lineal, como una línea de tres celdas, puede que no tienen números duplicados en el puzzle resuelto, pero ignoramos esto por el momento) que he sido capaz de escribir una función de Python que maneja además las etiquetas de caso por caso: darle la anchura del rompecabezas, el número de células en el dominio, y la suma de destino, y se devuelve una lista de tuplas de números válidos que suman hasta el objetivo.

El caso de la multiplicación se me escapa. Puedo conseguir un diccionario con claves iguales a los productos alcanzables en un dominio de un determinado tamaño en un rompecabezas de un tamaño determinado, siendo los valores listas de tuplas que contienen los factores dando el producto, pero no puedo trabajar en un caso -by-caso rutinario, ni siquiera una mala.

Factoring un producto determinado en primos parece fácil, pero entonces la partición de la lista de números primos en el número deseado de factores me tocones. (He meditado el fascículo 3 del Volumen 4 de TAOCP de Knuth, pero no he aprendido a 'grok' sus descripciones de algoritmos, así que no sé si sus algoritmos para el conjunto de partición sería un punto de partida. Descripciones Comprensión de Knuth podrían ser otra pregunta!)

Estoy muy feliz de calcular previamente el 'multiplicar' los diccionarios para los tamaños de dominio común y rompecabezas y justo tiza el tiempo de carga hasta el techo, pero tal método no parecería una forma eficaz de hacer frente a, por ejemplo, rompecabezas 100 células en un lado y dominios de 2 a 50 células de tamaño.

Answer 1

meta simplificado: se necesita para enumerar todas las combinaciones de números enteros que se multiplican entre sí para formar un determinado producto, cuando se fije el número de enteros

.

Para resolver esto, todo lo que necesita es una factorización prima de su número de destino y, a continuación, utilizar un enfoque combinatorio para formar todos los posibles sub-productos de estos factores. (También hay algunas otras limitaciones del rompecabezas que son fáciles de incluir una vez que tenga todas posibles sub-productos, como ninguna entrada puede ser grande que max_entry, y tiene un número fijo de números enteros de usar, n_boxes_in_domain.)

Por ejemplo, si max_entry=6, n_boxes_in_domain=3, y la target_number=20: 20 rendimientos (2, 2, 5); que va a (2, 2, 5) y (1, 4, 5).

El truco para esto es la formación de todos los posibles sub-productos, y el código de abajo hace esto. Funciona mediante bucle a través de los factores de la formación de todos los posibles pares individuales, y luego hacer esto de forma recursiva, para dar todos los conjuntos posibles de todos los vínculos individuales o múltiples. (Es ineficiente, sino que incluso un gran número tener una pequeña descomposición en factores primos):

def xgroup(items):
    L = len(items)
    for i in range(L-1):
        for j in range(1, L):
            temp = list(items)
            a = temp.pop(j)
            b = temp.pop(i)
            temp.insert(0, a*b)
            yield temp
            for x in xgroup(temp):
                yield x

def product_combos(max_entry, n_boxes, items):
    r = set()
    if len(items)<=n_boxes:
        r.add(tuple(items))
    for i in xgroup(items):
        x = i[:]
        x.sort()
        if x[-1]<=max_entry and len(x)<=n_boxes:
            r.add(tuple(x))
    r = [list(i) for i in r]
    r.sort()
    for i in r:
        while len(i)<n_boxes:
            i.insert(0, 1)
    return r

Lo dejo a usted genere los factores primos, pero esto parece que funciona para

max_entry=6, n_boxes=3, items=(2,2,5)
[2, 2, 5]
[1, 4, 5]

y para un caso más difícil, donde, digamos target_number=2106

max_entry=50, n_boxes=6, items=(2,3,3,3,3,13)
[2, 3, 3, 3, 3, 13]
[1, 2, 3, 3, 3, 39]
[1, 2, 3, 3, 9, 13]
[1, 1, 2, 3, 9, 39]
[1, 1, 2, 3, 13, 27]
[1, 1, 2, 9, 9, 13]
[1, 1, 1, 2, 27, 39]
[1, 3, 3, 3, 3, 26]
[1, 3, 3, 3, 6, 13]
[1, 1, 3, 3, 6, 39]
[1, 1, 3, 3, 9, 26]
[1, 1, 3, 3, 13, 18]
[1, 1, 3, 6, 9, 13]
[1, 1, 1, 3, 18, 39]
[1, 1, 1, 3, 26, 27]
[1, 1, 1, 6, 9, 39]
[1, 1, 1, 6, 13, 27]
[1, 1, 1, 9, 9, 26]
[1, 1, 1, 9, 13, 18]