| View previous topic :: View next topic |
| Author |
Message |
Androgicus
Joined: 10 Apr 2006
Posts: 2
Location: Sunshine
|
 Posted: Mon Apr 10, 2006 4:02 am Post subject: Definitions of terminology |
 |
|
Can someone please give me a solid explantation of the phrases:
Mandatory Pairs,
Candidate Profiles,
Mutual Reception. |
|
| Back to top |
|
 |
David Bryant
Joined: 29 Jul 2005
Posts: 559
Location: Denver, Colorado
|
| Posted: Mon Apr 10, 2006 11:11 pm Post subject: Candidate Lists |
|
|
I'm not sure I can explain mandatory pairs, or mutual reception. But I can define candidate lists.
The candidate list for a particular unresolved cell is the set of values that might possibly be placed in that cell without violating the rules of sudoku.
The initial candidate list for an unresolved cell is formed by removing all values already entered in the row, column, and 3x3 box containing that cell from the complete set of symbols {1, 2, 3, ..., 9}.
For example, if r1c1 is unresolved and row 1 contains {1, 2, 3}, column 1 contains {4, 5}, and the top left 3x3 box contains {6, 7}, then the initial candidate list for r1c1 is just {8, 9}.
Most people have to write some candidate lists down while working on a sudoku, especially if it's a tough one. Progress is often made by finding some way to eliminate one or more digits from the initial candidate list for a particular cell.
In general there are only two ways to place the right value in an unresolved cell.
-- If the candidate list can be reduced to a single value, that digit must go in this cell ("sole candidate").
-- If this cell is the only one in a row/column/box containing a particular candidate, then that digit must go in this cell ("unique in row/column/box").
Ask Alan R about the other terms. dcb  |
|
| Back to top |
|
|
Marty R.
Joined: 12 Feb 2006
Posts: 5770
Location: Rochester, NY, USA
|
|
| Back to top |
|
|
alanr555
Joined: 01 Aug 2005
Posts: 198
Location: Bideford Devon EX39
|
| Posted: Wed Apr 12, 2006 2:15 am Post subject: Re: Definitions of terminology |
|
|
| Code: |
> Can someone please give me a solid explanation of the phrases:
> Mandatory Pairs,
> Candidate Profiles,
> Mutual Reception.
Candidate Profiles are what computers use to solve a puzzle.
Each cell is allocated a "string" of numbers 123456789 and then
the digits are removed from that string when there is "evidence"
that the particular digit is "impossible" in that cell. When the
number of digits in the candidate profile for a cell has been
reduced to one - that cell is "resolved".
The term "Candidate Profiles" is sometimes used to refer to
a HUMAN solution method which uses what is essentially the
same technique - although humans tend to BUILD UP the
profile for each cell rather than using purely elimination. Once
the profiles have been "derived" in that way, the human solver
will usually proceed by eliminating the possibilities until only one
remains for each cell.
+++
Mandatory Pairs is the name of a system of recording information
that one has gleaned during the solution process but which is not
sufficiently complete, in itself, to resolve a cell. Essentially, this
is the restriction of the possible location for placing a digit to
exactly two cells of the nine within a region (ie proving that it
is impossible for that digit to be in any one of the seven other cells
in that region).
It is a system of recording that applies to HUMANS only and there
would be no point in attempting to adapt it to computer processing.
The theory behind Mandatory Pairs is the power of the "binary"
principle. Something is either "on" or "off" (true/false etc). With
the Mandatory Pair system this principle ensures that every pair
identified and marked on the grid (in ways explained elsewhere -
as recorded in another post in this topic) has one member that
is true and one that is false. The binary principle then asserts
that if one gets to prove that one member is false, the other
must be true. This proof of falsehood is something which occurs
quite frequently when applying logic to Sudoku puzzles - and so
is a very useful tool.
More recently, there have been posting on this site about the
principles of "Strong Links". These extend the principles of the
binary much further than their use in Mandatory Pairs - but
rely upon derivation of the candidate profiles first.
In the basic Mandatory Profiles methodology it is NOT necessary
to derive candidate profiles (thus avoiding what is perhaps the
greatest chore in Sudoku solution!!!). One can start applying the
logic and benefitting from the methodology right from the start.
Its simplicity comes from marking Mandatory Pairs only as they
apply to regions (3x3 boxes). As such the methodology misses
out on pairs not within the same region but in the same row or
column. Thus M/Pairs can solve SOME supposedly Very Hard
puzzles very easily whilst with others it cannot reach a solution
and, in the past, it has been necessary to resort to deriving the
Candidate Profiles (although with fewer cells involved as a lot
of the groundwork will have resolved a lot of cells in many cases).
With the concept of "Strong Links" being given greater prominence
it has become evident that the principles of M/Pairs could well be
extended to rows and columns - removing the impediment to
simple solution existent in some scenarios at present. The biggest
problem is one of documentation. There is a simple method of
recording M/Pairs (digits in bottom left corner of the cell). One
way forward would be to designate separate COLOURED PENS to
columns and rows as well as the existing REGION data. However
this does introduce an additional level of complexity (and human
dexterity in manipulating the trio/quartet) of pens! (NB: A quartet
applies because it is already recommended to xx to a different
colour pen for working after derivation of the candidate profiles).
I have not yet done the work on extending M/Pairs to rows/columns
- using the principle (but not the methodology!) of "Strong Links" -
but there could be some interesting aspects to be uncovered. I would
hope to find a methodology that leads to a resolution in a very high
proportion of cases - without needing to derive the Candidate Profiles.
+++
Mutual Reception applies within Mandatory Pairs when two digits
are constrained to be in the same two cells. This is a very powerful
situation in terms of knowledge. No other digit can get a look-in
so far as those cells are concerned and if one is resolved then
both are resolved. They are useful also for "counting". If a line
or region has, say, five cells resolved and a further two in Mutual
Reception, it can be demonstrated simply that the remaining two
cells must also be in Mutual Reception (and six resolved plus two
in M/R implies resolution of the remaining cell!).
If the cells in Mutual Reception are in the same row or column
(rather than being in oblique or skew relationship within a region)
they will "close" that row/column to any other occurrence of
EITHER of the digits in mutual reception (thereby giving scope
for application of the slice/dice or intersect methods in order to
resolve yet more cells, or at least to gain more useful data).
The term was "borrowed" from elsewhere because the two digits
are in a mutual relationship where they "receive" each other
and will brook no interlopers or external interference.
+++
The solution of a Sudoku puzzle is based on the accumulation
of information and, equally as important, a system of organising
such information to assist in further logical deduction. Of course,
some humans can use their short term memory for this purpose
but most of us prefer to have some form of written record.
Ideally each cell will have a unique digit associated with it, The
Mandatory pairs methodology reaches a compromise by recording
that a digit MUST be in one of just two cells. Candidate Profiles
comes at it in a different way by defining which digits are still
possibilities for the relevant cell. There may well be hordes of
other methods of recording information. In the end it is up to
each human solver to decide what suits her/him best.
Alan Rayner BS23 2QT
|
|
|
| Back to top |
|
|
Marty R.
Joined: 12 Feb 2006
Posts: 5770
Location: Rochester, NY, USA
|
| Posted: Wed Apr 12, 2006 4:54 pm Post subject: |
|
|
| Quote: | In the basic Mandatory Profiles methodology it is NOT necessary
to derive candidate profiles (thus avoiding what is perhaps the
greatest chore in Sudoku solution!!!). One can start applying the
logic and benefitting from the methodology right from the start.
Its simplicity comes from marking Mandatory Pairs only as they
apply to regions (3x3 boxes). As such the methodology misses
out on pairs not within the same region but in the same row or
column. Thus M/Pairs can solve SOME supposedly Very Hard
puzzles very easily whilst with others it cannot reach a solution
and, in the past, it has been necessary to resort to deriving the
Candidate Profiles (although with fewer cells involved as a lot
of the groundwork will have resolved a lot of cells in many cases). |
Alan, when I first saw your dissertation on MPs, I started using it, but only initially during the cross-hatching, and it is beneficial, but just minimally. Can you point me to an explanation of how to carry this concept further so as to reduce the job of candidate profile derivation? |
|
| Back to top |
|
|
samgj
Site Admin
Joined: 17 Jul 2005
Posts: 106
Location: Cambridge
|
| Posted: Wed Apr 12, 2006 5:22 pm Post subject: Re: Definitions of terminology |
|
|
| alanr555 wrote: | Candidate Profiles ... the digits are removed from that string when there is "evidence" that the particular digit is "impossible" in that cell. When the number of digits in the candidate profile for a cell has been reduced to one - that cell is "resolved".
|
Or, importantly, when there is only one location in any given row, column or box that can contain any given number.
| Quote: | Mandatory Pairs .... is a system of recording that applies to HUMANS only and there would be no point in attempting to adapt it to computer processing.
|
This is a useful (although perhaps not essential) computational step. My program (and the draw/play thing) use this logic in certain cases.
| Quote: | | Thus M/Pairs can solve SOME supposedly Very Hard puzzles very easily whilst with others it cannot reach a solution. |
I think this comes from the fact that several different logic requirements make puzzles hard and very hard in my grading. A couple of these are particularly ammenable to this approach, and sometimes their repeated application is enough to make a puzzle very hard.
| Quote: | One way forward would be to designate separate COLOURED PENS to
columns and rows as well as the existing REGION data. |
I do this by placing pencil marks that mean different things in different corners of the cell. Despite this, I prefer the smaller printouts, so a sharp pencil is required!
Sam |
|
| Back to top |
|
|
alanr555
Joined: 01 Aug 2005
Posts: 198
Location: Bideford Devon EX39
|
| Posted: Sun Apr 16, 2006 9:57 am Post subject: Re: Definitions of terminology |
|
|
| Code: |
>> Candidate Profiles ... the digits are removed from that string
>> when there is "evidence" that the particular digit is "impossible"
>> in that cell. When the number of digits in the candidate profile
>> for a cell has been reduced to one - that cell is "resolved".
> Or, importantly, when there is only one location in any given row,
> column or box that can contain any given number.
This latter is one of the rules applied by the computer - sometimes
known as "Sole Position". It is a matter of program design as to
whether this rule applies an override and resolves the cell directly
or whether it treats the necessity for that digit as eliminating all
others so that "standard" code can be used to resolve the cell on
the basis that only one digit remains in the "string".
Incidentally, this "Sole Position" rule is much easier for computers
than for humans. Has anyone NOT missed a "sole position"??
Alan Rayner BS23 2QT
|
|
|
| Back to top |
|
|
alanr555
Joined: 01 Aug 2005
Posts: 198
Location: Bideford Devon EX39
|
| Posted: Sun Apr 16, 2006 11:19 am Post subject: |
|
|
| Marty R. wrote: | | Quote: | In the basic Mandatory Profiles methodology it is NOT necessary
to derive candidate profiles (thus avoiding what is perhaps the
greatest chore in Sudoku solution!!!). One can start applying the
logic and benefitting from the methodology right from the start.
Its simplicity comes from marking Mandatory Pairs only as they
apply to regions (3x3 boxes). As such the methodology misses
out on pairs not within the same region but in the same row or
column. Thus M/Pairs can solve SOME supposedly Very Hard
puzzles very easily whilst with others it cannot reach a solution
and, in the past, it has been necessary to resort to deriving the
Candidate Profiles (although with fewer cells involved as a lot
of the groundwork will have resolved a lot of cells in many cases). |
Alan, when I first saw your dissertation on MPs, I started using it, but only initially during the cross-hatching, and it is beneficial, but just minimally. Can you point me to an explanation of how to carry this concept further so as to reduce the job of candidate profile derivation? |
|
|
| Back to top |
|
|
alanr555
Joined: 01 Aug 2005
Posts: 198
Location: Bideford Devon EX39
|
| Posted: Sun Apr 16, 2006 11:30 am Post subject: |
|
|
| Code: |
> When I first saw the dissertation on MPs, I started using it,
> but only initially during the cross-hatching, and it is beneficial,
> but just minimally. Can you point me to an explanation of
> how to carry this concept further so as to reduce the job
> of candidate profile derivation?
I spent over an hour replying to this in detail and then a couple
of wrong keys lost it all. I do not have time at present to recreate
what was a fairly full explanation and so, sorry to say, it will have
to wait until I am again in the mood - and not exasperated by loss!
Alan Rayner BS23 2QT
|
|
|
| Back to top |
|
|
Androgicus
Joined: 10 Apr 2006
Posts: 2
Location: Sunshine
|
| Posted: Thu Apr 20, 2006 12:08 am Post subject: Terminology Help |
|
|
Many thanks to all those wonderful gurus who have helped me, & my wife, continue to rise up the ladder of success in solving Sudoku puzzles. We can now solve Very Hard puzzles albeit with some difficulty. The main problem is that my wife is now better than I am at solving the difficult ones.
Thanks once again, Androgicus, Sunshine Coast. |
|
| 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
