The New Sudoku Players' Forum

[dxSudoku]

Here is what I understand the puzzle-solving technique Brute Force is defined:

"Brute Force
Brute Force is not really a technique: Place a digit in a cell and look, whether you get a solution or not. If that technique is enabled, every sudoku can be solved."

http://hodoku.sourceforge.net/en/tech_last.php

It seems to me having to use Brute-Force to solve a puzzle is the same thing as guessing. And if you are guessing it's the same thing as starting with a different constellation of givens.

So in my mind, having to use Brute-Force to solve a puzzle for a constellation of givens makes it an invalid puzzle. For a puzzle to be considered a valid Sudoku, it has to be solvable using logic, in my opinion.

Thoughts? Criticisms? Accusations of insanity?

[marek stefanik]

Hi dxSudoku,

Every puzzle that has exactly one solution is valid. The problem is what you define as logic.

Most of the hardest puzzles known contain an Exocet or a MSLS. Many of them can be solved using these techniques, yet without them Hodoku is absolutely clueless and might end up using brute force more than once. I think we can agree that they count as logic.

Most rating systems use something called Nested Dynamic Chains to solve and rate every sudoku currently known. Are these not considered logic?

If you answered 'no', it still doesn't mean that the puzzles aren't solvable logically, there could well be an elegant way we just haven't found.

Marek

[dxSudoku]

Hi dxSudoku,

Every puzzle that has exactly one solution is valid. The problem is what you define as logic.

Most of the hardest puzzles known contain an Exocet or a MSLS. Many of them can be solved using these techniques, yet without them Hodoku is absolutely clueless and might end up using brute force more than once. I think we can agree that they count as logic.

Most rating systems use something called Nested Dynamic Chains to solve and rate every sudoku currently known. Are these not considered logic?

If you answered 'no', it still doesn't mean that the puzzles aren't solvable logically, there could well be an elegant way we just haven't found.

Marek

Thank you for responding. I totally agree just because brute-force is used doesn't mean there doesn't exist a way using logic for some puzzle-solving technique yet undiscovered. And if someone where interested in finding a puzzle-solving technique that has yet to be discovered looking at puzzles requiring brute-force at the point where brute-force is needed is a good place to look for new yet undiscovered puzzle-solving techniques based on logic.

I never said Nested Dynamic Chains were not techniques based on logic. I'm not sure what Exocet or MSLS are but it seems to me we can come to an agreement that setting values in cells in a trial-and-error type way is not solving a puzzle based on logic but just guessing what the answer might be.

There is a big difference between what you are saying and what I am saying. What you saying is if a constellation of givens has a path to a solution grid that is enough to say a puzzle is valid. I am saying unless you can get from the the constellation of givens to the solution grid using what humans call puzzle-solving techniques based on logic then you do not have a valid Sudoku. In other words, being solvable using known steps of logic is a requirement for being labeled a "Sudoku puzzle". Solution grids by themselves are not Sudoku puzzles. A constellation of givens in a grid may not have a solution grid that works. But just because a constellation of givens has a solution grid that works doesn't automatically mean it is a valid Sudoku puzzle.

I appreciate your post but I don't see anything in what you said that convinces me brute-force is nothing but mindless guessing not based on logic.

[denis_berthier]

.
Hi dxSudoku

By definition, a sudoku puzzle is valid if it has one and only one solution. This definition is universally agreed upon. It doesn't say anything about how existence and uniqueness of the solution are proven - but there are easy ways to prove or disprove it, e.g. DFS.
One clear advantage of this definition is, it doesn't depend on our state of knowledge about any particular solving techniques.
It's unclear if you accept this definition or not, but if you don't there's nothing to talk about.

It seems you are confusing "valid" with "interesting", where "interesting" would mean something as "solvable by my preferred set of resolution rules". It's clear there can never be any agreement on such a definition.

Brute force as used by Hodoku and guessing are the same thing: try to add a value (possibly recursively); it it leads to a solution, accept it (this is a truncated form of DFS). One problem is, it doesn't prove uniqueness.

