Base Equation Resolution Theory

Advanced methods and approaches for solving Sudoku puzzles

Base Equation Resolution Theory

Postby logel » Mon Jun 13, 2016 8:47 pm

Preface:
After a long time of inactivity I like to present a discussion paper concerned with:

Topics:
- Base Equation Resolution Theory
- BERT is theory framework for Sudoku based on very few principles.
- BERT is no solver but uses many kinds of existing elimination patterns of any solver.
- The main goal is to compute a score value for resolution paths
- Comparing paths of the same Sudoku puzzle and optimizing is next.
- The view on Sudoku is radically different from concepts discussed here in this forum.
- A lot of special terms are introduced to avoid conflicts.

Details:
- the Sudoku puzzle is redefined as 324 arithmetic equations with integer variables
- describing eliminations or parts of it on basis of integer equations and arithmetic operations
- uses only three types of equations: B>=1 (base equation), L<=1(link equation) and Z=0(zero equation).
- defining some operators on these equations using an appropriate notation to produce equations
- describing the whole resolution path or parts of it with expressions of such operators
- identifying and using re-usable fractions of the path
- defining a metric to compute score values of unit with a definite meaning
- calculating the life cycle of eliminations
- optimizing resolution paths by mixing and reshuffling eliminations from various solvers

Benefits:
- The score value reflects an aspect of the simplicity of a resolution path
- Complex eliminations of "hard" puzzles are decomposed into smaller parts
- This makes eliminations more "understandable"
- The machine readable notation allows various pre- and post-processing

Download:
http://logelium.de/Sudoku/BERT/BERT_0.2.pdf

You may skip the first chapters with basic explanations
Comments are welcome.

  1. Wrong ideas and blunders
  2. Wrong or incomplete explanations
  3. Missing things
  4. Extensions
  5. Anything else

PS: The concept was sketched two years ago already. But I had been at a loss how to integrate exocet patterns. The solution idea was born after I almost gave up.
Although I used a thesis template, the paper is not meant as an scientific article. I just needed formatting formulas.
User avatar
logel
 
Posts: 55
Joined: 29 April 2012
Location: Germany

Re: Base Equation Resolution Theory

Postby JasonLion » Mon Jun 13, 2016 11:12 pm

Fill a 9 by 9 square that contains already some given numbers in a way, that every row, column and box contains all numbers from 1 to 9.

There are other rules to Sudoku, though they are not universally accepted. Around here we specify that a Sudoku puzzle must have exactly one solution. Many people also require that the placement of givens has some kind of symmetry, though we don't accept that one here. Some people further specify that the puzzle should be solvable by logic alone. Unfortunately that rule is poorly defined as brute force can be logically specified and solves all puzzles, yet these same people would not accept brute force solutions as meeting this rule.

a mathematical problem that requires a reasonable amount of logic to solve

Sudoku can be solved with trial and error alone, which many people argue is not logic. A substantial number of people who solve Sudoku puzzles do so with trial and error, even though we frown on that here.

This document addresses a reader already familiar with advanced Sudoku solving concepts that are capable of solving “hard” Sudoku puzzles. These are usually too difficult for humans and require computer aided procedures.

It is still an open question if there even exists a puzzle that is too difficult for humans. Certainly some of the most complex puzzles have been solved by human solvers, and it seems plausible that with sufficient effort any puzzle can be solved by a human solver.

There are a number of concepts for Sudoku that try to measure the severity of a Sudoku puzzle. All of these concepts are based on properties of the most complex elimination pattern only, afaik.

While difficulty measures that only depend on the most complex step are certainly popular, there are many difficulty measures that depend on all of the steps. Of course very very few of either kind are formally defined (unless you accept computer programs as formal definitions).

But we cannot ignore that something is missing, if all but one resolution step is ignored when calculating the severity. Solution paths usually consists of several hard elimination steps.

Why? You provide no justification for this claim either inside or outside your formalism. To my mind, this is an arbitrary decision, both answers are equally valid. That is really the fundamental problem with any effort to define a difficulty measure, it must inherently be based on numerous such arbitrary value judgements.

