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)
{
solution = rows.ToArray();
return true;
}
int newrow = rows.Count();
foreach (int[] permute in permutations)
{
if (IsValid(rows, permute))
{
int[][] newgrid = rows.Concat(new int[][] { permute }).ToArray();
if (rulesByRow[rows.Count()].All(r =>
r.Eval(board, newgrid.ToArray())))
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.