Originally only for private use within the sudoku wave here in Germany ( for my gf ) I have coded my own sudoku version. I have tried to give it a professional look. Now I will release it after some additional polish such as more sodukos. I would also be nice to add a sudoku solver, but that is another story. How many of you play sudoku ( = would be also interested in contributing your own sudokus and testing it )?

Here a shot:

http://www.jray.de/sudoku.JPG

[EDIT]
Fixed typos.

I enjoy solving difficult sudokus during boring breaks or travel. Given the difficulty and the minimum amount of time I spend on it (some times as little as 5 minutes a day), a sudoku can take me a few weeks to solve it.

However, I prefer the paper version.

As to the "new sudoku" part: Have you tried the sudoku generator? That'd give you nearly infinite supply of puzzles.

edit: fixed grammar.

I am a Sudoku player too, and I've already written a Sudoku generator, but now it crashes all the time ...
Otherwise I would have given you my source code for it.

I normally play Sudoku whenever I'm in my classroom, and bored...

I have written a solver (actually quite easy) , but no generator

[url http://mattsmith.allegronetwork.com/java/Sudoku.html][/url]

I have a solver that was originally based on simple bit manipulations. This is enough for simple Sudoku's, but harder ones require non-local constraints to be recognised, and I wasn't sure how to implement those elegantly. I haven't worked on it for several months though... maybe I'll have a good idea if I have a new look at it.
The fun thing is that it used all constraints it could (conterary to solvers that start with simple patterns and only use more complex ones if the simpler ones fail), which meant that it solved those Sudoku's it could solve in a few (ten or less) sweeps.

Ok, here is download link for a demo version with a single, playable sudoku. If you ask yourself why there is this color rainbow fancy thingie: it is a feature that is not fully implemented yet. The idea is that you can set markers with different colors while pressing Ctrl and clicking left. But that does not work yet, though.

http://www.jray.de/Sudoku.rar

You're Sudoku doesn't run-

SUDOKU caused an invalid page fault in module ALLEG42.DLL at 0187:679eab65. Registers: EAX=00000000 CS=0187 EIP=679eab65 EFLGS=00010246 EBX=00000000 SS=018f ESP=0073fb10 EBP=0073fd28 ECX=00000000 DS=018f ESI=000000ff FS=3f47 EDX=000000ab ES=018f EDI=000000ff GS=0000 Bytes at CS:EIP: ff 50 1c eb f2 8d b6 00 00 00 00 83 ec 0c 8b 44 Stack dump: 000000ff 000000ff 0073fd28 00401ed8 00a71e90 00a71b20 00000000 00000000 00000027 00000026 00000013 0000001a 7801a8fd 00000009 7801a8e8 00000000

micah said:

So you basically want sudoku examples, right?
They come up in the newspapers every day, solve them if you can and write them down, and put it into your sUdOkU game...

cough cough !@#$
Seems familiar?

It's very easy to write a Sudoku solver using a recursive algorithm. That way, it can find a solution to any possible Sudoku puzzle.

Goes about like this:

function solve(x,y)
1) insert number 9 at the given position
2) check if the puzzle is still correct
3) no? insert number 8. check- no? insert number 7... and so on..
4) yes? look for the next blank field and recursively call solve(x,y) for the new position

If 3) gives no for all numbers (there is no possible number for this field), the function just aborts. That way the recursive loop goes back to the last instance of the recursive function and tries the next number there.

If (x,y) points to the last field at 4), the Sudoku is solved and you should somehow completely terminate the recursive stuff (using a global variable, for example).

I once coded it that way and it could solve any Sudoku I put into it, even the "hardest possible" one I found at some Sudoku site. It may not be the fastest algorithm, but you can easily prove that it works for any Sudoku that has at least one solution.

And about your Sudoku game, Micah Crow:

Professional usually means that you use real transparency. The method you use (dithering of fully transparent pixels with non-transparent pixels, or maybe it has some special name?) can only be found in some old 256-color games nowadays.

A sudoku generator really isn't all that hard (especially if you have created a solver) If you start with the fully solved Sudoku:

123 456 789
456 789 123
789 123 456

234 567 891
567 891 234
891 234 567

345 678 912
678 912 345
912 345 678

(Actually you could you any fully solved Sudoku, but I prefer to start from a logical state such as this.)

Then swap two columns within (1-3)(4-6)(7-9) It wont work if you swap 1&5 or 6&7, etc. Do the same thing for the rows. Repeat as necessary.

Remove any one number. If the Sudoku is still solvable with by your algorithm, good. If not, put the number back. For difficulty settings, just choose how many numbers you want to fully remove.

If source code would help, I have a complete Sudoku generator / solver written in Java (and highly commented at that). Just email joshuaarogers@gmail.com

Ok, the reason is very simple. The font is white with grey or black outlines. I would use "real" transparency you would remark these outlines.

[EDIT]

Notice the mousepointer which uses "real" transparency, because it does not have any outlines ( i.e. there is no need to make the color wheel contrastive to the background.

Don't be mean only because I criticised you. Beside the point that we do not have any sudokus in our newspapers ( just in case that your answer was a serious one ) and that I am well able of solving sudokus I do not get the message behind the upper and lower case letters and the bold written word "game". Could you explain that precisely, please?

Further, concerning the crash: What is your system config, desktop color depth and so on?

Checked it on two computers (mine and my friends). Crashed on both.
Config(Mine): Win98SE, 24 bit
Config(Friend): WinXP, 24 bit

Hm that is strange. I must have to do with the 24 bit color depth, although I do the following:

set_color_depth( desktop_color_depth() );

Has anyone else tested it with 24 bit color depth? ( I can't because my GeForce does only allow 16/32... )

I'm surprised. Maybe you didn't try enough puzzles. The problem with the basic backtracking approach is that it can easily get trapped down one branch of the search tree which won't lead to any solutions, or it retries a lot of the same sort of board configurations with only minor variations which won't lead to solutions.

Uh... Isn't the point of the backtracker that it can get out of such situations?

I think the problem is that it can take far too long for a brute-force algorithm to get out of such dead-ends.
Anyway, writing a brute-force Sudoku solver isn't really that challenging... writing one that solves by logic alone is far more interesting.

Or you can mix both brute and logic together...?

Every solver must have brute force to some extent. When one solves by hand a sudoku of the highest difficulty degrees, one often has to make guesses and run into dead ends, then return. This is kind of brute force, right? When an algorithm reaches a point, where no obvious numbers can be added, it could either continue with brute force guessing, or one could come up with an even deeper analysis of the situation. But is it proved that an algo must exist for every situation? As I see it, those presumptive algos would be so complicated and so many that one could almost think of them as brute force. Or anyhow, at some point brute force is the most economic solution.

Not at all! That is to say, if the puzzle is properly constructed, then you never need to guess.

It should not be nescessary, but it can be easier than spotting the pattern that constrains what the correct moves are.

Yes. Brute force (in this context) means try every move and pick the best one (ie, the one that leads to the solution).

I think so, yes. But you have to combine all non-local constraints, which can be very hard.

If they don't involve guessing, then it's not brute force.

Oh, definately: if logic does not work, guess on one of the most constraint squares and try again is definately easier and possibly more economic. It's not the challenge though.

Well, you could speed up the brute force algorithm by weeding down all of the easy choices first. Create an array of flags, turn off flags for every number that cannot occupy a given square, find first square with only one flag set, set the square to that number, and repeat until no "single" flag can exist. At this point, you could create a tree with possible solutions and you should have a significantly less troublesome time (at least time wise) finding the solution. Heck, on some easier puzzles, you won't even need to do this, you could solve it by marking the squares alone...

Then again, if one was to read up on common sudoku solving strategies, the whole brute force create-a-tree-to-find-the-solution step could be replaced with more "elaborate" logical mechanisms for filling in the gaps.

So one can always use some flag algo that in any sudoku with only one solution, in any situation, always finds at least one space with only one possible number. Like:

do
   zeroflag_all_impossible(my_sudoku);
   set_the_numbers_in_all_spaces_with_only_one_flag(my_sudoku);
while (my_sudoku->not_ready());

As I see it, a properly constructed sudoku only has to fulfill the requirement that it has only one solution. Not requiring the solver to make guesses is in itself not a requirement for a properly constructed sudoku. I mean, even if the sudoku requires guessing, it might still have only one solution and therefore it would be properly constructed.

I don't think that's true, I think a sudoku that has exactly one solution can never require a guess, but I lack the mathematical skill to even attempt to prove it.
I think you only need to guess if you fail to recognise some pattern (higher order swordfish, say) that tells you that some numbers are impossible. A human may very well detect such a pattern more easily by trial and error, but computers are not human.

You don't think it's true, I do think it's true. Let's wait for a mathematical proof. I kind of wish I'm wrong. But what I tried to explain was that the qualities of the definite algo might be so complex that it might be hard to distinguish it from brute force and guessing.

I mean, consider the flagging thing. First you set all nine flags of one empty space. Then you check all other spaces in that room and reset flags. Then you check all other spaces in same row, then ditto for same column. Well, when you first set the flags, you kind of guessed that all nine numbers were possible. Then, after some restraining zeroflagging, you kind of guessed that this or that number is the right number, and so on. These are not real guesses, but the more complex the algo is, the more you might have to deal with logic branches that could be considered guesses.

For instance, you can check if three particular free cells have the same three flags, meaning these three corresponding numbers cannot occure in any other free cell in that room, column or row. Well, checking all combinations of three free cells might result in no result. So this whole branch has been a dead end, just like guessing that one free cell might be 9.

I think that even if you solve it using logic you still need an algorithm to search for the appropriate solution. As Johan said I think it requires back-tracking when searching for said solution. I've got no proof either though so it's up for debate.

If a Sudoku gets to the point where no more numbers can be figured out (assuming it isn't finished at this point) then the puzzle has more than one solution. Something that a self-respecting Sudoku creator would not do.

The idea with the flags is correct. It's a good approach. I've built a solver / builder in Java using that approach. It takes only a second to solve the puzzle. Good thinking on the part of whoever suggested it.

So you've built a Sudoku-solver which doesn't need to do any form of search? In each step it always knows what to do without looking at future steps (ie seatch)? Care to fill us in on how it works? And perhaps point us to your solver if its available on the net? It would be interesting material.

I'm not sure that I fully understand your question, but yes, I have built a solver. For each square it keeps track of what it can be and what it can't be. Simple deduction yields the answers. Much in the same way that a human would. No guessing is needed.

If you would like the program, just email me at joshuaarogers at gmail dot com. (Notice there is an a between joshua and rogers). I hope that it helps. Thanks.

My solver works by operating on bits: for each of the squares, bits are set for which numbers `may be' there. For each column, row and mini-block we have the same. A sequence of logical ands and xors then eliminates impossible combinations, after which bitshifts and logical ors construct the new row and column bitfields, whichare used in the next iteration. It gets a bit more complicated if the constraints are non-local, in which case simple shifts no longer do the trick, at least not easily.
The advantage of the method is that it eliminates all unknowns that it can in one sweep, and automatically applies `difficult' constraints as well as easier ones. It will either solve the puzzle in a split second in fewer than ten iterations, or fail in a similar number of iterations.

Well, it turns out that it happens quite often that you cannot solve a puzzle via pure "flagging" alone. Take this example:

000|200|304
061|300|092
302|050|000
---+---+---
420|805|100
108|000|207
005|9X2|046
---+---+---
000|090|701
610|004|980
509|001|000

It becomes quite obvious that the X should be the number 1. Unfortunately, simply "flagging" what a blank can/cannot be doesn't provide you with a definate answer in this case, without doing a block uniqueness test. (Since it is the only square in the given block that can be the value 1, it must be the value 1). Unfortunately, by simply marking the squares that cannot be one from the row/column/coexist on same block rules, you cannot deduce this without another step.

Of course, this is easily fixed by occasionally doing a uniqueness test for all of the squares and updating them accordingly. But then you run into puzzles like this: (websudoku evil puzzle #8,873,319,999)

040|050|000
600|000|005
020|000|867
---+---+---
000|001|300
090|384|050
006|700|000
---+---+---
387|000|010
500|000|002
000|070|090

The algorithm so far can only fill in the puzzle to this point, then dies because of a lack of information:

040|050|000
600|000|005
025|000|867
---+---+---
050|001|300
090|384|050
036|705|000
---+---+---
387|000|010
509|000|002
000|070|090

So, no, you cannot solve the puzzle simply by "flagging" possible solutions using the core rules.

Here is the python program I've been using so far to solve the puzzles:

I'm going to look into the more advanced solution methods and add them to the program.

EDIT:

Yes, if the constrant's are not local, it is quite difficult to solve the puzzle using bits (or sets, as I have in the above example) alone without adding some more "interesting" logic.

EDIT2:

As for the more simple puzzle, it looks like this above program takes only 3 passes to solve it (three rounds through the while loop in the solve function) . And it only takes 3 passes before it realizes it cannot complete the harder puzzle as well.

Could someone translate that program into C so I can read it.

Well, you could always just learn python. It is great for just hacking up stuff. I will admit though, some of the stuff I used in the above program is rather odd (yield, lambda's, [foo for bar in foobar()], reduce, filter)... . I'll be the first to admit some of those functions don't apply cleanly in C though (you can do a lot of them in C++ using the STL). (No, I'm not saying you can't do them in C, I'm saying that you can't do them this easily in C)

That's what I meant by saying you need non-local constraints.
The good thing about the algorithm is that it is fast if it works. I should really find the time to update my little solver...

What you get which can solve all Sudoku's is a good search with back-tracking. I think you could use an A* and measure the distance to the goal by the number of local constraints. So that it gets "spot on" if there are only local constraints all the way to the solved puzzle. In that case you will also get an optimal search (as it's one of the features of a correctly implemented A*).

It's a SUDOKU. Even an unoptimized brute force solver needs less than one second for one of the harder puzzles (which your solver cannot even solve). I don't say that it is a sophisticated solution, but it works perfectly, and coding it takes about half an hour.