Sudoku!

skylineaddict · Jan 7, 2011, 05:05 PM

Hey guys. Over the break I decided to make a Sudoku game. It's pretty basic and not too fancy, but I think it's the best I could do with my current level of knowledge. It even uses the standard Java GUI components including the buttons and all that. I may change that if I find the time.

For any Sudoku fans out there, could you do my a favor and test it out? For any programmers, could you critique it a little? Thanks a bunch.

http://krazyboi.pbworks.com/f/blahbot.jar

I promise there's no malicious code in there. I'm too stupid to write anything that complicated.

skylineaddict · Jan 9, 2011, 09:21 PM

Latest build with some added functionality and fixed bugs. Same link as above.

IvanV · Jan 9, 2011, 10:05 PM

Very nice. Also, this version looks better than the previous one (mainly the numbers that are predetermined now look better). It works fine. It would be nice if the player could navigate the grid with the cursor keys and also each puzzle should have exactly one solution (which isn't the case).

skylineaddict · Jan 9, 2011, 10:24 PM

Quote:

Originally Posted by IvanV

Very nice. Also, this version looks better than the previous one (mainly the numbers that are predetermined now look better). It works fine. It would be nice if the player could navigate the grid with the cursor keys and also each puzzle should have exactly one solution (which isn't the case).

I'll work on cursor navigation.. I didn't think of that. As for exactly one solution, it is incredibly hard (At least by my understanding) to generate a random puzzle that has only one solution. My randomizing algorithm is very simplistic, but it is to save programming time and was done for the sake of efficiency. Regardless, I will look up how publication companies generate their puzzles and see if I can do something similar.

IvanV · Jan 9, 2011, 10:47 PM

Well, there's a challenge for you!

Seriously though, I've seen a lot of Sudoku programs with the same problem, so I trust you that it's a hard one. Perhaps a reverse approach would work best:
1. generate a random fully populated grid;
2. pick a random cell, check if clearing it would create ambiguity and, if not, clear it;
3. repeat step two until there are enough cleared cells;
4. save puzzle for later use.

Takaharu · Jan 9, 2011, 11:27 PM

Have you got a webpage you can stick it on? It'd make it easier to test.

skylineaddict · Jan 9, 2011, 11:32 PM

Quote:

Originally Posted by IvanV

Well, there's a challenge for you!

Seriously though, I've seen a lot of Sudoku programs with the same problem, so I trust you that it's a hard one. Perhaps a reverse approach would work best:
1. generate a random fully populated grid;
2. pick a random cell, check if clearing it would create ambiguity and, if not, clear it;
3. repeat step two until there are enough cleared cells;
4. save puzzle for later use.

That's how I do it right now, except I don't check for ambiguity. I don't even know how to do that.

The hardest thing for me was generating a random grid. I don't know if you program, but if you do, give it a shot. Using Java, I ran into so many problems trying to generate random grids that I finally just chose a hack solution that generates a semi-random grid. In case you haven't noticed, the second and third square in the first quadrant will almost always be 1 and 2 respectively.

**temeteus82** · Jan 9, 2011, 11:55 PM

hey could you make it as webpage that runs that applet?

IvanV · Jan 10, 2011, 12:08 AM

Quote:

Originally Posted by skylineaddict

That's how I do it right now, except I don't check for ambiguity. I don't even know how to do that.

The hardest thing for me was generating a random grid. I don't know if you program, but if you do, give it a shot. Using Java, I ran into so many problems trying to generate random grids that I finally just chose a hack solution that generates a semi-random grid. In case you haven't noticed, the second and third square in the first quadrant will almost always be 1 and 2 respectively.

Yeah, I started thinking about how I'd do it and the data structures just kept getting more and more entwined.

Checking for ambiguity is simple, I once made (but can no longer find) a very simple Sudoku solver for my sister which just went from left to right and from top to bottom and for each empty cell tried values from 1 to 9 until it found a number that can stand there (I just checked if it conflicted with an existing number); when it found a cell it can't fill, it simply backtracked to the previous cell it filled and tried bigger values for it (and possibly backtracked some more if neccessary). After it finished, that is after it found the first solution, I'd just make it backtrack from the last cell as if no solution had been found and if it produced another result the grid was ambiguous. Not very efficient, but not too slow either and shouldn't be a problem to make.

skylineaddict · Jan 10, 2011, 12:26 AM

That definitely isn't very efficient.. But, if people want one-solution puzzles, I guess it's a sacrifice they could make. I'll put that on the bottom of my to-do list. First I'm going to get cursor navigation and UI tweaks done.

skylineaddict · Jan 10, 2011, 12:27 AM

Quote:

Originally Posted by temeteus82

hey could you make it as webpage that runs that applet?

I don't know how to do that.. I don't have a website or anything, and I don't think pbworks will let me do that through their server. Are you having trouble running it?

IvanV · Jan 10, 2011, 12:38 AM

Applets get downloaded and executed on the client machine (but inside a web browser window), so they don't require anything special, any server which hosts a static HTML page can host a page with an applet. You just load the applet together with the HTML page containing the appropriate HTML tags onto the server and that's it.

EDIT: The solving algorithm I described isn't pretty, but it's a maximum of 9 possibilities for each cell of the 9x9 grid. That's a maximum of 9x9x9=729 function calls to produce a single solution; a function call compares a value against a maximum of 20 other cells, giving a total of less than 15,000 operations, which is not much at all for today's computers.

skylineaddict · Jan 10, 2011, 12:52 AM

Quote:

Originally Posted by IvanV

Applets get downloaded and executed on the client machine (but inside a web browser window), so they don't require anything special, any server which hosts a static HTML page can host a page with an applet. You just load the applet together with the HTML page containing the appropriate HTML tags onto the server and that's it.

EDIT: The solving algorithm I described isn't pretty, but it's a maximum of 9 possibilities for each cell of the 9x9 grid. That's a maximum of 9x9x9=729 function calls to produce a single solution; a function call compares a value against a maximum of 20 other cells, giving a total of less than 15,000 operations, which is not much at all for today's computers.

Yeah, that isn't much at all. The solver in my program uses brute force, so it can take anywhere from 81 to over 6 million iterations to solve a puzzle. So far, though, the hardest puzzle it's ever taken on has taken just over a 100 seconds. Usually it takes more time to redraw the grid than it does to solve the actual puzzle.

IvanV · Jan 10, 2011, 01:05 AM

On second thought, I have vastly underestimated the maximum number of operations of my algorithm (I failed to account for backtrack - only goes to show how long it's been since I solved a serious algorighmic problem). Still, I remember the program producing a single solution instantly, regardless of the difficulty.

skylineaddict · Jan 11, 2011, 11:11 PM

Latest version has updated UI and you can now navigate the grid by using arrow keys (The ones that aren't on the number pad if you have one. I'll add that later). The solution for it isn't very intricate and you may have to get used to the way the cursor jumps around. Once I can think of something better, I'll change it up a little.

Again, the link is the same as the one in the first post, but I'm posting it here to save you from scrolling up.

http://krazyboi.pbworks.com/f/blahbot.jar

skylineaddict · Jan 14, 2011, 04:28 AM

Redid the randomizing algorithm and fixed an issue with the load binary function. Random grid now takes a lot less time (Next I will be implementing code that generates a grid with only one solution).

IvanV · Jan 14, 2011, 01:42 PM

Nice progress.

skylineaddict · Jan 16, 2011, 01:37 AM

I found a way to generate single-solution puzzles. Problem is they take way too long to generate. I'll keep the current random generator in the application, but I will upload a bunch of files containing single-solution puzzles to my Wiki. That will save everyone the trouble of waiting for a few minutes to get a puzzle.

skylineaddict · Feb 5, 2011, 07:04 AM

Sudoku by Ankit Patel

Alright, I've updated the program a little. It now accepts puzzle archives that contain puzzles with a single solution (That claim hasn't been tested by people, but my algorithm in theory generates single-solution puzzles. I hope that someone can test that for me). To load puzzle archives:

-Download one of the files below (Each one contains a thousand puzzles)
-Click on the load button
-Select (*.vsky) as the file you want to open
-Select the file you downloaded
-The menu option "Puzzle Set" should be enabled now
-Click on that, and then click on "Load puzzle from set"

Expert puzzles aren't available yet because they take a really long time to generate (Around 24 hours). The last bunch I generated were invalid because of a stupid mistake in my generation algorithm. I will update the links once I get them generated though.

That will open a random puzzle from that set. I will be implementing code later on that deletes any puzzles that have already been viewed or solved from the archive so that you won't see them again (Hence the menu option "Stop using puzzle set" not working.

Other things added: Tooltips on the buttons, a better way of navigating the grid using arrow and tab keys (Shift + Tab needs to be added so that you can traverse backwards. I shall be working on that soon).

Easy Puzzles

Medium Puzzles

Hard Puzzles

Let me know if the links aren't working or if you want more puzzle files.

skylineaddict · Feb 6, 2011, 10:53 PM

I made a puzzle creator (That should create single-solution puzzles) and viewer earlier and I figured I'd share it with you guys. I'll see if I can add a function that can print the puzzles later on (I'll have to do some more research to get that).

Puzzle Creator by Ankit Patel
To generate puzzles, type in a puzzle number and difficulty (1-4) and click generate. Choose where you want to save and voila!

Puzzle Viewer by Ankit Patel
First, load a file, then type in a number based on the bounds displayed above the text field and press enter.

The viewer is compatible with the files I posted earlier.

Jan 7, 2011, 05:05 PM	#1
skylineaddict Sleep Deprived Ant Join Date: Aug 2008 Posts: 895 Rep Power: 136 System Specs	Sudoku! Hey guys. Over the break I decided to make a Sudoku game. It's pretty basic and not too fancy, but I think it's the best I could do with my current level of knowledge. It even uses the standard Java GUI components including the buttons and all that. I may change that if I find the time. For any Sudoku fans out there, could you do my a favor and test it out? For any programmers, could you critique it a little? Thanks a bunch. http://krazyboi.pbworks.com/f/blahbot.jar I promise there's no malicious code in there. I'm too stupid to write anything that complicated. __________________ Couldn't come up with anything snappy to say, so I'll just be awkward.

Jan 9, 2011, 09:21 PM	Thread Starter #2
skylineaddict Sleep Deprived Ant Join Date: Aug 2008 Posts: 895 Rep Power: 136 System Specs	Re: Sudoku! Latest build with some added functionality and fixed bugs. Same link as above. __________________ Couldn't come up with anything snappy to say, so I'll just be awkward.

Jan 9, 2011, 10:05 PM	#3
IvanV HH Assassin Guild Member Join Date: Dec 2004 Posts: 5,921 Rep Power: 336 System Specs	Re: Sudoku! Very nice. Also, this version looks better than the previous one (mainly the numbers that are predetermined now look better). It works fine. It would be nice if the player could navigate the grid with the cursor keys and also each puzzle should have exactly one solution (which isn't the case). __________________ If anyone has Portal 2 and hasn't played the co-op and wants to do me a favour, let me know (PM me or whatever). Last edited by IvanV; Jan 9, 2011 at 10:11 PM.

Jan 9, 2011, 10:47 PM	#5
IvanV HH Assassin Guild Member Join Date: Dec 2004 Posts: 5,921 Rep Power: 336 System Specs	Re: Sudoku! Well, there's a challenge for you! Seriously though, I've seen a lot of Sudoku programs with the same problem, so I trust you that it's a hard one. Perhaps a reverse approach would work best: 1. generate a random fully populated grid; 2. pick a random cell, check if clearing it would create ambiguity and, if not, clear it; 3. repeat step two until there are enough cleared cells; 4. save puzzle for later use. __________________ If anyone has Portal 2 and hasn't played the co-op and wants to do me a favour, let me know (PM me or whatever).

Jan 9, 2011, 11:27 PM	#6
Takaharu I can fart in 7 languages Join Date: Aug 2009 Location: England, UK Posts: 1,862 Rep Power: 113 System Specs	Re: Sudoku! Have you got a webpage you can stick it on? It'd make it easier to test. __________________ I don't get paid to know the answer, therefore I'm far more likely to give you a straight and honest answer. Mods Rig, Box Mods Rig, Folding details

Jan 10, 2011, 12:26 AM	Thread Starter #10
skylineaddict Sleep Deprived Ant Join Date: Aug 2008 Posts: 895 Rep Power: 136 System Specs	Re: Sudoku! That definitely isn't very efficient.. But, if people want one-solution puzzles, I guess it's a sacrifice they could make. I'll put that on the bottom of my to-do list. First I'm going to get cursor navigation and UI tweaks done. __________________ Couldn't come up with anything snappy to say, so I'll just be awkward.

Jan 10, 2011, 12:38 AM	#12
IvanV HH Assassin Guild Member Join Date: Dec 2004 Posts: 5,921 Rep Power: 336 System Specs	Re: Sudoku! Applets get downloaded and executed on the client machine (but inside a web browser window), so they don't require anything special, any server which hosts a static HTML page can host a page with an applet. You just load the applet together with the HTML page containing the appropriate HTML tags onto the server and that's it. EDIT: The solving algorithm I described isn't pretty, but it's a maximum of 9 possibilities for each cell of the 9x9 grid. That's a maximum of 9x9x9=729 function calls to produce a single solution; a function call compares a value against a maximum of 20 other cells, giving a total of less than 15,000 operations, which is not much at all for today's computers. __________________ If anyone has Portal 2 and hasn't played the co-op and wants to do me a favour, let me know (PM me or whatever). Last edited by IvanV; Jan 10, 2011 at 12:47 AM.

Jan 10, 2011, 01:05 AM	#14
IvanV HH Assassin Guild Member Join Date: Dec 2004 Posts: 5,921 Rep Power: 336 System Specs	Re: Sudoku! On second thought, I have vastly underestimated the maximum number of operations of my algorithm (I failed to account for backtrack - only goes to show how long it's been since I solved a serious algorighmic problem). Still, I remember the program producing a single solution instantly, regardless of the difficulty. __________________ If anyone has Portal 2 and hasn't played the co-op and wants to do me a favour, let me know (PM me or whatever).

Jan 11, 2011, 11:11 PM	Thread Starter #15
skylineaddict Sleep Deprived Ant Join Date: Aug 2008 Posts: 895 Rep Power: 136 System Specs	Re: Sudoku! Latest version has updated UI and you can now navigate the grid by using arrow keys (The ones that aren't on the number pad if you have one. I'll add that later). The solution for it isn't very intricate and you may have to get used to the way the cursor jumps around. Once I can think of something better, I'll change it up a little. Again, the link is the same as the one in the first post, but I'm posting it here to save you from scrolling up. http://krazyboi.pbworks.com/f/blahbot.jar __________________ Couldn't come up with anything snappy to say, so I'll just be awkward.

Jan 14, 2011, 04:28 AM	Thread Starter #16
skylineaddict Sleep Deprived Ant Join Date: Aug 2008 Posts: 895 Rep Power: 136 System Specs	Re: Sudoku! Redid the randomizing algorithm and fixed an issue with the load binary function. Random grid now takes a lot less time (Next I will be implementing code that generates a grid with only one solution). __________________ Couldn't come up with anything snappy to say, so I'll just be awkward. Last edited by skylineaddict; Jan 14, 2011 at 04:44 PM.

Jan 14, 2011, 01:42 PM	#17
IvanV HH Assassin Guild Member Join Date: Dec 2004 Posts: 5,921 Rep Power: 336 System Specs	Re: Sudoku! Nice progress. __________________ If anyone has Portal 2 and hasn't played the co-op and wants to do me a favour, let me know (PM me or whatever).

Jan 16, 2011, 01:37 AM	Thread Starter #18
skylineaddict Sleep Deprived Ant Join Date: Aug 2008 Posts: 895 Rep Power: 136 System Specs	Re: Sudoku! I found a way to generate single-solution puzzles. Problem is they take way too long to generate. I'll keep the current random generator in the application, but I will upload a bunch of files containing single-solution puzzles to my Wiki. That will save everyone the trouble of waiting for a few minutes to get a puzzle. __________________ Couldn't come up with anything snappy to say, so I'll just be awkward.

Feb 5, 2011, 07:04 AM	Thread Starter #19
skylineaddict Sleep Deprived Ant Join Date: Aug 2008 Posts: 895 Rep Power: 136 System Specs	Re: Sudoku! Sudoku by Ankit Patel Alright, I've updated the program a little. It now accepts puzzle archives that contain puzzles with a single solution (That claim hasn't been tested by people, but my algorithm in theory generates single-solution puzzles. I hope that someone can test that for me). To load puzzle archives: -Download one of the files below (Each one contains a thousand puzzles) -Click on the load button -Select (*.vsky) as the file you want to open -Select the file you downloaded -The menu option "Puzzle Set" should be enabled now -Click on that, and then click on "Load puzzle from set" Expert puzzles aren't available yet because they take a really long time to generate (Around 24 hours). The last bunch I generated were invalid because of a stupid mistake in my generation algorithm. I will update the links once I get them generated though. That will open a random puzzle from that set. I will be implementing code later on that deletes any puzzles that have already been viewed or solved from the archive so that you won't see them again (Hence the menu option "Stop using puzzle set" not working. Other things added: Tooltips on the buttons, a better way of navigating the grid using arrow and tab keys (Shift + Tab needs to be added so that you can traverse backwards. I shall be working on that soon). Easy Puzzles Medium Puzzles Hard Puzzles Let me know if the links aren't working or if you want more puzzle files. __________________ Couldn't come up with anything snappy to say, so I'll just be awkward.

Feb 6, 2011, 10:53 PM	Thread Starter #20
skylineaddict Sleep Deprived Ant Join Date: Aug 2008 Posts: 895 Rep Power: 136 System Specs	Re: Sudoku! I made a puzzle creator (That should create single-solution puzzles) and viewer earlier and I figured I'd share it with you guys. I'll see if I can add a function that can print the puzzles later on (I'll have to do some more research to get that). Puzzle Creator by Ankit Patel To generate puzzles, type in a puzzle number and difficulty (1-4) and click generate. Choose where you want to save and voila! Puzzle Viewer by Ankit Patel First, load a file, then type in a number based on the bounds displayed above the text field and press enter. The viewer is compatible with the files I posted earlier. __________________ Couldn't come up with anything snappy to say, so I'll just be awkward. Last edited by skylineaddict; Feb 7, 2011 at 01:10 AM.