**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?

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

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

There is no emoticon for what I am feeling!

i apologize, i'm not so fond of "numbers", i'm a crosswords lover, i can solve any kind of scheme in few minutes...

two wrongs don't make a right.

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 ]

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. sonnypondrom@charter.net

[ December 19, 2005: Message edited by: Sonny Pondrom ]

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_

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.

Namma Suvarna Karnataka

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

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.

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 ]

"I'm not back." - Bill Harding, *Twister*

Sheriff

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 ]

"I'm not back." - Bill Harding, *Twister*