Найти все возможные факторы в KenKen головоломка «умножить» домен - PullRequest
Новая
       10

Найти все возможные факторы в KenKen головоломка «умножить» домен

3 голосов
/ 06 июня 2009

Головоломка KenKen - это латинский квадрат, разделенный на домены, соединенные ребрами: одна ячейка, две соседние ячейки в одной строке или столбце, три ячейки, расположенные в ряд или в ячейку и т. Д. Каждый домен имеет метку, которая дает целевое число и одну арифметическую операцию (+ - * /), которая должна применяться к числам в ячейках домена, чтобы получить целевое число. (Если в домене только одна ячейка, оператор не задан, только цель - квадрат решается за вас. Если оператор - или /, то в домене всего две ячейки.) Цель Задача состоит в том, чтобы (заново) построить латинский квадрат в соответствии с границами доменов и метками. (Я думаю, что однажды я видел загадку с неуникальным решением.)

Число в ячейке может варьироваться от 1 до ширины (высоты) головоломки; Обычно головоломки состоят из 4 или 6 ячеек на одной стороне, но учитывают головоломки любого размера. Домены в опубликованных головоломках (4x4 или 6x6) обычно имеют не более 5 ячеек, но, опять же, это не является жестким ограничением. (Однако, если бы у головоломки была только одна область, было бы столько же решений, сколько было бы латинских квадратов этого измерения ...)

Первым шагом к написанию решателя KenKen было бы иметь подпрограммы, которые могут создавать возможные комбинации чисел в любом домене, сначала пренебрегая геометрией домена. (Линейный домен, как линия из трех ячеек, не может иметь повторяющихся чисел в решаемой головоломке, но мы на данный момент игнорируем это.) Я смог написать функцию Python, которая обрабатывает метки добавления в каждом конкретном случае: дать его ширина головоломки, количество ячеек в домене и целевая сумма, и она возвращает список кортежей действительных чисел, суммирующих до цели.

Случай умножения ускользает от меня. Я могу получить словарь с ключами, равными продуктам, достижимым в домене заданного размера, в головоломке заданного размера, со значениями, представляющими собой списки кортежей, содержащие факторы, дающие продукт, но я не могу разобрать случай на каждый случай, даже не плохой.

Выделение данного продукта в простые числа кажется легким, но разделение списка простых чисел на желаемое количество факторов ставит меня в тупик. (Я размышлял над 3-й главой тома TAOCP Кнута, но я не научился «впитывать» описания его алгоритмов, поэтому я не знаю, будут ли его алгоритмы для разделения наборов отправной точкой. Понимание описаний Кнута может быть другой вопрос!)

Я очень рад предварительно рассчитать словари «умножения» для общих доменов и размеров головоломки и просто записать время загрузки до непроизводительных затрат, но такой подход не кажется эффективным способом решения, скажем, головоломок на 100 ячеек на сторона и домены размером от 2 до 50 клеток.

1 Ответ

4 голосов
/ 06 июня 2009

Упрощенная цель: вам нужно перечислить все целочисленные комбинации, которые умножаются вместе, чтобы сформировать определенный продукт, в котором количество целых чисел фиксировано.

Чтобы решить эту проблему, все, что вам нужно, это простая факторизация вашего целевого числа, а затем использовать комбинаторный подход для формирования всех возможных субпродуктов из этих факторов. (Есть также несколько других ограничений головоломки, которые легко включить, если у вас есть все возможные субпродукты, например, ни одна запись не может быть больше, чем max_entry, и у вас есть фиксированное число целых чисел, n_boxes_in_domain .)

Например, если max_entry=6, n_boxes_in_domain=3 и target_number=20: 20 выходов (2, 2, 5); который идет к (2, 2, 5) и (1, 4, 5).

Хитрость заключается в том, чтобы сформировать все возможные субпродукты, и код ниже делает это. Он работает, просматривая факторы, формирующие все возможные одиночные пары, и затем делает это рекурсивно, чтобы получить все возможные наборы всех одинарных или множественных пар. (Это неэффективно, но даже большие числа имеют небольшую простую факторизацию): 

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

Я оставлю вам возможность генерировать основные факторы, но, похоже, это сработает для 

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

и для более сложного случая, скажем, 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]
...