SoDuko puzzle

There is a puzzle that is becoming very popular called SuDuko. It was on the CBS Sunday Morning program today. It is like a cross-word puzzle but with digits 1 thru 9 instead of letters. It started in the U.S. and became very popular in Japan. There is a game player written for it using Windows, but I have not seen one for my Mac.

The board has 9 X 9 boxes laid out in a square. Each box has 9 fields laid out in a 3 x 3 square. Some of the fields are initiated with numbers. An easy game has many initial numbers and a more difficult game has fewer initial numbers.

The game with an unlimited number of puzzles could be written in Java by using a random number generator. A new puzzle could be generated by a text file with the starting numbers on nine input lines. Each line could have nine entries that are numbers 0,1,2,3,4,5,6,7,8 and 9. The zero could represent a blank puzzle field. The input level of difficulty could be the number of starting values.

The Daily SuDuko web site puzzle for 4 Dec 2005 is shown below as provided by Daily SuDuko Puzzle. This puzzle is represented by 81 numbers on the 9 lines with 3 sets of 3 numbers:

0,0,0, 0,0,0, 0,1,2
0,0,0, 0,5,1, 3,8,0
0,8,0, 0,0,6, 0,0,0

1,0,0, 2,4,0, 0,7,0
0,0,0, 0,3,0, 0,0,0
0,7,0, 0,6,5, 0,0,3

0,0,0, 4,0,0, 0,2,0
0,5,9, 6,8,0, 0,0,0
8,1,0, 0,0,0, 0,0,0

The object of the puzzle is to replace the 0's (blanks) with numbers 1 thru 9 such that each row, each column and each 3 x 3 box has only the numbers 1 thru 9. Can anyone write a Java code that would solve this very hard puzzle with only 25 starting numbers?

Wikipedia lists sudoku as:

it is a registered trademark of puzzle publisher Nikoli Co. Ltd in Japan

Not American after all I take it. We have had it in Britian for around a year now. I'll have a go at this and post results sometime after tomorrow.

The daily SuDoku site that you mentioned actually have a solver -- just choose draw, enter the values, and get either the next possible number, or the complete solution. Since you got the puzzle from that very site, you can also send the puzzle to the draw function directly.

If you want more SuDokus, the websudoku.com site has literally billions of them.

Apparently, they are also certain rules for a properly formed SuDoku. They can only have one solution, and must not be reached by guessing. I think the difficulty rating is also based on what type of logic techniques are used.

I know this is the "programming diversion" forum, but... IMHO, developing a solver is not very useful. What would be the point? SuDoku is probably a more addictive diversion, than any programming diversion.

Henry

Okay, so I am an addict... It wasn't too bad. Took about 40 minutes.


Please skip if you don't want the solution





Last chance








Okay




735 894 612
624 751 389
981 326 457

193 248 576
546 137 298
278 965 143

367 419 825
459 682 731
812 573 964

Produces this output:

[ December 28, 2005: Message edited by: Ryan McGuire ]

WOW That is amazing.

It is a little brute-force though, and there is plenty of other logic that is interesting to implement. Maybe lok at a Java sudoku solver

Originally posted by Darren Horsman:

Not American after all I take it. We have had it in Britian for around a year now. I'll have a go at this and post results sometime after tomorrow.

Take a closer look at the Wikipedia article. It states that:

Although first published in 1979, Sudoku initially caught on in Japan in 1986 and attained international popularity in 2005.

and

Dell Magazines, the puzzle's originator, has been using numerals for Number Place in its magazines since they first published it in 1979.

Dell is an American publisher. Yup, su doku is Japanese by adoption, like tofu

i'm sorry but I think sudoku is such a b�llsh�t. here in italy it has started to be famous last summer. when i was working in greece in an international holyday club i saw so many people trying to handle that... the "audience" was divided between the da vinci code (another b�llsh�t) and sudoku.
i apologize, i'm not so fond of "numbers", i'm a crosswords lover, i can solve any kind of scheme in few minutes...

Originally posted by David O'Meara:
It is a little brute-force though, and there is plenty of other logic that is interesting to implement. Maybe lok at a Java sudoku solver

A LITTLE???

My take on brute force:
I guess it depends on how many puzzles you plan to solve. Why take 8 hours to write an elegant program to solve the puzzle in 87 ms, when you can spend just 30 min to write brute force code that solves it in 15 sec?
[ December 12, 2005: Message edited by: Ryan McGuire ]

But it depends if your interested in the answer or the question. Migrating the same logic used to solve it by pencil can be an interesting exercise... to some

Solving by computer rather than pencil is better. I started to write a Java code to make it easier, but then my plans looked so much like a spreadsheet, that I decided to use one.

I call it "Sum 45" because it calculates the sum of the missing numbers for each box, row and column. The puzzle initially has a string with a single quote and 9 multi-colored numbers (1-9) in each cell. The single quote is there to avoid the cell being added to the sum of missing numbers. You have to replace these cells with the given puzzle entries. I make these number default font size 36 to make them different from the other cells.

To start solving the puzzle, you begin deleting the bad digits from the number string. When you get down to just one digit, then you delete the single quote as well. When a box, row or column is completed, then the sum of missing numbers will change from the starting value of 45 to zero.

I would show you a picture (Sum_45.tiff), but I don't know how to upload one.
Send me an email if you would like a copy of the Excel file. [email protected]
[ December 19, 2005: Message edited by: Sonny Pondrom ]

I like Ryan's solution. It's just a simple depth-first search of the game space. If I was still teaching second year CD students I'd probably have this as one of my programming assignments.

