
Here is an interseting wikipedia page for Sudoku solving algorithms:
http://en.wikipedia.org/wiki/Sudoku_algorithms
may be interestring to implement some of them.



Cool find. I'm particularly interested in the last article that describes the hardest sudoku puzzles. I put one into my javascript solver and it failed... I am interested what technique needs to be used in these cases.


Mar 21, 2012 at 12:03 PM
Edited Mar 22, 2012 at 3:10 PM

Hi, I love the challenge, I made some c# code for you. Remove this is you don't want to see it :)
My algoritme solving the hardest puzzles on that wiki page (CodeCleaner was talking about):
HardestSudokusThread02085;Discrepancy: 1381 ms
golden nugget: 1490 ms
HardestSudokusThread00245;Red_Dwarf: 895 ms
HardestSudokusThread01418;coloin: 100 ms
on a Dell intel core i7 1.6ghz notebook
This algoritm does a recursive bruteforce on the cell with the less possible combinations.
There are faster ways to implement this algoritm, but will be less readable.
I hope you like it.
SudokuBoard.cs
public class SudokuBoard
{
// offsets:
// +====+====+====+====+====+====+====+====+====+
// # 0  1  2 # 3  4  5 # 6  7  8 #
// ++++++++++
// # 9  10  11 # 12  13  14 # 15  16  17 #
// ++++++++++
// # 18  19  20 # 21  22  23 # 24  25  26 #
// +====+====+====+====+====+====+====+====+====+
// # 27  28  29 # 30  31  32 # 33  34  35 #
// ++++++++++
// # 36  37  38 # 39  40  41 # 42  43  44 #
// ++++++++++
// # 45  46  47 # 48 (49) 50 # 51  52  53 #
// +====+====+====+====+====+====+====+====+====+
// # 54  55  56 # 57  58  59 # 60  61  62 #
// ++++++++++
// # 63  64  65 # 66  67  68 # 69  70  71 #
// ++++++++++
// # 72  73  74 # 75  76  77 # 78  79  80 #
// +====+====+====+====+====+====+====+====+====+
// so ([column]4,[row]5) = 4 + (5 * 9) = 49
private bool _isSolvedChecked;
public byte[] Cell { get; set; }
public SudokuBoard()
{
Cell = new byte[9 * 9];
}
public SudokuBoard(byte[] Cells)
{
Cell = Cells;
}
public SudokuBoard Copy()
{
byte[] copy = new byte[9 * 9];
Array.Copy(Cell, copy, 9 * 9);
return new SudokuBoard(copy);
}
public bool IsSolved
{
get
{
// if this board is already checked and solved, we don't have to recalculate it again. (because of recursion)
if (_isSolvedChecked) return true;
for (int offset = 0; offset < 9 * 9; offset++)
if (this.Cell[offset] == 0)
return false;
_isSolvedChecked = true;
return true;
}
}
}
Sudoku.cs
public class Sudoku
{
public static readonly byte[] ValidNumbers = new byte[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
private static IEnumerable<int> FindEmptyCells(SudokuBoard sudokuBoard)
{
// only return the empty cells
for (int offset = 0; offset < 9 * 9; offset++)
if (sudokuBoard.Cell[offset] == 0)
yield return offset;
}
private static byte[] CheckValidNumbers(int offset, SudokuBoard sudokuBoard)
{
// start with all numbers
HashSet<byte> numbers = new HashSet<byte>(ValidNumbers);
// converting the offset to column and row
int column = offset % 9;
int row = offset / 9;
// filtering them on the rules
CheckValidNumbersInRow(row, sudokuBoard, numbers);
CheckValidNumbersInColumn(column, sudokuBoard, numbers);
CheckValidNumbersInGroup(column, row, sudokuBoard, numbers);
return numbers.ToArray();
}
private static void CheckValidNumbersInRow(int row, SudokuBoard sudokuBoard, HashSet<byte> numbers)
{
// all numbers that have been found, should be removed
for (int columnIndex = 0; columnIndex < 9; columnIndex++)
{
int lookupOffset = columnIndex + (row * 9);
// read what number is found there
byte number = sudokuBoard.Cell[lookupOffset];
// the number is removed from the numbers hashset if it is found
numbers.Remove(number);
}
}
private static void CheckValidNumbersInColumn(int column, SudokuBoard sudokuBoard, HashSet<byte> numbers)
{
// all numbers that have been found, should be removed
for (int rowIndex = 0; rowIndex < 9; rowIndex++)
{
int lookupOffset = column + (rowIndex * 9);
// read what number is found there
byte number = sudokuBoard.Cell[lookupOffset];
// the number is removed from the numbers hashset if it is found
numbers.Remove(number);
}
}
private static void CheckValidNumbersInGroup(int column, int row, SudokuBoard sudokuBoard, HashSet<byte> numbers)
{
// check in what group this column/row is:
int groupColumn = column / 3; // integer division gives the groupcolumn index
int groupRow = row / 3; // integer division gives the grouprow index (like (4,5) gives 4/3=1, 5/3 = 1 (so 4,5 is in the middle group))
// multiply the group indices by 3 (to get the first cell (top left) within the group.
int columnStart = groupColumn * 3;
int rowStart = groupRow * 3;
// check the 3x3 from there
for (int rowIndex = rowStart; rowIndex < rowStart + 3; rowIndex++)
for (int columnIndex = columnStart; columnIndex < columnStart + 3; columnIndex++)
{
// calculate the offset on the sudoku board
int lookupOffset = columnIndex + (rowIndex * 9);
// read what number is found there
byte number = sudokuBoard.Cell[lookupOffset];
// the number is removed from the numbers hashset if it is found
numbers.Remove(number);
}
}
public static SudokuBoard Solve(SudokuBoard sudokuBoard)
{
// find all empty (0) cells
int[] emptyCellOffsets = FindEmptyCells(sudokuBoard).ToArray();
// is there are no empty cells this could be already done.
if (emptyCellOffsets.Length == 0)
return sudokuBoard;
// select the cell with the least combinations
var collection = from offset in emptyCellOffsets
// check the possible numbers valid for this cell
let validNumbers = CheckValidNumbers(offset, sudokuBoard)
let count = validNumbers.Length
// order them by the number of numbers (we want to bruteforce the least possible combinations, try descending the the orderby count.. :) )
orderby count
select new { offset, validNumbers };
var first = collection.First();
foreach (byte number in first.validNumbers)
{
// create a copy (because we need to preserve the previous board layout)
SudokuBoard copy = sudokuBoard.Copy();
// lets test this number at that offset
copy.Cell[first.offset] = number;
// try solving the board with the test number at the offset
SudokuBoard result = Solve(copy);
// is the result is solved, then we don't need to look much futher
if (result.IsSolved)
return result;
}
return sudokuBoard;
}
}



This is very good work jvanlangen. I'm very pleased with the performance for a brute force solution.
After doing some reading it is my understanding that the hardest Sudoku puzzles are not human solvable. The only limitation placed on a board is that it must have 1 solution, this means some puzzles may fail to be solved by deduction. In those cases only
a brute force solution will succeed.
Very good work.


Mar 22, 2012 at 11:09 AM
Edited Mar 22, 2012 at 3:09 PM

Hi campbel,
Thanks for your response, i could make a much cleaner implementation in the repository. Are there any issues or obstacles you've run into?
So the brief explanation is:
#1 Find all empty cells
#2 Check for each cell the valid numbers
#3 Sort them on the cell with less possible combinations (and start from there)
#4 Select the top cell (with the less combinations)
#5 Make copies of the sudoku board fillin the value and for each combination and start execute #1 on each board
The hardest puzzles are the puzzles that have more combinations per cell. (and will take more solve executions (so it takes more time)
For fun you could try to change the ascending sorting to descending, You will see it will take 'ages'.
So, this is almost the same as the solution you explained. Only difference is recursive vs queued.
Kind regards,
Jeroen



Hi Jeroen,
I added your code to the SVN repository for you. I liked your implementation of the SudokuBoard class, I think I will use it for my solutions in the future.
If you look in the repository there are two solutions currently (VS 2010 and VS 11) the visual studio 2010 solution is the only one up to date.
Another project we may want to work on is creating a Sudoku Puzzle generator. Here is an article I found on doing this http://dryicons.com/blog/2009/08/14/asimplealgorithmforgeneratingsudokupuzzles/
Thanks,
Chris



Hi Chris,
Yes, the SudokuBoard is lean and mean :)
The advantage is:
 easier to copy (because you have to test multiple values)
 The results from find functies are simple types and fast to sort/compare.
I think the generator will work on the same way. (I'll give myself a try to create 1 that support difficulty levels)
So whats the plan? Do you want to create a library with 1 algoritm? of implement more than 1? Also with generating puzzles etc. like a collection?
Or are you trying to find the 'best' way.
Greetz,
Jeroen


Mar 22, 2012 at 5:55 PM
Edited Mar 22, 2012 at 5:56 PM

My vision was to produce a library that can generate and solve puzzles as fast as possible. How we do this is still open for discussion.
I am not opposed to multiple solutions. I have a feeling that some solutions will be very quick, but can't solve all puzzles, while others are slower that can. Your solution is a great starting point with which to compare other solutions.
If a new solution isn't faster than yours, it isn't worth using.
Chris



My resolve tool is built in Excel using VBA which is a much slower language compare to c#, it can solve these 4 puzzles in seconds. You could pick up the workbook from http://vdisk.weibo.com/s/jwPLc
VBR,
Tao


Dec 3, 2012 at 9:24 PM
Edited Dec 10, 2012 at 2:09 PM

Now within 1 second by VBA code. http://vdisk.weibo.com/s/khNwe
Tao