Sudoku Explainer by Glenn Fowler

Sudoku Explainer was developed by Nicolas Juillerat.

All of them give litte to none explanation, why a particular step was chosen in a situation.

"Little to none" does not seem appropriate to me. I've never seen a solver that gives no explanation for it's choice of solving step. Likewise I have never seen one that gives a complete formal definition (aside from it's source code). But nearly all of them give some fairly intuitive, though incomplete, explanation. For example Sudoku Explainer uses the most complex solving technique required where complex is determined by an ordered list of solving techniques (which is mostly, but not completely, documented) and the assumption that the easiest technique that makes forward progress is used at each step.

We want to assess the quality of a resolution path without using the information what rules or strategies are used to find it. Up to now there seem to be no convincing concept of comparing resolution paths of the same Sudoku problem. Although the claim “my eliminations are simpler” is frequently used in many discussions, a substantial definition of “simplicity” is painfully missing.

I believe that you are mixing up the difference between science and art. In science a formal definition of simplicity is indeed required to answer this question. But on this forum simplicity is defined in terms of artistic merit. In the same sense that someone might compare two paintings and ask which one is "better", we ask which solution is more beautiful.

Then they switch to recursion (brute force) or fail.

Recursion is not a good word to use here. For any recursive algorithm there is an equivalent non-recursive algorithm. Brute force is a much better phrase, as it at least captures the essence of what you are saying. However, brute force has never been formally defined in relation to Sudoku, so you are on slippery ground in any case. The dividing line between brute force and non-brute force methods has been long debated without any generally accepted resolution. It seems possible that the exact location of the dividing line might be another arbitrary choice. While it seems slightly more likely that complexity theory will eventually draw a hard line, we just can't say right now.
User avatar
JasonLion
2017 Supporter
 
Posts: 620
Joined: 25 October 2007
Location: Silver Spring, MD, USA

Re: Base Equation Resolution Theory

Postby logel » Fri Jun 17, 2016 5:11 pm

JasonLion wrote:
There are a number of concepts for Sudoku that try to measure the severity of a Sudoku puzzle. All of these concepts are based on properties of the most complex elimination pattern only, afaik.

While difficulty measures that only depend on the most complex step are certainly popular, there are many difficulty measures that depend on all of the steps. Of course very very few of either kind are formally defined (unless you accept computer programs as formal definitions).

Maybe there are concepts I don't know about. It would be helpful to give a link or hint.
My measuring concept is well defined and documented, gives an unambiguous result and is even calculable manually. Of course a script does it faster and more reliable. Seems formally enough.

JasonLion wrote:
But we cannot ignore that something is missing, if all but one resolution step is ignored when calculating the severity. Solution paths usually consists of several hard elimination steps.

Why? You provide no justification for this claim either inside or outside your formalism. To my mind, this is an arbitrary decision, both answers are equally valid. That is really the fundamental problem with any effort to define a difficulty measure, it must inherently be based on numerous such arbitrary value judgements.

I can't follow your argument. The terms "severity" or "difficulty" relate in my opinion to a solver concept. A particular puzzle is more or less difficult for a particular solver. This is not what I am doing, I try to compare paths of the same puzzle to assess their quality. Therefore I use the term "score" for the total effort to justify a resolution path within a calculation framework that is solver independent. If you use only a part of available input data for measurement, you can' t get a total effort value.

JasonLion wrote:
Sudoku Explainer by Glenn Fowler

Sudoku Explainer was developed by Nicolas Juillerat.

Will be corrected.

JasonLion wrote:
All of them give litte to none explanation, why a particular step was chosen in a situation.

"Little to none" does not seem appropriate to me. I've never seen a solver that gives no explanation for it's choice of solving step. Likewise I have never seen one that gives a complete formal definition (aside from it's source code). But nearly all of them give some fairly intuitive, though incomplete, explanation. For example Sudoku Explainer uses the most complex solving technique required where complex is determined by an ordered list of solving techniques (which is mostly, but not completely, documented) and the assumption that the easiest technique that makes forward progress is used at each step.

Maybe I have a different expectation of "explanation". What you describe is the "simplest-first" strategy solvers are using generally. They take the first valid elimination in their list or procedure. This makes some progress because an elimination is certainly a progress. But this strategy does not control the progress to effort ratio. How to measure progress? BERT is intended to achieve this with an appropriate calculation framework.
The optimization example in the paper shows that by rearranging the moves in another order roughly on third of the path steps become redundant. This is a typical result. Giving the optimizer more alternative eliminations to work with produces an even more efficient result. This is of course always relative to the underlying scoring concept.
Solving strategies try to make the solving process efficient. But I am not interested in solver efficiency but in the efficiency of the resolution path.

JasonLion wrote:
We want to assess the quality of a resolution path without using the information what rules or strategies are used to find it. Up to now there seem to be no convincing concept of comparing resolution paths of the same Sudoku problem. Although the claim “my eliminations are simpler” is frequently used in many discussions, a substantial definition of “simplicity” is painfully missing.

I believe that you are mixing up the difference between science and art. In science a formal definition of simplicity is indeed required to answer this question. But on this forum simplicity is defined in terms of artistic merit. In the same sense that someone might compare two paintings and ask which one is "better", we ask which solution is more beautiful.

I see Sudoku as mathematical puzzle. This does not exclude that patterns and paths have aesthetics and beauty. But for me the beauty is related to efficiency and not to cumbersome structures. Making simplicity or efficiency a solely subjective matter kills all arguments.
User avatar
logel
 
Posts: 55
Joined: 29 April 2012
Location: Germany

Re: Base Equation Resolution Theory

Postby JasonLion » Fri Jun 17, 2016 10:18 pm

A typical difficulty score that counts all steps works by making a list of solving techniques, assigning a score to each possible solving step, and returning the sum of the scores across all steps in the resolution path. Everyone has their own set and ordering of the solving techniques and their own weighting of the scores assigned to each one. Many (mostly quite unpopular) difficulty raters use some version of this approach. Another, more mathematical, approach is mentioned here.

Another interesting approach to this same basic subject matter is described here.

If you are outside of a formalism, the meanings of words are imprecise. "effort" and "score" are no more well defined, nor more useful than "severity" or "difficulty". Your discussion of "effort" works backwards from the definition you have already given it, so of course it ends up working the way you meant it to work. But speaking outside of the formalism, your definition is no more intuitive or obvious than several others, some of which do not count all steps,

Personally, my unconscious mind directly solves many techniques, with no effort at all on "my" part. I see no reason to count those techniques or include them in a "score" for the puzzle. You can of course define things differently, but nothing either of us can do will demonstrate that either of our approaches is preferred, or more correct. These varied definitions allow the construction of many many different formalisms, none of which can be preferred over another without introducing new criteria, which themselves are arbitrary. You speak of the "efficiency of the resolution path", but defining such a thing requires a formalism, and defining a formalism requires making many of these arbitrary choices.

Making simplicity or efficiency a solely subjective matter kills all arguments.

Even a very brief glance at the world of fine art shows that this is clearly a false statement. Essentially all aspects of fine art are subjective, yet people argue about them endlessly.
User avatar
JasonLion
2017 Supporter
 
Posts: 620
Joined: 25 October 2007
Location: Silver Spring, MD, USA

Re: Base Equation Resolution Theory

Postby David P Bird » Fri Jun 17, 2016 10:21 pm

I'm not qualified to enter the discussion here in earnest but I do have a couple of coments to make.

1. I consider methods that need to consider mutiple outcomes to be able make any deduction to be less elegant and harder than the rest - templating, branched paths etc. Therefore one measure would be how many alternative cases are under simultaneous consideration through the logical path.

2. Some recent research on how people plan their subway journeys showed that the number of different lines they needed to use was a far greater factor than the number of stations on they would pass through. In Sudoku terms this would make two long single digit chain segments easier to follow than a shorter route using a variety of linking digits - and I would suppose particularly so if they needed to be grouped together in ALSs or other patterns.
David P Bird
2010 Supporter
 
Posts: 944
Joined: 16 September 2008
Location: Middle England

Re: Base Equation Resolution Theory

Postby logel » Sat Jun 25, 2016 11:16 am

JasonLion wrote:A typical difficulty score that counts all steps works by making a list of solving techniques, assigning a score to each possible solving step, and returning the sum of the scores across all steps in the resolution path. Everyone has their own set and ordering of the solving techniques and their own weighting of the scores assigned to each one. Many (mostly quite unpopular) difficulty raters use some version of this approach. Another, more mathematical, approach is mentioned here.

Another interesting approach to this same basic subject matter is described here.

Thanks for the links.
The first one translates the puzzle into a CSP and solves the problem with a special SAT solver. There are plenty of references to math theory background. The runtime behaviour is used to define "hardness" of the puzzle (relative to that algorithm). "The dynamics of the algorithm should be indicative to the problem's hardness". No resolution path with explicit eliminations is generated.
The second paper makes a simpler approach. All candidates are tested by T&E with singles if a contradiction is reached. All single eliminations to verify a cell are counted. The average total count for several runs with random starting points is taken as rating value. Again there is no result path. An elimination with T&E and singles corresponds always to a braid pattern (see papers of Denis Berthier). So this approach has the same limitations.
Both concepts a indeed interesting but address a different issue than I do. The synonymous terms "hardness", "difficulty" or "rating" are related (outside of formalism) to the puzzle as such and relative to the solver algorithm.
My concept is instead concerned with explicit resolution paths and uses only their direct properties. So scoring values of eliminations and paths reflect the evaluation effort and are not dependent on any solver algorithm.

Arbitrary choices? Yes. Any decision on solving strategy or rating is arbitrary. So this is no point. Assigning scores to solving techniques as "everyone" does requires many independent ad-hoc parameters. This is clearly not very much interesting, but I started there too. As David Byrd pointed out with his subway example, any target function for optimization depends on a motivation and cannot be assessed separately..

A leading idea is to reduce redundancy. There are three types.
- redundancy inside of an elimination pattern, e.g. unnecessary candidates from T&E or coloring patterns
- eliminations maybe substituted by a simpler one, if the order of moves is rearranged (requires a weight function)
- eliminations may share significant parts of logic, therefore eliminations need to be decomposed into meaningful fractions.

Every system that assigns quantitative values needs a formal description of it's objects. The chosen description here is an abstraction layer on top of eliminations that transforms eliminations into four basic fragment kinds and their combinations. There is no arbitrariness in that formalism, it is simply correct and consistent and therefore undisputable. One can only argue about limitations that reduces usefulness.

A metric on top that takes this formal description as basis includes inevitably additional arbitrary choices but the choice to use the mentioned formalism reduces the options significantly. The additional requirement that the score value is invariant to any decomposition of elimination into fragments is reducing the options again. Finally I wanted single eliminations with zero value without exception rules. This is the main motivation background and I do not claim that this scoring is "better" than whatever. I found it useful for myself and decided to share it. The optimization produced amazingly compact resolution paths.
It's up to everybody to use it or walk another road.
User avatar
logel
 
Posts: 55
Joined: 29 April 2012
Location: Germany

Re: Base Equation Resolution Theory

Postby JasonLion » Sat Jun 25, 2016 2:24 pm

logel, well said!

I suggest that you rewrite section one of your document to focus on this material, and remove some of the wording currently there that appears to make value judgements about other approaches.
User avatar
JasonLion
2017 Supporter
 
Posts: 620
Joined: 25 October 2007
Location: Silver Spring, MD, USA

Re: Base Equation Resolution Theory

Postby logel » Sun Jul 03, 2016 5:30 pm

JasonLion wrote:I suggest that you rewrite section one of your document to focus on this material, and remove some of the wording currently there that appears to make value judgements about other approaches.

OK, you are right. The first part contains a lot of secondary aspects. It's more a story how the ideas evolved. In retrospect I am not happy with this too. But rewriting will take some time.
If some comments appear as value judgements, this was not intended. I tried to point out differences to other approaches only. Seems this should be done more careful.
User avatar
logel
 
Posts: 55
Joined: 29 April 2012
Location: Germany

Re: Base Equation Resolution Theory

Postby Noumenon » Sat Oct 15, 2016 2:24 pm

Non-expert here. However, I have thought about defining "shortest path" solvings; perhaps they are "most efficient."

Somewhere on this board is a discussion of how in certain cases placing an easy numeral makes further progress more, rather than less, difficult. I suspect this relates to this discussion.

Also, to me, some people make great mental gymnastics to hide the fact they are using the vilified "brute force" methods to solve. Every time a conditional "what if" proposition is used, and the outcome eliminates a candidate, brute force is being used. One might even say that even a path length of 1 is doing this with each clear elimination of a numeral in a family which already contains it: "what if I place a numeral '2' here?" "I can't because this row already has a 2."

Shortest path lengths as the 'best" method for each puzzle? I will step aside here but point out before I do that much of Sudoku depends on rules the solvers impose on themselves. For example if I see a path leads to a situation such that the puzzle would not have a unique solution, I won't use that knowledge; it seems like a cheat; and find another path. It's my own arbitrary rule.
Noumenon
 
Posts: 6
Joined: 25 August 2010

Re: Base Equation Resolution Theory

Postby champagne » Sat Oct 15, 2016 3:07 pm

Noumenon wrote:Also, to me, some people make great mental gymnastics to hide the fact they are using the vilified "brute force" methods to solve. Every time a conditional "what if" proposition is used, and the outcome eliminates a candidate, brute force is being used. One might even say that even a path length of 1 is doing this with each clear elimination of a numeral in a family which already contains it: "what if I place a numeral '2' here?" "I can't because this row already has a 2."


Hi Noumenon,

I think that nobody will follow you in that endless discussion.

In that forum, the common understanding for the "brute force" to-day is that the "solver" uses only very basic rules and uses trial and error against that very limited set of rules to solve the puzzle. (usually the only rule is only one occurrence of a digit in a row/column/box. In the brute force I use, digits locked in rows/ column boxes are also applied)

Use of other "rules" (in fact logical consequences of the basic rules) are there, as you say, to show as short as possible reasons to clear a candidate, that's it.



Noumenon wrote: I will step aside here but point out before I do that much of Sudoku depends on rules the solvers impose on themselves.


Usually, it depends on their skills.


Noumenon wrote: For example if I see a path leads to a situation such that the puzzle would not have a unique solution, I won't use that knowledge; it seems like a cheat; and find another path. It's my own arbitrary rule.


That another point. What is clear is that paths using the unique solution property are usually much shorter. You can also decide to avoid pencil marks ...

The common understanding in that forum is that a sudoku has a unique solution.
champagne
2017 Supporter
 
Posts: 5576
Joined: 02 August 2007
Location: France Brittany

Re: Base Equation Resolution Theory

Postby Noumenon » Sat Oct 15, 2016 6:17 pm

I do suspect the folks doing these analyses might get a lot of mileage from studying difficult puzzles but deliberately set up to have 2 and only 2 solutions. Or more.
I would pay attention if they did! But I haven't seen anyone go in that direction.
Noumenon
 
Posts: 6
Joined: 25 August 2010

Re: Base Equation Resolution Theory

Postby m_b_metcalf » Sun Oct 16, 2016 9:34 am

Noumenon wrote:I do suspect the folks doing these analyses might get a lot of mileage from studying difficult puzzles but deliberately set up to have 2 and only 2 solutions. Or more.
I would pay attention if they did! But I haven't seen anyone go in that direction.


Here's a very hard one with two solutions for you to investigate:
Code: Select all
 . . . . . 1 . . 2
 . . 3 4 . . 5 . .
 . 6 . . 7 . . 1 .
 . 2 . . . . . . 8
 . . 9 . . . 7 . .
 8 . . . . 5 . 9 .
 . . . . 9 . . 6 .
 . . 7 . . 2 1 . .
 4 . . 8 . . . . .

Best of luck,

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

Re: Base Equation Resolution Theory

Postby m_b_metcalf » Tue Oct 18, 2016 5:19 pm

m_b_metcalf wrote:Here's a very hard one with two solutions for you to investigate:
Code: Select all
 . . . . . 1 . . 2
 . . 3 4 . . 5 . .
 . 6 . . 7 . . 1 .
 . 2 . . . . . . 8
 . . 9 . . . 7 . .
 8 . . . . 5 . 9 .
 . . . . 9 . . 6 .
 . . 7 . . 2 1 . .
 4 . . 8 . . . . .

@champagne: This is, of course, from one of your recent submissions to the Patterns Game (currently suffering severe h/w problems). I thought at first that the two possible values at r7c2, a 3 or 5, would be members of a simple UA4. In fact, there are only 34 common clues, so the UA is then of size 47. Below are the two solutions and the common clues.

Regards,

Mike

Code: Select all
  9  7  4  6  5  1  8  3  2
  1  8  3  4  2  9  5  7  6
  5  6  2  3  7  8  4  1  9
  7  2  5  9  1  3  6  4  8
  3  4  9  2  8  6  7  5  1
  8  1  6  7  4  5  2  9  3
  2  5  8  1  9  4  3  6  7
  6  9  7  5  3  2  1  8  4
  4  3  1  8  6  7  9  2  5

  9  5  4  6  8  1  3  7  2
  7  1  3  4  2  9  5  8  6
  2  6  8  5  7  3  9  1  4
  3  2  1  9  4  7  6  5  8
  5  4  9  1  6  8  7  2  3
  8  7  6  2  3  5  4  9  1
  1  3  2  7  9  4  8  6  5
  6  8  7  3  5  2  1  4  9
  4  9  5  8  1  6  2  3  7

Common clues (34):
  9  .  4  6  .  1  .  .  2
  .  .  3  4  2  9  5  .  6
  .  6  .  .  7  .  .  1  .
  .  2  .  9  .  .  6  .  8
  .  4  9  .  .  .  7  .  .
  8  .  6  .  .  5  .  9  .
  .  .  .  .  9  4  .  6  .
  6  .  7  .  .  2  1  .  .
  4  .  .  8  .  .  .  .  .
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 8121
Joined: 15 May 2006
Location: Berlin

Re: Base Equation Resolution Theory

Postby champagne » Tue Oct 18, 2016 5:38 pm

m_b_metcalf wrote:@champagne: This is, of course, from one of your recent submissions to the Patterns Game (currently suffering severe h/w problems). I thought at first that the two possible values at r7c2, a 3 or 5, would be members of a simple UA4. In fact, there are only 34 common clues, so the UA is then of size 47. Below are the two solutions and the common clues.

Regards,

Mike


Hi Mike,

Congratulations first to have quickly produced a 2 solutions grid out of the last high submissions.

I am not surprised to see 2 solutions with so few common cells.

Most often, a cell leading to a valid grid with a relatively small number of clues hit several UAs (assuming a lot of UAs with no subset).
For example, if you accept that a solution grid has in average more than 340 UAs of size 4-12, a sudoku with 17 clues must in average hit more than 20 such UAs.
champagne
2017 Supporter
 
Posts: 5576
Joined: 02 August 2007
Location: France Brittany

Re: Base Equation Resolution Theory

Postby m_b_metcalf » Thu Oct 20, 2016 7:13 am

Here are two more (hard, with two solutions) for OP to play with:

Code: Select all
000001002000300040005060700008000076600080000950000800006070900030004000100200000

000001002000300040005060700008000010600090007970000800006070500030002000100400000

It seems that they're not so rare.
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 8121
Joined: 15 May 2006
Location: Berlin

Next

Return to Advanced solving techniques