Sudoku Programmers Forum Index

 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister   ProfileProfile   Log inLog in          Games  Calendar

Log in to check your private messagesLog in to check your private messages   

Elimination Method

 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Solving sudoku
View previous topic :: View next topic  
Author Message
King Wonka

Joined: 14 Dec 2005
Posts: 26
:

Items
PostPosted: Wed Dec 14, 2005 7:48 pm    Post subject: Elimination Method Reply with quote

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
View user's profile Send private message
Ruud
Site Admin
Joined: 17 Sep 2005
Posts: 708
:
Location: Netherlands

Items
PostPosted: Wed Dec 14, 2005 8:35 pm    Post subject: Reply with quote

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
View user's profile Send private message Visit poster's website
Bob Hanson

Joined: 05 Oct 2005
Posts: 187
:
Location: St. Olaf College

Items
PostPosted: Thu Dec 15, 2005 12:28 am    Post subject: Reply with quote

Welcome! Have fun.... But be careful, this can suck you in! Very Happy

http://www.stolaf.edu/people/hansonr/sudoku may have some tips for you.
_________________
Bob Hanson
Professor of Chemistry
St. Olaf College
Northfield, MN
http://www.stolaf.edu/people/hansonr
Back to top
View user's profile Send private message Send e-mail Visit poster's website
King Wonka

Joined: 14 Dec 2005
Posts: 26
:

Items
PostPosted: Thu Dec 15, 2005 2:04 am    Post subject: Reply with quote

So you would store your board in:

Code:
 cell[81]


as opposed to:

Code:
grid[9,9]
?

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 Idea
KW
Back to top
View user's profile Send private message
gaby

Joined: 02 Jul 2005
Posts: 120
:

Items
PostPosted: Thu Dec 15, 2005 3:01 pm    Post subject: Reply with quote

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
View user's profile Send private message Visit poster's website
Bob Hanson

Joined: 05 Oct 2005
Posts: 187
:
Location: St. Olaf College

Items
PostPosted: Thu Dec 15, 2005 5:10 pm    Post subject: Reply with quote

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
View user's profile Send private message Send e-mail Visit poster's website
dwsexton

Joined: 03 Jan 2006
Posts: 2
:

Items
PostPosted: Tue Jan 03, 2006 10:20 pm    Post subject: New to Solver Reply with quote

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
View user's profile Send private message
Bob Hanson

Joined: 05 Oct 2005
Posts: 187
:
Location: St. Olaf College

Items
PostPosted: Sun Jan 08, 2006 4:19 pm    Post subject: Reply with quote

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
View user's profile Send private message Send e-mail Visit poster's website
dwsexton

Joined: 03 Jan 2006
Posts: 2
:

Items
PostPosted: Wed Jan 11, 2006 1:32 am    Post subject: Reply with quote

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
View user's profile Send private message
mugnyte

Joined: 07 Dec 2005
Posts: 13
:
Location: portland, or

Items
PostPosted: Wed Jan 11, 2006 1:37 am    Post subject: Reply with quote

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
View user's profile Send private message Visit poster's website Yahoo Messenger MSN Messenger
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Solving sudoku All times are GMT
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
Sudoku Programmers topic RSS feed 


Powered by phpBB © 2001, 2005 phpBB Group

Igloo Theme Version 1.0 :: Created By: Andrew Charron