View previous topic :: View next topic |
Author |
Message |
| King Wonka
| Joined: 14 Dec 2005 | Posts: 26 | : | | Items |
|
Posted: Wed Dec 14, 2005 7:48 pm Post subject: Elimination Method |
|
|
Just getting into Sudoku here and I've been perusing these boards. I like to keep things simple so here's my assessment of how to start off solving a Sudoku.
1. build an array called Grid[9,9]
2. assign the string "123456789" to all empty spots
3. go cell by cell and remove numbers that already exist in each column, row, and block
4. if the length of the string = 1 then show that cell (right answer)
A visual:
Code: |
123|0A0|456
000|070|000
000|080|000
--------------
|
The only possible answer for A would be 9 using the above method. Think you guys call this Only Candidate or something. |
|
Back to top |
|
|
| Ruud Site Admin
| Joined: 17 Sep 2005 | Posts: 708 | : | Location: Netherlands | Items |
|
Posted: Wed Dec 14, 2005 8:35 pm Post subject: |
|
|
Are you sure you want to work with strings?
Computers (and the programs that we build for them) have a preference for numbers, not strings.
Tip:
Build arrays of cell that can "see" each other. You'll need them often when you build a solver.
Ruud. _________________ Meet me at sudocue.net |
|
Back to top |
|
|
| Bob Hanson
| Joined: 05 Oct 2005 | Posts: 187 | : | Location: St. Olaf College | Items |
|
|
Back to top |
|
|
| King Wonka
| Joined: 14 Dec 2005 | Posts: 26 | : | | Items |
|
Posted: Thu Dec 15, 2005 2:04 am Post subject: |
|
|
So you would store your board in:
as opposed to:
?
I know it's apparent I'm very new to this. Feel free to mold me lol. I'm taking a look at the C code and starting to get somewhat familiar with it.
Very extensive work you 2 guys (and dukuso) have done here...hopefully it will sink in
KW |
|
Back to top |
|
|
| gaby
| Joined: 02 Jul 2005 | Posts: 120 | : | | Items |
|
Posted: Thu Dec 15, 2005 3:01 pm Post subject: |
|
|
If you get stuck on terms, I have compiled a list of terms (taken from many of the postings here, and other places):
http://vanhegan.net/sudoku/dictionary.php
Which may help kick-start your understanding of some of the topic discussed here.
Gaby _________________ Free daily sudoku - Online puzzle database
http://vanhegan.net/sudoku/ |
|
Back to top |
|
|
| Bob Hanson
| Joined: 05 Oct 2005 | Posts: 187 | : | Location: St. Olaf College | Items |
|
Posted: Thu Dec 15, 2005 5:10 pm Post subject: |
|
|
Take a look at the .js files in
http://www.stolaf.edu/people/hansonr/sudoku
sudoku.js -- main code
utility.js -- array construction is in here
crosscheck.js -- some setup there, looking for singles
blocks.js -- looking for block-row/cell-locked candidates
subsets.js -- setting up the subsets and almost-locked sets
strong.js -- setting up the chains
weak.js -- connecting the chains
logic.js -- fancy trial and error
useraction.js -- all user interaction
sudoku3d.js -- just for fun
I'm not claiming this is the way to do it, but it works. One trick I found
very helpful was to alias the cells both as
Data[irow][icol]
and
Block[iblock][ipt]
So both of these point to the same data element. Sometimes it's easier
to use one than the other -- really just a convenience.
Good luck. You'll learn a lot. _________________ Bob Hanson
Professor of Chemistry
St. Olaf College
Northfield, MN
http://www.stolaf.edu/people/hansonr |
|
Back to top |
|
|
| dwsexton
| Joined: 03 Jan 2006 | Posts: 2 | : | | Items |
|
Posted: Tue Jan 03, 2006 10:20 pm Post subject: New to Solver |
|
|
My wife bought me this silly Sudoku book for christmas and after I worked the first 12 puzzels and found myself following the same process. I decided that to prevent myself from waisting a lot of time that I should write a program and take the fun out of it. I waisted an evening and wrote a simple Java program that solves these things first by applying two simple rules to extract the values that cells must have and then by recursively trying and eliminating all pairs of possible solutions until a solution is reached - does not tell if there is more than one solution. Most problems it solves quickly but the problem on the London times web page called superior21 it grinds on for a minute or two before it comes to a solution. I am sure the program could be made better/faster but I am willing to share it with anyone interested. I would also be interested if there is a particularly heinous problem to throw at it just to make sure I am done.
D. Sexton _________________ Dan Sexton |
|
Back to top |
|
|
| Bob Hanson
| Joined: 05 Oct 2005 | Posts: 187 | : | Location: St. Olaf College | Items |
|
Posted: Sun Jan 08, 2006 4:19 pm Post subject: |
|
|
Dan,
What you describe is basically a trial and error/backtracking solver.
If it works for you, I wouldn't spend lots of time optimizing it. I think if
you look that the prgramming subforum, you will find several of these.
I guess they can be as short as about 20 lines of code. My goal
was a bit different -- write a solver that identifies the sorts of structures
that people actually look for when solving Sudoku puzzles by hand.
Mostly just a way of learning how to do it myself in my own way.
Bob _________________ Bob Hanson
Professor of Chemistry
St. Olaf College
Northfield, MN
http://www.stolaf.edu/people/hansonr |
|
Back to top |
|
|
| dwsexton
| Joined: 03 Jan 2006 | Posts: 2 | : | | Items |
|
Posted: Wed Jan 11, 2006 1:32 am Post subject: |
|
|
Bob,
Thanks for the reply
I think you are partially correct. When I solved a few puzzles by hand I found myself first looking for the solutions to the obvious cells and after exhausting these I then started looking for the solution to cells based on what they could not be. I repeated this process until I had all the cells filled that I could. This solved all of the intermediate puzzels and many of the puzzels labeled hard. There was no - "trial and error" involved because no numbers were tried. Where I think I copped out was when I started looking for harder puzzles and found ones that this technique could not come up with a single solution. It was only after these first two methods failed to find unique solutions to all cells that the program then looks at remaining cells with only two possibilities. It then starts the trial and error process by trying one of the possibilities and then going back to the first two rules again. Since the program also displays its work on the screen it runs slow, I could speed it up significantly if I was not using the display objects as storage elements for the cells as it is working on them, however it is fun to watch it work. This was a fun but I doubt I will work on it anymore.
Dan _________________ Dan Sexton |
|
Back to top |
|
|
| mugnyte
| Joined: 07 Dec 2005 | Posts: 13 | : | Location: portland, or | Items |
|
Posted: Wed Jan 11, 2006 1:37 am Post subject: |
|
|
That said, I wonder if any has compiled a list of sites that have open source sudoku solvers..? I have enjoyed reading code solutions along with the text explanations to help me write my own and solve them by hand.
Dan -
Your same path lead me back to just generating them and solving them by hand once my program was stable.
Jim _________________ thanks |
|
Back to top |
|
|
|