• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

SoDuko puzzle

 
Ranch Hand
Posts: 128
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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?
 
Greenhorn
Posts: 9
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
author
Posts: 23951
142
jQuery Eclipse IDE Firefox Browser VI Editor C++ Chrome Java Linux Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
 
Henry Wong
author
Posts: 23951
142
jQuery Eclipse IDE Firefox Browser VI Editor C++ Chrome Java Linux Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
 
Bartender
Posts: 1205
22
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator


Produces this output:

[ December 28, 2005: Message edited by: Ryan McGuire ]
 
Sonny Pondrom
Ranch Hand
Posts: 128
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
WOW That is amazing.
 
Rancher
Posts: 13459
Android Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
 
Ranch Hand
Posts: 1780
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
 
Greenhorn
Posts: 10
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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...
 
Ryan McGuire
Bartender
Posts: 1205
22
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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 ]
 
David O'Meara
Rancher
Posts: 13459
Android Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator


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
 
Sonny Pondrom
Ranch Hand
Posts: 128
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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. sonnypondrom@charter.net
[ December 19, 2005: Message edited by: Sonny Pondrom ]
 
Ranch Hand
Posts: 108
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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_
 
Ranch Hand
Posts: 999
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
Henry Wong
author
Posts: 23951
142
jQuery Eclipse IDE Firefox Browser VI Editor C++ Chrome Java Linux Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
 
Sheriff
Posts: 4313
Android IntelliJ IDE Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
found this cool Javascript Sudoku solver: http://shannonandmike.net/sudoku/
 
Ranch Hand
Posts: 145
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Originally posted by steno druetta:

i'm a crosswords lover


which is another kind of b�llsh�t
 
Ryan McGuire
Bartender
Posts: 1205
22
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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. )
 
Java Cowboy
Posts: 16084
88
Android Scala IntelliJ IDE Spring Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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.
 
Jesper de Jong
Java Cowboy
Posts: 16084
88
Android Scala IntelliJ IDE Spring Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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.
 
Greenhorn
Posts: 3
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Check this code: http://kulandai.blogspot.com/2006/10/sudoku-puzzle-java-source.html
 
Wanderer
Posts: 18671
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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 ]
 
Jim Yingst
Wanderer
Posts: 18671
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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 ]
 
Consider Paul's rocket mass heater.
reply
    Bookmark Topic Watch Topic
  • New Topic