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 

Puzzle #47 Hard, or Impossible...

 
Post new topic   Reply to topic    dailysudoku.com Forum Index -> Other puzzles
View previous topic :: View next topic  
Author Message
rikko



Joined: 22 Feb 2006
Posts: 2

PostPosted: Wed Feb 22, 2006 12:16 pm    Post subject: Puzzle #47 Hard, or Impossible... Reply with quote

Hi, new to this forum, Not sure if this is the right place to ask, but anyway, I am able to do the majority of "hard" puzzles solved without relying on a 'hint', but probably only less than half of the ones marked as "very hard". However, this one (number 47, marked "hard") was in our local newspaper a few days ago, and it is a doozy - I am totally stuck!! I think it should be marked as "very hard indeed"!! and I can't resolve even one square using logic? (I obviously need some help with my logic). Has anyone else had problems with 47 too? (do I need to type it out here?). I'd rather not use a "hint" unless I could see the logic behind it...

- - - - 3 - - 6 -
- 5 - 4 - 1 7 3 -
- - - 6 - 7 - - -
2 - - - - 9 1 - -
- - 7 - - - 9 - -
- - 1 8 - - - - 4
- - - 9 - 6 - - -
- 8 9 7 - 3 - 1 -
- 6 - - 2 - - - -

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



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

PostPosted: Wed Feb 22, 2006 12:49 pm    Post subject: Maybe this will get you started ... Reply with quote

Hi, Rikko! Welcome to the forum. This is the right place to ask questions about "other" puzzles.

You need to think in terms of candidate profiles to solve this one. I'd suggest that the first number you can set is r6c2 = 9. Let me explain.

Concentrate on column 2, and on the middle left 3x3 box. By direct enumeration you can see that the only possible values at r4c2 are {3, 4} -- you have {1, 2, 7} in the middle left box, {5, 6, 8} in column 2, and a "9" in row 4. r5c2 is exactly the same because there's also a "9" in row 5. We can concude, then, that the pair of digits {3, 4} lies in r4c2 & r5c2, in some order.

Now look at r6c2. The only possibilities are {3, 9} -- you have {1, 2, 7} in the middle left 3x3 box, {5, 6, 8} in column 2, and a "4" in row 6. But there can't be a "3" in r6c2 because of the pair we just located. The only possible value in r6c2, then, must be the "9". dcb
Back to top
View user's profile Send private message Send e-mail Visit poster's website
TKiel



Joined: 22 Feb 2006
Posts: 292
Location: Kalamazoo, MI

PostPosted: Wed Feb 22, 2006 2:34 pm    Post subject: Reply with quote

Rikko,

IMO a puzzle like this is a good reason to use a helper software program, because there are no cells that can be solved by direct exclusion. I use a program that lists the candidates for each cell, after the starting grid has been entered. (I know some people think of this as cheating.) With that feature it is easy to see that there is a naked pair at r4c2 & r5c2 (3,4) and that the only candidates for r6c2 are (3,9), which allows for the exclusion of 3 and the placement of the 9 in that cell, as outlined by David in his post above. Actually, this whole puzzle has 3 naked pairs that, once those exclusions are made from other cells, allows one to solve the puzzle with nothing but singles, which doesn't seem to qualify as hard by anyones definition.

The question, in my mind, is how long does one want to spend figuring out candidate lists for each cell, until one finds the cells that allow some exclusions or placements that advance the puzzle? Truly hard puzzles don't allow placement of values in very many cells by direct inspection, so some kind of candidate list for each cell must be maintained, whether on the computer screen, on the paper or in your head. I can't/don't want to do it in my head and got tired of using up a whole eraser and having the paper look like bird cage liner material when I was done, so I use the software, which allows me to concentrate on solving the puzzle, not on making and maintaining candidate lists.

David,

I'm not sure what you mean by 'candidate profile'.
Back to top
View user's profile Send private message
David Bryant



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

PostPosted: Wed Feb 22, 2006 4:12 pm    Post subject: "Candidate Profiles" Reply with quote

Tracy wrote:
I'm not sure what you mean by 'candidate profile'.

Hi, Tracy! I'm glad you got your login fixed.

All I mean by "candidate profile" is the list of possibilities in a particular unresolved cell. For example, in the initial setup Rikko asked about the "candidate profiles" at r4c2, r5c2, and r6c2 are {3, 4}, {3, 4}, and {3, 9}, respectively. dcb
Back to top
View user's profile Send private message Send e-mail Visit poster's website
TKiel



Joined: 22 Feb 2006
Posts: 292
Location: Kalamazoo, MI

PostPosted: Wed Feb 22, 2006 4:18 pm    Post subject: Reply with quote

