Put Another KenKen on the Barbie

Subtitle: Partitions with Pari/GP

If you like Sudoku, you'll love KenKen!

Tetsuya Miyamoto

Tetsuya Miyamoto (宮本 哲也), a Japanese mathematics teacher invented KenKen (“cleverness squared”) in 2004 to help his students improve math and logic skills. His students have dominated Japan’s “Math Olympics,” the country’s top mathematics competition for ages 11–15. Mr. Miyamoto said he believes in “the art of teaching without teaching”, and his favorite hobby is scuba diving. He’s the star of the new documentary, “Miyamoto and the Machine, The Story of KenKen”, and featured in a New Yorker article, “The Puzzle Inventor Who Makes Math Beautiful.”

Miyamoto told Device Plus, “Some would say the most important thing in mathematics is calculation. You memorize the formulas and calculate to solve a problem. In my opinion, there is much more than just calculation. I think the process of challenging yourself with different questions and struggling to figure out solutions on your own is what makes solving any kind of problems more fun and meaningful. This is the reason why I never step in to help my students solve puzzles, because I do not want to risk taking away their invaluable learning experiences.”

Tetsuya Miyamoto

Tetsuya Miyamoto

His approach to challenges is, “I make a list of things I do not like to do and I pick one from the list that I absolutely do not want to do. Then, I set a date and get it done.”

Your list might be different.

KenKen

If you’ve played Sudoku, you know that the game is a 9×99 \times 9 grid of cells where the cells must be filled with the integers 191 - 9 such that each digit appears exactly once in each row, column, and 3×33 \times 3 block. KenKen is similar, but Miyamoto added an intriguing twist.

KenKen puzzle

KenKen Puzzle

Instead of square blocks, the board is divided into irregularly shaped cages, outlined in black. Each cage has a number in the upper left square and an arithmetic operator (+×÷)(+ - \times \div). For example, in this puzzle, the cage in the upper left corner is 1×21 \times 2 with 11- indicating that the difference between the two numbers must be 11. You could enter 9,89,8 or 8,98,9 or any other pair that differs by one. The order doesn’t matter except that you need to satisfy the rules of Sudoku by having one of each digit in every row and column.

Notice that cages containing subtraction or division operators have only two squares, but ones with addition or multiplication often cover many squares. The next cage to the right contains the operation 90×90 \times meaning that the product of the three numbers must be 9090, and the cage in the upper right corner has 13+13+ indicating that the sum of the two squares must be 1313.

For a Sudoku puzzle to be uniquely solvable at least 17 squares must be filled, but KenKen puzzles are completely blank. In this puzzle, there is a 99 without any arithmetic operators in the fourth row from the top, and the sixth column. This means that you can fill in that one square with a 99.

The online game lets you choose the size of the puzzle so you might want to start with a smaller one.

Partitions

Suppose your puzzle has a cage with 7+7+ in it. How many ways can you write 77 as the sum of integers from 11 to 77? The answer is 15:

{(7),(1,6),(2,5),(3,4),(1,1,5),(1,2,4),(1,3,3),(2,2,3),(1,1,1,4),(1,1,2,3),(1,2,2,2),(1,1,1,1,3),(1,1,1,2,2),(1,1,1,1,1,2),(1,1,1,1,1,1,1)}\{(7),(1,6),(2,5),(3,4),(1,1,5),(1,2,4),\newline (1,3,3),(2,2,3),(1,1,1,4),(1,1,2,3),(1,2,2,2),\newline (1,1,1,1,3),(1,1,1,2,2),(1,1,1,1,1,2),(1,1,1,1,1,1,1)\}

and this set is called the partition of 77.

See the 20+20+ in the first column? There are 627627 ways to write 2020 as the sum of numbers between 11 and 2020. The good news is that you can eliminate any that aren’t exactly 44 long and any that repeat numbers. The bad news is that you still have to look through 627627 possible solutions. The number of partitions of an integer is given by the Partition function. The only way to get an exact solution for the number of partitions is through recurrence relations, meaning that you have to calculate the solutions for smaller numbers and then use those answers to get the answer you want.

You will also need to work out multiplicative partitions. In the bottom row is 28×28 \times in a cage with two elements. This isn’t too bad because 2828 can be factored as

28=22×7.28 = 2^2 \times 7.

This means that we can write the product in two ways, 28=2×1428 = 2 \times 14 or 28=4×728 = 4 \times 7. Since the grid is 9×99 \times 9, no entry can be greater than 99, so the only possible partition is (4,7)(4,7). We don’t know the order, but at least we’ve narrowed it down to two numbers.

Above the 2828 is a cage containing 4050×4050 \times with 55 elements spanning 22 rows and 33 columns. The factors of 40504050 are

4050=2×34×52.4050 = 2 \times 3^4 \times 5^2.

You have to be careful with this one because a 11, 33, 55, or 99 could appear in each row if it’s in two different columns. One possible solution might be

Solution 4050

How can we find all of the partitions? Let’s take a look at the PARI/GP computer algebra language.

PARI/GP and Notepad++ Installation

PARI/GP is an open-source computer algebra system originally developed by Henri Cohen for fast computations in number theory, but it can also be used for matrices, polynomials, power series, algebraic numbers, and transcendental functions. PARI is the C language library of functions for fast computations while GP is the scripting language on top of PARI.

PARI/GP doesn’t have an Interactive Development Environment (IDE) typical of many programming languages, but functions may be written in any text editor and imported into the interactive scripting shell gp. My preferred editor for PARI/GP is Notepad++ because syntax highlighting is available for many languages including PARI/GP.

Download the latest version of PARI/GP here and run the installer. If you want to be one of the cool kids, download the logo and convert it to an icon so you can start PARI from your desktop. Next, get the latest version of Notepad++. Once Notepad++ is running, click on Language \rightarrow User Defined Language \rightarrow Open User Defined Language folder …

Besides the languages that come with Notepad++, there is a collection of User Defined Languages (UDL) (list here), and the PARI/GP definition is available here. Click on “Raw”, copy the text into a new tab in Notepad++, and save it as “PariGP.xml” in the UDL folder. Now click on Language \rightarrow User Defined Language \rightarrow Define your language… which opens a dialog box. Click on Import… and navigate to the UDL folder. Select PariGP.xml and open it. If you click on Language again, you should see a dot next to User-defined at the bottom indicating that the PARI/GP lexer has been loaded. The Notepad++ user manual contains the complete instructions for working with UDLs.

PARI_GP UDL

The PARI/GP Command Window

Start PARI/GP by clicking on the desktop icon (because you’re one of the cool kids). It should look something like this:

PariGP Command Window

The command prompt gp > is where you interact directly with the PARI engine. PARI understands all of the basic mathematical expressions as well as many specific to number theory. If you type numbpart(20) at the prompt PARI will return 627, the number of arithmetic partitions of 20. Enter partitions(5) to get a list of the partitions of 55.

Partitions

You might find it handy to have the PARI/GP Reference Card open in a browser window to quickly look up the commands, or the available functions by category, which is more current. The partitions function is in the Combinatorics section.

An Additive Partition Function

As we’ve seen, PARI/GP comes with a partition function built-in. For KenKen, though, we don’t need all possible partitions of a number. The size of the puzzle limits the maximum value in any partition. If the sum is 2020 but the puzzle is 9×99 \times 9, we can eliminate any subset containing values greater than 99. We can also get rid of any sets that aren’t the right length. In the example above, the leftmost column contains a cage with 44 squares and must sum to 2020.

Any of the partitions of 2020 that aren’t 44 long can be eliminated. Since all of the squares for this cage are contained in the first column, the values must be unique which further reduces the possible partitions. Just below this cage is another with 2 squares and 17+17+ as the required operation. The only way to get a sum of 1717 is 8+98+9. We don’t know the order, but only an 88 and a 99 can appear in those two squares. This means that any partition of 2020 can’t have 88 or 99 in it.

In PARI/GP the partitions of a target integer tt can be stored in a vector,

v = partions(t);

and the number of partitions as

np = numbpart(t);

Semi-colons at the end of lines suppress the output in the command window and separate lines in a function.

To filter out the partitions that don’t meet the requirements of a cage, we need to check each partition vector to see if the length is the size of the cage, cc,

length(v) == c

and the maximum value of vv is less than the size of the puzzle, nn,

vecmax(v) <= n

If the input parameter uu has been set to 11 (true) then we need to check that all entries in vv are unique. Sets in PARI/GP are defined to have unique values, so simply converting vv to a set and then back to a vector removes duplicates,

u = Vec(Set(v));

Then, if the length of uu is the same as the length of vv we know that vv contains all unique entries,

length(v) == length(unique(v));

where the unique function is defined as

unique(v) = {u = Vec(Set(v));}

Functions are given names (in this case, unique), and the code is contained within curly braces. The value returned is either the last value calculated (u) or explicitly as Return(u).

Putting it all together, you can write the function sumPart in Notepad++ (save with the extension .gp to get syntax highlighting)

