title: Find all possible factors in KenKen puzzle 'multiply' domain
body: <p>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.)</p>
  
  <p>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...)</p>
  
  <p>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.</p>
  
  <p>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.</p>
  
  <p>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!)</p>
  
  <p>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.  </p>