12,352,739 members (70,414 online)
Add your own
alternative version

34K views
366 downloads
14 bookmarked
Posted

KenKen Solver in WPF

, 7 Dec 2008 CPOL
 Rate this:
Please Sign up or sign in to vote.
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)
{
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.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

About the Author

 United Kingdom
No Biography provided

Comments and Discussions

 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: 27-Jun-16 16:16 Refresh 1

General    News    Suggestion    Question    Bug    Answer    Joke    Praise    Rant    Admin

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Terms of Use | Mobile
Web01 | 2.8.160621.1 | Last Updated 7 Dec 2008
Article Copyright 2008 by tspitz
Everything else Copyright © CodeProject, 1999-2016
Layout: fixed | fluid