The New Sudoku Players' Forum

[champagne]

I don't understand all the fuss about this. We are talking of an exact cover problem - a problem whose solution has been known for decennies. It is know to be NP-complete.
999_spring made a very smart find for this puzzle. Finding the base and cover sets was great.
But there can be no debate about exact covers and I can't see the point of inventing new names for it.
Wikipedia is not always reliable, but in the present case, it has a good article: https://en.wikipedia.org/wiki/Exact_cover

And seen years ago by ronk in a nice example, the exact cover is a restrictive condition. The logic works as well with a vertice having 2 truths and 2 links

[denis_berthier]

I don't understand all the fuss about this. We are talking of an exact cover problem - a problem whose solution has been known for decennies. It is know to be NP-complete.
999_spring made a very smart find for this puzzle. Finding the base and cover sets was great.
But there can be no debate about exact covers and I can't see the point of inventing new names for it.
Wikipedia is not always reliable, but in the present case, it has a good article: https://en.wikipedia.org/wiki/Exact_cover

And seen years ago by ronk in a nice example, the exact cover is a restrictive condition. The logic works as well with a vertice having 2 truths and 2 links

Irrelevant in the current case.

[Ajò Dimonios]

In my opinion, together with Robert Maurie's proof that it is relative to all msls and sk-loops, it can be obtained as a rule deriving from the more general law that a rank <= -1 always produces an invalid sudoku because there is no possible solution that satisfies both the links that the truths when the links (not superimposable) are fewer than the truths, would always remain an unsatisfied truth. The rank = -1 would be created when any candidate present in a link not belonging to the truths was also imposed as true. I think that manually identifying the base of an msls is a fairly complex operation, certainly it is more useful to start from certain input numbers rather than candidates.

Paolo

[champagne]

In my opinion, together with Robert Maurie's proof that it is relative to all msls and sk-loops, it can be obtained as a rule deriving from the more general law that a rank <= -1 always produces an invalid sudoku
Paolo

Hi Paolo,

True and False.
True (but a conjecture) if basic moves are done,
False with an example here using Allan Barker's definition of truths with all candidates in the same box

I assume basic moves done when the TLG0 logic is applied

[Mauriès Robert]

Hi Denis,

I don't understand all the fuss about this. We are talking of an exact cover problem - a problem whose solution has been known for decennies. It is know to be NP-complete.
999_spring made a very smart find for this puzzle. Finding the base and cover sets was great.
But there can be no debate about exact covers and I can't see the point of inventing new names for it.
Wikipedia is not always reliable, but in the present case, it has a good article: https://en.wikipedia.org/wiki/Exact_cover

You seem to be saying that an MSLS is just a problem of exact coverage. Am I understanding correctly?
If so, it means that it is possible to fill the 16 boxes of the MSLS with the 9 occurrences without this generating a contradiction with the sudoku rules. But then, I don't see how this guarantees the eliminations associated with an MSLS, because there is no proof that this arrangement of the 9 occurrences in the 16 boxes is compatible with the solution of the whole puzzle.
I have obviously read the wikipedia article you refer to, but here the question of exact coverage is asked for the whole puzzle and not for a sub-puzzle of the puzzle.
Sincerely.
Robert

[denis_berthier]

Hi Denis,

I don't understand all the fuss about this. We are talking of an exact cover problem - a problem whose solution has been known for decennies. It is know to be NP-complete.
999_spring made a very smart find for this puzzle. Finding the base and cover sets was great.
But there can be no debate about exact covers and I can't see the point of inventing new names for it.
Wikipedia is not always reliable, but in the present case, it has a good article: https://en.wikipedia.org/wiki/Exact_cover

You seem to be saying that an MSLS is just a problem of exact coverage. Am I understanding correctly?
If so, it means that it is possible to fill the 16 boxes of the MSLS with the 9 occurrences without this generating a contradiction with the sudoku rules. But then, I don't see how this guarantees the eliminations associated with an MSLS, because there is no proof that this arrangement of the 9 occurrences in the 16 boxes is compatible with the solution of the whole puzzle.
I have obviously read the wikipedia article you refer to, but here the question of exact coverage is asked for the whole puzzle and not for a sub-puzzle of the puzzle.
Sincerely.
Robert

I'm not speaking of MSLS; I've never seen any definition of what an MSLS is. I'm speaking of the precise pattern at the start of this thread. The 16 rc-cells are covered by 16 rn and cn transversal cells.

[Ajò Dimonios]

Hi Champagne

Code: Select all

Champagne wrote
True and False.
True (but a conjecture) if basic moves are done,
False with an example here using Allan Barker's definition of truths with all candidates in the same box

I assume basic moves done when the TLG0 logic is

The two examples that I found in the link you sent me to me seem to show the first (3.2 Negative rank) the superposition of the two truths one of row and one of column and the second (5.1.1 TLG-1 plus one free truth ) an overlap of two truths (truth 1 in box 9 and truth 1 in r7). I meant truths and non-overlapping links. Can you give me an example with non-overlapping truths and overlapping links with rank = -1 in which the sudoku is valid?

Paolo

[champagne]

Hi Champagne

Code: Select all

Champagne wrote
True and False.
True (but a conjecture) if basic moves are done,
False with an example here using Allan Barker's definition of truths with all candidates in the same box

I assume basic moves done when the TLG0 logic is

The two examples that I found in the link you sent me to me seem to show the first (3.2 Negative rank) the superposition of the two truths one of row and one of column and the second (5.1.1 TLG-1 plus one free truth ) an overlap of two truths (truth 1 in box 9 and truth 1 in r7). I meant truths and non-overlapping links. Can you give me an example with non-overlapping truths and overlapping links with rank = -1 in which the sudoku is valid?

Paolo

Hi Paolo,

When I wrote that it is a conjecture for me that a valid puzzle can not give a negative TLG, It means that I strongly believe that this is true but that I can not prove it.
As you noticed, the only negative rank that I could figure out has an overlapping candidate and this candidate is true. BTW, it is the only candidate in the pattern having a "rank 0" using Allan Barker's adjustment.

The TLG-1 plus one is another story. Having recently analyzed the "fish guide", I have to-day a more precise view of the TLG-1 plus 'n' situation.

[Mauriès Robert]

Hi Denis,

I'm not speaking of MSLS; I've never seen any definition of what an MSLS is. I'm speaking of the precise pattern at the start of this thread. The 16 rc-cells are covered by 16 rn and cn transversal cells.

I don't understand your answer to my question. In his post at the beginning of thread 999_Springs presents this schema as that of an MSLS(*). But it doesn't matter. If you prefer to say that it is a 16 cells rc schema covered by 16 cells rn and cn, my question becomes: what proves the eliminations just because this schema is an exact cover.
Sincerely.
Robert
(*) I can give you my definition of an MSLS if you like.

[denis_berthier]

If you prefer to say that it is a 16 cells rc schema covered by 16 cells rn and cn, my question becomes: what proves the eliminations just because this schema is an exact cover

It is the same proof as for Subsets: a counting argument.

[eleven]

I don't see any advantage to formulate that as as an exact cover problem, and i would not know, how to integrate the requirement, that the number of cells is equal to the number of outside digits.
Also seeing normal sudoku as an exact cover problem was not very fruitful, after it had turned out, that direct backtracking was faster than the dancing links algorithm.

[Mauriès Robert]

Hi Eleven,
What is your definition of an MSLS ?
I can't find a rigorous definition on the forum.
Robert

[denis_berthier]

I don't have Windows and I can't use XSudo. What does one get from XSudo when it is given this puzzle (with no added hint)? Does it find this pattern?

[Mauriès Robert]

I don't have Windows and I can't use XSudo. What does one get from XSudo when it is given this puzzle (with no added hint)? Does it find this pattern?

Me neither, with Apple, I don't have the possibility to use Xsudo. But Phil's solver (http://www.philsfolly.net.au/) finds this MSLS.
Robert

[eleven]

Hi Eleven,
What is your definition of an MSLS ?
I can't find a rigorous definition on the forum.

I tried it in the other thread here. But it is not the clearest definition and i am not sure, if all would agree with it. (What i call "link" there is represented by the "outside candidates" in the example of the top post here)