I'm working a small Java project of mine, it's a Sudoku solver. I'm programming it to exercise in OO-programming and the Java Language.



(The 'runs' count is the amount of iterations over the whole 9x9 grid needed to solve the bugger.)

Does anyone have any really hard sudoku's to test it with ? Or a super-trick to solve these things ?

I'm trying to implement all of the techniques described on this webpage: http://www.angusj.com/sudoku/hints.php, but the more advanced ones (Swordfish Algorithm ... ) demand a lot of code.

I know Lep also wrote a PHP one (http://www.snarkpit.net/dev/sudoku), but I'm not trying to steal his thunder or anything. I beat him anyway (enter the sudoku from the image above and watch that poor thing excuse for not solving it ! evil laugh)

Source code and the program itself soon, of course. I'm going to write a GUI before I release it, because working with command lines might be l33t, but not very popular these days.

---

:: Forceflow.be :: Nuclear Dawn developer

That's sick. These things drive me friggin nuts.

I had to work on one of these for my AI course. The puzzle could be any size. Also, we used sat solvers to help, since sudoku puzzles can be put into CNF form. (hint hint). Those things solve them insanely fast.

What search methods are you using? Some sort of breadth first, I imagine? (If you aren't, you should look into it.)

All of this makes the "search" easier and would give a good introduction to AI, actually.

I also suggest you check out other languages if you venture into AI. Java, C, C are terrible for it, because they're very clunky. Nickle is suppose to be very nice for this exact type of work (easier too)

Edit:
I meant deapth first search. Although Breadth first is also applicable.

You can mix this with some heuristics to get good searches. Just to note, if you're not already aware, everything you're doing right now is using heuristics.

I suggest delving deeper into this topic, because, what you're doing now is really not far from developing game or robotics AI, it's just the amount that changes.

---

Blame it on Microsoft, God does.

Thanks for the advice, Crono.

It's really interesting to program this stuff, and terribly difficult at certain times.

I've got roughly 1200 lines of code now, but I'm going to clean them up in the next days before I continue. Some methods could be written more efficient, and I could probably get rid of a s**tload of local variables.

Not to mention I have to clean up my comments here and there, since I tend to comment-curse when something's not working.

By adding the 'Naked Pairs' method and part of the X-Wing algorithm (google is your friend) I managed to cut the amount of runs for that thing down to 11.

---

:: Forceflow.be :: Nuclear Dawn developer

What program do you use to compile it? Normally there are compilers
that have some sort of parameter you can enter that will tell you a
bunch of stuff to clean up (unused variables, local/global variable
problems, ect.).

---

Posting And You

I would imagine he uses Javac or something as such to compile it. If you mean what IDE, of course that's a different question. I'm a command line man my self, so I just run it and give classpaths if needed.

Force, Make sure you use javadoc comments!! Having too many comments really is not an issue. If you're unfamilure with JavaDocs, you should definitly check them out, they're a God send.

They take notes you give in comments and produce HTML documentation on your classes. Very useful for anyone even yourself if you ever come back to it.

Here's some examples of what I'm talking about:
http://web.cecs.pdx.edu/~whitlock/docs/

Those are all custom classes provided by an instructor of mine for the java course in me department. It's pretty neat stuff.

---

Blame it on Microsoft, God does.

Recursive backtracker/depth first search:

boolean function solve(referenced gameboard g)
if isSolved(g)
   return true
else
   for all valid moves m
      makeMove(g, m)
      if solve(g)
         return true
      else
         undoMove(g,m)
return false

You may implement heuristics by messing with the order in which valid moves are generated.

---

http://maze5.net

Yet again, thanks for the advice.

I haven't implemented the recursive stuff yet, I fear the solving time will skyrocket, so I might implement it as a last option (after all the regular techniques, which usually find some grid elements pretty fast). At the moment, the program solves an 'average' labeled sudoku in 0.6 seconds.

And Crono: since I started programming Java, I always wrote Javadoc documentation, even for the smallest, stupidest projects. I'm in love with the clean HTML front-end to present other team members. :smile:

As IDE's I use JCreator Pro and BlueJ. (BlueJ is in fact an educational tool, doesn't really have much options as an editor, but has great visual testing aids.)

My compiler is the standard Java compiler which comes with the SDK (javac). I'm interested in the command line options to check for unused variables and other problems ... anyone happen to have more info on that ?

---

:: Forceflow.be :: Nuclear Dawn developer

Damn this forum boasts some brains.

So this project is just for fun Forceflow?

I haven't implemented the recursive stuff yet, I fear the solving time will skyrocket, so I might implement it as a last option (after all the regular techniques, which usually find some grid elements pretty fast).

Not necessarily.

Recursive stuff runs the same, it's easier to understand (for the human coder) and the only downside is space, not time. Also, the space allocated when working recursively is on the program stack and not on the heap, unlike dynamic memory, keep that in mind. (Also be aware that all objects in java, with small exceptions, are pointers. Which is why you never explicitly need to declare or use them, but you do need to keep them in mind sometimes.)

However, ultimately, recursive or iterative does not determine the speed. Complexity does. I would suggest you learn how to find out the complexity, or worst case running time of algorithms as it will be immensely useful. It is also very important. You will KNOW how well the program will run even before you write it.

I can give examples if you wish.

---

Blame it on Microsoft, God does.

I have learned the basic rules to calculate complexity, but not of recursive formulas.

I know, for example, that:

for(int counter = 0; counter <= array.length-1; counter++)
{
for(int counter2 = 0; counter2 <= array.length-1; counter2++)
{
...

Results in an n? complexity (with n the amount of elements in the array), because we're having a double loop here. And yes, Addicted to Morphine, this is just for fun. I can recommend these kinds of projects to anyone wanting to exercise in programming, since they involve a lot of thinking and exercising the language properties you've learned.

Other good examples are simple GPS-systems (choose a grid, paste a map, define obstacles and road blocks, define the shortest route, alternative routes, bicycle routes, ...) or games like Mastermind or Battleship. You don't need to develop a complete GUI, you just need an algorithm that works.

I've done some other things this year too. As our end exam for university we needed to program a small tool which could display 3d objects and calculate correct ground shadowing and light intensities on them, given a specific time, geo location and date.

Here are some screens:

The program interface
The create-item dialog, with the most horrible amount of Java Swing ever :razz:
Although it was not asked, we included parametrisation based objects like horns, spheres and mobius rings

We weren't allowed to use other tools than standard Java stuff, so importing a Java 3d engine (which would work a lot quicker) wasn't a possibility. The rendering has an acceptible speed on most mid-range machines, but you better don't try rendering that sphere on anything lower than a 1 ghz :razz: .

---

:: Forceflow.be :: Nuclear Dawn developer

Heh, I had to write one too for school. I took a simple approach, I guess, which was storing the possible options per tile, and crossing them away by sweeping rows, collumns and 3x3 blocks. Then I'd do a search on each row/collumn/block to see if there was a certain number that could only be placed in one tile, and another type of search that checked for tiles that had only one option left.

Didn't really solve everything, I definitely should've added more relationship checks (the Swordfish method doesn't get covered for example).

I noticed however, that sudoku's lost their fun ever since I've written that program. :smile:
I recently found a different type of sudoku's though, called killer sudoku's. The same basics apply, but you start with no numbers filled in, and there are grey shapes marked on the field with a number indicating the sum of their tiles values. Quite a fun approach. Of course, the simpler puzzles have grey shapes that only cover one tile, giving that value away immediatly, but more difficult puzzles don't... :wink:

---

Create-ivity - a game development blog

This one's a reall b****
http://img102.imageshack.us/img102/1924/unfinishedjr8.jpg
and the finished product:
http://img372.imageshack.us/img372/5234/finishedce9.jpg

---

Also change the texture of the dock. Docks are rarely tile. -Facepunch
As I Lay Dying

Solved ! (In 7 runs ~ 0.4 seconds)

---

:: Forceflow.be :: Nuclear Dawn developer

Is there some kind of 3D sudoku puzzle? (sure I COULD google, but..) like a 9³? is that even possible? I think I solved a sudoku once. So when can we get our hands on this solver? (I want to impress my daddy)

3D sudoku? Only the issue of filling that thing in already breaks my brain... :razz:

---

Create-ivity - a game development blog

Is there some kind of 3D sudoku puzzle? (sure I COULD google, but..) like a 93? is that even possible? I think I solved a sudoku once. So when can we get our hands on this solver? (I want to impress my daddy)

When it's done. I want it polished :smile:
Give or take another 2 weeks, I guess.

That's without a GUI. Would you guys mind executing a command like

sudokusolve 0,1,2,3.... (all elements of the sudoku)

or maybe

sudokusolve 0123...

?

(Because that's basicly how you use the thing now.)

---

:: Forceflow.be :: Nuclear Dawn developer

Spooky, I've worked on and off on this very same project. I'm an EE student, so this comp sci stuff is more of a hobby than anything else. Yours is far more efficient than mine... not even sure if mine still works, or if I broke it and never fixed it :smile:

At any rate, I saw this on Digg the other day, something to shoot for, i guess: http://markbyers.com/moinmoin/moin.cgi/ShortestSudokuSolver

Agh, pearl gives me fits just looking at it. They've removed all white space, obviously.. but still.. damn short...

Is there some kind of 3D sudoku puzzle? (sure I COULD google, but..) like a 9³?
is that even possible? I think I solved a sudoku once. So when can we
get our hands on this solver? (I want to impress my daddy)

You can buy them at gadget-y style shops. They're called "Sudokubes". Kinda redundant when it's done though.

beguiledfoil said:
I'm an EE student, so this comp sci stuff is more of a hobby than anything else.

I'm an EE student as well, but I'm doing a double with CS so I have to be good with both. Havent had to write a sudoku solver yet, that will probably come in a couple of years when I get a chance to do AI.

But what this world really needs is a sudoku pronunciation guide. The next person to say "sodoko" gets their face stabbed

---

"If you talk at all during this lesson, you have detention. Do you understand?"

• My yr11 Economics teacher

I'd be willing to help you on a GUI if its just a matter of drawing it up.

Well, just a java window with some sudoku like thing in which can give me numbers. That's all I need.

A reference to a good site about writing such a GUI would be cool, too. I know there are swing tutorials on Sun's site, but that's an enormous amount of reading :razz:

Anyway, I'll see it later. There's still a lot advanced techniques to be programmed, not to speak of the tweaking and cleaning up.

---

:: Forceflow.be :: Nuclear Dawn developer

Aren't you glad you know me?

http://web.cecs.pdx.edu/~whitlock/

Look at weeks 5, 6, and 7. That will tell you just about everything you'd want to know on GUI programming in Java. It's all very concise too.

Also, there should be some language stuff too in one of those lectures, so you can make it language independent.

Dr. Glass, in Java the graphical part of GUI is already done, while you can make custom graphics, you don't have to. The general OS window stuff is already supplied.

---

Blame it on Microsoft, God does.

Hehe, what a coincidence. I'm learning C++ with Bruce Eckel's book, didn't know he also had a Java one.

I'm going to check that out soon, first I'll have to learn a bit for my exams (I failed 3, and have to re-do them. f**k thermodynamics !)

I'll try to get a command line version out next week.

---

:: Forceflow.be :: Nuclear Dawn developer

I know, for example, that:

for(int counter = 0; counter <= array.length-1; counter++)
{
for(int counter2 = 0; counter2 <= array.length-1; counter2++)
{
...

Results in an n? complexity (with n the amount of elements in the array), because we're having a double loop here.

While that is correct, do you really know how to calculate it?
The running time of that alone is O(n²), are you aware that OMEGA(n²) for that algorithm as well? It's also the average case.

Double looping doesn't guarentee quadratic or exponential time.

There's a set of rules, actually for this. (you should also use psuedo code so programming symantecs don't get in the way)

c1  n              for counter <- 1 to length[A]
c2  n + SUM<sup>n</sup>[size=10]counter = 1[/size]t[size=10]counter[/size]     do for counter2 <- 1 to length[A]

T(n) = c1 * n + c2 * (n + SUMⁿcounter = 1tcounter)

The summation is an arithmetic series

> c (n + n + (n(n + 1))/2)

> T(n) = (n² + 5n)/2

Since n² dominates the function, that is the running time. You can be more specific using that equation with a size n, but, it's in like microseconds, so it's very negligable.

So, the worst case is O(n²).

If you want to calculate the best case, you just use the best case cost. In this situation, the second loop is going through all elements (n) no matter what, so it's the same. Obviously, if the worst case and best case are the same, then the average case is the same also.

It really comes down to knowing what series to use when.

To get the running time of a recursive algorithm there are some methods to go about that. One of which is the master method, which is very simple to use. But, the recurrence needs to be in a specific form for you to use it. There's also a tree method (can't remember the name right now). But, you'd start seeing that more times than not with recursive algorithms (as opposed to looping inside a loop) you get logrithmic time rather than exponential!

Edit: Apparently, omega and summation ascii characters are not useable here. Lame.

---

Blame it on Microsoft, God does.

Heh, big long post on computer science and then you say omega and sigma are ascii. Theyre unicode characters, and the site can only support ascii. HTML limitations?

I did some complexity work last semester and it sounds to me like youre overcomplicating finding complexity. Its really just a matter of breaking the algorithm down in such a way that you can count up the number of O(1) statements and figure it out in your head. At least thats what I've seen so far, maybe theres more methodical ways that work better with more complex algorithms, but works just fine for what I did (show that the search operation in a binary search tree is O(log n)), and logically extends to more complex algorithms.

---

"If you talk at all during this lesson, you have detention. Do you understand?"

• My yr11 Economics teacher

Don't even think about proposing it as a bug fix :razz:

Heh, big long post on computer science and then you say omega and sigma are ascii. Theyre unicode characters, and the site can only support ascii. HTML limitations?
I did some complexity work last semester and it sounds to me like youre overcomplicating finding complexity. Its really just a matter of breaking the algorithm down in such a way that you can count up the number of O(1) statements and figure it out in your head. At least thats what I've seen so far, maybe theres more methodical ways that work better with more complex algorithms, but works just fine for what I did (show that the search operation in a binary search tree is O(log n)), and logically extends to more complex algorithms.

No. I tried using the ones in the extended ascii character set, numbers 228 (sigma) and 234 (omega). Try them out. I tried using the ascii characters because the site doesn't support html (thus unicode) in posts.

What I showed is the best way to go about it. You will not be incorrect, in other words. Also, it is just counting the operations, assuming they are O(1), unless there is a system call, which will be whatever time that system call takes. Incrementing in a loop is ignored too, but the point is, is that you're trying to find the highest order n. And a lot of algorithms are deceiving.

Who doesn't know that the height of any tree is lg height? (Base 2, by the way) Seriously, that's like a rule of thumb memorization thing, since showing it takes awhile. (Also, trees really only apply to recursive algorithms.)

This seems more useful when you're talking about recursive functions.

Also, many times, if you do this for a course or research, you have to show how you got the running time, to prove it. This is how you do that. If you can do it your head: great. But, it wont always be accurate unless you're very familiar with the algorithms.

Just counting the number of operations and not their complexity, is a shallow understanding. There's much more to it all.

---

Blame it on Microsoft, God does.

Character map begs to differ on what characters are actually at 228 (E4, ?) and 234 (EA, ?).

I said counting the number of O(1) operations, not just counting operations and assuming O(1). And in this case, a definitive proof is not required. I dont know as much as you do about this stuff (I've not seen omega notation before) but, provided you do understand the processes, my method is also valid. I can demonstrate if you really want, but it would be a long post.

---

"If you talk at all during this lesson, you have detention. Do you understand?"

• My yr11 Economics teacher

Crono said:
Who doesn't know that the height of any tree is lg height? (Base 2, by the way) Seriously, that's like a rule of thumb memorization thing, since showing it takes awhile. (Also, trees really only apply to recursive algorithms.)

Not always. A straight line is a tree, but to search it you have to go through all elements which is O(n). There are also lots of other trees that take O(n) time Mostly they are graphs that start out like a usual tree branching this way and that, and then one of the branches stops acting like a usual tree and just continues out in a straight line for a long ways.

Logarithm time can only be achieved if you guarantee other conditions on the tree. For example if you are guaranteed to have at least a constant percentage of the nodes go left, and at least a constant percentage of the nodes go right (regardless of the number of nodes in the tree), then you can show that the tree's height will be logarithmic in the number of nodes.

And that is why you should never memorize formulas.

---

http://maze5.net

You need to assume all operations are done in constant time, and since the cost constants go away anyway, just let them be 1. (This is the same as saying each line is O(1))

Yeah, except when I use the ascii character 228 (0xE4) I see Sigma ... This mapping also confirms that. I'm not sure why it's different. For that character it's 132 (0x82).

There's no need to demonstrate it, I never said it was wrong, remember?
I don't think you'd be able to use the same method on recurrences. It doesn't work the same way. What I showed is very close. Of course, you could ignore all of that and just build a recursion tree.

And, again, if you're making something that you're documenting ... it'd be nice if you had some sort of proof. I mean, I could say one section of my code runs in THETA(lg n), but it actually runs THETA(n lg n) or something as such. It makes a difference. (if the length was 8 one would run in 3?s the other 24?s)

Edit: Ah, apparently, the database (or perhaps the browser or php functions) is translating from ASCII to unicode when things are submitted, the symbols I was using are in the extended ascii character set, but not in the Unicode character set, so it just uses the html equivalent, but the forums have html code turned off for posting ...

---

Blame it on Microsoft, God does.

Here's an example of the output the solver generates:

http://users.pandora.be/history/forceflow/dl/sudoku_output.txt

---

:: Forceflow.be :: Nuclear Dawn developer

I released the two most important classes of the project: the 'Sudoku' class, representing the puzzle itself, and the 'Element' class, representing one grid element. Most of the code still needs optimizing. The first class is fully documented, excepts for the parts which are a work in progress.

http://users.pandora.be/history/forceflow/dl/sudoku_source/

---

:: Forceflow.be :: Nuclear Dawn developer

Hot s**t, Forceflow.

I went back and cleaned my C++ implementation up a little. Like I said, this cs stuff isn't my strong suit (that would be clubs, btw) so I've probably done some very silly things. Commenting is still sporadic, and my method of generating puzzles is rather sketchy (it fails ~10% of the time, and when it does I just make another until I suceed :smile: ). But I think the method of it is rather clear.

The puzzle itself is represented as a 3d 9x9x10 array. The zeroth 9*9 layer is the puzzle itself, and each layer above it represents possible answers for a square on that layer. For instance the 1st 9x9 layer is all the possible spots that a '1' could go, the second 9x9 layer is all the possible spots that a '2' could go, etc. To solve the puzzle, the program just looks through the each layer for boxs (3x3), columns, and rows that have only one value in them as per the game rules. Anytime a box, row, or column is found to have only one possible value, then a spot is written.

Each time a value is written the matrix above the puzzle is updated and the puzzle is solved. Pretty simple, not sure if it's very fast, though (fast, that is, compared to other algorithms, certainly fast enough for my purposes).

Generating sudoku's is weirder, and I haven't really found a good way to generate good player solvable ones (IE, ones with a unique solution but with relatively few supplied spots). I have made a generator that just makes a valid sudoku, and lately I've been thinking about ways to remove entries such that it is guarenteed that there remains a unique solution, but I haven't really found a clever/quick way to do this :sad:

Can't think of a good place to post the code, so not going to bother. Pretty much just 500 lines of for statments anyway :smile:

Since you guys helped me out quite a lot, you'll be the first to test it:

http://www.forceflow.be/dl/sudokusolver.jar

This version pops up some simple dialogs asking you to input rows, and saves the solution and program output to a file.

Of course, a Java Runtime is needed.

---

:: Forceflow.be :: Nuclear Dawn developer