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 

Can "mandatory pairs" technique solve the followin

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



Joined: 07 Aug 2005
Posts: 275
Location: Munich

PostPosted: Fri Dec 02, 2005 1:57 pm    Post subject: Can "mandatory pairs" technique solve the followin Reply with quote

Hi Alan,

I would like to supply you a couple of puzzles and find out if the "mandatory pairs" technique can solve any of them.
If yes, I will have to start working and understanding this technique.

I have the feeling, that it is just "an other way" of the techniques that are more or less known. I hope that I am wrong and looking for at least one example that "classic" techniques are not enough and "mandatory pairs" is doing the job.

OK, here some puzzles:

Code:
6.2.5....
.....3.4.
.........
43...8...
.1....2..
......7..
5..27....
.......81
...6.....


Code:
6.2.5....
.....4.3.
.........
43...8...
.1....2..
......7..
5..27....
.......81
...6.....


Code:
6..3.2...
.5.....1.
.........
7.26.....
.......54
3........
.8.15....
....4.2..
......7..


Code:
340600000
007000000
020080570
000005000
070010020
000400000
036020010
000000900
000007082


Code:
000000060
900003000
600090704
000000109
070080400
000000005
003005001
040100600
060470300


Code:
000000060
900003000
000000704
006000109
070020430
000000005
003005001
040100600
069470000


Code:
000000060
900003000
000090704
006000109
070020400
000000005
003005001
040100600
060470300


Code:
000000060
900003000
000090704
006000109
070020400
000000005
003005000
040100600
160470300


Code:
000000060
900003000
000090704
006000109
070080430
000000005
003005001
040100600
060470000


Any other techniques that are cracking them, are wellcomed.

see u,
Back to top
View user's profile Send private message
Guest






PostPosted: Sat Dec 03, 2005 1:18 am    Post subject: Re: Can "mandatory pairs" technique solve the foll Reply with quote

Code:

> I would like to supply you a couple of puzzles and find out if
> the "mandatory pairs" technique can solve any of them.

> I have the feeling, that it is just "an other way" of the techniques that
> are more or less known.

This assertion is basically correct.

> I am looking for at least one example that "classic" techniques are
> not enough and "mandatory pairs" is doing the job.

Sadly you will be disappointed in this BUT it is not the intention of
Mandatory Pairs (M/P) to usurp the "classic" methods.

We all know that some puzzles can be solved without pencil marks.
Some are graded "easy", others "medium" etc but there comes a
point where the human mind finds it difficult to retain all the data
that it has discovered in relation to a puzzle.

Thus we use "pencil marks" to assist us.

We all know also that computers can solve the majority of puzzles
presented (given that all the algorithms suggested and successfully
tested are suitably programmed) and that they depend upon the
generation of "Candidate Profiles" followed by elimination of the
candidates until a cell has only one candidate remaining (or a direct
inference as to the value to be held in a particular cell). I accept
that some solvers now user additional "state" grids but these are
really ancillary to the main candidate profiles and are not always
needed (although highly useful with 'colouring' and forcing chains).

The "classic" pencil marks follow the same lines as the computer
programs in terms of using "Candidate Profiles". These are easy
for computers to generate in a few milli-seconds (using a suitable
program language which uses vectors and arrays). However they
take much longer for humans and humans (unlike computers!) are
prone to error when compiling these profiles.

"Mandatory Pairs" was conceived as an idea for MANUAL solution of
Sudoku puzzles and is definitely NOT intended to supplant any of
the classic methods or any of the computerised methods. Indeed,
there would be no point whatsoever in developing a computer program
to apply M/P techniques when the 'classic' programs do the job already
so much more effectively.

The principal merit of the M/P technique is that it AIDS the human
solver by allowing her/him to record useful information that has been
discovered about a particular puzzle in such a way that it can be
easily retrieved and used later in the solution process.

In simplistic terms, a human solver may have to work through three
stages say A, B, C in order to resolve a cell. Without using any form
of pencil marks the user would need to retain in her/his short term
memory the logic and implications of all three stages. If, however
it is possible to mark the implications of stage A on the grid, the
human solver now has LESS to carry and if that also reduces the
complexity of the thought process to derive B then there is an even
greater benefit - leaving the person to concentrate on finding C, the
logic that leads to the resolution of the cell.

This theory already applies with the classic pencil marks. They are
used in "hard", "difficult" etc puzzles precisely because the chain of
logical thought processes has reached beyond the capacity of MOST
human beings to retain within short term memory (in contrast to the
chain of thoughts necessary to solve an "easy" puzzle - although even
these form a major confront to some members of the general populace
and solving such puzzles is a great success for such people).

Mandatory Pairs has the advantage of being an "as you go" technique
and in that respect differs from "Candidate Profiles" where the value
to be gleaned depends upon TOTAL ACCURACY of the profiles. One
error in compiling a profile can really screw the solution and lead to an
internal contradiction several placements later - necessitating a fresh
start to the whole process.

M/P is like "banking" part of one's winnings part way through a process
so that one does not need to go back to the very beginning. If there is
an interruption in building a house one does not need to check the
foundations every time one places a roof tile. One can rely on the
validity of the foundations and check only the roof trusses. However
this applies only if the foundations have been properly checked and
a "certificate" issued to record that they are OK.

The equivalent in Candidate profiles is demonstrating "congruency".
Congruency is checking that every row, column or region has an
EXACTLY equal number of distinct candidate digits and unresolved
cells. Checking congruency is not necessary for a computer program
as it compiles the profiles accurately in the first place. The human mind
is more fallible! I find that congruency checks are a VITAL part of
setting up the candidate profiles - but they are long and tedious!

On the latter point, I note that another site has a facility (called SWEEP)
which generates the candidate profiles on an initial puzzle so that they
can be printed on the equivalent to the 'DRAW' facility on this site
as a string of superscripts in each cell. This might be a useful optional
facility for those who use candidate profiles but dislike the chore of
generating them.

+++

Solving a puzzle using M/P has, potentially, three phases (but with
many techniques used within each).

1) Inspect the puzzle, derive both Pair and Sole values using the
    standard "manual" techniques and those specific to M/Pairs.
    Manual techniques include "slicing/dicing" and "counting" and
    any others that do not require a candidate profile. M/Pairs
    techniques include particularly "Mutual Reception" but also some
    others such as the "third row/column effect".

2) Derive the "Missing" profiles for each row/column.
    This aids the "sole candidate" search and can assist "counting".
    It is not essential - but it can concentrate the mind so that the
    resolution is more easily apparent.

3) Derive the Candidate Profiles for the REMAINING cells.

Each phase includes the possibility (indeed probability!) of reverting
to a prior phase to progress the solution once the information to be
found in the higher-numbered phase has been gleaned.

Each succeeding phase introduces a greater complexity and so is
a "crunch point" for the M/P technique. An objective is to avoid
having to move up a phase if at all possible. This can be quite a
psychological confront - especially when one discovers having
derived the candidate profiles that the solution was perfectly
obvious without have done all that extra work!

+++

Thus the benefits are

1) It is simpler to "get going" on the puzzle. The decision on whether
    or not to use candidate profiles can be postponed for quite a while.

2) The processes of logical thinking are easier in that one does not
    need to 'retain' or 're-visit' the processes that led to the recording
    of the mandatory pair. One can concentrate on "new logic" in the
    quest for a solution.

3) It is likely that M/P (in phase 1) will resolve more cells that using
    purely mental logic. This means that the puzzle is likely to be much
    further progressed before one needs (if at all!) to generate the
    candidate profiles - and so the process of compiling the profiles
    will be that much easier.

4) The second phase (which generates "Missing" profiles by recording
    them at the end of each row/column) was added after the intial
    M/P idea was launched. It has the advantages as claimed above
   and ALSO makes generation of candidate profiles much easier.

   (I find that I can use the "Union" concept of set theory to find
    a string of possible values for a cell as the digits that are within
    the 'Missing' profile for the intersecting row and column; then
    I need only eliminate any values that occur in the region in which
    the cell is located to get the profile for the cell. It might be useful to
    find out how others generate the profiles).

5) If phase 1 on its own has not resolved the puzzle (or phases 1
    and 2 together) there is often merit in REVERTING to these
    after using the C/P to get through the crunch point - as very
    often the solution is then like a coast on a downhill slope.

6) Overall, one is using "simpler" techniques as much as possible
    allowing the mind the rewards of dealing with logic rather than
    scanning profile matrices for patterns which may or may not
    exist. SamGJ has opined previously that many human solvers
    use far more complex techniques than are really necessary to
    solve many of the puzzles. M/P is a contribution to simplicity -
    but should not detract from the challenge raised recently about
    solving "medium" puzzles without pencil marks. That said, one
    can always revert to M/P if one is stuck without marks (and to
    'classic' C/P if stuck with M/P!!).

+++
> {Some puzzles were supplied for solution by M/P.}

> Any other techniques that are cracking them, are wellcomed.

I have declined to accept these challenges.
If they are problematic for 'classic' methods, they will be problematic
also for M/Pairs.

M/P is NOT claiming to address the "leading edge" of solution
techniques. For that one does need the 'candidate profile' approach.

What is does do, hopefully, is provide an enriching experience for
the human solver who is not just replicating a computer approach.

++++

On the last point, I note that our friend from Stoiber-land produces
solutions with annotations of method used and cells involved
alongside each placement.

I would doubt that such details are typed each time and would suspect
that some form of computer aid is used. How much assistance is
given? Is it just a typing aid (ie fill in a few parameters and the
program compiles the print line) or has a computer generated the
solution?

For example, if digit '4' is the only digit eligible to go into cell r6c4
what generates the print line with the (Sole Candidate) annotation?

++
I perceive an increasing tendency to post step-by-step solutions
on this site. I would ask those posting them to indicate whether
they are manual or computer solutions.

So far as I understand it, this site is not primarily one for the
consideration of computer techniques. There are several other sites
which cover that aspect of Sudoku quite well.

We all know that computers can assist us but as SamGJ asks on the
introductory page to this site "What's the Point?" when it comes to
a computer solution. There CAN be a point - if the computer solution
has something to teach us and to enhance our understanding - but
otherwise the value of a computerised solution is really only to the
programmer who developed it. As I have posted earlier, I have
found the step-solver on another site very useful in terms of my
own learning curve. In the early days, I needed to learn the basic
approaches to solution and the step solver revealed several of them
to me (in a way that SamGJ's [Hint] does not always!).

Thus, I would ask those who present detail solutions to pause and
ask first "What am I contributing to the benefit of others by posting
this solution?". DavidJB is very good on this. He posts just sufficient
to cover the point in context and encourages the querent to work
on from that point. I posted ONE complete solution using M/Pairs -
just to indicate that such was possible and how the identification of
pairs and subsequent use of them functions. I do not intend to post
solutions just for the sake of them - although I may offer advice
on the ease or otherwise of solving a puzzle using the M/P techniques.

In the end, each of us will develop our own solution methods and it
is HIGHLY likely that even those using basically the same method will
emplace the cells in a different sequence.

Please enjoy expressing your unique diversity in your solutions.

Alan Rayner  BS23 2QT
Back to top
someone_somewhere



Joined: 07 Aug 2005
Posts: 275
Location: Munich

PostPosted: Sat Dec 03, 2005 8:15 am    Post subject: Reply with quote

Thank you, Alan for the response.

see u,

P.S. I am still looking for "human" techniques to solve the above posted puzzles. Any idea is welcomed.
Back to top
View user's profile Send private message
David Bryant



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

PostPosted: Mon Dec 05, 2005 7:01 pm    Post subject: Invalid example? Reply with quote

Someone_Somewhere wrote:
Code:
6.2.5....
.....4.3.
.........
43...8...
.1....2..
......7..
5..27....
.......81
...6.....

Those are some very tough puzzles! I think, though, that you may have made a mistake on this one ... I found two solutions. dcb

Code:
692853174   672953814
851794632   958714632
374612895   341862975
437528916   437528196
918467253   819647253
265139748   265139748
583271469   583271469
729346581   724396581
146985327   196485327


PS I'm working on solutions for the others, as well, but so far I haven't found a simple way to solve any of them.
Back to top
View user's profile Send private message Send e-mail Visit poster's website
someone_somewhere



Joined: 07 Aug 2005
Posts: 275
Location: Munich

PostPosted: Mon Dec 05, 2005 7:20 pm    Post subject: Reply with quote

Hi David,

I am sorry, if one of it has not a unique solution.
I did not have the resources to check this.
But I can indicate the source where I got it from:

http://www.stolaf.edu/people/hansonr/sudoku/top95-methods.htm#p9

What is funny is that there is one puzzle same as this one with only 2 digits interchaged:

http://www.stolaf.edu/people/hansonr/sudoku/top95-methods.htm#p7

see u,
Back to top
View user's profile Send private message
someone_somewhere



Joined: 07 Aug 2005
Posts: 275
Location: Munich

PostPosted: Mon Dec 05, 2005 7:26 pm    Post subject: Reply with quote

Hi,

At that link, the published solution is a 3-dt one:

Code:
682|153|479
951|764|832
374|892|165
---+---+---
437|528|916
816|947|253
295|316|748
---+---+---
568|271|394
729|435|681
143|689|527


And it looks valid too.

Could it be that I could not solve it, because it has "multiple solutions" ? Laughing

see u,
Back to top
View user's profile Send private message
someone_somewhere



Joined: 07 Aug 2005
Posts: 275
Location: Munich

PostPosted: Mon Dec 05, 2005 7:37 pm    Post subject: Reply with quote

Hi,

I could work that puzzle up to this point:

Code:
6       4789    2       13789   5       379     1489    179     49   

1789    5789    15789   1789    169     4       1689    3       2   

13789   4789    13489   1789    169     2       14689   15679   4569   

4       3       5679    1579    2       8       169     1569    569   

789     1       56789   34579   349     35679   2       4569    38   

289     25689   5689    13459   1349    3569    7       14569   38   

5       4689    134689  2       7       139     3469    69      469   

2379    2679    3679    3459    349     359     3569    8       1   

139     49      1349    6       8       1359    3459    2       7   


And from here no method (except try and error) could help me eliminate any of the remaining digits.

If you could do more, just tell me.

see u,
Back to top
View user's profile Send private message
David Bryant



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

PostPosted: Mon Dec 05, 2005 7:44 pm    Post subject: I goofed! Reply with quote

Sorry, it was my mistake -- I put the "6" in row 9 in the wrong place. dcb :oops:

PS Thanks for the link to the "top95" web site.
Back to top
View user's profile Send private message Send e-mail Visit poster's website
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