David,

That's what I thought but I wanted to check to make sure. Thanks.

The auto log-in still doesn't work, so I'm just logging in manually.
Back to top
View user's profile Send private message
Marty R.



Joined: 12 Feb 2006
Posts: 5770
Location: Rochester, NY, USA

PostPosted: Wed Feb 22, 2006 5:55 pm    Post subject: Reply with quote

Tracy,

I've been engaged in this insanity for about two months now, and I'm strictly a paper, pencil and eraser guy. I never cared for doing puzzles on the computer. It's so much more comfortable for me to sit on a couch, fully support my back and have the paper on a clipboard. Maybe someday I'll try the computer thing.

But I must admit, filling in cells with candidates is time-consuming, mistake-prone, drudgery and real "grunt" work. So is erasing the whole thing after I've backed myself into a corner with a duplicate number.

I don't think computer help is "cheating." After all, we're just entertaining ourselves, not engaged in competition where we've pledged to not use any electronic aids. Same with crosswords. I'll use dictionaries, almanacs, atlases, etc., again, just because I'm trying to entertain myself.

Rikko,

This is solvable using hidden singles, naked pairs and triples and locked candidates. It took me three times because twice I got backed into a corner with duplicate numbers due to mechanical errors. But no fancy, arcane techniques are needed.
Back to top
View user's profile Send private message
rikko



Joined: 22 Feb 2006
Posts: 2

PostPosted: Thu Feb 23, 2006 12:03 pm    Post subject: Puzzle #47 Hard, or Impossible... Reply with quote

Thank you all for your kind assistance. I think I can see some light to get me going now!
Cheers,
Back to top
View user's profile Send private message
alanr555



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

PostPosted: Sat Feb 25, 2006 11:37 pm    Post subject: Reply with quote

Code:

> Filling in cells with candidates is time-consuming, mistake-prone,
> drudgery and real "grunt" work. So is erasing the whole thing
> after I've backed myself into a corner with a duplicate number.

Agreed!

One way to reduce the drudgery and to retain an interest in the
"logic" (rather than doing profile derivation and searches) is to
start off with Mandatory Pairs. In most puzzles (almost all of those
set by SamGJ as Classics - possibly all) it is possible thereby to
resolve some cells and to reduce the number of unresolved cells.
Indeed, many of the Hard and V.Hard puzzles can be solved fully
using this recording method so that candidate profile derivation
is unnecessary. However M/Pairs cannot resolve all puzzles!

The point is that when one comes to a halt with M/Pairs, the next
stage is derivation of the "Missing" profiles. This is a digit string
for each row and column listing the digits yet to be placed on the
row or column. Normally these can be written at the top of the
column (outside the grid) or to the right of the row.

An important use of the Missing Profiles is to determine embedded
pairs/triples etc and these can be recorded by surrounding each
substring in parenthesis eg if there is a pair 34 in a string 23458
the original string (23458) can be rewritten as (34)(258).

Sometimes the pairs "leap out" at one as the Missing profiles are
derived (some arise directly from the M/Pairs work!) but sometimes
they do not become apparent until the candidates are being derived.
Either way, the "Missing" profiles help considerably with deriving the
candidate profiles and those profiles will usually be shorter than the
equivalent ones set at the beginning of a puzzle. The method is to
inspect the row and column "Missing" for each unresolved cell and
to determine the COMMON elements. Then a quick check to remove
any from the common subset that appear elsewhere in the region of
the relevant cell will produce an accurate candidate profile (so long
as the Missing profiles were derived accurately!!).

Using the M/Pairs methodology there are three stages

 a) Use normal logic to resolve cells and to record M/Pairs.
     (There are specific techniques which enable the recordings
     to reveal either resolved values or further pairings).

 b) Derive the Missing profiles
     (and use such to identify pairs between regions or to assist
      with sole position and/or sole candidate placements)

 c) Derive the full Candidate Profiles
     (although one would hope not to have to do this)

If a puzzle gets to stage (c) then there is normally some subtle
aspect of the profiles that one needs to find; whereas using the
profiles at an earlier stage means greater complexity and/or
proneness to error - just to resolve the "easier" cells.

In a lot of "stage c" cases, I find that the M/Pairs can assist
greatly with the "pruning" of the candidates. One of the problems
is that cells seem just to resolve themselves and it is very easy
to skip keeping the candidate profiles updated. Thus, I find myself
quite often reverting to use of M/Pairs once the "crunch point" has
been resolved by use of the candidate details.

