# What algorithm to use to fill a KenKen square board with cages?

I am working on recreating KenKen, a popular math puzzle involving a blank grid that is divided into "cages". Each cage is just a collection of adjacent squares and has a clue which is generally a number and an operand, shown below:

What type of algorithm would be best to fill the square with cages? Assume the maximum number of cells per cage would be 3 and the board is 4x4 in size, like in the example above.

• stackoverflow.com/questions/2316055/… might help Apr 19 '13 at 20:08
• Actually, I think this would fit better on Stack Overflow. It would probably have some answers by now there since its much more active. Apr 19 '13 at 20:15
• @UnderscoreZero, while the answer on that page gives a good overall approach, I'm just wondering if there are any algorithms out there that handle this situation. Apr 19 '13 at 20:26
• @Doorknob, I won't repost it yet, but if there are no bites over the next week or so then I will move it. No need to spam the stack exchange sites. Apr 19 '13 at 20:26
• @Doorknob Which site a question fits best doesn't depend on the activity of that site. Game development includes mathematical and algorithmic problems so this question belongs here. Moreover, if a question fits many sites, in my opinion, it's preferred to ask it on the more specialized site. That helps the network to stay specialized and smaller sites like Game Development to grow. Apr 19 '13 at 21:37

you can build those kind of puzzles in 4 phases:

1. create a Sudoku puzzle board
2. choose regions
3. put some random operations for those regions and their respective results
4. try solving that puzzle yourself and check if there is any other solution for that specific puzzle. (which is not really necessary)

if by any chance you've generated a puzzle with multiple results, you can keep changing some of those regions or operators until there is a unique answer!

Edit

Now to specify regions: Here is some basic idea, start from the top left square and move over all squares using DFS method, with a little adjustment. In each iteration choose the direction you are moving in a random order. Here is the potential path your DFS algorithm might follow:

And then when closing each node you group them with number of their parents as a block. which might result in boxing as follows:

to increase or decrease difficulty you can try gearing block sizes toward 3 or 1.

• I think he asked about choosing the block regions specifically. Apr 19 '13 at 21:48
• @danijar I need to refine my algorithm for that part, so I'll write it in about a day. the base idea is simply to first choose 3 block cages and then put 2 block ones in free spaces and finally everything left will be single block cages. Apr 19 '13 at 22:01
• danijar is correct, I am asking specifically about the layout of cages on the board. Thanks in advanced, @Gajoo. Apr 22 '13 at 14:08
• @JimmyBoh I've updated my answer to provide a simple idea for that part too. Apr 22 '13 at 15:28
• @Gajoo I'm guessing Prim's Algorithm would work for this? I never thought about generating and modifying a maze. Apr 22 '13 at 17:46

Another way would be to repeatedly merge adjacent blocks.

2. Pick two adjacent blocks, with a combined cell count less than S, at random.
3. Merge them.
4. Repeat N number of times, from step 2.

Adjust S and N for difficulty.

A good data-structure for this, is Disjoint-sets.

Board GenerateBoard(int width, int height, int maxSize, int numMerges)
{
var rnd = new Random();
var board = new Board(width, height);

// TODO: Optimize
var candidates =
Enumerable.Range(0, width).SelectMany(x1 =>
Enumerable.Range(0, height - 1).Select(y1 =>
new { x1, y1, x2 = x1, y2 = y1 + 1 }))
.Concat(
Enumerable.Range(0, width - 1).SelectMany(x1 =>
Enumerable.Range(0, height).Select(y1 =>
new { x1, y1, x2 = x1 + 1, y2 = y1 })))
.OrderBy(o => rnd.Next());

foreach (var o in candidates)
{
var cell1 = board.Grid[o.x1, o.y1].FindRoot();
var cell2 = board.Grid[o.x2, o.y2].FindRoot();
if (cell1.Size + cell2.Size <= maxSize)
{
cell1.Merge(cell2);
if (--numMerges == 0) break;
}
}

return board;
}

class Board
{

public Board(int width, int height)
{
Width = width;
Height = height;

Grid = new Cell[width, height];
for (int y = 0; y < height; y++)
for (int x = 0; x < width; x++)
{
Grid[x, y] = new Cell(x, y);
}
}
}

class Cell
{

public Cell Parent;
public int Size = 1;

public Cell(int x, int y)
{
X = x;
Y = y;
}

public void Merge(Cell other)
{
var root1 = FindRoot();
var root2 = other.FindRoot();
if (root1 == root2) return;

if (root1.Size < root2.Size)
{
var tmp = root1;
root1 = root2;
root2 = tmp;
}

root2.Parent = root1;
root1.Size += root2.Size;
}

public Cell FindRoot()
{
if (Parent == null) return this;
var root = Parent.FindRoot();
Parent = root;
return root;
}
}


Sample grid: