The New Sudoku Players' Forum

[dobrichev]

Some puzzles may require very complex logic to determine that they have no solution or have many solutions.

Are there discussions on this subject?

[Mathimagics]

Are there discussions on this subject?

Well, there is at least one now!

It's a good question, really. And I'm happy to make some initial observations:

• Consider the much-maligned "brute force" method. The solver, human or otherwise, examines the consequences of pencilling in a cell value, from which it either finds a solution, or a contradiction. So an invalid puzzle to with is fundamentally equivalent to a "bad guess", albeit one presented to the solver disguised as a given.

• So, on one level, there seems to be no need for any logic outside what we already know & do. Or perhaps Mladen means: "is there some advanced validation technique" that might be used, like (allegedly) AST's are used for valid puzzles, that might allow one to deduce that the puzzle is invalid?

I guess, whoops, I deduce that I am asking what it is you mean by "very complex logic" ...

[m_b_metcalf]

Some puzzles may require very complex logic to determine that they have no solution ...
Are there discussions on this subject?

Taking no solution first, I use three tests after the basic eliminations (counting can sometimes be very expensive):

check that each empty cell has at least one candidate;

check that that each row/column/box has at least one candidate for each missing value;

check for clashes: that no two single candidate values share the same cell (can be extended to no three single values share same cell, etc.).

For many solutions, I check that all UA4s and UA6s are covered. That's a start but not sufficient.

Regards,

Mike

[dobrichev]

@Mathimagics: "very complex logic" = something worth to be investigated. In hope "monsters" to appear.

@m_b_metcalf: But using ordinary pencilmarks identifies these contradictions (except UA), right?
And knowing UA for still unknown solution grid(s) is a challenge

For determining multiple solutions, counting for at least 8 different given digits and looking for no two empty rows in a band can be considered most basic techniques, "singles".


Is Denis Berthier's rating sensitive to puzzle validity?

[Mathimagics]

Ah, you see, I thought "complex logic" was actually something like that expressed by my primitive avatar!

For determining multiple solutions, counting for at least 8 different given digits and looking for no two empty rows in a band can be considered most basic techniques, "singles".

Yes, indeed, and that's a good illustration of the key point of your question ... so AVT's exist! The hunt is officially on for more ... Tally ho!

[denis_berthier]

Is Denis Berthier's rating sensitive to puzzle validity?

Let me first recall some context:

- Each of the ratings I defined (there are several: W, B, gW, gB, S+B, S+gB, S+gW, S+gB, SpB, BpB, ...) is based on an increasing sequence of resolution theories, i.e. pure logical (more precisely: pattern-based) ways of solving puzzles. The corresponding rating of a puzzle (possibly infinity) is the level of the smallest theory in the hierarchy that solves the puzzle.
- The approach applies to any finite CSP, not only Sudoku.
- What is produced when a puzzle (valid or not) is fed to some of these resolution theories is all that can be logically deduced about it by this theory (in the present case: value assertions and candidate eliminations).
- In this approach, logical deduction is intuitionnistic/ constructive.
- A logical theory (be it classical or constructive) can prove what and only what is common to all its models.

As a result of the last point, when a puzzle P (not necessarily valid) is fed to a resolution theory, the outcome may be:
1) its solution (together with the associated rating and the resolution path - which is a constructive proof of the solution);
2) a contradiction (together with the path leading to it - which is a constructive proof of the contradiction); in PBCS, I've given an example of this case, showing that proving a contradiction can be as hard as finding a solution; (indeed, I had given examples much before, but the forums have disappeared); the level reached to prove the contradiction can be considered as its rating;
3) a intermediary resolution state, made of proven values, eliminated candidates and remaining candidates.

The first case is the standard case and has been discussed at length.

I think the second case fully answers Mathimagics' initial question about contradictory puzzles: if a contradiction can be proven in any of the above resolution theories, it will be found and an associated rating will be produced. However, this leaves open one question. I've proven long ago that all the known valid 9x9 puzzles (and very likely all the valid 9x9 puzzles) can be solved in some BpB with p≤7; I don't know whether this can be extended to contradictory puzzles; I have the feeling that yes, but not enough data to make it a conjecture; it may be a very interesting question to explore: find an invalid 9x9 puzzle the invalidity of which requires 3 levels of T&E. More generally, one could also define a notion of a minimally contradictory puzzle, compute the number of such puzzles (modulo isomorphism or not), compute their distribution wrt to some rating, produce a list of the potentially hardest minimally contradictory puzzles, ... Moreover, it may be almost as much fun to logically prove a contradiction as to find a solution: the same techniques can be used.

The third case is more complex to deal with. The question is "what can be said of the final resolution state when it's neither a solution nor a contradiction?". In this case, it's not even guaranteed to be the state common to all the solutions of P (some stronger resolution theory might eliminate more candidates or prove more values). Anyway, this case raises a more basic question: what do we want to define as the rating of a multi-solution puzzle? A possibility would be to ask only for the minimum level of T&E required to find all the solutions. But most definitions may be totally intractable in most cases: what's the rating of the empty puzzle? I'm not very eager to analyse this case further.

[dobrichev]

Hi Denis,
Thank you for the answer.

The multiple-solution case shouldn't be a stopper if
- you take care when using resolution theories that assume uniqueness of the solution. Most trivial patch is to disable these theories for this particular case.
- at some stage you are using (educated or not) T&E. Then the "else" path should be investigated too (possibly even for traditional rating). When a secondary solution is found, then the difference between the two solutions forms a deadly pattern, which proves the non-uniqueness of the puzzle. At this stage the process can stop.
- by introducing the elementary checks for non-empty areas and insufficient digits (as mentioned above in the thread) all wild cases like empty grid can be resolved by these "basic resolution theories".

Is your rating system materialized in an open source software?

Is it possible (after minor modifications) pencilmarks to be used as input instead of ordinary puzzle?

Thanks,
MD

[blue]

Hi Mladen,

For determining multiple solutions, counting for at least 8 different given digits and looking for no two empty rows in a band can be considered most basic techniques, "singles".

I almost mentioned this earlier, but didn't know if it was relevant: there are puzzles with fewer than 8 digits and/or with 2 or 3 empty rows in a band, that have no solution, rather than multiple solutions.

Would the goal be to determine the final disposition, or only to determine whether it does/doesn't have a unique solution ?

Blue.

[dobrichev]

I almost mentioned this earlier, but didn't know if it was relevant: there are puzzles with fewer than 8 digits and/or with 2 or 3 empty rows in a band, that have no solution, rather than multiple solutions.

Good point!

Would the goal be to determine the final disposition, or only to determine whether it does/doesn't have a unique solution ?

It isn't clear. Maybe more correct is to do (and rate) the necessary steps that prove the non-existence of a solution?

[denis_berthier]

The multiple-solution case shouldn't be a stopper if
- you take care when using resolution theories that assume uniqueness of the solution. Most trivial patch is to disable these theories for this particular case.

No patch is needed; resolution theories don't include rules based on uniqueness (said otherwise, they don't "assume uniqueness"). Uniqueness is proven at the time a solution is found. And the question of uniqueness vanishes if a contradiction is found.
Occasionally, I've written and used rules for uniqueness (mainly to test them) but I don't use them on a regular basis.

Is your rating system materialized in an open source software?

No. SudoRules or its CSP-Rules generalisation are not open source.

Is it possible (after minor modifications) pencilmarks to be used as input instead of ordinary puzzle?

Yes, it could be done. It would only require to write the proper input function.
But I've never been interested in multi-sol puzzles and I still don't see the point of trying to rate them.

[m_b_metcalf]

2) a contradiction (together with the path leading to it - which is a constructive proof of the contradiction); in PBCS, I've given an example of this case, showing that proving a contradiction can be as hard as finding a solution; (indeed, I had given examples much before, but the forums have disappeared); ...

Denis,

If the Programmers' Forum is the one you meant, you'll find an archived copy here.

Regards,

Mike

[denis_berthier]

2) a contradiction (together with the path leading to it - which is a constructive proof of the contradiction); in PBCS, I've given an example of this case, showing that proving a contradiction can be as hard as finding a solution; (indeed, I had given examples much before, but the forums have disappeared); ...

Denis,
If the Programmers' Forum is the one you meant, you'll find an archived copy here.

Mike,
Thanks for the reference. It may be useful at some point. For the present discussion, it doesn't really matter where an example appeared.
I checked the no-solution example I gave in PBCS: it's rated B7, which is moderately hard. I'm sure one can find still harder ones.