Ossudo - ultimage open source sudoku

Saturday, August 26, 2006

Creating a new Sudoku

Creating a new Sudoku is a two step process:
  • First, create a complete 9x9 valid array
  • Then clear cells

Creating a complete valid array

Creating a correct full array is not that difficult. You start at upper left corner, set a value at random, move on to the next cell, see what values are still allowed, chose one at random and proceed.

Of course, as you move on, there are fewer and fewer possible values. Every time you set one cell, you must update possible values for rows, columns, blocs, and finally for individual cells.

So you move on this way, picking values at random, among those that remain available. At some points you get into a deadend, where there are no candidates left for a given cell. This usually occurs when you reach row 5 or 6.

At this point, you need to track back and start again. My algorithm makes a simple assumption, which I have not proved, but turns out to never fail: going back at the last complete bloc level row will allways get you out of deadends. This means if you encounter a deadend at row 6 for instance, you go back to row 4 (because row 4 is the beginning of the second bloc-row, row of 3x3 blocs), if you have reached row 7 and hit a deadend, then you start over at row 7 only (because row 7 is the beginning of the third bloc-row).

Well, this seems to work and is quite faster and also simpler then a real track-back trial-and-error algorithm.

Clearing cells towards a playable Sudoku

So once you have built a complete array, you start clearing cells.

A good Sudoku should have as many empty cells as possible. This means it is not possible to clear any one cell without getting a invalid Sudoku, one with more than a single solution.

It is definitely wrong to believe a difficult Sudoku is one with a lot of empty cells, and an easy Sudoku is one with not-too-many empty cells. It has nothing to do with empty cells. A Sudoku where more cells could be cleared is not a good Sudoku, although it's of course not as bad as one that would have two solutions.

Friday, August 25, 2006

PortableApps' Pocket Sudoku (v1.1.7)

What I like
  • It’s usability is quite above that of Windows Sudoku: values are entered at keyboard, changing cells is done with arrow keys, which seems obvious, but Windows Sudoku is missing this.
  • It has a scalable graphic interface, with fonts changing size as you resize the form. I had done the same on Ossudo.
  • It allows you to enter candidate values in empty cells. This is the most interresting feature in this application. Candidate values are displayed at their conventionnal spot within the cell. This is definately one I wish I had coded, because indeed you cannot actually play a Sudoku program, searching for a solution by yourself, if you don’t have this, because you don’t have pencil and eraser.
  • And of course it’s pretty compact too, and easy to deploy.

What's missing of weak
  • It is quite weak on algorithms, worse than Darren's actually. If you generate a new Sudoku at difficult “hard”, quite often it is not a valid Sudoku, that is to say it has more than one solution. This is quite a major shortcomming for a Sudoku player. I haven’t looked at the source code yet, but I suspect it just clears a number of cells randomly, without checking that there is a single solution. If it so, then it’s really a flawed approach. Actually it would mean Pocket Sudoku does not have solving algorithms at all. Yes that’s probably it.
  • It does not have hints at all. Same reason, very likely.
  • You cannot enter a Sudoku by yourself, one that you have read in the paper.
  • You cannot print, so you cannot take a Sudoku with you unless you have your laptop.
  • You cannot save a Sudoku, nor read one of course.

Darren Cole's Windows Sudoku Puzzle Game (v2.5)

What I like :
  • Reading and exchanging Sudokus on the web is a great idea. I don’t plan on adding this however, I want to concentrate on algorithms and usability.
  • Multiple player contests is a nice feature, as well as having a timer. The timer I might do also, since it’s pretty easy.
  • The executable file is very compact and installation is so fast. Since I develloped in .Net, I don’t think I can make such compact distributions. Unless I could assume users have .Net 2 framework installed.
  • You can load and save games.

What's missing or weak :
  • The way values are entered is awful. Clicking on cell and number and not being able to use keyboard is really unfriendly.
  • It does not have enough algorithms coded. I entered an expert-level Sudoku and asked it to be checked, the answer was: “Could not check Sudoku”. And since it could not solve it, it could not provide hints as well.
  • It does not really give hints anyway, it only gives you the value in a random cell. Most of the time that is really not what you want. What you want is a true hint, some indication of where to search and how to search, and maybe you’ll find the value yourself.
  • It does not show candidate values, nor allow you to set them.

