| View previous topic :: View next topic |
| Author |
Message |
someone_somewhere
Joined: 07 Aug 2005
Posts: 275
Location: Munich
|
 Posted: Fri Dec 02, 2005 1:57 pm Post subject: Can "mandatory pairs" technique solve the followin |
 |
|
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 |
|
 |
Guest
|
| Posted: Sat Dec 03, 2005 1:18 am Post subject: Re: Can "mandatory pairs" technique solve the foll |
|
|
| 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
|
| Posted: Sat Dec 03, 2005 8:15 am Post subject: |
|
|
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 |
|
|
David Bryant
Joined: 29 Jul 2005
Posts: 559
Location: Denver, Colorado
|
| Posted: Mon Dec 05, 2005 7:01 pm Post subject: Invalid example? |
|
|
| 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 |
|
|
someone_somewhere
Joined: 07 Aug 2005
Posts: 275
Location: Munich
|
|
| Back to top |
|
|
someone_somewhere
Joined: 07 Aug 2005
Posts: 275
Location: Munich
|
| Posted: Mon Dec 05, 2005 7:26 pm Post subject: |
|
|
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" ? 
see u, |
|
| Back to top |
|
|
someone_somewhere
Joined: 07 Aug 2005
Posts: 275
Location: Munich
|
| Posted: Mon Dec 05, 2005 7:37 pm Post subject: |
|
|
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 |
|
|
David Bryant
Joined: 29 Jul 2005
Posts: 559
Location: Denver, Colorado
|
| Posted: Mon Dec 05, 2005 7:44 pm Post subject: I goofed! |
|
|
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 |
|
|
|
|
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
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
