Allegro.cc - Online Community

Allegro.cc Forums » Game Design & Concepts » Sudoku

This thread is locked; no one can reply to it. rss feed Print
 1   2 
Sudoku
Mordredd
Member #5,291
December 2004
avatar

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.

Indeterminatus
Member #737
November 2000
avatar

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.

_______________________________
Indeterminatus. [Atomic Butcher]
si tacuisses, philosophus mansisses

Michael Faerber
Member #4,800
July 2004
avatar

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.

--
"The basic of informatics is Microsoft Office." - An informatics teacher in our school
"Do you know Linux?" "Linux? Isn't that something for visually impaired people?"

Lucid Nightmare
Member #5,982
July 2005
avatar

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

Click Here For My Website

Two Golden Rules of life- Firstly, I'm always right and secondly, if you think otherwise, slap your face and read rule number one again!

Matt Smith
Member #783
November 2000

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

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

Evert
Member #794
November 2000
avatar

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.

Mordredd
Member #5,291
December 2004
avatar

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

Lucid Nightmare
Member #5,982
July 2005
avatar

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:

Quote:

How mnay of you play sudoku ( = would be also interested in contributing your own sudokus and testing it )?

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 !@#$:o
Seems familiar?

Click Here For My Website

Two Golden Rules of life- Firstly, I'm always right and secondly, if you think otherwise, slap your face and read rule number one again!

Simon Parzer
Member #3,330
March 2003
avatar

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:

Quote:

I have tried to give it a professional look.

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.

Joshua Rogers
Member #2,499
June 2002
avatar

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

---

Now approaching 0.1 forum posts per year!

Mordredd
Member #5,291
December 2004
avatar

Simon Parzer said:

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.

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.

Lucid Nigthmare 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...

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?

Lucid Nightmare
Member #5,982
July 2005
avatar

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

Click Here For My Website

Two Golden Rules of life- Firstly, I'm always right and secondly, if you think otherwise, slap your face and read rule number one again!

Mordredd
Member #5,291
December 2004
avatar

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

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

Peter Wang
Member #23
April 2000

Quote:

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.

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.

Wetimer
Member #1,622
November 2001

Quote:

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,

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

<code>if(Windows.State = Crash) Computer.halt();</code>

Evert
Member #794
November 2000
avatar

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.

Lucid Nightmare
Member #5,982
July 2005
avatar

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

Click Here For My Website

Two Golden Rules of life- Firstly, I'm always right and secondly, if you think otherwise, slap your face and read rule number one again!

Johan Halmén
Member #1,550
September 2001

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.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Years of thorough research have revealed that the red "x" that closes a window, really isn't red, but white on red background.

Years of thorough research have revealed that what people find beautiful about the Mandelbrot set is not the set itself, but all the rest.

Evert
Member #794
November 2000
avatar

Quote:

Every solver must have brute force to some extent.

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

Quote:

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.

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

Quote:

This is kind of brute force, right?

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

Quote:

But is it proved that an algo must exist for every situation?

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

Quote:

As I see it, those presumptive algos would be so complicated and so many that one could almost think of them as brute force.

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

Quote:

Or anyhow, at some point brute force is the most economic solution.

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.

Carrus85
Member #2,633
August 2002
avatar

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.

Johan Halmén
Member #1,550
September 2001

Quote:

if the puzzle is properly constructed, then you never need to guess.

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.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Years of thorough research have revealed that the red "x" that closes a window, really isn't red, but white on red background.

Years of thorough research have revealed that what people find beautiful about the Mandelbrot set is not the set itself, but all the rest.

Evert
Member #794
November 2000
avatar

Quote:

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.

Johan Halmén
Member #1,550
September 2001

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.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Years of thorough research have revealed that the red "x" that closes a window, really isn't red, but white on red background.

Years of thorough research have revealed that what people find beautiful about the Mandelbrot set is not the set itself, but all the rest.

kentl
Member #2,905
November 2002

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. :)

Joshua Rogers
Member #2,499
June 2002
avatar

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.

---

Now approaching 0.1 forum posts per year!

 1   2 


Go to: