Sudoku Helper 1.3

There are huge changes in the solving algorithm. It now solves 9×9 Sudoku (or finds out that it is unsolvable) in less than 15ms. It also solves 99% of Sudoku 16×16 with 40 random numbers in less than 1 second. The remaining 1% is solved in over 5 minutes, but I have also found such a Sudoku that my algorithm was unable to solve in 30 minutes. If you like challenges and would like to show me that your skills are much better than my programming skills, feel free to solve it – you will find it below. Solving algorithm also now has a 2 second timeout, so the program will no longer freeze, but will display a message “too complex puzzle”. I am going to implement over the weekend a Sudoku generator that generates puzzles with one unique solution. But for now, here is a jar file and here is the code.

Patchnotes:

  • added: advanced automatic suggestions removal.
  • added: if solving/validating the puzzle takes more than 2 seconds, the puzzleis considered too complex and the algorithm stops.
  • fixed: solving algorithm improved – it now undoes its changes rather than making a grid’s copy before each change. It works about twice as fast as the previous algorithm, and moreover do not use that much memory.
  • fixed: sudoku is now in a scroll pane – it is possible to play 16×16 Sudoku in low screen resolution.
  • changed: filling a cell clears all suggestions in this cell if auto suggestions remove is on – it can be undone.

Challenge for you:
This is the puzzle my algorithm was unable to solve in over 30 minutes. Show that you are better!

How do solving algorithms work:

The grid consists of N*N x N*N cells (e.g. in Sudoku 9×9 N = 3 and there are 81 cells). The zone is a row, a column or a square, it contains N*N cells. The square is a NxN large part of the grid (in 9×9 there are 9 squares of size 3×3). The neighbours are all those cells that share the zone with the cell. Also each cell contains a filled number and the set of possibilities (candidates).

1. Basic suggestions removal:

for each cell C
	for each possibility P in C
		if any neighbour of C is filled with P
			remove P from C' possibilities

2. Basic auto fill:

for each cell C
	if there is only one number in C' possibilities
		fill it in

3. Advanced auto fill:

for each zone Z
	for each number N
		if there is no N in Z and there is only
		one cell C in Z where N can be put
			fill C with N

4. Advanced suggestions removal:

for each cell C
	for each zone Z that contains C
		for each cell D in Z
			if there are exactly X cells in Z
			where X is the number of D's possibilities
				remove all D's possibilities
				from all other N*N-X
				cells' possibilities in Z

About Jaroslaw Pawlak

I have done MSci in Computer Science at King’s College London and currently work as Software Engineer specialising in Java. I spend most of my time in front of computer improving my programming (and other) skills or just relaxing with a good game. I also train some sports but at the moment I am not a member of any club. I love cycling and volleyball, but I have also played a lot of football, tennis and trained martial arts.

Posted on March 16, 2012, in My Projects and tagged , . Bookmark the permalink. Leave a comment.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: