x-cycle, y-cycle & 3D-Medusa

Advanced methods and approaches for solving Sudoku puzzles

Postby ronk » Thu Dec 15, 2005 5:48 pm

Ruud wrote:
ronk wrote:I'm of the impression that the "magic candidate" would be the candidate eliminated causing [8,5]=8, also via the simplest of constraints (naked or hidden single).

When looking for the optimal solving path, I used the term "magic candidate" for the candidates that forced a complete solution. Since there can be only one per cell, the term "magic cell" is equally valid.

What you're proposing here is that any single candidate that, when eliminated, forces a magic cell to it's solution digit is in itself a "magic candidate".

I apologize for my prior flippant comment, so let me explain my thinking.

I believe there are two categories of magic cells or magic candidates: one category for those interested in solutions by a human solver, or a computer program that emulates a human solver, and another category for those interested in computer-based solutions.

Without really realizing it earlier, most likely because of our earlier discussion on the Optimal Solving Path thread, I was thinking of a definition that would be appropriate for a human solver. The logical human solver is able to make cell assignments only as a result of, or in conjunction with, elimination of candidates.

At any given state of the puzzle, there might be several possible eliminations from which to choose, depending upon the skill and patience of the human solver. In this context, and in the context of an optimal solving path, finding an elimination that leads to a solution via singles only ... as early as possible ... seems like a reasonable basis for the definition of magic candidate.

For computer-based solutions, the objective of finding one (or more) magic candidate(s) that can be assigned in one (or more) magic cell(s) is different. Here we are interested in the assignment of a magic value at a magic location, at a time when candidate elimination is likely not available to cause that assignment.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Bob Hanson » Thu Dec 15, 2005 6:39 pm

It's important to remember that "magic cells" are completely
solver-dependent. What your solver is capable of determines where it gets
stuck and what it can do if it gets unstuck.

So this term is only significant in context. A puzzle does not inherently have
any "magic cells." Once you tell me what can be done with a solver --
Can it look for X-wings? Can it apply almost-locked sets? Does it use
templates? These must be defined first. If you allow it to check fully for
more of these things, you will get far more magic cells and a lower level of
"N-constrainedness" than if you allow your solver to only do "standard
singles-only" trial-and-error (like dancing links).
Bob Hanson
 
Posts: 75
Joined: 04 December 2005

Postby gsf » Thu Dec 15, 2005 7:41 pm

Bob Hanson wrote:It's important to remember that "magic cells" are completely
solver-dependent. What your solver is capable of determines where it gets
stuck and what it can do if it gets unstuck.

that's why I qualified my posts with "using FN constraints" or equivalently "using the simplest constraints"
all solvers have these, and for the most part solvers written for speed and not logical intuition use these exclusively in combination with a forward checking backtrack tree search

forward checking with learning rips through 9x9 sudoku
using this strategy requires only 9 backtracks for the top1465
but a move trace from those solvers is not much help to a human solver
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Re: x-cycle, y-cycle & 3D-Medusa

Postby RichardGoodrich » Wed May 01, 2013 3:49 am

Gentlemen,

Love the dialog on 3D Medusa. I "think" I really am beginning to understand it. I use Bob Hanson's Sudoku Assistant to check my work. I suppose at this time you guys have corrected my work on the puzzle I posted.

Anyway, I went off in a different direction, but suspect it may ultimately lead me back to 3D Medusa. I tool the first puzzle from Frank Longo's Absolutley Nasty Sudoku Level 4. However I decided to "finally" give a try to Denis Berthier's grid transformations.

So far I am encouraged even in generating them by hand - I took a slightly different approach then Denis Bethier suggested on page 47+ of his book: "The Hidden Logic of Sudoku - Part 2" So far it seem to have worked well for me.

If anyone would like to see my "Nasty1" Series that uses Bethier's grids here is a link to my sudoku blog: BigSudoku:
http://bigsudoku.wordpress.com/

BTW, I did do a bit of Medusa 3D coloring to find an elimination, but perhaps got a bit overwhelmed when I submitted it to
Bob Hanson's Sudoku Assistant! I want to get back to studying Bob's extensive analysis some time.

In the mean time I will post my one use of Medusa 3D to make an elimination on my BigSudoky Blog anon!

My one question about documenting 3D Medusa is the best way to show the chains to document it. I understand and like what Bob Hanson has done. I also see some references that DIC (Double Implication Chains) and Eureka notation are the way to go.

Any comments on that? I don't know the history on Eureka notation - was it David Eppstein who started it?

Shalom!
GrandPaBig
RichardGoodrich
 
Posts: 40
Joined: 12 December 2012
Location: Cash, Texas USA

Previous

Return to Advanced solving techniques