T&E and guessing are different things: in T&E, you also try a candidate, but if it leads to a solution, you just forget about it. If it leads to a contradiction (say using only Singles), then you can delete the candidate. This is a perfectly valid technique and the most widely used one; but it is not "logic" - in the sense that it is not based on patterns. However, I've shown that any elimination done by T&E can be done by a braid - a perfectly defined chain pattern (with no OR branching) that can be spotted on a grid (contrary to a "chain of inferences").

As for the "Nested Dynamic Chains" of SE, I've never seen any definition of them and the java code of SE doesn't contain a single line of comment.
Based on what I can guess from the SE output, they are implemented as forcing T&E at depth 2, with some control on the number of "nodes", i.e. the number of of "inferences". So, no, in and of themselves, they are not "logic"; they are a variant of T&E(2).
However, all the known valid puzzles can be solved by T&E(2) (T&E at depth 2), which I've shown implies they can be solved by B-Braids, also a perfectly defined chain pattern (admittedly a very complex pattern that no one would want to read). From an abstract POV, it implies that any known valid puzzle can be solved by "logic".

[dobrichev]

Brute Force is not really a technique

I disagree.

Place a digit in a cell and look, whether you get a solution or not. If that technique is enabled, every sudoku can be solved.

I agree.

Every puzzle that has exactly one solution is valid.

I agree, but the puzzles that have many solutions are valid too.

By definition, a sudoku puzzle is valid if it has one and only one solution. This definition is universally agreed upon.

I disagree. My definition is "fill in the numbers 1-9 exactly once in every row, column, and 3x3 region" and it works pretty well, even for the empty puzzle.

T&E and guessing are different things

I disagree.

It seems you are confusing "valid" with "interesting", where "interesting" would mean something as "solvable by my preferred set of resolution rules". It's clear there can never be any agreement on such a definition.

I agree.

[denis_berthier]

By definition, a sudoku puzzle is valid if it has one and only one solution. This definition is universally agreed upon.

I disagree. My definition is "fill in the numbers 1-9 exactly once in every row, column, and 3x3 region" and it works pretty well, even for the empty puzzle.

This is the definition of a Sudoku problem. Not the definition of "valid".

T&E and guessing are different things

I disagree.

So, what are your definitions of both?

[dobrichev]

The problem is that no clear definitions exist.

From common sense a Trial is every branch in the logic. This applies to basic techniques and pattern matching as well.

Also I have no definition for the threshold where the force becomes Brute.

I like the term Educated Guess where the number of trials is drastically reduced on the basis of previously investigated proven cases or heuristics. But this is applicable differently in different contexts, and sometimes requires clarifications.

After additional qualifications, the term T&E can become clear about a specific problem. As we see this does not apply to sudoku solving.

It is easy to see that internet is polluted by a mess of sudoku terminology. Each of the authors believes that his own terminology is most perfect and the ultimate one, and some authors propagate it aggressively.

Authors I respect always ask for feedback from the expected audience and make many adjustments before stating a definition of a common term. And they are prepared that it isn't always possible and rational.

[denis_berthier]

The problem is that no clear definitions [of T&E] exist.

False. I have given clear definitions, based on the pre-existing standard usage of the term in the Sudoku solving community (forgetting its other usage as a nonsensical insult). You may not agree with them, but they do exist and they do allow to prove clear results - what a definition is meant for. I you don't agree with them, you'd better say on which point you disagree instead of propagating this kind of fake news.
Moreover, how do you reconcile your statements that 1) no clear definition exists and 2) T&E and guessing are the same thing?
Is this how "authors you respect" proceed?

From common sense a Trial is every branch in the logic. This applies to basic techniques and pattern matching as well

I can't see any relationship between common sense and this unsupported claim. This whole sentence is totally meaningless to me.

[dxSudoku]

Guessing is not logic. It's random. Brute-force is guessing. Logic is based on reason not guessing.

[dxSudoku]

.
Hi dxSudoku

By definition, a sudoku puzzle is valid if it has one and only one solution. This definition is universally agreed upon. It doesn't say anything about how existence and uniqueness of the solution are proven - but there are easy ways to prove or disprove it, e.g. DFS.
One clear advantage of this definition is, it doesn't depend on our state of knowledge about any particular solving techniques.
It's unclear if you accept this definition or not, but if you don't there's nothing to talk about.