sumPart(t,c,n,u=1,e=[]) =
{
\\ List of all additive partitions
v = partitions(t);
np = numbpart(t);

\\ Select partitions meeting input requirements
P = [];
for(k = 1,np,
if(kFilt(v[k],c,n,u,e),P = concat(P,[v[k]]))
);

\\ Print partitions
for(k = 1,length(P),
print(Vec(P[k]))
);

return(P)

}

and the filtering function kFilt

kFilt(v,c,n,u=1,e=[]) =
{
length(v) == c &
vecmax(v) <= n &
if(u,isunique(v),1) &
length(setintersect(Set(v),Set(e))) == 0;
}

In the function sumPart, the inputs are t,c,n,u,e. Setting u=1 and e=[] means that the default value for u is true, and the default value for e is empty. This means that if there is a cage contained in a row or column and you haven’t eliminated any entries yet, you need only supply sumPart with the input parameters t,c,n.

In the middle section where the partitions are filtered the first line is

P = [];

which creates the empty vector P. Next, the function loops over all np partitions, and if it finds one that satisfies the requirements, it concatenates the vector v[k] to P. The function kFilt returns true or false, so the if statement checks if kFilt is true and if it is, it does the concatenation. If you want something done when kFilt is false, put another comma in after P = concat(P,v[k]) and write the code for the false condition.

Comments are started with double backslashes, \\ and block comments contained between /* and */.

Let’s try it out. Click on the links above to get the code, save the files to a local folder, and start PARI/GP in that folder. In PARI/GP type,

gp> \r sumPart

The \r command loads an external function, and PARI/GP will print the entire function when it loads. To find partitions for the cage with 20+20+, run

sumPart(20,4,9,1,[8,9]);

which should return

[2, 5, 6, 7]
[3, 4, 6, 7]

Instead of searching through 627 possible partitions, we only need to consider two of them. These functions are available on GitHub along with the dependent functions unique and isunique.

A Multiplicative Partition Function

Multiplicative partitions (also called unordered factorizations, “factorisatio numerorum” in Latin) have been studied at least since 1923, but there doesn’t seem to be a closed-form solution for the number of multiplicative partitions of an integer although there are upper bounds on how big it can be. A multiplicative partition of an integer is the set of all sets whose product is the integer.

The Online Encyclopedia of Integer Sequences (OEIS) describes a multiplicative partition function as the number of ways of factoring nn with all factors greater than 11. This is a pin plot of the number of partitions for each integer up to 200:

Pin plot A001055

Suppose a cage with four cells has the operation 72×72 \times. There are 1616 multiplicative partitions of 72=23×3272 = 2^3 \times 3^2,

{(2,2,2,3,3),(2,2,2,9),(2,2,3,6),(2,2,18),(2,3,3,4),(2,3,12),(2,4,9),(2,6,6),(2,36),(3,3,8),(3,4,6),(3,24),(4,18),(6,12),(8,9),(72)}\{(2,2,2,3,3),(2,2,2,9),(2,2,3,6),(2,2,18),(2,3,3,4),\newline (2,3,12),(2,4,9),(2,6,6),(2,36),(3,3,8),\newline (3,4,6),(3,24),(4,18),(6,12),(8,9),(72)\}

The three 22’s could all go into separate cells, or two could go into one cell and the other in a different cell, or they could all go into the same cell. The 33’s are similar, but there are only two of them. Looking at the list of multiplicative partitions of 7272 it’s easy to see that the only possible partitions in a 9×99 \times 9 puzzle are (2,2,2,9),(2,2,3,6)(2,2,2,9),(2,2,3,6), and (2,3,3,4)(2,3,3,4), but you’d need to generate the full list first to be sure.

But there’s a complication because of the KenKen rules. Partitions don’t include 11’s, but the puzzle might have a multiplicative partition that includes a 11. One of the partitions is (2,4,9)(2,4,9), but the cage might contain (1,2,4,9)(1,2,4,9).

PARI/GP doesn’t have a multiplicative equivalent of the function numbpart, but there is one on the OEIS written by Michael B. Porter called fcnt. The inputs are the integer nn and the maximum factor value mm. For consistency with PARI/GP notation, I renamed it mnumbpart and made the second input, mm, optional. I haven’t found a PARI/GP function to return the set of multiplicative partitions, so I wrote mpartitions.

With these two functions for multiplicative partitions, we can write a function called multPart that will work like sumPart does for additive partitions for KenKen. The only difference is that with multiplicative partitions we need to be able to include 11’s in the set of possible solutions. To do this, find all of the possible partitions with cage size cc, then append a 11 to solutions with length c1c-1, and if the cage spans multiple rows or columns, append two 11’s to solutions with length c2c-2.

