Su Doku

Feeling BLUE? You'll fit right in here. [insane laughter]

Moderator: BoxJam

Su Doku

Postby Zzedar on Tue Sep 13, 2005 5:23 am

Could you show us the source for the Su Doku solver? I'd like to take a look at how it works.
Throw from behind the cheese.
User avatar
Zzedar
Grand Poobah Keenspotter
 
Posts: 336
Joined: Sun Aug 11, 2002 3:06 pm

Postby BoxJam on Tue Sep 13, 2005 6:55 am

ALright. I'll do that when I get a chance.

Basically it does the same thing people do -

-in a row, column, or box, if there are 8 squares filled in, it knows the ninth.
-for a square, if its three groups (row, column and box) have 8 distinct values, it know itself.
-for all the unsolved squares in a group, if there is only one that can contain a value, it must be that value (like 3 squares, A, B, and C, have possible values 1,4,9, 4,9 and 4,9 - A must be 1).

THere are a couple other possible rules - if a group has *2* boxes which can only take the same 2 possible values, no other square can contain it. Like A, B, C, D have possible values 1,4,6,9, 1,3,6,9 6,9 and 6,9. Since C and D must be 6 and 9 or 9 and 6, A and B's possibilities are really only 1,4, and 1,3. I didn't implement this rule.

After that, it just takes guesses - it finds the square with the fewest possibilities, and follows each possibility down the rabbit hole. Eventually, for each, you get to a point where you see it's impossible, or you get to the next part where you have to guess, or it's complete.

If you know those rules, a Sudoku becomes pretty much a matter of not making clerical errors. We deserve better.

I'll post the code for the solver classes when I get a chance.
User avatar
BoxJam
Keenspot Despot
 
Posts: 1730
Joined: Sat Mar 11, 2000 12:00 am
Location: Glenview, IL, USA

Postby teenidol on Tue Sep 13, 2005 8:05 am

I did not know Sudoku. But now I hate it.
From The Desk Of
"There's more to life than a little money, you know. Don't you know that? And here ya are, and it's a beautiful day. Well, I just don't understand it." Marge Gunderson
User avatar
teenidol
Keenspotter Supreme
 
Posts: 106
Joined: Thu Oct 23, 2003 8:25 am
Location: VA

Postby BoxJam on Wed Sep 14, 2005 6:13 am

http://www.boxjamsdoodle.com/bupware/SolveUtils.cs
http://www.boxjamsdoodle.com/bupware/Square.cs
http://www.boxjamsdoodle.com/bupware/Group.cs
http://www.boxjamsdoodle.com/bupware/Grid.cs
http://www.boxjamsdoodle.com/bupware/Co ... omparer.cs

Everything's hardwired to 9x9, but meh. SolveUtils.SolveIt is what gets called when you press the solve button.

P.S. Good news! I'm now the top google hit for "hate sudoku"!
User avatar
BoxJam
Keenspot Despot
 
Posts: 1730
Joined: Sat Mar 11, 2000 12:00 am
Location: Glenview, IL, USA

 

Return to BoxJam's Doodle

Who is online

Users browsing this forum: No registered users and 1 guest