Sonny Pondrom

Ranch Hand

Posts: 128

posted 11 years ago

There is a puzzle that is becoming very popular called

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?

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

Darren Horsman

Greenhorn

Posts: 9

posted 11 years ago

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

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

Ryan McGuire

Ranch Hand

Posts: 1138

8

posted 11 years ago

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

Jeff Albertson

Ranch Hand

Posts: 1780

posted 11 years ago

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

and

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

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!

steno druetta

Greenhorn

Posts: 10

posted 11 years ago

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...

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.

Ryan McGuire

Ranch Hand

Posts: 1138

8

posted 11 years ago

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 ]

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 ]

Sonny Pondrom

Ranch Hand

Posts: 128

posted 11 years ago

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 ]

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 ]

Mike Noel

Ranch Hand

Posts: 108

posted 11 years ago

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_

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_

Arjunkumar Shastry

Ranch Hand

Posts: 986

posted 11 years ago

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.

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

posted 11 years ago

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

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

Ram Bhakt

Ranch Hand

Posts: 145

Ryan McGuire

Ranch Hand

Posts: 1138

8

posted 11 years ago

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 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. )

posted 11 years ago

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 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.

posted 11 years ago

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

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

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.

Joseph Kulandai

Greenhorn

Posts: 3

posted 10 years ago

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

Jim Yingst

Wanderer

Sheriff

Sheriff

Posts: 18671

posted 10 years ago

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

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

Jim Yingst

Wanderer

Sheriff

Sheriff

Posts: 18671

posted 10 years ago

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

In reality, I made RMSudoku2 (shown earlier)

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 ]

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*

Did you see how Paul cut 87% off of his electric heat bill with 82 watts of micro heaters? |