Sudoku By Me! (Runs in your Web Browser!)

DarkDepths

Your friendly neighbourhood robot overlord
#1

I'll follow this post up with another on some of the technicalities, but for those who don't care, I'll show you a pretty picture, tell you what my program does, and then give you a link.

Keep in mind that I really didn't have any grand purpose for making this, so I just decided that it would be one of those little projects that gets stuck into my portfolio. So on that note, criticism of all flavours (but preferably constructive) would be greatly appreciated! I don't want junk in my portfolio, after all! It's also the reason my name is in big blocky letters at the top =P

The Aforementioned Pretty Picture:

What does it do?
It started out as a simple Sudoku solver, but now it's so much (at least a little bit, any ways) more! You can enter numbers into a blank grid and have it find a solution (or tell you that there are no solutions... or several solutions for that matter). But you can also play a random Sudoku puzzle.

That's right, I also made a puzzle generator! Sometimes the puzzles it produces are easy, sometimes they are nearly impossible. But hey, it'll give you a puzzle and track how long it takes you to solve it. It'll even show you when you enter a wrong answer, if you want it to.

Where's the Link?
In Hyrule! (Dead horse is dead...). Any who:


The links back to my homepage don't work yet, so don't bother clicking them! I haven't got a project page set up for it yet! (But this link works just fine! Go and find out for yourself!)

Also, if you try it, please let me know what you think, and also what device you were using. It runs pretty well on my Galaxy S3, so I'd just like to know how it runs on other phones/tablets, more out of curiosity than anything.


THANK YOU!
 
Last edited:

DarkDepths

Your friendly neighbourhood robot overlord
#2
The Technical Follow Up That No-One Will Read!
I'm not actually going to make this too technical, or at least I'll try not to! I just want to talk about the process, a bit. First, indulge me as I release my inner artist and explain my motiviation.

Why?
It's simple - I was lying in bed one night at approximately 2 am after having working on my GalleryEnthusiast WordPress plugin for what seemed like 6 days straight when I noticed certain feelings of anguish within me. I needed a break from all that work, but I couldn't just do nothing. I mean that's literally impossible, I had to do something, and I thought it might as well be something productive that interested me. So, in my infinite wisdom, I decided that the best way to relieve the stress of coding a WordPress plugin was to code a Sudoku Solver. I figured I could do it in a day, two at most.

But That was 2 Weeks Ago!?
Yes, yes it was. However, I was right. I finished a functioning Sudoku solver the next day. And then I thought "Well, why not make it generate puzzles too?" After all, I already had a solver, I could just tell it to solve an empty grid and then have it try to remove each number from the grid. If removing it resulted in the puzzle having multiple solutions, I'd put it back. You don't want a puzzle with multiple solutions! "It'll be easy," I thought.

And it was, I finished that up on the second day.

Cool! What did you do for the Other 12 Days?
Well, there was a problem. Two of them, actually. The first was that the puzzles produced by the generator didn't look very nice. Because of the nature of pseudo-random number generation, there was often a fairly obvious bias present in the way the "clues" would be left. So that wasn't good. The second problem was more pressing, though!

The solver was too slow. On average, it took almost 300 milliseconds for the solver to solve a puzzle!

Seems Pretty Fast... It Would be Done Before I Could Finish Blinking!
On it's own, it would be fast enough, but it was a bottleneck in a larger process. If you refer back to my plan on generating the puzzles, you will notice that I would have to solve 82 times when generating a puzzle. That's 24 seconds on my i7. I happen to think that's really impressive, if you take it out of context of todays standards. None the less, we live in the now, and the now demands things to happen instantly!

So you Rewrote the Solver?
I did, three times actually. The first really only a test of a process I had been thinking about, but the results weren't great. So after some reading, I learned of some existing algorithms for solving these kinds of exact cover problems. I implemented one of them, and it worked pretty well. But once I had finished, I was curious about another approach - essentially a highly optimized version of my first attempt. It was essentially just as fast as the second approach (admittedly a bit slower, but not egregiously), used less memory, and was much simpler. So that's the one I'm using today!

