Sudoku
BlitzMax Forums/BlitzMax Programming/Sudoku
| ||
| I'm making a Sudoku game and it looks like quite a few others are too. Blitz is really good for this too. Check out this website, it has some really good info on it. http://www.setbb.com/phpbb/viewforum.php?f=3&sid=e5b841fa066c45840d20d4cc1d9ea160&mforum=sudoku Looks like sswift found my secret site too hehe. |
| ||
| sswift, I can tell you Ruud and the gang there know DLX very indepth. Understanding DLX takes a lot of patience. Especially when trying to implement the 729x324 matrix. It just takes time to "get it". I hounded those guys for about a month straight asking all kinds of questions just like you're doing and then the light bulb finally went on. Soon as I get home I'll throw up a ss of my sudoku game...it's about 80% complete. |
| ||
| Chroma: I was just coding a Sudoku algorithm for someone else who hired me to do it. It only needed to be fast enough for generating puzzles in realtime, and I didn't want to make it so complicated that they couldn't understand it. So no need for me to figure out dancing links. I don't have time to play around with it anyway. Also, it's more fun to discover algorithms than implement them. :-) |
| ||
| Generating sudoku's is the easy part. The difficult part is generating sudoku's that have only 1 unique solution and have symmetrical clues and varying diffficulty levels. I have this all done and it was quite time consuming. I just wanted to avoid plagiarism, meaning just using someone's existing code verbatim. So I learned how it worked and wroted my generator and solver in that context. |
| ||
| Chroma: It's not a proper Sudoku if it has more than one solution. :-) My algorithm does the job by solving a blank sudoku, and then removing squares at random, and checking to see if there is more than one solution to the resulting puzzle. That's what I meant by "fast enough". It has to solve it so many times when generating one. It can't do symmetrical clues, but I think it would take a lot more time to generate a puzzle if you wanted to do that. I guess some people try to get it symmetrical and then add a few non-symmetrical clues as needed to "fix" it. But if you wanted a specific pattern, that might involve generating puzzles and then seleting all the squares outside the pattern and checking to see if the puzzle then has one solution. If not, generate a whole new puzzle. Not too difficult, but I don't know how fast it would be. Alternatively I guess you could write a different sort of "solver" which permutates through all possible values, and at each juncture, checks to see if the resulting puzzle has one solution. I'm really not convinced that would be faster though. It might even be slower. Because now instead of creating a set of clues that you know generate one or more valid solutions, you're now generating clues which may have no solution at all. And that could well force the solver to try every single combination of numbers, which would take a very long time even for a single try. |
| ||
| "It's not a proper Sudoku if it has more than one solution. :-) " Right, that's what I stated in my post right above yours. Not sure what I said that led you to think I didn't know that. :-) |
| ||
| read an article the other day where a guy came up with a formula for something... sudoku unrelated... and when applied to a sudoku grid it solves it. Not just one grid. ALL GRIDS. The game is over. It's been cracked. :) |
| ||
| Kanati: I read that article. My sudoku solver ALSO solves ALL GRIDS. Oh, did I forget to mention it has to solve them one at a time? Oopsie! The same goes for this guy's solver. You can't solve all grids simultaneously. That would take a trillion terrabytes of memory and a quantum computer. :-) What was neat about what the guy did was he applied a sudoku-like solving algorithm to the problem of solving the offsets of the waves for an inverse fourier transform. And the way he did that, was by figuring out that he could specify the solution to the puzzle as being one where all spaces outside some object in the center should be 0. I'm not sure though what rule this guy applied to make this work. I don't undertsand fourier well, but it seems like one would not get 0's around the edges until one had added up a lot of waves. And that's no good, because then you might have to do some weird minimuzing algorithm which just finds the number that brings you closest to the solution, and who knows if that's possible. This guy, apparently, but not I. :-) Anyway when i read that article I wondered if perhaps it would have applications in deblurring images. |
   |