dailysudoku.com Forum Index dailysudoku.com
Discussion of Daily Sudoku puzzles
 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

Method Solving Techniques

 
Post new topic   Reply to topic    dailysudoku.com Forum Index -> General discussion
View previous topic :: View next topic  
Author Message
AZ Matt



Joined: 03 Nov 2005
Posts: 63
Location: Hiding under my desk in Phoenix AZ USA

PostPosted: Tue Nov 15, 2005 11:19 pm    Post subject: Method Solving Techniques Reply with quote

I am wonder what types of methods other people use to begin solving a puzzle, and how far they can get using them. This is mine:

I note where the given 1s are and I start with block 7 and try to solve for the number 1. If it is already there, or I can solve for it using row/column interaction with the block, I move to block 4 to solve for number 1. If I can't solve for 1 in box 7, I see how many cells 1 is a candidate in. If it is only two cells, I write a 1 in the upper left corner of those cells. If it is a candidate in three cells, I write 1 in the lower left hand corner. If it is more than three cells, I don't note anything on the first go through.

For each number I proceed clockwise through the blocks in this order -- 7, 4, 1, 2, 3, 6, 9, 8, and 5. Each time that I note that a number can only fit in two or three cells, I post the number as described above in its approximate location from left to right along the upper or lower line (a 4, for example, would go near the middle, a 9 at the far right corner). As I fill in cells, I erase the notations and/or move the numbers up accordingly so that the information in any cell is always accurate.

I can solve most medium and even some hard puzzles using this method on the first go through, before I even start looking at candidates by cell. This method also almost eliminates the need to "find" hidden pairs or triplets; they become fairly obvious. I denote matched pairs and triplets by moving the numbers to the middle of the square and drawing a little line under them and an arrow pointing where to look for the rest of the set.

Only after I have extracted all the information I can from this method do I proceed to look for candidates in particular cells, begining with the cells that appear to have the fewest candidates given all the information in the other cells in the respective row, column, or box. I write the candidates into the center of the cell (obviously, I print large versions of the puzzle).

That's about it. From there it's just a judgment call (the way I do it) on when to look for x-wings and sowrdfish and forcing chains. I also look for patterns in the numbers, but that is advancing to another topic.

Is this typical? Is there an easier or more efficient way?
Back to top
View user's profile Send private message
gadgetgirl
Guest





PostPosted: Wed Nov 23, 2005 2:57 am    Post subject: general approach Reply with quote

I think its simpler to start by looking for numbers that frequently appear in the puzzle. If multiple boxes/lines have 5 for example, I try to fill in all the fives. Them, I go to the next most frequent number. After about 2-4 of these, it becomes easier to fill in boxes or horizontal or vertical series. I have found this much faster than starting with one. Idea
Back to top
GeierWilly
Guest





PostPosted: Wed Nov 23, 2005 5:31 pm    Post subject: Brute-Force Reply with quote

The brute-force method is not so bad.
http://sudoku.nanosim.net
works with this method.
Back to top
David Bryant



Joined: 29 Jul 2005
Posts: 559
Location: Denver, Colorado

PostPosted: Wed Nov 23, 2005 5:39 pm    Post subject: Re: Brute Force Reply with quote

GeierWilly wrote:
The brute-force method is not so bad.

It works for a computer, Willy. But can you do that in your head? dcb
Back to top
View user's profile Send private message Send e-mail Visit poster's website
AZ Matt



Joined: 03 Nov 2005
Posts: 63
Location: Hiding under my desk in Phoenix AZ USA

PostPosted: Wed Nov 23, 2005 10:43 pm    Post subject: Re: general approach Reply with quote

gadgetgirl wrote:
I think its simpler to start by looking for numbers that frequently appear in the puzzle. If multiple boxes/lines have 5 for example, I try to fill in all the fives. Them, I go to the next most frequent number. After about 2-4 of these, it becomes easier to fill in boxes or horizontal or vertical series. I have found this much faster than starting with one. Idea

That makes sense gadgetgirl, I'll try it -- but what about notations and a method for keeping track of what must fit where versus what will fit where (i.e., filling in for candidates)? We all seem to get to the same place in a puzzle (although I sometimes can't resist looking for a more difficult solve before I really have to). I suppose one could just start filling in for candidates and get to that place, so I am wondering if there is any value in keeping track of 2-cell and 3-cell candidates by number before identifying candidates by cell.

Now I don't know if I am even making sense.

And what is brute force method?
Back to top
View user's profile Send private message
David Bryant



Joined: 29 Jul 2005
Posts: 559
Location: Denver, Colorado

PostPosted: Wed Nov 23, 2005 11:29 pm    Post subject: Solving techniques Reply with quote

AZ Matt wrote:
Now I don't know if I am even making sense.

Well, I think I understand you. You're thinking about the difference between identifying which cells a particular digit can fit into, and identifying which values can fit in a particular cell.

On simpler puzzles I try to keep all that stuff in my head. I rarely make marks to indicate that a particular value must fit into some pair or triplet of cells, unless it's to make a small mark outside the puzzle indicating that the occurrence of this digit in this row/column must fall in this particular 3x3 box.

I do start marking candidates for particular cells (pairs only, at first) when I can't make any further progress without marks. But I always try to avoid making marks as much as I can. Too many marks just get me confused.

AZ Matt wrote:
And what is brute force method?

I think Willy was referring to a simple "guess and backtrack if it doesn't work out" strategy, which can be programmed into a computer fairly easily, but doesn't tend to work very well for most human solvers. dcb
Back to top
View user's profile Send private message Send e-mail Visit poster's website
alanr555



Joined: 01 Aug 2005
Posts: 194
Location: Bideford Devon EX39

PostPosted: Thu Nov 24, 2005 3:45 am    Post subject: Re: general approach Reply with quote

Code:

> I think its simpler to start by looking for numbers that frequently
> appear in the puzzle.  If multiple boxes/lines have 5 for example,
> I try to fill in all the fives.  Them, I go to the next most frequent
> number.  After about 2-4 of these, it becomes easier to fill in
> boxes or horizontal or vertical series.  I have found this much
> faster than starting with one.   

This is certainly true as a concept. At one time, I tried developing a
frequency chart before starting on the grid (ie counting how many times
each digit appeared) but this was an overhead chore. Now, I compromise
by tackling digits where there are two occurrences within the same
"broad column" or "broad row". These are the the most likely to produce
a placement of the obligatory 'third' occurrence. A bit more detail on this
is included in my posting on the 18th October Medium puzzle (to which
I am not posting a link as I have no understanding of the methodology
for so doing and copying it would be a waste of space resource).

Whilst this initial "go for the higher frequencies" approach is effective,
later stages need some co-ordination and logical approach. I do tend
now to use the "1 through 9" method now but I keep a note whenever
I have found 9 occurrences of a digit - so that I do not have to check
the puzzle again to re-discover that there is nothing left to be found.

Alan Rayner  BS23 2QT
Back to top
View user's profile Send private message
alanr555



Joined: 01 Aug 2005
Posts: 194
Location: Bideford Devon EX39

PostPosted: Thu Nov 24, 2005 4:06 am    Post subject: Re: general approach Reply with quote

Code:

> I suppose one could just start filling in for candidates and get to that
> place, so I am wondering if there is any value in keeping track of 2-cell
> and 3-cell candidates by number before identifying candidates by cell.

One of the difficulties with the candidate approach is that it is an "all-or-
nothing" technique. To gain information about a row, say, one needs to
have the candidate profile for ALL the unresolved cells in that row. That
is easy if there are just three unresolved cells and each has only two
remaining values - but tedious with say seven unresolved cells!

I started looking for intermediate assistance - and out of tha was developed the "Mandatory Pairs" system - called recently the "Mandatory
BOXWISE Pairs" system as it involves identifying two cells in each region
of which one MUST be the one in which the digit is held and where the other seven cells in the region CANNOT hold the specified digit.

The M/P system has a number of advantages - specifically the ON/OFF
nature of binary toggles. If it can be shewn that a digit is not in one
of its pair then it MUST be in the other.

This sort of logic CANNOT apply for 3-cell candidates. Indeed, there
are so many occurrences of 3-cell candidates that marking them would
be both tedious and counter-effective. A 3-cell candidature is useful
to know only if it lies totally within a row or column in a region - because
it can then deprive a linked space to other placements of that digit.

So, yes, there is merit in keeping track of 2-cell candidates. The M/P
method can often solve hard or very hard puzzles (paradoxically the
latter are easier!) in a way that manual solving would be more than
the poor brains of most of us could handle.

Thus I see the challenge as

a) Solve medium without pencil marks
b) Solve hard/v.hard without progressing to candidate profiles

This applies to puzzles set by SamGJ on this site. However, a lot of
other puzzles come in from elsewhere and they set us challenges
relating to advanced techniques - as is evident from the other fora.

Behind it all, however, is the basic motivation. We each need some form
of challenge and the psychological rewards to keep at it. Part of creating
such for ourselves will be our selection of the solution methods/techniques
and the grade of puzzles that we tackle. For instance, I decline to tackle
any puzzles which require trial and error or have multiple solutions. Each
one of us has the right to choose (with apologies to Roe v Wade!).

Alan Rayner  BS23 2QT
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    dailysudoku.com Forum Index -> General discussion 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


Powered by phpBB © 2001, 2005 phpBB Group