+++
In the early days (for me May 2005) I was introduced to the
concept of "tiny writing" (ie candidate profiles) as THE method
to solve Sudoku. I accepted that and developed an elementary
computer solver (no sophistication!). Very soon, I got dissatisfied
with the "drudgery" etc and looked to develop an alternative way
of "getting in" to a puzzle. Gradually I became aware of the power
inherent in "binary" attributes - the yes/no, on/off aspect which
means that if it is [X or Y] and it is [not X] it MUST be [Y] and
so was led to develop the Mandatory Pairs approach. I find that
much more satisfactory than merely deriving candidate profiles
as I did when "tiny writing" was my only weapon in the armoury.

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



Joined: 12 Feb 2006
Posts: 5770
Location: Rochester, NY, USA

PostPosted: Sun Feb 26, 2006 7:09 pm    Post subject: Reply with quote

Alan,

Thank you very much for taking the time to write that reply. I am definitely interested in learning how to solve puzzles with less drudgery. At this point, I have been able to solve what I think are some difficult puzzles, such as the one introduced in this thread, by basic techniques such as hidden singles, naked pairs, triples and quads and locked candidates. I rarely, if ever, find an X-Wing, swordfish, XY-Wing or unique rectangle. The only advanced technique, if it is even considered advanced, that I’ve been able to use with any degree of regularity is forcing chains. Not coincidentally, these chains employ more mechanics than logic. I’m weak on binary logic and related areas.

What I do is start out by filling in whatever cells I can by techniques called “cross-hatching” and “slicing and dicing.” This solves very few cells in the more difficult puzzles. Then it’s writing the missing numbers for rows and columns outside the grid, which I did not know was called “derivation of missing profiles”). Then it’s filling in all cells with their candidates, which I didn’t know was called “derivation of candidate profiles.” Then it’s on to the techniques described in my first paragraph.

Unfortunately, I do not know what “mandatory pairs” are or how they would be used. Of course, I could easily determine embedded pairs/triples from the missing profiles, but wouldn’t know what to do with them.

Thanks again for your time and information. If you or others would like to amplify on the mandatory pairs and embedded pair/triples, that would be much appreciated.
Back to top
View user's profile Send private message
alanr555



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

PostPosted: Tue Feb 28, 2006 12:34 am    Post subject: Reply with quote

Code:

>Writing the missing numbers for rows and columns outside the
> grid, which I did not know was called “derivation of missing
> profiles”).

Please do not rely upon my terminology. I make it up as I go!
It was good to learn that someone else uses the technique (a
rose or a missing profile is as sweet by any other name!)

> Then it’s filling in all cells with their candidates, which I did
> not know was called “derivation of candidate profiles.”

Again my terminology - this time  to describe the "drudgery"!

> Unfortunately, I do not know what “mandatory pairs” are or
> how they would be used.

Essentially Mandatory Pairs is a system of recording whenever
a digit is restricted to one of just TWO places in a 3x3 region.
The digit concerned is written small in the bottom left of the cell
(unlike candidates which are usually written in the upper left).

There are a number of techniques that can be used with these
Mandatory Pairs. Many of them correspond to the "pattern
searches" used with candidate profiles but are generally much
more obvious when they occur. I have written about many of
them in this forum but they are not consistently collated.

Although the objective is to find just ONE cell in a region that
can hold a particular digit, it is very useful information to know
that the placing is restricted to just TWO (but virtually useless to
know that it is restricted to three places!!). The system is not
one for 'programming' as it is designed to assist the human brain
with the overload of data in short-term memory so that one can
concentrate on the logic rather than holding patterns in mind.

Using the 25th Feb as an example. One could start by noticing the
digits '1' in r2c1 and r1c5. These two constrain a digit '1' in box 3
to row 3 and the '1' in r8c9 excludes the '1' being in r3c9. This
leaves just r3c7 and r3c8 as possibilities for the '1' in box 3.
The M/Pairs technique would put a small '1' in the bottom left
corner of each of those two cells.

Eventually it will become apparent that the '1' belongs in r3c7 and
at that time one would expunge BOTH the small '1's in box 3.

Similarly to the placing of the '1' would be the restriction of the '6'
in box 3 to r1c7 and r1c8 - with consequent marking of those two.

I did not mark up the sequence of resolution for that puzzle (it
takes nearly three times as long to document as to solve!) but
I note that at some point box 4 has both '6' and '7' marked as
Mandatory Pairs in each of r4c1 and r6c1. Together with the '8'
in r5c1, this "closes" col 1 in box 4 - even though one does not
know which holds the 6 and which hold the 7. As I recall that led
to at least one pair in cols 2 or 3 in that box. What usually happens
is that setting one pair allows the potential for another pair and
the placings of the digit become increasingly constricted. As soon
as one of a Mandatory Pair becomes impossible, there is an
immediate setting of its partner as resolved - WITHOUT having to
revisit the logic that got one to that place earlier.

The M/Pairs method is excellent when pairs (or triples) are fully
within a box but they do not cope so well with remote pairs as
the only 'marks' allowed MUST be paired off within a region.
Thus the need to move to candidate profiles in a proportion of
hard/v.hard cases. I find that the gradings "hard" and "very hard"
do not apply distinctively when using M/Pairs. Either of them
could be solved fairly easily or fail completely without resort to
candidate profiles. Usually I aim to do "Medium" without any marks
but to treat hard and v.hard as equally difficult (or easy!) when
using M/Pairs. It all depends upon whether the subtleties of the
puzzle occur within a region or between regions.

Incidentally, Feb 25th has a triple in row 4 cols 7,8,9. This shews
up in M/Pairs as (48),(58),(45) in the three cells. As soon as one
of them is resolved the others fall immediately. Say (for example)
that r3c8 is set to '5'. This makes r4c8 impossible to be 5 and so
its partner (r4c9) MUST be '5'. This makes the '4' in that cell to be
impossible and promotes in partner in r4c7 to be '4', which in turn
invalidates '8' for that cell and promotes the '8' in r4c8. This is part
of the power of the method - the cascading of resolutions. However
it is VITAL not to confuse M/Pairs with Cand/Profs. Mandatory Pairs
do NOT include all possible values for a cell and MAY not include the
eventual value for a cell. Sometimes a cell can be involved as the
"impossible" partner in two or three pairs before being resolved
with a digit never previously associated with the cell.

+++

The basics of Mandatory Pairs were developed when I was on
vacation in France last October but additional features have been
discovered or added since then. The original idea (including some
features since dropped!) can be read using the following link.


Here is the link to the previous
notes.


Code:

That should give sufficient clues to start off an exploration of the
potential of a method which cuts candidate derivation drudgery
by half. Have fun!

PS:
> Of course, I could easily determine embedded pairs/triples from
> the missing profiles, but wouldn’t know what to do with them.

The normal approach would be to "prune" the candidate profiles in
the intersecting row/col and the region concerned.

With M/Pairs one would do the same thing - but without the full
candidate marks.

The substrings constrain digits to certain cells and. also, by the
same token reduce the number of cells where a digit may be placed.
When that number of cells reduces to TWO, the M/Pair should be
marked. If that creates a "Mutual Reception" then there is usually
wonderful scope for further constraint! A M/Reception is where two
cells each are involved with the SAME two digits as M/Pairs. This
equates to a 'hidden' or 'naked' pair but the distinction is totally
irrelevant in the Mandatory Pairs lexicon. The point is that their
"dance" around each other excludes interlopers!

If a triple is noted from the substrings of the Missing profile, the
best news is if it is within one region. Then the objective is to
identify and to record the M/Pairs within it. Sometimes this will
lead to a Mutual Reception and a single - great when it happens!

If however, the sub-string digits are spread over two (or three)
regions the informational value is mainly for the "counting"
process (checking the intersecting line and encompassing region).
Sadly the M/Pairs technique has no way of recording pairs which
operate between regions. I have tried marking such as 'candidates'
(ie top left instead of bottom left) but this just confuses the issue
until one moves to full candidate profiles. Incidentally, I have found
that a change of colour pen when making the move to c/profs is
a great advantage - not least being that one has a check-point to
which to return if one makes an error with the profiles!

Alan Rayner  BS23 2QT

Back to top
View user's profile Send private message
Marty R.



Joined: 12 Feb 2006
Posts: 5770
Location: Rochester, NY, USA

PostPosted: Tue Feb 28, 2006 5:46 pm    Post subject: Reply with quote

Alan, once again, thank you for the explanation. I've printed it out so I can study and try to digest it somewhere more comfortable than a computer chair.
Back to top
View user's profile Send private message
Marty R.



Joined: 12 Feb 2006
Posts: 5770
Location: Rochester, NY, USA

PostPosted: Thu Mar 02, 2006 6:30 pm    Post subject: Reply with quote

Alan, just to provide a little feedback: I now am using the mandatory pairs. Some puzzles they're of little help, others, a fair amount. Sometimes they yield naked pairs early in the process and can solve cells more easily and earlier than they would otherwise. Of course the drudgery of "Candidate profile derivation" hasn't disappeared, but can be a little less time-consuming.

I doubt that I am using mandatory pairs to its fullest potential, but it's definitely a helpful addition to the arsenal of techniques.
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    dailysudoku.com Forum Index -> Other puzzles 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