Awesome! So That's the end of Week 1?
Approximately. Solve time was now way down! So I set about solving the other problem, the "ugly-sudokuling" problem as I like to call it (I don't really). So I know that Sudoku puzzles generally have symmetry. So using that knowledge, I set about re-imagining the way that clues were removed from the grid. Instead of 1-by-1, now I did 4-by-4. If removing them cause there to be multiple solutions, I put them all back. Then I did it 2x2 (diagonally) on the remaining clues, and then 1-by-1 on the remaining clues. It makes pretty pretty puzzles!

Alright...
Then I realized that, if the user doesn't care about their being the minimal number of clues, I didn't even need to do the 1-by-1 step, so I added an option to trigger that. But as a side-effect of all this the number of solves required when generating was now significantly reduced as well! Without testing 1x1, on average it seems to take about 37 solves. With testing 1-by-1, it generally takes about 64. Either way, it's much fewer. Combined with a faster solver, it performs much better now!

Still a Few Days Unaccounted for Here...
The presentation, of course! Before, there was no interface. You would just type values in the developer console and it would print back the solution along with various statistics. So I spent a few days making it look nice. And then today I finished up by writing the "Help" section and cleaning up the code.

What's next?
I still want to improve the commenting in the code a bit. A lot of it is OK right now, but some was written in a bit of a hurry as notes to myself. I just want to clean those up so it's more presentable to others. And then, if I find time one day, I might try my hand at writing a Sudoku Grader. Something that can look at a puzzle and determine how hard it is. One of the problems with my program right now is that the puzzle it produces can be of any difficulty, and it's pretty hard to see how difficult it is without really getting into. I'd like to add something that can say "This is a really hard puzzle! Do you want to roll again?"

But I have other things on the go, so I don't know if I'll ever get to it.

The End!
See, I don't think I made it too technical. I just wanted to share my journey, in case any one is interested in how or why I made the thing you can see today.
 
Last edited:

nerdman

pig's gotta fly
#9
Instead of "this puzzle is hard!" approach, what if you let the user have an option of choosing the difficulty of puzzles?
 

DarkDepths

Your friendly neighbourhood robot overlord
#10
Instead of "this puzzle is hard!" approach, what if you let the user have an option of choosing the difficulty of puzzles?
That'd be ideal from a ux standpoint, but it would be impractical for me to implement.

How do you reliably produce a puzzle that is of a certain difficulty? That's pretty hard. It's much simpler to analyse an existing puzzle and give it some difficulty rating. Even then, it's not cut and dry because it's hard to objectively determine which puzzles are hard and which are easy.

One of the approaches that commercial products have used is to produce a random puzzle, grade its difficulty and, if it doesn't match the desired difficulty, try again.

For that to be plausible, though, you need to be able to generate and grade a puzzle imperceptibly fast. My solver simply isn't fast enough, for various reasons, to generate multiple puzzles in that single ui step without being very annoying to the user.

Even now, if I check the toggle to guarantee a minimal puzzle, my Galaxy S3 can, depending on the puzzle, take 15 seconds to produce a puzzle. Imagine if I had to roll the die 4 times to get the right difficulty - it could take a whole minute for the puzzle to be generated.

One of the problems with my solver is that it uses what you could rightly call a naïve algorithm. It's not smart. It must check every possible combination of inputs until it has found a solution. If there is no solution, it must check ALL combinations.

Now, consider what the generator does. It solves an empty board, which is a fast step. Then, it removes numbers from the board. After it removes a number (or group of numbers) it tries to find 2 solutions. It will find the first solution and then carry until it finds the second or that the second does not exist. So in the worst case, it has to try ALL combinations. Now consider that an irreducible puzzle WILL have between 17 and 39 numbers. The average puzzle seems to have about 24.

So, for my generator, in the average case, there are 81-24=57 numbers where a second solution is NOT found. In other words, there are 57 numbers where the generator has to try ALL combinations, and another 24 where it has to find 2 solutions.

Because of the way I take advantage of the symmetry of the puzzles, those numbers do not directly equate to the number of solves required, but it shows the principle.

So there must be a better way to solve the puzzle, right? Well, sort of. Perhaps you've heard of the term NP-Hard? In simple terms, it means a problem is hard to solve, but it's easy to check if a solution is correct or not. Well, Sudoku solving is NP-Hard.

There is an algorithm for solving Sudoku puzzles that is better than mine. Well, there are probably several, but this one in particular is probably the best (for most puzzles). It's called Algorithm X and it works on what are know as "exact cover" problems.

Exact cover problems have a set of constraints and candidates. Each candidate can fulfill multiple constraints. A solution to the problem is a set of candidates that fulfills all of the constraints with no overlap.

Sudoku can be represented in this way. There are four classes of constraints for Sudoku:

1) A cell must have a value.
2) A row must have each of the values 1-9.
3) A column must have the values 1-9.
4) A 3x3 region must have the values 1-9.

For a 9x9 Sudoku, there are 324 constraints in total. For the candidates, you simply consider the possibility of each value in each cell, so there are 729 candidates.

So then, you simply find the subset of those 729 constraints that fulfills all 324 constraints exactly once.

And believe it or not, at least as far as time cos concerned, it's a much more efficient approach to the problem.

However, it's an approach I didn't really feel like digging into at the time.

This is probably more of a response than you were expecting, but oh well! =P
 

nerdman

pig's gotta fly
#11
My idea was to have the puzzle generated but not shown to the user, then check its difficulty. If it was the right match, then present it.

I see now that this would just take way too long.

Another idea would to have a set amount puzzles of each difficulty saved. When the user selected a difficulty, the game would pick from the list so that the process was quick.

While the user worked on the puzzle, the game could work on creating a new one behind the scenes. Once it generated one, it could add it to the list (maybe removing old, already solved puzzles to save on space). All of this unseen by the user.

I'm not sure how feasible that would be though.
 
Top