The features of Ossudo

Here are the main features of Ossudo:
  • Where algorithms are concerned
    • It has many, almost all, solving algorithms, that is 6 at the current time. I did find some http://www.angusj.com/sudoku/hints.php that I have not coded yet, but they are so seldom needed that I wonder if it’s worth it.
    • It builds new Sudokus and evaluates them by solving them. In order to solve a Sudoku, it tries the easiest algorithms first, as long as it can fill cells, then turns to a more difficult algorithm, finds another cell, and goes back to easy ones if possible. Thus, when a Sudoku is solved, the evaluator knows exactly how many runs of each algorithms it took, from easiest to most advanced. When all algorithms have been applied and no cell can be determined, it does some trial-and-error as well, choosing a cell with the fewests possible candidates. It does as little trial and error as possible, meaning after trying just one cell, it will turn back to algorithm solving. The number of times that trial and error was required is also recorded and impacts evaluation. Any board that requirest trial-and-error is at minimum “expert”, and if there were too many, it is called “crazy”.
  • Where user interface, playing features and usability are concerned
  • It optionnaly provides hints as you play. Either a single hint or many hints, on all cells that can be found with simple algorithms at a given time.
  • It will also tell you the value on a given cell, if you ask.
  • It will tell you exactly and precisely which algorithm it applies and which algorithms are necessary to solve a given Sudoku.
  • Based on that, it gives an accurate assessment of difficulty level, finer than just (easy, medium, hard).
  • It lets you enter any Sudoku, and will analyse and evaluate it for you, telling you if it’s correct or not.
  • It has a scalable user interface, with scalable fonts.
  • It will save and load Sudokus as Xml files.
  • It allows you to print a Sudoku, as it is on screen, that is with or without hints, and possible values.
  • It optionnaly will display possible values for each cell.
  • Since it can solve absolutely ANY Sudoku, no matter how hard, it knows which values are correct, and will optionnaly tell you as you proceed.
  • Where environment and source code are concerned
  • It’s written in C# for .Net 2.0, using Visual Studio 2005. I wish I could port it to Java/SWT as well, it should not be too difficult since user interface is quite compact, most of the code is algorithms.
  • I tried to make it as clean as possible, with a true object oriented approach. The main class hierarchy is as follows:
  • SudoArray: The basic 9x9 array of cells, with get/set methods and little more.
  • SudoArrayWithVectors: SudoArray. An array together with a permanent update of a number of vectors that hold values found in rows, columns and blocs, as well as remaining candidate values. No real algorithm at this level, but exceptions thrown if an attempt is made to set a cell incorrectly. Not because it is not the final value, final values are not known by this class, but because it breaks some of the rules.
  • SudoFinder: SudoArrayWithVectors. It holds all the solving algorithms. Maybe I could break it a little more, separating the trial-and-error from rule-based.
  • SudoPlayer: SudoFinder. It holds information for a game being analysed and played. The moves that where perfomed, the final values. Little added-value actually.
  • SudoMaker: SudoFinder. It is the class that builds new Sudokus. It relies on all algorithms to check Sudokus as they are made up. It clears cells as long as it can, while still having a unique solution. This is a big difference with Pocket Sudoku for instance: a difficult Sudoku is not one with many cells cleared, it is one which requires difficult algorithms to be solved.

Ossudo, yet another Sudoku ?

There are 117 games of Sudoku in sourceforge.net.

When I discovered this, after I’d spent some of my holidays writing Ossudo, I found it pretty depressing.

But then I looked at some of the most popular games out there, and felt better. Ossudo will bring you a little more than most of them, even though on some other aspects, it does lack some of their features.

Overall, it seems to me Ossudo has better algorithms than the two I’ve looked at, that seem to be the most popular out there: Windows Sudoku and Pocket Sudoku.

Because this is a blog, as you may have noticed, posts are in reverse order compared to what you might expect. So here is a little table of content: