查找KENKEN益智「乘法」的所有可能的因素域

Question

甲KENKEN難題是拉丁方分成邊連接域：一個單一的單元中，同一行或列內的兩個相鄰的單元，佈置成一排或在三個小區等等。每個域都有一個標籤，它給出一個目標編號和一個算術運算（+ - * /），該運算將應用於域中單元格中的數字以產生目標編號。 （如果域只有一個單元格，就沒有給定操作符，只是一個目標---正方形爲你解決，如果操作符是 - 或/，那麼域中只有兩個單元格）。難題是（重新）構建與領域邊界和標籤一致的拉丁廣場。 （我認爲我已經看到與非唯一解一個謎一次。）

在細胞的數目的範圍可以從1到拼圖的寬度（高度）;通常，謎題是一側有4或6個細胞，但考慮任何尺寸的謎題。已發佈的謎題（4x4或6x6）中的域通常不超過5個單元格，但同樣，這似乎不是硬性限制。 （然而，如果謎題只有一個域名，那麼將會有與該維度的拉丁方塊一樣多的解決方案...）

編寫KenKen解算器的第一步是創建可以生成首先忽略域的幾何形狀，可能的數字組合在任何域中。 （一個線性域，就像一行三個單元一樣，在解決的難題中不能有重複的數字，但我們暫時忽略它）。我已經能夠編寫一個Python函數來處理添加標籤的情況：給它拼圖的寬度，域中單元的數量以及目標總和，並且它返回一個有效數字的元組列表，並加入到目標中。

乘法情況避開了我。我可以得到一個字典，其中的密鑰等於在給定大小的謎題中可達到的產品的產品，其中的值是包含提供該產品的因素的元組列表，但我無法制定出案例逐個例程，甚至不是一個壞例程。

分解一個給定的產品爲素數似乎很容易，但隨後劃分素數列表爲因素樹樁我的期望數量。 （我已經在Knuth的TAOCP的第4卷的第3部分中進行了思考，但是我還沒有學會如何「理解」他的算法描述，所以我不知道他的集合分割算法是否是一個起點。瞭解Knuth的描述可能是另一個問題！）

我很樂意預先計算普通域和拼圖大小的「多個」字典，只是將加載時間記入開銷，但這種方法似乎並不是一種有效的方式來處理，比如說，拼圖100側的細胞和2到50個細胞的大小的域。

Answer 1

簡體目標：你需要枚舉乘在一起，形成一個特定的產品，其中整數的數量是固定的所有整數組合。

爲了解決這個問題，你需要的是你的目標數的因式分解，然後用一個組合的方法來形成所有可能的子產品，從這些因素。 （一旦你有所有可能的子產品，這個難題還有一些其他的限制，比如沒有輸入可以比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]