Click here to Skip to main content
Click here to Skip to main content

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)

Share

About the Author

tspitz

United Kingdom United Kingdom
No Biography provided

Comments and Discussions

 
Questionimpossible kenken? Pinmembertspitz8-Mar-09 2:37 
GeneralNeed pics Pinmembersk8er_boy2877-Dec-08 21:41 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin 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
Web04 | 2.8.141223.1 | Last Updated 7 Dec 2008
Article Copyright 2008 by tspitz
Everything else Copyright © CodeProject, 1999-2014
Layout: fixed | fluid