\\ Select partitions meeting input requirements
P = [];
for(k = 1,np,
\\ Select all solutions with cage length c
if(kFilt(v[k],c,n,u,e),P = concat(P,[v[k]]));

\\ Select solutions with cage length c-1 and include one 1
if(kFilt(v[k],c-1,n,u,e),P = concat(P,[concat(1,v[k])]));

\\ If uniqueness is not required, allow two 1's
if( u == 0,
if(kFilt(v[k],c-2,n,u,e),P = concat(P,[concat([1,1],v[k])]));
);
);

The last case assumes that at least one cage dimension is less than or equal to two.

To load the two KenKen helper functions, at the gp prompt type

\r sumPart
\r multPart

which will give you access to the functions sumPart, multPart, mnumbpart, mpartitions, kFilt, and unique at the PARI/GP command prompt.

What’s Next?

Tetsuya Miyamoto would likely say that this takes away from your opportunity to explore the logic of KenKen, so it would probably be a good idea to try a few puzzles before using this PARI/GP code. These functions won’t solve the puzzle, but they significantly reduce the number of possible partitions for a cage. If you’d like to try to build a KenKen solver, Vardges Melkonian wrote, “An Integer Programming Model for the KenKen Problem”. He provides code written in AMPL (A Mathematical Programming Language). AMPL is proprietary, but it may be possible to run some code online, or to download the AMPL Community Edition, or to use the open-source subset of AMPL, GNU MathProg.

For experiments in number theory and combinatorics, PARI/GP excels. Hundreds of specialized functions have been written for the language, and it is very fast. It lacks an IDE and debugging can only be done at the command line. Scripts are written in an external text editor, or may be run in a SageMath notebook.

It might be possible to write an extension for PARI/GP in VSCode or Eclipse, where the FAQ page has a section called “Implementing Support for Your Own Language.” With an integrated debugger, PARI/GP would be a very powerful mathematical language.

And now it’s time to present the revised list of things you absolutely don’t want to do:

  1. Play endless games of KenKen
  2. Learn number theory
  3. Writing an editor/debugger for PARI/GP.

Image credits

Hero: Barbie Life, Shrimp on the Barbie: Annette MacKay, Pinterest

Tetsuya Miyamoto: Device Plus, KenKen Puzzle Inventor’s Tips for Engineers to Think “Outside the Box”, October 31, 2016

OEIS Pin Plot of A001055 as a graph

Code for this article

sumpart.gp - Additive partitions of integers

multpart.gp - Multiplicative partitions of integers

unique.gp, isunique.gp - Returns a vector of the unique elements of v

mnumbpart.gp - Returns the number of multiplicative partitions of integer n


Software

Pari/GP

PARI/GP is a widely used computer algebra system designed for fast computations in number theory (factorizations, algebraic number theory, elliptic curves, modular forms, L functions…), but also contains a large number of other useful functions to compute with mathematical entities such as matrices, polynomials, power series, algebraic numbers etc., and a lot of transcendental functions.

Posts using Pari/GP

Notepad++

Notepad++ is a free (as in “free speech” and also as in “free beer”) source code editor and Notepad replacement that supports several languages.

Posts using Notepad++

AMPL

A fully integrated system of optimization, AMPL has been developed for the real-world modeler who needs to manage all phases of the optimization development cycle without sacrificing computational performance. AMPLs straightforward language lets you formulate optimization models the way you think about them, and makes model logic accessible to your team members.

GNU MathProg

GNU MathProg is a modeling language intended for describing linear mathematical programming models. Model descriptions written in the GNU MathProg language consist of a set of statements and data blocks constructed by the user.

SageMath

SageMath is a free open-source mathematics software system built on top of many existing open-source packages: NumPy, SciPy, matplotlib, Sympy, Maxima, GAP, FLINT, R and many more. Access their combined power through a common, Python-based language or directly via interfaces or wrappers.

VSCode

Visual Studio Code is a lightweight but powerful source code editor which runs on your desktop and is available for Windows, macOS and Linux. It comes with built-in support for JavaScript, TypeScript and Node.js and has a rich ecosystem of extensions for other languages and runtimes (such as C++, C#, Java, Python, PHP, Go, .NET).

Posts using VSCode

Eclipse

Eclipse is an integrated development environment (IDE) used in computer programming. It contains a base workspace and an extensible plug-in system for customizing the environment. It is the second-most-popular IDE for Java development, and, until 2016, was the most popular.

See all software used on wildpeaches →