You might be able to prune the tree down a bit with a smarter inner loop (the for 1..9 loop). At the point where the comments say "// Try each possible..." you could generate three Sets. One for the available row numbers, one for the available column numbers, and one for the available rectangle numbers. Then using set intersection between the three you could end up with a Set of all of the available numbers for that position. Use an iterator over that set in a while loop instead of the for loop.

If the result Set was ever empty then there would be no need to go down that path anymore.

Just a thought.

BTW, the fact that this can easily be solved with a depth-first approach is the main reason that I haven't been all that excited about the game. Kinda like word-search puzzles. No real thought involved, just busy work.

(Yeah, I'm about to get smacked on the head by a zillion soduko fans...)

_M_

I think solving Sudoku by pencil than computer is better.Every Sudoku puzzle can not be solved by brute force on paper.Some hard Sudoku puzzles take more than 1 hour or sometimes 2 hours in my case.It also required actually writing down possible numbers and then deducing the possible solution.Interesting question will be "How will you generate Sudoku puzzle?" and how will you grade the puzzles from easy,medium,hard.
Say I fill all 81 squares according to rules,then which squares should be left blank to make puzzle easy,medium,hard?Here you need to write a program.

By definition, a properly formed Sudoku must have only one possible answer -- so hence, a bruce force solution should not only solve every sudoku, it can also be able to determine if the sudoku is properly formed.

However, I don't think that a brute force solution would be able to rate the sudoku. I believe that the daily sudoku site is able to determine whether the puzzle is easy, or hard, based on what techniques it used to solve the puzzle -- which means that it doesn't use a brute force solution.

BTW, have anyone seen the daily sudoku recently. I haven't tried them yet, but I noticed that they now have Christmas Sudokus...

Henry

found this cool Javascript Sudoku solver: http://shannonandmike.net/sudoku/

Originally posted by steno druetta:

i'm a crosswords lover

which is another kind of b�llsh�t

Originally posted by Jessica Sant:
found this cool Javascript Sudoku solver: http://shannonandmike.net/sudoku/

Cool? It'd be even cooler if it actually solved the puzzle I put in.

Today's Daily SuDoku (click here and then on Thu 5-Jan-06 "very hard" puzzle) seems to be too hard for the (current version of the) solver.



(I'm so glad my code works with this initial data. )

Originally posted by steno druetta:
i'm sorry but I think sudoku is such a b�llsh�t. ...
i apologize, i'm not so fond of "numbers", i'm a crosswords lover, i can solve any kind of scheme in few minutes...

Sudoku is not a numbers game!

You can replace the numbers with any kind of symbol you like. If you don't like numbers but you do like letters, try replacing the numbers '1', '2', '3', ... in Sudoku with letters 'A', 'B', 'C', ... and it will still be the same game.

Originally posted by Arjunkumar Shastry:
I think solving Sudoku by pencil than computer is better.Every Sudoku puzzle can not be solved by brute force on paper.Some hard Sudoku puzzles take more than 1 hour or sometimes 2 hours in my case.It also required actually writing down possible numbers and then deducing the possible solution.Interesting question will be "How will you generate Sudoku puzzle?" and how will you grade the puzzles from easy,medium,hard.
Say I fill all 81 squares according to rules,then which squares should be left blank to make puzzle easy,medium,hard?Here you need to write a program.

Have a look at http://sudoku.sourceforge.net

It includes a program to generate puzzles and a solver with some very clever algorithms.

Check this code: http://kulandai.blogspot.com/2006/10/sudoku-puzzle-java-source.html

Interesting, Joseph. You should try using one of the input arrays Ryan tried above. I input the one he showed in the code itself, and your code is still working on it after about a half hour. I don't know if it's in an infinite loop or not.

I recently got into sudoku a bit thanks to a few plane trips with nothing else to do. Unfortunately the book I grabbed has some quality issues, and about a tenth of the puzzles in it have more than one solution. Which leads to wasted time as you try in vain to find a way to choose between several possibilities, and there isn't any. So I figured a sudoku solver would be useful to tell me how many solutions there were. Being lazy, I grabbed Ryan's code above as a starting point. I was surprised how fast a brute-force solution could be - six seconds for for the sample puzzle Ryan used, on my laptop. Being a geek though, I felt compelled to find some ways to try to optimize it. I fully agree with Ryan's "my take on brute force" above - but in my case, I hadn't done any work of my own on the problem, and optimizing a simple existing solution seemed more productive than making my own from scratch. As a result, I was able to find some fairly minor changes that took the execution time for the demo problem from 6 seconds down to just under one second. (Yay!) Here's the code:

The key difference is in isLegal(): rather than checking every single rule each time, the code now only checks the row, column, and block of the most-recently-added element. (All others have already been checked.) This results in about a factor of nine decrease in the number of checks to run, and shorter code with fewer "magic numbers" to boot.
[ October 31, 2006: Message edited by: Jim Yingst ]

And with further tweaking & refactoring to suit my own OO-design sensibilities (i.e. to convince myself this was my own work, not just piggybacking off Ryan, even though I was) , I got the execution time down to about 0.4 sec, and delivered the additional data that was part of my original motivation here (are there multiple solutions, and if so, what do they have in common?). Here's the code:

Obviously that's a bit more verbose than the original, and many of the differences don't matter that much. But the net effect is faster.

In reality, I made RMSudoku2 (shown earlier) after the above code. After I'd gone through a number of revisions and learned what changes were most significant, I went back to Ryan's original and created RMSudoku2 as an alternate version that made just a few changes for maximum benefit, otherwise leaving the original unchanged (for easier comparison).

Also for what it's worth, here are two of the invalid boards with multiple solutions that motivated me in the first place:

[ October 31, 2006: Message edited by: Jim Yingst ]