A Sudoku program with some advanced features

• Download demo - 867 KB
• Download source - 962.1 KB 

Introduction

Sudoku is a program built in C# with a WPF user interface. It can generate 9x9 or 16x16 boards at easy, medium or advanced level. I programmed it years ago and finally decided to publish it seeing that it implements some functions not found in the other postings.

Features

This sudoku program features:

• 9x9 or 16x16 boards with different difficulty levels
• Resolution of any 9x9 or 16x16 Sudoku puzzle
• Customizable fonts and colors
• Customizable symbols used to represent values (numbers, letters or symbols)
• Choices of input modes: cell toggle or value picker
• Input value modes which accepts only valid values or accepts any values
• Printing of sudoku boards (the current one or in batch)
• Designing your own sudoku (design mode)
• Saving or loading of a sudoku board
• Undo / redo functions
• Different kinds of hints
• Etc.

                                   Sudoku board using symbols instead of numbers

                                   16x16 Sudoku board using letters instead of numbers

Versioning

Demo Provided

The provided demo is the sudoku program in C# with the WPF interface.

Sources Provided

In addition to the source of the provided demo, I also include a prior version of this program written using Windows Forms. This latter version is not supported.

What Needs to be Improved?

    - It would be nice to be able to annotate the board.
    - I saw interesting input methods in other Sudoku games which can be added to this version.
    - The level difficulty can be more subtle.
    - Adding a help file to the game would be welcome.

Source Description

The main classes included in the project are:

Engine Classes

• CellPos: Cell position (x,y)
• SudBoard: Abstract class implementing the sudoku board
• SudBoard9: SudBoard implementation for a 9x9 board
• SudBoard16: SudBoard implementation for 16x16 specific functions
• SudBoardGenerator: Generates 9x9 or 16x16 board synchronously or asynchronously
• ValCount: Abstract class implementing a counter for each possible value for a type of region (lines, squares or columns)
• ValCount9: ValCount implementation for a 9x9 board
• ValCount16: ValCount implementation for a 16x16 board

WPF and User Interface Classes

• app: Application
• dlgAbout: About box
• dlgBoardAppearance: Dialog box to change the fonts and colors used to draw the interface
• dlgGenerateABoard: Dialog box to handle board generation
• SudControl: Visual control inheriting from UserControl and holding a sudoku board (SudBoard)
• ValPickerControl: Implements the value picker used to choose what value to play. Used by SudControl
• wndMain: Main window

1. Data Structures

The values are stored in the single dimension array int[] m_arrBoardVal. The use of a single dimension array instead of a two dimension array improves significantly the performance. The values in the array range from 0 to 9 (for 9x9 board) or 0 to 16 (for 16x16 board). Value 0 denotes an empty cell. The first value of the array is used to store the upper left cell value while the last one is used to store the bottom right value.

        The range of values stored in the single dimension array ValueTypeE[] m_arrBoardValType:

The ValueCount class is designed to keep the count of values for lines, columns and squares. Each time a cell value is updated, the ValCount of the line, the column and the square where the cell is located are updated accordingly.

The program needs to convert a linear position to a line/column and square position. These conversions are heavily used and must be optimised (especially with 16x16 board). The conversion in a 16x16 board is done with multiplication and modulo by 16. These operations are done using bit shifts and the '&' operator. This is the reason why the classes SudBoard9/16 and ValCount9/16 exist.

The conversion from square position to linear position is done using these two arrays:

The sudoku board class supports the undo or redo moves. To do so, two stacks hold the moves which can be undone or redone:

2. Moves

A move is defined has being valid if the value being entered is unique in its column, its line and its square.

The main method to change the value of a cell is PlayAt. The method updates the m_arrBoardVal and m_arrBoardValType arrays. It updates the corresponding square, line and column ValCount instances. If specified, the undo and redo stacks are updated.

3. Solving a board

A given sudoku board can have no solution, one solution or more than one solution. A solving method must be able to find a board solution if it exists and to indicate if more than one solution is possible.

A simple backtracking method can be enough to solve a 9x9 board.

while No Solution Found
    Find the first empty cell
    For each possible value in this cell
        Play it
        Call recursively
        If Solved
            Solution Found, exit
        Else
            Undo the move
        EndIf
    Next
    Oops, bad board!
wend

However, using this simple approach for solving a 16x16 board is too slow (at least to generate a 16x16 board where the Solve method has to be called many times). A better approach is to use an improved backtracking method:

do {
    Fill the obvious cells
    If solution not found,
        Find the first empty cell
        For each possible value in this cell
            Play it
            Call recursively
            If solve
                Solution Found, exit
            Else
                Undo the move
            EndIf
        Next
        Oops, bad board!
    EndIf
} while No solution found

A way to improve further the performance is to compute the list of possible moves in advance. The problem is now to implement the "Fill the obvious cells". In this context, obvious means:

• A value which can be played in only one cell of a square, a line or a column.
• A cell in which only one value can be played.

4. Generating a sudoku board

The different objectives of this board generator are:

• To generate a valid board which has one and only one solution.
• To generate a 9x9 or 16x16 board.
• To generate different levels of boards (easy, medium and difficult).

The computer uses three strategies to solve a board:

1. Fill cells with a value which can be played in only one cell of a square, a line or a column.
2. Fill cells where only one value can be played.
3. Brute force (try permutations one by one)

For humans, the first method is the easiest, the second one is more difficult and the third is the most difficult. An easy board needs only the first method to be solved. A medium board needs the first two methods while a difficult board needs the three methods to be solved.

The general approach used by this program to generate a board is:

1. To generate a completed board
2. To remove values one by one as long as:

• There is only one solution to the board
• Only strategies compatible with the difficulty level are being used

The board generation is done by the SudBoardGenerator class. The board can be generated on the main thread or on a worker thread.

4.1 Generating a completed board

A board can be filled using a simple backtracking method:

Fill(iPos)
    If Board Filled,
        Return
    ForEach Value
        If Value is valid at this position
            Play it
            If Fill(iPos+1) = Filled
                Return
            Else
                Undo the move
            EndIf
        EndIf
    Next
    <Must never get here>

This method will always give the same board. To make a random board generation, we just shuffle the order of the filled position.

In general, generating a completed board using this method is quite fast. However, from time to time, some 16x16 boards can take a long time to complete. When it happens, it's faster to cancel this generation and restart it.

4.2 Shaving the board (Digging holes)

Once a completed board has been generated, we just have to remove values from random cells:

ForEach Pos in Random Order
    Set the position value to 0
    If Solve doesn't give 1 solution or used strategies not compatible with the expected difficulty level
        Restore the value
    EndIf
Next

On a 16x16 board, this routine can take a relatively long time. For this reason, a timeout can be provided. If the timeout is reached, the board will still be valid but will contain more completed cells.

5 Sudoku Control

The SudControl implements a visual control inheriting from System.Windows.Controls.UserControl. It's used to play sudoku.