Does Using Brute-Force to solve a puzzle make it invalid

Everything about Sudoku that doesn't fit in one of the other sections

re: number of answers

Postby Pat » Sun Jul 18, 2021 7:39 pm

dobrichev wrote:
marek stefanik wrote:Every puzzle that has exactly one solution is valid.

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


yes!

we like puzzles with exactly one answer,
but others are valid too
User avatar
Pat
 
Posts: 3926
Joined: 18 July 2005

Re: Does Using Brute-Force to solve a puzzle make it invalid

Postby eleven » Sun Jul 18, 2021 9:09 pm

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

From the very point, where you made your guess, you are using pure logic.
How do you decide, where you make the guess ? When your are looking for a skyscraper or swordfish, where do you start ? With number 1, or randomly ?
Most brute force solvers start with bivalue candidates scanning the cells top-down, left to right. This is a solid and pure logic plan.

You can like or dislike, what you want, but don't tell us, what logic is or not.
eleven
 
Posts: 2785
Joined: 10 February 2008

Re: Does Using Brute-Force to solve a puzzle make it invalid

Postby yzfwsf » Sun Jul 18, 2021 10:43 pm

marek stefanik wrote: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.

I think the length of the denis_berthier's chains is equivalent to the recursion depth of BFS.
yzfwsf
 
Posts: 511
Joined: 16 April 2019

Re: Does Using Brute-Force to solve a puzzle make it invalid

Postby denis_berthier » Mon Jul 19, 2021 1:36 am

marek stefanik wrote: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.

The numbers are the same if there are no inner Subsets.
But SE doesn't count the number of "strong inferences"; it counts the total number of inferences (the "nodes"). That makes a huge difference. As I said, it allows to define braids of a fixed length as a pattern; it doesn't allow to define dynamic chain with a fixed number of nodes as a pattern.
denis_berthier
2010 Supporter
 
Posts: 3166
Joined: 19 June 2007
Location: Paris

Re: Does Using Brute-Force to solve a puzzle make it invalid

Postby denis_berthier » Mon Jul 19, 2021 1:39 am

yzfwsf wrote:
marek stefanik wrote: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.

I think the length of the denis_berthier's chains is equivalent to the recursion depth of BFS.

The maximum length, yes; obviously not the length of any individual chain.
denis_berthier
2010 Supporter
 
Posts: 3166
Joined: 19 June 2007
Location: Paris

Re: Does Using Brute-Force to solve a puzzle make it invalid

Postby marek stefanik » Mon Jul 19, 2021 9:32 pm

yzfwsf wrote:I think the length of the denis_berthier's chains is equivalent to the recursion depth of BFS.
But that's true for dynamic chains too, isn't it? That's what determines the SER.

denis_berthier wrote:
marek stefanik wrote: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.
,
The numbers are the same if there are no inner Subsets.
But SE doesn't count the number of "strong inferences"; it counts the total number of inferences (the "nodes"). That makes a huge difference. As I said, it allows to define braids of a fixed length as a pattern; it doesn't allow to define dynamic chain with a fixed number of nodes as a pattern.
I see, so you were saying that braids[length] can be defined as a pattern, not braids in general.
That's interesting, because the logic is the same no matter what the length is, and even braids of a given length can look completely different in the actual grid, but I think this depends on the definition of the word 'pattern'.
marek stefanik
 
Posts: 250
Joined: 05 May 2021

Re: Does Using Brute-Force to solve a puzzle make it invalid

Postby denis_berthier » Tue Jul 20, 2021 12:05 am

marek stefanik wrote:
denis_berthier wrote:
marek stefanik wrote: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.
,
The numbers are the same if there are no inner Subsets.
But SE doesn't count the number of "strong inferences"; it counts the total number of inferences (the "nodes"). That makes a huge difference. As I said, it allows to define braids of a fixed length as a pattern; it doesn't allow to define dynamic chain with a fixed number of nodes as a pattern.
I see, so you were saying that braids[length] can be defined as a pattern, not braids in general.
That's interesting, because the logic is the same no matter what the length is, and even braids of a given length can look completely different in the actual grid, but I think this depends on the definition of the word 'pattern'.

I define a resolution rule as a 1st order formula "pattern ==> elimination/assertion". In this view, a braid[n] can be defined as a pattern and it is precisely defined as such in my books (and directly implemented as such in CSP-Rules).
However, defining "braid" as a pattern would require an infinite disjunction on length, which is not 1st order. Of course, the braid[1], ... braid[n] form a family of similar (but logically not identical) patterns.

You may consider this as an irrelevant subtlety, but that's what allows the development of the whole theory (definition of all my ratings in pure logic terms, stability of the ratings under isomorphism, proof of T&E vs braids theorems, confluence of the T-braids theories, ....).
How a pattern visually looks on a grid is secondary (though of course important when it comes to spotting them); what counts is the underlying logic. In the case of chains, each building block (each link in the natural language sense) is similar to any other.

