Topic: Genetic Sudoku solver

Ok, I've made one. It works, and is able to solve any sudoku genetically.

It came up with this:

quote:

---

---------------------.
|5 3 4 |6 7 8 |9 1 2
|6 7 2 |1 9 5 |3 4 8
|1 9 8 |3 4 2 |5 6 7
---------------------.
|8 5 9 |7 6 1 |4 2 3
|4 2 6 |8 5 3 |7 9 1
|7 1 3 |9 2 4 |8 5 6
---------------------.
|9 6 1 |5 3 7 |2 8 4
|2 8 7 |4 1 9 |6 3 5
|3 4 5 |2 8 6 |1 7 9

---

As the solution for this:
http://fr.wikipedia.org/wiki/Image:Sudoku-by-L2G-20050714.gif

However, as discussed previously with 2D, while this evolves flawlessly towards the solution in all cases, it took it 150000+ generations to find the result.
Eg. half of the night

I can refine it of course, but again, it's a matter of balance: say the algorithm engages in a wrong "evolutionary path", it has to turn back for a few steps, so it *needs* regression which makes it slower
(every now and then it jumps back in evolution).

Still, for easy sudokus, the GA approach is not worth it, there are empirical algorithms that get the job done quick.

But I wonder about really hard Sudokus.. Are there grids that couldn't be soilved using classic programmatic ways?

Ah, and one sure benefit of GA over classic methods: have your GA solve an "empty" gris (all random numbers, none fixed), and you got a niftey Sudoku generator.

<off to tweak this a little before implementing a SOAP interface for automod>

Rhmmmm... turned it into a standalone Java app.
You can pick it up from:
http://www.beyondwonderland.com/data/java/sudoku/genetic_sudoku.jar

It doesn't accept user input, and only works with the preset sudoku grid mentionned.
It has been designed to be fully customizable and integrated in a user interface, but as stated above, turned out to be slow to use (even if I improve the mutation fonction
and rethink it a little bit, the best scores I have seen for genetic sudokus like this one are *solution in 15000 generations, it still is darn slow).

So? Useful for students who would like to see GA in action, or anyone else who is curious.

Oh, requires Java, and the display shows:
* parents of the current generation and theyre respective fitness
* generation (batch) number

...disappointed. GA is fantastic but can get really really slow. I was considering making part of the automod project genetic (evolving the KB or the rules or both),
but it's not worth it, I surely could come up with a code that works, but I guess from the sudoku example it would be utterly slow.

Oh, and if you don't believe this can solve Sudokus, let it run overnight, but beware: when it find the solution, it writes it to stdout and closes the application
(so you cannot "see" the solution but you can have the app write it down to a file on exit).

Ah, for further reference:

Similar project, reaches results in 10-15000 generations:
http://www.logicalgenetics.com/forums/viewtopic.php?p=5768

Highly insulting traditional approach using php:
http://www.jarra.nl/?p=91

(however, the traditional approach is fast as hell but doesn't overcome hard sudokus. GA does...)

-- EOP (end of project marker)

You can find a JavaScript one here:

http://www.codecouch.com/jeff/

Dan

Not sure my motivations are clear here.

Mine is genetic, the emphasis is on that: it's not doing it by classical algorithmy and therefore simply acts as
a demonstration and correct, academic usage of new ways.

As opposed to yours, mine solves any sudoku so far in the same time regardless of complexity - which is a lot of time, too much to be useful for the industry.

But it never was it's purpose.

For the rest, congrats on making one using classic algorithmy, but my take was an "AI experiment"
and was an assignment.
...google returns a load of those js sudoku solvers btw, I can see pathfinding ways to solve them (the a* algorithm for instance),
but genetic ones are more rare - for, again, GA doesn't suite this
problem well in terms of time, but perfectly in terms of problems resolution.

In addition: if you can create 1000 virtual sudoku grids and process them 150000 times in a row, all of them, in javascript,
you get a free beer from me.


By then, though, your browser will likely have leaked to the point of killing your comp, while the VM keeps running cool.

quote:

---

Still, for easy sudokus, the GA approach is not worth it, there are empirical algorithms that get the job done quick.

But I wonder about really hard Sudokus.. Are there grids that couldn't be soilved using classic programmatic ways?

---

^my original point. Thanks for proving it and providing the "other way".

(Edited by _Mauro on 06-21-2006 00:31)

There you go, the genetic Sudoku solver source is now available. The zip is an Eclipse project as a whole, so you should be able
to drop it in your "workspace" in the file system, and create a new project named "Sudoku", which will automagically import it into Eclipse.

http://www.beyondwonderland.com/data/java/Sudoku.zip

Now it is both a good way to get started using Eclipse (4 classes all, no comments sadly), and a decent - and quite extreme, very pure, determinism close to 0 -
genetic code sample.

Enjoy, fiddle, learn, and if you manage to improve it a lot, let me know.

That's a very clever use of GA's, I'd never have thought of doing it that way, but it makes very good sense. I imagine that you need a very large population, though.

Is it possible to produce a hybrid approach of top-down and bottom-up, such that it WILL solve every Sudoku, even hard ones, but it cuts corners where it can using standard approaches? I bet it would cut down the number of generations dramatically, and make it so it's not only robust, but also practical to a large degree, which is something that often cannot be said of Sudoku solvers...

---
Website

Thanks IW, I *think* I got a real decent mark for this one, but haven't got the final AI mark for this year anyway.
Hybrid approach? Sounds good, and yes, it is possible. Many AI's do, but I don't know how to weigh the difficulty of a Sudoku code wise,
never gave it a try.

As the credit in the source says, *play, fiddle*. I think I am the only one in the class who got down to implementing it instead of just
landing a report. One of the most pompous idiots (and worst coders) there even dared to tell me "it's impossible, cannot be done".

One way would be trying with classic algorithms, then submitting the "solution" to my fitness function, and if it doesn't reach a fitness of 81,
evolving it.

Populations, it's in the gui / entry point: the public version used 100 Sudokus per generation (150000 gens required for a perfect solution), with 1000,
it gets a tad faster but still.. With 10000,
it gets quite slow, takes something like one second per generation. But I noticed when posting it that I have left a couple of mistakes in the main loop,
should be easy to improve that loop by at least 1/3 (I actually 2x2 parents for the next gen, but use only 2, for instance).

My first shot at GA.

Additional, simple thought: BillyRayPreacherSon's sudoku does exactly, in javascript, what *should be the first part of mine to make it fast.
Why not turning it into an applet (it just involves removing the gui package and using the classes it contains in an applet instead),
and sending the output through the existing javascript => java pipes?

Would involve "whacking" the two scripts in the same page, and connecting.

Guess someone already is preparing something of that kind by now though...

(Edited by _Mauro on 07-01-2006 23:08)