The New Sudoku Players' Forum

[ravel]

Only true if you catagorize brute force methods as logical.

Hm, for me there is no doubt, that Carculs method to find the solutions is not (equivalent to) brute force. Otherwise he would still be sitting before the hard puzzles trying to solve them. I do not think, that you can apply the Algorithmic Information Theory in that simple way to decide this. You have to take into account
- the enourmous number of theoretical possibilities a solver can exclude in short time (by his experience) and
- all the shortcuts he has by applying known techniques.
Also note that not only the complexity of single steps has to be considered, but also the order and efficiency of the steps. This gives a much higher complexity than you talked of.
Without being able (and very interested) to prove it, i am sure that Carculs method reduces the overall complexity so essentially, that it does not fall into the brute force category.

[RW]

Specifically, it states that for a theory to be a theory, it must be simpler than the data it describes. In our sudoku problem, that usually means that the number of candidates you use in your "theory" to eliminate a specific candidate or set of candidates needs to be able to be less than the number of "data" candidates you use to "crash the puzzle" if you just assumed that the candidate you eliminated was true. In the case of Carcul's SIN and RW's trailing method, the number of candidates in the "theory" is always identical to the number of candidates in the "data", therefore there is no theory.

I am aware of the "brute force" aspect of my trailingmethod, but I wish to point out that there is also a difference between defining a "theory" and solving a puzzle. I did not try to define any universal theory that could be applied in many different situations. My goal was simply to find a solution that applies as little brute force as possible. This I try to achieve by finding short trails and find the "key cells", cells where removal of the candidate actually helps us solve the puzzle. Any solver could indeed break this puzzle by applying SINs (which I think equals my trails, right?) but can You solve it using less than 3 SINs?

So the "technique" part in my solving is actually a lot more complex than the data it describes (which should make it even less a theory). I take in consideration lots of candidates that don't have anything to do with the specific trail I follow. The actual trails, as you say, use exactly the amount of data needed to "crash the puzzle", but the real work is done before I start the trails.

As for the solutions, I think they are definately logical. Then it's a totally different question if they can be regarded "beautiful". Personally I think a solution is beautiful when I can crack an extremely hard puzzle with a <5 step trail. In this case I don't think that is possible and then things might get a bit more ugly. I would though be very interested to see any possible solutions that require less brute force than my. Of course the ideal would be to define theories that can solve any situation, but I don't think we'll ever get there. The hardest puzzles will always require some amount of brute force.

I have some thoughts on the way you wish to define theory and brute force as well, but I'll post more about that in the thread where it belongs when I've studied your arguments a bit more closely.

Regards
RW

[gsf]

Specifically, it states that for a theory to be a theory, it must be simpler than the data it describes.

the existence of single cell xy-cycle backdoors (magic cells) for almost all 9x9 sudoku
(actually all of the ones scraped from the forums) gives support for mj's statements

the puzzle in question has 4

Code: Select all

[73]=6[83]=4[87]=6[97]=4

find a way to solve any of these and the puzzle cracks

so the backdoors provide a clue to what the theory should be
start with the answer and work backwards to produce elegant solutions

in a sense the algorithmic info theory limit for 9x9 sudoku would
be to list one of the backdoors (can't get much simpler than that)

at the moment nobody has a method for predict backdoors
without solving a puzzle in the first place (therein lies my interest)
so its not much help for the solvers except to provide a hint/goal
for short/elegant solutions

[Myth Jellies]

Hm, for me there is no doubt, that Carculs method to find the solutions is not (equivalent to) brute force. Otherwise he would still be sitting before the hard puzzles trying to solve them.

So, your logical statement is: If Carcul is not still sitting before the hard puzzles trying to solve them, then Carcul's method must not be "brute force." I do not get that kind of respect even from my family . Since I do not know Carcul that well, I will stick with the branch of mathematics that was developed to answer questions like this.

I do not think, that you can apply the Algorithmic Information Theory in that simple way to decide this. You have to take into account
- the enourmous number of theoretical possibilities a solver can exclude in short time (by his experience) and
- all the shortcuts he has by applying known techniques.
Also note that not only the complexity of single steps has to be considered, but also the order and efficiency of the steps. This gives a much higher complexity than you talked of.

We are only talking about the merits of the SIN method here. If Carcul chooses to incorporate other theoretical methods, such as uniqueness rectangles, in his chains, then the brute force comparison is allowed to incorporate those methods as well. You don't get a free ride on the coat-tails of another theoretical method.

We are only worried about advancing the puzzle from a state A (just before the application of the method in one of the SIN steps) to a state B (just after the SIN step). If you compare the number of operations in the SIN method and compare it to the number of operations for brute force to assume the value and follow it along until it crashes, you will find that the delta is always zero at best. Why do we know this? Because SIN has actually documented one possible brute force crash for us which uses the same number of steps, and it might not have even been the quickest crash. (I hope this answers ronk's question as well.)

I will grant that both Carcul and RW's experience enables them to make better educated guesses for which candidates will provide quick crashes or more valuble results for solving the puzzle. These are worthy ideas, especially if you measure success in terms of solving speed or solving without pencil marks. They can also be chock full of logic. But that does not make the methods employed any less brute force.

Of course the ideal would be to define theories that can solve any situation, but I don't think we'll ever get there. The hardest puzzles will always require some amount of brute force.

If you have visited the website and read the article, then you know that this is a definite possibility. With all of the advancements we have made in coming up with theoretical methods for solving sudokus in the past few months, I don't think it is time to throw in the towel just yet, though.

[RW]

the existence of single cell xy-cycle backdoors (magic cells) for almost all 9x9 sudoku
(actually all of the ones scraped from the forums) gives support for mj's statements

the puzzle in question has 4

Code: Select all

 
[73]=6[83]=4[87]=6[97]=4


find a way to solve any of these and the puzzle cracks

In case any of you wishes to try this I can give you a little hint. The first three cannot be solved by numeral logic until you've first solved number 5 in r8c4 or number 4 in r7c5*. How can I be so sure about that? Because those are the only cells that can define valid row information for r7c3, r8c3 or r8c7. Without any of those cells solved you could (through lots of work) find that r78c3=(46) or row 78c7=(56) but never define which one goes in which row. If you had both those pairs solved (through even more work) and also solved number 4 in r2c6, then you could solve all of them through the uniqueness reduction r78c5<>5.

[edit: *Obviously you cannot solve r7c5=4 either, until you've solved r8c5=1, as you will not get any row information for that number from unsolved r8c3 => the only way of solving any of the numbers would be by first solving r8c5=1 or r6c5=5.]

So my best guess is: if you want to take advantage of these backdoors, try r9c7.

RW

[ravel]

RW's comment shows that the number of single backdoors or backdoor pairs does not say very much about how hard a puzzle is. It can be easier to resolve more and other numbers than to try to get to the backdoors.

[Carcul]

the existence of single cell xy-cycle backdoors (magic cells) for almost all 9x9 sudoku (actually all of the ones scraped from the forums) gives support for mj's statements (...) the puzzle in question has 4 (...) [73]=6[83]=4[87]=6[97]=4

Just to be more exact, r9c7=4 is the only "true" magic cell for this puzzle, as from it we only need singles, locked candidates, and naked pairs or triples to solve the puzzle, while for the other three backdoors given by Gsf we need, besides that, a X-Wing and two XY-Wings.

Carcul

[gsf]

the existence of single cell xy-cycle backdoors (magic cells) for almost all 9x9 sudoku (actually all of the ones scraped from the forums) gives support for mj's statements (...) the puzzle in question has 4 (...) [73]=6[83]=4[87]=6[97]=4

Just to be more exact, r9c7=4 is the only "true" magic cell for this puzzle, as from it we only need singles, locked candidates, and naked pairs or triples to solve the puzzle, while for the other three backdoors given by Gsf we need, besides that, a X-Wing and two XY-Wings.

"true" is a misleading word choice
sudoku backdoors must be qualified by the techniques applied
I did that by saying "xy-cycle backdoor"
if you prefer less techniques then there is 1 "singles, locked candidates, and naked pairs" backdoor
(neither hidden pairs nor triples or quads needed)

[StrmCkr]

deleted