Sudoku Algorithms

Developer
Mar 16, 2012 at 4:42 AM

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.

Coordinator
Mar 16, 2012 at 5:20 AM

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.

Developer
Mar 21, 2012 at 11:03 AM
Edited Mar 22, 2012 at 2: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):

HardestSudokusThread-02085;Discrepancy: 1381 ms
golden nugget: 1490 ms
HardestSudokusThread-00245;Red_Dwarf: 895 ms
HardestSudokusThread-01418;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;
		}
	}
Coordinator
Mar 22, 2012 at 12:08 AM

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. 

Developer
Mar 22, 2012 at 10:09 AM
Edited Mar 22, 2012 at 2: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'.

 

orderby count descending

 

So, this is almost the same as the solution you explained. Only difference is recursive vs queued. 

Kind regards,
Jeroen

Coordinator
Mar 22, 2012 at 3:51 PM

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/a-simple-algorithm-for-generating-sudoku-puzzles/

Thanks,

Chris

Developer
Mar 22, 2012 at 4:32 PM

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

Coordinator
Mar 22, 2012 at 4:55 PM
Edited Mar 22, 2012 at 4: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

Dec 1, 2012 at 4:46 PM

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 8:24 PM
Edited Dec 10, 2012 at 1:09 PM

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

Tao