This thread is locked; no one can reply to it. 1   2
 Sudoku
 Mordredd Member #5,291 December 2004 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 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 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 I normally play Sudoku whenever I'm in my classroom, and bored... Click Here For My WebsiteTwo 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
 Evert Member #794 November 2000 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 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.
 Lucid Nightmare Member #5,982 July 2005 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 !@#\$Seems familiar? Click Here For My WebsiteTwo 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 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 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 789456 789 123789 123 456234 567 891567 891 234891 234 567345 678 912678 912 345912 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 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 Checked it on two computers (mine and my friends). Crashed on both. Config(Mine): Win98SE, 24 bitConfig(Friend): WinXP, 24 bit Click Here For My WebsiteTwo 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 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... )
 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? if(Windows.State = Crash) Computer.halt();
 Evert Member #794 November 2000 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 Or you can mix both brute and logic together...? Click Here For My WebsiteTwo 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 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 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 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 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: Allegro Development Installation, Setup & Configuration Allegro.cc Comments Off-Topic Ordeals The Depot Game Design & Concepts Programming Questions Recent Threads