This is really what this thread is about. I play Sudoku all the time. I am not a mathematician. As a Sudoku player, for me, the "solution" is the sequence of steps I take in solving the puzzle from the constellation of givens to a solution grid. Unlike the mathematicians who have no interest in how the game is played claim the solution grid IS the "solution" is just made up convention because it makes the math problems easier. It reduces the game to just a pattern of numbers.

I've played may Sudoku puzzles where in the solution path there can be more than one path at a point. Here is a very good example where at this point in the puzzle four different people game up with different steps of logic for solving the same puzzle. I diagrammed each of the four ways:

Here is the Skyscraper approach:

https://imgur.com/GrooNKy

Here is the 2-String Kite approach:

https://imgur.com/Zf6drfw

Here is the Bug+1 approach:

https://imgur.com/tYjN6ES

And here is the Remote Pair approach:

https://imgur.com/sIhBoAZ

Whenever the hardest puzzle is talked about or the idea of "solution" why do the mathematicians get to decide brute-force is a step based on logic when it is clearing guessing. In all the years I've played Sudoku I have never used brute-force in solving a puzzle. I have never met anyone who has ever claimed they have used brute-force to solving a puzzle. I have heard some players admit they use or used "guessing" to solve the puzzle. But their is pretty much universally accepted guessing is the incorrect way to play the game.

I continue to stand by my argument. No one has come even close to convincing me otherwise. I'm not being stubborn it's just the arguments made so far are of the "this is how it is" variety. No one has actually tackled the problem of brute-force being logic or just guessing argument. For me every Sudoku has three parts. A constellation of givens, a solution-path, and a solution-grid. Sometimes the solution-path has multiple branches. It is widely accepted the solution-grid cannot have a uniqueness problem. The solution-grid by itself is NOT a Sudoku. The solution-grid by itself is NOT a solution.

My big problem with Sudoku mathematicians and people claiming to have created the hardest puzzle is they completely ignore the requirement of the use of logic when it comes to the solution-path. Without logic, it's not a Sudoku in my mind. It's just an arrangement of numbers in a grid. Who cares? Solving a Sudoku by trial-and-error is no different than starting out with a different constellation of givens. Here is a great example which is the very first puzzle taken from the first post on the hardest Sudokus thread:

Not a valid puzzle in my opinion:

https://imgur.com/0mIHrLU

To solve this puzzle the person solving the puzzle will have to use trial-and-error by first setting the cell R5C8 to 1. Then to 2. Then to 3. All the way up to 8 when they get this constellations of givens:

https://imgur.com/UIIWMO3

Now that R5C8 has a given of 8, this becomes a real Sudoku puzzle. Most people accept uniqueness of the solution-grid is a requirement. It seems not accepting brute-force as being "logic" or "guessing" is not acceptable is in the same category of thinking.

[denis_berthier]

Hi dxSudoku
I can't see anything contradicting what I said.
The existence of multiple resolution paths is obvious to everybody. Not sometimes. But for most of the puzzles - probably all the puzzles, because they have a final sequence of Singles that can generally be applied in different orders.

[marek stefanik]

Your example of an 'invalid' puzzle actually has a very elegant move at the beginning.

Code: Select all

             /6      /24      /2              /46
   +------------------------+------------------------+------------------------+
   | 1       2       589    | 4       567     56789  | 3       678     679    |
   | 3       789     489    | 2789    1       6789   | 24689   5       24679T |  246
   | 489     5789    6      | 235789  2357    5789   | 1       2478    2479   |
   +------------------------+------------------------+------------------------+
   | 7       1568    1258   | 158     9       1458   | 24568   123468T 12346T |  246
   | 289     4       12589  | 6       57      3      | 2589    1278    1279   |
   | 689     15689   3      | 1578    457     2      | 45689   14678   14679  |
   +------------------------+------------------------+------------------------+
   | 5       1369    1249   | 1239    8       1469   | 7       12346   12346  |  246
   | 24689   13689   7      | 1239    2346    1469   | 246B    12346   5      |
   | 246     136     124    | 12357   234567  14567  | 246B    9       8      |
   +------------------------+------------------------+------------------------+

Notice r89c7 (base cells). In r247 (cross-lines) each digit has to appear three times.
Each of the digits 246 can only appear in two columns (cover-houses) outside the right-hand stack as marked above the grid (other givens prevent them from appearing in r247c15).
Each of them then has to appear at least once in r247c789.
That means that the two digits in the base cells are forced in r2c9 r4c89 (target cells), where they form a triple with 3 (already forced in r4c89).
The target cells can therefore only contain the digits 2346.

This pattern is called Junior Exocet and it produces several inferences we can use.
Firstly no digit can appear twice in the target cells (as the other base digit could then only appear once in r247).
Secondly the digit in each target has to appear in the corresponding mirror node: r2c9 in r56c8, r4c89 in r13c89.
It's important to note that we know there is one base digit in r2c9 and r56c8 and one in r4c89 and r13c89.
If the 3 were forced in r24c9, instead of r4c89, we wouldn't be able to use the next step, as both base digits could just appear in r4c89 and r13c89.

Now look at the digits restricting 246 in c2346. We have 26b15 and 4b24.
There are several ways to prove that if 4 is a true base digit, we get a UR. The way I prefer starts in the mirror nodes:

Suppose 4r56c8 and (2 or 6)r13c89. Then in c1 both of them are forced into r89c1.
Suppose 4r13c89 and (2 or 6)r56c8. Then in c5 both of them are forced into r89c5.

If 4 is a true base digit, it and the other base digit will create a UR in r89c17 or r89c57.
Therefore 4 is not a true base digit.

What we ended up with is 26 in base cells and 236 in target cells.
Since 26 are now proven base digits, they can only appear once in r247c789, meaning they can be eliminated in their cover-houses (outside the cross-lines).

I have no doubt that Hodoku will be able to solve it from now on (I think the elimination of 4r89c7 was itself enough).

For a better explanation of Junior Exocet, see this thread.

[marek stefanik]

I don't see anything in what you said that convinces me brute-force is nothing but mindless guessing not based on logic.

Probably because it is. What I said was that there were ways to solve the puzzles other than brute force.

I've just realised that I had found a JE-like pattern that I was only able to prove using brute force (but I haven't tried nested nets).
I then applied this pattern a few times with different sudokus (it was very easy to spot and I knew that the eliminations were valid).
I'm curious to see everyone's opinion on whether this counts itself as brute force, logic or both.

As for the "Nested Dynamic Chains" of SE, I've never seen any definition of them and the java code of SE doesn't contain a single line of comment.

I don't know the definition either, I just assumed that Dynamic Chains work the same way they're implemented in YZF_Sudoku (which I think is equivalent to braids, but I don't know much about braids), so it would make sense if this was equivalent to B-Braids.

Every puzzle that has exactly one solution is valid.

I agree, but the puzzles that have many solutions are valid too.

How do you solve a puzzle with more than one solution?
I know that there are 1-cell sudokus, where the content of exactly one cell can be determined, and that is the solution, but that's probably not what you mean.

[denis_berthier]

As for the "Nested Dynamic Chains" of SE, I've never seen any definition of them and the java code of SE doesn't contain a single line of comment.

I don't know the definition either, I just assumed that Dynamic Chains work the same way they're implemented in YZF_Sudoku (which I think is equivalent to braids, but I don't know much about braids),

There's a major difference between dynamic chains and braids:
- braids have an inherent length based on the number of CSP-Variables involved, which allows to define them as a pattern;
- dynamic chains are a variant of T&E with some restrictions based on the number of inferences made ("nodes" in SE), which makes it impossible to define them as a pattern.

[marek stefanik]

Isn't the number of CSP-Variables in a braid the same as the number of strong inferences in the corresponding dynamic chain?
I'm not convinced that substituting 'dynamic chains' for 'braids' and 'strong inferences' for 'CSP-variables' would make the sentence false.