Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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:

sorry the image is gone...

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.

share|improve this question
    
stackoverflow.com/questions/2316055/… might help –  UnderscoreZero 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. –  Doorknob 冰 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. –  JimmyBoh Apr 19 '13 at 20:26
3  
@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. –  JimmyBoh Apr 19 '13 at 20:26
2  
@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. –  danijar Apr 19 '13 at 21:37

2 Answers 2

up vote 2 down vote accepted

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:

enter image description here

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

enter image description here

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

share|improve this answer
    
I think he asked about choosing the block regions specifically. –  danijar 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. –  Ali.S 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. –  JimmyBoh Apr 22 '13 at 14:08
    
@JimmyBoh I've updated my answer to provide a simple idea for that part too. –  Ali.S 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. –  JimmyBoh Apr 22 '13 at 17:46

Another way would be to repeatedly merge adjacent blocks.

  1. Start with a grid of singleton 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 readonly int Width;
    public readonly int Height;

    public readonly Cell[,] Grid;

    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 readonly int X;
    public readonly int Y;

    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.Rank < root2.Rank)
        {
            root1.Parent = root2;
            root2.Size += root1.Size;
        }
        else if (root1.Rank > root2.Rank)
        {
            root2.Parent = root1;
            root1.Size += root2.Size;
        }
        else
        {
            root2.Parent = root1;
            root1.Rank++;
            root1.Size += root2.Size;
        }
    }

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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.