Flagged Revisions installed. Unapproved pages display a Red unchecked notice under the title. Trolls attack here by creating and archiving pages with offensive content. To verify an archived page, check the original URL. Questions about administration? Contact User talk:Abd. Limited privacy on this site, see CFC:Limited privacy

Difference between revisions of "Sudoku/Controversies/Uniqueness"

From CFC
Jump to: navigation, search
[checked revision][checked revision]
(Follow-up)
(Follow-up)
 
Line 75: Line 75:
 
==Follow-up==
 
==Follow-up==
 
I answered a question about "unsolvables" on Quora, [https://www.quora.com/Has-anyone-ever-seen-an-unsolvable-Sudoku/answer/Abd-Ul-Rahman-Lomax Has anyone ever seen an unsolvable Sudoku?] and there was [https://www.quora.com/Has-anyone-ever-seen-an-unsolvable-Sudoku/answer/Abd-Ul-Rahman-Lomax/comment/114348130 a comment by Roy Leban], which [https://www.quora.com/Has-anyone-ever-seen-an-unsolvable-Sudoku/answer/Roy-Leban/comment/114348644 he summarized in response to a comment on his own answer] as "You are incorrect." I quote his first reply on the subpage, [[/Leban]], for purpose of study and analysis. --[[User:Abd|Abd]] ([[User talk:Abd|talk]]) 13:16, 23 October 2019 (UTC)
 
I answered a question about "unsolvables" on Quora, [https://www.quora.com/Has-anyone-ever-seen-an-unsolvable-Sudoku/answer/Abd-Ul-Rahman-Lomax Has anyone ever seen an unsolvable Sudoku?] and there was [https://www.quora.com/Has-anyone-ever-seen-an-unsolvable-Sudoku/answer/Abd-Ul-Rahman-Lomax/comment/114348130 a comment by Roy Leban], which [https://www.quora.com/Has-anyone-ever-seen-an-unsolvable-Sudoku/answer/Roy-Leban/comment/114348644 he summarized in response to a comment on his own answer] as "You are incorrect." I quote his first reply on the subpage, [[/Leban]], for purpose of study and analysis. --[[User:Abd|Abd]] ([[User talk:Abd|talk]]) 13:16, 23 October 2019 (UTC)
 +
==Reddit 2020==
 +
There was a discussion on Reddit that became extensive, and extensive discussions on Reddit can become annoying. A lengthy post was detailed and is being copied here: [[/Reddit]].

Latest revision as of 17:10, 15 January 2020

From Sudopedia, as mirrored here ("last modified 06:22, 20 March 2008.").

Indented, italic commentary is by Abd (talk) 20:13, 26 September 2019 (UTC)

Uniqueness Controversy[edit]

The use of solving techniques that base deductions on the premise that the Sudoku has a unique solution is controversial.

On the one hand, there is only one fundamental rule to Sudoku:

You must place digits into the grid in such a way that every row, every column, and every 3x3 box contains each of the digits 1 through 9.

There is nothing in this rule that states the puzzle must have a unique solution. Indeed, the extreme case--a blank puzzle, with no givens whatsoever, has over 46,000 solutions just from possible placements of a single digit on the starting blank puzzle.

So there is nothing in the rules, some say, that entitles a solver to assume a Sudoku has a unique solution.

What is this "entitles" concept? Is it logical? I can assume anything I choose, and math is generally based on assumptions, called "axioms." Different systems of math exist that use differing assumptions. Now, some assumptions may lead me to conclusions that are counterfactual. On the other hand, if 99.99% of all swans are white, I might well assume that a black bird is not a swan, and it gets even more certain if I decide that if a bird is black, it simply is something else, perhaps a Bad Swan, defective.

On the other hand, say others, nearly all published Sudoku puzzles have only one solution--or claim the solution is unique.

This was a wiki, and the good thing about wikis is that language often gets polished. A crucial qualification was added, "nearly all." There are some published Sodoku with more than one solution, and we have seen, as I recall, three examples in recent months on the Sudoku subreddit.

It is irritating both to the publishers of such puzzles and to their solving audience if the puzzle has more than one solution. So if you know that the proposer of the Sudoku intends it to have a unique solution, why shouldn't you be allowed to take advantage of that bit of knowledge when making logical deductions to solve the puzzle?

Again, this odd language: "Allowed." Is there some authority watching to make sure we do not commit logic sins?

Again on the other hand, the claim has been made that all logical deductions made by the Uniqueness family of solving techniques that assume a puzzle has a unique solution can be found by other means that do not require the Uniqueness assumption.

I make that claim, and, in fact, no contrary example is known. Peter Gordon, in his Mensa Guide (2006), wrote about his discovery of what he called "Gordonian rectangles," which were what others have called, "deadly rectangles," patterns that if they are allowed, would create multiple solutions. He was thrilled, because it enabled him to solve a Sudoku which, it had been claimed, was unsolvable "without guessing." He published that puzzle. It was solvable without guessing. This whole category of puzzle (unsolvable) was created out of ignorance, a translation of personal incapacity into a then-assumed quality of the puzzle.
Yet every sudoku is solvable without guessing. In fact, Gordon knew that the puzzle he was working on had a unique solution because his friend Frank Longo had tested it with his computer solver. Computers don't guess. They operate off of lists and follow strict logic. The same process done by a human would merely be tedious, but it would not be guessing.
The normal meaning of a "guess" is a random pick from some set of possibilities. And the Sudopedia definition of "guess" was:
A digit placed into a cell without a logical reason.
I must understand "placed into a cell" as meaning an entered resolution. In ink, so to speak, as opposed to pencil. Are candidate markings (pencil marks) "guessing'? No, we add up to nine pencil marks, usually much fewer, listing "candidates" for the cell. Pencil marks list candidates, and we assume that all nine candidates are possible until and unless some are eliminated. Elsewhere, we will explore this issue of "guessing," and it's received some serious attention -- and there is serious nonsense written by experts who should know better, my opinion. There has been a lack of rigor.

But again contrariwise, no rigorous mathematical proof of this assertion has been put forward.

Depends on what one means by "rigorous mathematical proof." It is simply not controversial at all that all Sudoku are solvable with Ariadne's Thread, which is what computer solvers use (or equivalent, I just saw a claim that a particular solver does not use AT). Ariadne's Thread can be implemented with efficiency or without, and computers are fast enough that it is not worth the programming effort to make them more efficient.
Human solvers using Ariadne's Thread can use more efficient approaches, and restricting tests to bivalue choices made following a specific algorithm is one of these. In order to reject the assertion that not all are solvable by "other means" than uniqueness tests, one must ignore the obvious fact, so what is really meant is "solvable by logic," and, then, it turns out "logic" in that does not mean "logic" as the word is ordinarily understood. It means a "Using a set of relatively simple patterns or procedures that can be recognized with relative ease." Thomas Snyder defines it as "can be done in my head without any writing."
But one can solve puzzles by analyzing them using distinctive candidate marks, and this is called "coloring." And then coloring has been rejected because it is allegedly complicated and involves "guessing" what to color. None of that is based on sophisticated experience with how to use coloring without simply guessing what seed pair to color (and many discussions of coloring don't even mention using pairs as seeds, but just "guessing" a digit to color from, and they completely ignore the interactions that can then be seen. They ignore the use of intelligence to choose the seed. Instead, they call it "trial and error," when no "error" is involved, only the observation of logical consequences, and in actual practice, results are obtained, quite often, before any "contradiction" is identified.)

And so the controversy continues.

I'll be bringing examples here. This was from 2008 or earlier.

The following should help clarify and limit the controversy:

- Sudoku axioms are constraints on the solution, given the entries (whichever these are); they are constraints the PLAYER must satisfy;

- Uniqueness is a constraint on the entries; it is a constraint the PUZZLE CREATOR must satisfy and the player may use if he trusts the puzzle creator; for the player, it is like an oracle on the puzzle.

Accepting rules based on the "axiom" of uniqueness is thus mainly a matter of personal taste. There is nevertheless an objective feature of these rules: even if they are not needed (which is not proven), they may simplify the solution.

Axioms are assumptions, considered fundamental. Who decides what is fundamental? This is a fact: uniqueness was hardly mentioned in the early years, it was assumed without being formally stated, and because uniqueness was not used to find solutions, but rather purely logical inference from the numbers, so there was no need for the assumption. It is still not stated as a rule, even in books that propose using uniqueness. (Frank Longo's Beyond Black Belt Sudoku, very aware of Gordon's work (and mentioning "Gordonian Rectangles" without explanation), does not state it as a rule, he makes the standard statement.
What has been claimed is that if a Sudoku has more than one solution, it is not a Sudoku. This is the "No True Scotsman" argument. My own opinion on that is that a non-unique Sudoku is just that, nothing more and nothing less. They are rare, to be sure. What we know is that if one assumes uniqueness for a solution, one has obviously not shown that the solution is unique. Using a uniqueness resolution can conceal the other solutions, this is known.
What one "should" do as a solver depends on the goal. If the goal is to find a solution, any solution will do, using uniqueness is not known to conceal a valid solution. I have seen no proof of this, though; however, if a uniqueness strategy is used and the puzzle then has no solution, I would hope the person would bring this puzzle to the attention of the community! One could test the puzzle with a computer solver, as one way beyond the problem. The Sudokuwiki Solver will list up to 500 solutions, if they exist. It should also be possible to show more than one solution explicitly. (It has been claimed that in order to "solve" a non-unique sudoku, one must guess. Again this is all ontologically naive. The SW Solver doesn't guess, it simply finds and lists all solutions (up to 500) based on strict logic.)
On the other hand, if the goal is to find and prove that one solution is valid and that there are no others (if that is so) or that there exists more than one (if that is so), then uniqueness strategies cannot accomplish that.
By using uniqueness, Gordon was avoiding discovering deeper and more powerful strategies, in favor of finding a quicker solution.
I have solved one particular well-known "unsoveable," and it took maybe a day of exploration. I found a solution, but proving it was unique would take another day, which I haven't done. It is a little more difficult because solving assistants like Hodoku refuse to work with "invalid" Sudoku. It must all be done manually. Now, if we like the process of logical examination, is that "good news" or "bad news"?
It is either, if we say so.
It all depends on our goals, and, if we are free, we choose our goals. Pretending that this is not a choice, but exists in some realm of the "right" and "wrong" ways, is disempowering, restricting us, reducing possibilities and decreasing fun -- and creating useless arguments. My opinion!

Comments and edits welcome.

Follow-up[edit]

I answered a question about "unsolvables" on Quora, Has anyone ever seen an unsolvable Sudoku? and there was a comment by Roy Leban, which he summarized in response to a comment on his own answer as "You are incorrect." I quote his first reply on the subpage, /Leban, for purpose of study and analysis. --Abd (talk) 13:16, 23 October 2019 (UTC)

Reddit 2020[edit]

There was a discussion on Reddit that became extensive, and extensive discussions on Reddit can become annoying. A lengthy post was detailed and is being copied here: /Reddit.