KenKen Solver in WPF

• Download source code - 185 KB

(Requires .NET 3.5 SP1)

Introduction

To kill three birds with one stone, I wrote my first WPF application, using the free Microsoft DataGrid in the new Microsoft WPF Toolkit (requires .NET 3.5 SP1), and used it to solve KenKen puzzles, also utilising LINQ-style collections and operators in the process.

Download the app, and press Test to see a sample puzzle, then press Calculate to solve.

Background

KenKen puzzles consist of a 6 by 6 grid of squares, with various cells grouped together by bold lines. In each group, there is a number and basic arithmetic operation, e.g., 6+, which means the sum of all the cells is 6. Like Soduko, each digit between 1 and 6 can only appear once in each row and column.

KenKen Solver

The KenKen solver uses a brute-force approach, trying each permutation of digits row by row, and backtracking whenever a problem is found: either a digit appears in the same place in another row, or one of the rules is broken. For efficiency, I sort the rules by row, so they can be tried as early as possible.

To capture a puzzle, from a website or newspaper, the puzzle has to be translated into a grid of letters and the rule associated with each letter. Press 'Test' to see a sample.

The basic solver operates as follows:

if (!board.Validate())
    throw new Exception("Grid has letter missing from Rules");
AnalyseRules();
CreateRowPermutations();
solution = null;
TryRowSolution(new int[0][]);

Creating the permutations operates by starting with an empty 'left' list and 1-6 in the 'right' list, then appending each element of 'right' to 'left' successively and recursively:

private void CreateRowPermutations()
{
    Permute(new int[0], new int[] { 1,2,3,4,5,6} );
}

private void Permute(IEnumerable<int> left, IEnumerable<int> right)
{
    if (left.Count() == 6)
    {
        permutations.Add(left.ToArray());
        return;
    }
    for (int i = 0; i < right.Count(); i++)
        Permute( left.Concat(new int[] { right.ElementAt(i)} ), 
                 right.Where((val, index) => index != i).ToArray());
}

In a similar way, finding a solution recursively adds each permutation of rows, checking each is correct before recursing down to the next row. I use the All predicate to check each rule is met, and Concat to append the new row:

bool TryRowSolution(int[][] rows)
{
    if (rows.Count() == 6) //bottom-out 
    {
        solution = rows.ToArray();
        return true;
    }
    int newrow = rows.Count();
    foreach (int[] permute in permutations)
    {
      if (IsValid(rows, permute)) //check new row is consistent 
      {
          int[][] newgrid = rows.Concat(new int[][] { permute }).ToArray();
          if (rulesByRow[rows.Count()].All(r => 
                          r.Eval(board, newgrid.ToArray())))
          //test each rule 
             if (TryRowSolution(newgrid))
                return true;
      }
    }
    return false; 
}

WPF

The Microsoft DataGrid allows extremely simple two-way binding to in-memory data structures like a list of any class, even creating columns automatically to match the public properties (Note: not members) of the class:

rules = new ObservableCollection<Rule>(solver.board.rules); 
RulesGrid.ItemsSource = rules;

By setting the appropriate properties in the XAML, it will even add new elements to the list (Note: check you have a default constructor on your object):

<my:DataGrid Name="RulesGrid" 
    xmlns:my="clr-namespace:Microsoft.Windows.Controls;assembly=WPFToolkit" 
    CanUserAddRows="True" CanUserDeleteRows="True" 
    Margin="40,0,0,0" HorizontalAlignment="Right"> 

That's it... enjoy solving your KenKens.