12,394,788 members (72,392 online)
alternative version

34.1K views
14 bookmarked
Posted

# KenKen Solver in WPF

, 7 Dec 2008 CPOL
 Rate this:
My first WPF application to demonstrate solving KenKen puzzles.

## 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)
{
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"
Margin="40,0,0,0" HorizontalAlignment="Right"> ```

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

## Share

 United Kingdom
No Biography provided

## You may also be interested in...

 First Prev Next
 impossible kenken? tspitz8-Mar-09 1:37 tspitz 8-Mar-09 1:37
 Need pics sk8er_boy2877-Dec-08 20:41 sk8er_boy287 7-Dec-08 20:41
 Last Visit: 31-Dec-99 18:00     Last Update: 23-Jul-16 0:35 Refresh 1