Suche alle möglichen Faktoren in KenKen Puzzle ‚mehrfach‘ Domain

Question

A KenKen Puzzle ist eine lateinische Quadrat geteilt in kanten verbunden Domänen: eine einzelne Zelle, zwei benachbarte Zellen innerhalb der gleichen Zeile oder Spalte, drei Zellen in einer Reihe oder in einer ell angeordnet usw. Jede Domäne hat, die ein Etikett gibt eine Zielnummer und eine einzige Rechenoperation (+ - * /), die zu den Zahlen in den Zellen der Domäne angewandt werden soll, die Zielnummer zu erhalten. (Wenn die Domäne nur eine Zelle hat, gibt es keinen Operator gegeben, nur ein Ziel --- der Platz für Sie gelöst ist, wenn der Betreiber -. Oder /, dann gibt es nur zwei Zellen in der Domäne.) Ziel das Puzzle ist (wieder) die lateinische Quadrat im Einklang mit dem Domains' Grenzen und Etiketten erstellen. (Ich glaube, dass ich ein Puzzle mit einer nicht eindeutigen Lösung gesehen habe nur einmal.)

Die Zahl in einer Zelle kann von 1 bis zur Breite (Höhe) des Puzzles reicht; Üblicherweise Rätsel sind 4 oder 6 Zellen auf einer Seite, aber Puzzles jeder Größe berücksichtigen. Domains in der veröffentlichten Puzzles (4x4 oder 6x6) hat in der Regel nicht mehr als 5 Zellen, aber auch hier scheint dies nicht eine harte Grenze. (Wenn jedoch das Puzzle nur eine Domäne hat, gäbe es so viele Lösungen geben, wie es lateinische Quadrate dieser Dimension ...)

Ein erster Schritt, um eine KenKen Solver Schreiben wären Routinen zu haben, die die möglichen Kombinationen von Zahlen in einem beliebigen Domäne produzieren können, zunächst die Domäne der Geometrie zu vernachlässigen. (. Eine lineare Domäne, wie eine Linie von drei Zellen kann keine doppelten Zahlen im Rätsel gelöst, aber wir ignorieren dies für den Moment) Ich habe in der Lage gewesen, eine Python-Funktion zu schreiben, die zusätzlich Etiketten von Fall Griffe: geben die Breite des Puzzles, die Anzahl der Zellen in der Domäne, und die Zielsumme, und es gibt eine Liste von Tupeln von gültigen Zahlen bis zum Ziel hinzugefügt wird.

Die Multiplikation Fall entzieht sich mir. Ich kann ein Wörterbuch mit den Tasten gleich den erreichbaren Produkte in einer Domäne einer bestimmten Größe in einem Puzzle mit einer bestimmten Größe erhalten, mit den Werten Listen von Tupeln sind die Faktoren, erhält das Produkt enthält, aber ich kann nicht einen Fall ausrechnen -von-Fall Routine, nicht einmal ein schlechter.

ein bestimmtes Produkt in Primfaktoren Factoring scheint einfach, aber dann Partitionierung der Liste der Primzahlen in die gewünschte Anzahl von Faktoren Stümpfe mich. (Ich habe auf Faszikel 3 von Band 4 von Knuth TAOCP sann, aber ich habe nicht gelernt, wie man ‚grok‘ seine Algorithmus Beschreibungen, so dass ich weiß nicht, ob seine Algorithmen für Satzpartitionierung ein Ausgangspunkt sein würden. Verstehen Knuth Beschreibungen könnten eine andere Frage!)

Ich bin sehr glücklich das ‚Multiplizieren‘ Wörterbücher für gemeinsame Domäne und Puzzle-Größen vorauszuberechnen und Kreide nur die Ladezeit zu Overhead, aber dieser Ansatz nicht eine effiziente Art und Weise scheinen zu behandeln, sagen wir, Puzzles 100 Zellen auf ein Seiten- und Domänen von 2 bis 50 Zellen in der Größe.

Answer 1

Vereinfachte Ziel: Sie müssen alle ganzzahligen Kombinationen aufzuzählen, die zusammen multiplizieren, um ein bestimmtes Produkt zu bilden, wobei die Anzahl der ganzen Zahlen festgelegt ist

.

Um dies zu lösen, alles, was Sie brauchen, ist eine Primfaktorzerlegung Ihrer Zielnummer und dann einen kombinatorischen Ansatz verwenden, um alle möglichen Nebenprodukte aus diesen Faktoren zu bilden. (Es gibt auch ein paar andere Einschränkungen des Puzzles, die leicht zu zählen sind, wenn Sie alle möglichen Nebenprodukte haben, wie kein Eintrag als max_entry groß sein kann, und Sie haben eine feste Anzahl von ganzen Zahlen zu verwenden, n_boxes_in_domain.)

Wenn beispielsweise max_entry=6, n_boxes_in_domain=3 und die target_number=20: 20 Ausbeuten (2, 2, 5); die zu geht (2, 2, 5) und (1, 4, 5).

Der Trick dabei ist, alle möglichen Nebenprodukte zu bilden, und der folgende Code tut dies. Es funktioniert durch die Faktoren Schleife durch alle möglichen einzelnen Paare zu bilden und diese dann tun, rekursiv alle möglichen Sätze aller einzelnen oder mehreren Paarungen zu geben. (Es ist ineffizient, sondern auch eine große Zahl haben eine kleine Primfaktorzerlegung):

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

Ich werde es verlassen, um die Primfaktoren zu erzeugen, aber dies scheint für die Arbeit

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

und einem härteren Fall, in dem, sagen wir 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]