Find all possible factors in KenKen puzzle 'multiply' domain

Question

A KenKen puzzle is a Latin square divided into edge-connected domains: a single cell, two adjacent cells within the same row or column, three cells arranged in a row or in an ell, etc. Each domain has a label which gives a target number and a single arithmetic operation (+-*/) which is to be applied to the numbers in the cells of the domain to yield the target number. (If the domain has just one cell, there is no operator given, just a target --- the square is solved for you. If the operator is - or /, then there are just two cells in the domain.) The aim of the puzzle is to (re)construct the Latin square consistent with the domains' boundaries and labels. (I think that I have seen a puzzle with a non-unique solution just once.)

The number in a cell can range from 1 to the width (height) of the puzzle; commonly, puzzles are 4 or 6 cells on a side, but consider puzzles of any size. Domains in published puzzles (4x4 or 6x6) typically have no more than 5 cells, but, again, this does not seem to be a hard limit. (However, if the puzzle had just one domain, there would be as many solutions as there are Latin squares of that dimension...)

A first step to writing a KenKen solver would be to have routines that can produce the possible combinations of numbers in any domain, at first neglecting the domain's geometry. (A linear domain, like a line of three cells, cannot have duplicate numbers in the solved puzzle, but we ignore this for the moment.) I've been able to write a Python function which handles addition labels case by case: give it the width of the puzzle, the number of cells in the domain, and the target sum, and it returns a list of tuples of valid numbers adding up to the target.

The multiplication case eludes me. I can get a dictionary with keys equal to the products attainable in a domain of a given size in a puzzle of a given size, with the values being lists of tuples containing the factors giving the product, but I can't work out a case-by-case routine, not even a bad one.

Factoring a given product into primes seems easy, but then partitioning the list of primes into the desired number of factors stumps me. (I have meditated on Fascicle 3 of Volume 4 of Knuth's TAOCP, but I have not learned how to 'grok' his algorithm descriptions, so I do not know whether his algorithms for set partitioning would be a starting point. Understanding Knuth's descriptions could be another question!)

I'm quite happy to precompute the 'multiply' dictionaries for common domain and puzzle sizes and just chalk the loading time up to overhead, but that approach would not seem an efficient way to deal with, say, puzzles 100 cells on a side and domains from 2 to 50 cells in size.

Answer 1

Simplified goal: you need to enumerate all integer combinations that multiply together to form a certain product, where the number of integers is fixed.

To solve this, all you need is a prime factorization of your target number, and then use a combinatorial approach to form all possible sub-products from these factors. (There are also a few other constraints of the puzzle that are easy to include once you have all possible sub-products, like no entry can be great than max_entry, and you have a fixed number of integers to use, n_boxes_in_domain.)

For example, if max_entry=6, n_boxes_in_domain=3, and the target_number=20: 20 yields (2, 2, 5); which goes to (2, 2, 5) and (1, 4, 5).

The trick to this is to form all possible sub-products, and the code below does this. It works by looping through the factors forming all possible single pairs, and then doing this recursively, to give all possible sets of all single or multiple pairings. (It's inefficiently, but even large numbers have a small prime factorization):

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

I'll leave it to you to generate the prime factors, but this seems to work for

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

and for a harder case where, say 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]