Now you may wonder why there is absolutely zero theory of dynamic chains or of any of the other chains that have appeared in the Sudoku literature. The reason is very simple: they can't be defined as patterns. Their various restrictions (leading to the different ratings) are based on the number of inference steps ("nodes"), which can't be expressed in any logical formula. The origin of all this is clear: it is the obsolete view of chains as chains of inferences and their lack of foundations in logic (I mean FOL).
(In the case of Robert's tracks, it's still worse: there's no notion of length in his original version - but it seems he has now adopted mine).
denis_berthier
2010 Supporter
 
Posts: 3166
Joined: 19 June 2007
Location: Paris

Re: Does Using Brute-Force to solve a puzzle make it invalid

Postby Pupp » Wed Aug 25, 2021 5:16 am

I don't think using brute force makes it invalid. As long as there is only a single solution, then the puzzle is valid.

I can't really talk about nested dynamic chains, but if you're at the point where your solving puzzles harder than 9.5, your probable smart enough to figure out what exactly, a nested dynamic chain is.

That being said, at that point, I suspect the biggest problem a person has in solving a puzzle at that level is having enough of a memory to keep track of everything. From what I've heard, it can take hours to solve a puzzle that's over 11 SE.

I heard that X-Sudoku has problems over 12 SE.
Pupp
 
Posts: 246
Joined: 18 October 2019

Re: Does Using Brute-Force to solve a puzzle make it invalid

Postby m_b_metcalf » Thu Aug 26, 2021 10:29 am

Pupp wrote:I heard that X-Sudoku has problems over 12 SE.

You'll find a list of Xtreme puzzles here.

Mike
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 13094
Joined: 15 May 2006
Location: Berlin

Re: Does Using Brute-Force to solve a puzzle make it invalid

Postby Pupp » Thu Oct 07, 2021 3:55 am

I don't think it's possible to make a unique solution puzzle that can only be solved with brute force.

Now, there are 2 types of solvers.

1. Solvers that use logic to solve every step to the end of the puzzle. It's the version that most programmers aspire to create.

2.Brute force solvers. They don't use logic to solve puzzles. They quickly guess the answer and cross check. There's only so many guesses needed to validate a puzzle. It's purpose is to just validate that a puzzle has only one solution. I'm guessing it's used mainly by programs churning out puzzles to toss puzzles with multiple solutions.
Pupp
 
Posts: 246
Joined: 18 October 2019

Re: Does Using Brute-Force to solve a puzzle make it invalid

Postby Mathimagics » Thu Oct 07, 2021 5:58 am

All software solvers use logic.

I think by "logic" you actually mean something like "solving technique", eg Naked/Hidden sets, various varieties of fish, etc.

It's true that brute-force solvers are faster (and simpler), and that they are most commonly used for puzzle validation (uniqueness testing), and related tasks like finding minimal puzzles.

As with hardware, it's good to select the right tool for job! As a programmer, one simply aspires to produce the best software for that job.
User avatar
Mathimagics
2017 Supporter
 
Posts: 1870
Joined: 27 May 2015
Location: Canberra

Re: Does Using Brute-Force to solve a puzzle make it invalid

Postby denis_berthier » Thu Oct 07, 2021 8:27 am

Pupp wrote: there are 2 types of solvers.
1. Solvers that use logic to solve every step to the end of the puzzle. It's the version that most programmers aspire to create.
2.Brute force solvers. They don't use logic to solve puzzles. They quickly guess the answer and cross check. There's only so many guesses needed to validate a puzzle. It's purpose is to just validate that a puzzle has only one solution. I'm guessing it's used mainly by programs churning out puzzles to toss puzzles with multiple solutions.

I wouldn't say it that way. There are indeed conceptually two types of solvers, corresponding to different and opposite goals (readability vs speed):
- pattern-based,
- based on structured search (DFS, BFS, T&E, ...); they are the fastest.

But, among the pattern-based solvers, there are two sub kinds:
- solvers based directly on pattern-matching: AFAIK, CSP-Rules is the only one of this kind (not counting the toy solver included in the CLIPS examples);
- solvers based on procedural code and in particular on some form of T&E, BFS or DFS for chains. It's hard to say that such solvers "use logic for every step" (unless you stretch the meaning of "logic" to "anything that isn't false").
.
denis_berthier
2010 Supporter
 
Posts: 3166
Joined: 19 June 2007
Location: Paris

Re: Does Using Brute-Force to solve a puzzle make it invalid

Postby Serg » Thu Oct 07, 2021 11:49 am

Hi, Denis!
denis_berthier wrote:... among the pattern-based solvers, there are two sub kinds:
- solvers based directly on pattern-matching: AFAIK, CSP-Rules is the only one of this kind (not counting the toy solver included in the CLIPS examples);
- solvers based on procedural code and in particular on some form of T&E, BFS or DFS for chains. It's hard to say that such solvers "use logic for every step" (unless you stretch the meaning of "logic" to "anything that isn't false").

Do you really mean that your approach doesn't use any form of "T&E, BFS or DFS" for spotting whips/braids?

Serg
Serg
2018 Supporter
 
Posts: 785
Joined: 01 June 2010
Location: Russia

Re: Does Using Brute-Force to solve a puzzle make it invalid

Postby denis_berthier » Thu Oct 07, 2021 12:04 pm

Serg wrote:Hi, Denis!
denis_berthier wrote:... among the pattern-based solvers, there are two sub kinds:
- solvers based directly on pattern-matching: AFAIK, CSP-Rules is the only one of this kind (not counting the toy solver included in the CLIPS examples);
- solvers based on procedural code and in particular on some form of T&E, BFS or DFS for chains. It's hard to say that such solvers "use logic for every step" (unless you stretch the meaning of "logic" to "anything that isn't false").

Do you really mean that your approach doesn't use any form of "T&E, BFS or DFS" for spotting whips/braids?


YES. It is pure pattern-matching.
denis_berthier
2010 Supporter
 
Posts: 3166
Joined: 19 June 2007
Location: Paris

Re: Does Using Brute-Force to solve a puzzle make it invalid

Postby Serg » Thu Oct 07, 2021 12:57 pm

Hi, Denis!
Could you post an example of spotting some whip/braid? I'd like to see not final result (which can be found in "Puzzles" division of this Forum), but steps of finding some whip/braid. It looks like you know magic way of intellectual search of a pattern w/o some BFS, DFS etc.

Serg
Serg
2018 Supporter
 
Posts: 785
Joined: 01 June 2010
Location: Russia

PreviousNext

Return to General