The New Sudoku Players' Forum

[denis_berthier]

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

Hi Serg,
There's nothing magic here and nothing new either. It's the very classical technology of inference engines (dating back to the 1970s, with improvements since them). The rules are the code. The main function of the inference engine is pattern-matching, i.e. finding the combinations of facts that match the rules. There's no way I could post an example of finding a whip/braid, as this is precisely what pattern-matching does automatically.

If you want details, check any of the files in "CSP-Rules-Generic/CHAIN-RULES-SPEED/WHIPS". For instance, here is the "code" for a whip[3] - pure logic definition (in a syntax very close to FOL):

Code: Select all

(defrule whip[3]
   (declare (salience ?*whip[3]-salience*))
   (chain
      (type partial-whip)
      (context ?cont)
      (length 2)
      (target ?zzz)
      (llcs $?llcs)
      (rlcs $?rlcs)
      (csp-vars $?csp-vars)
      (last-rlc ?last-rlc)
   )
   
   ;;; ?new-llc
   (exists-link ?cont ?new-llc&~?zzz&:(not (member$ ?new-llc $?llcs))&:(not (member$ ?new-llc $?rlcs)) ?last-rlc)
   
    ;;; ?new-csp
   (is-csp-variable-for-label (csp-var ?new-csp&:(not (member$ ?new-csp $?csp-vars))) (label ?new-llc))
   (forall (csp-linked ?cont ?new-llc ?xxx ?new-csp)
      (exists (exists-link ?cont ?xxx ?vvv&:(or (eq ?vvv ?zzz) (member$ ?vvv $?rlcs))))
   )
   ?cand <- (candidate (context ?cont) (status cand) (label ?zzz))
=>
   (retract ?cand)
   (if (eq ?cont 0) then (bind ?*nb-candidates* (- ?*nb-candidates* 1)))
   (if (or ?*print-actions* ?*print-L3* ?*print-whip* ?*print-whip-3*) then
      (print-whip 3 ?zzz $?llcs $?rlcs $?csp-vars ?new-llc . ?new-csp)
   )
)

[Serg]

Denis,
I think, every search is some kind of "trial-and-error" procedure. Let's consider, for example, procedure of finding a number which is equal to given number "a".

Code: Select all

FOR ALL ELEMENTS bi IN THE SET "B" DO
    IF bi = a     /* Trial */
        THEN EXIT
        ELSE CONTINUE SEARCH     /* Error */
    END
END

Is't it T&E method? Inference engines use search (i.e. T&E) too, but one using this method don't code search sequence exactly. So, I don't understand what is the principal difference between your solver and other logic solvers. You can add new rule in more general and simple way, yes?

Serg

[denis_berthier]

I think, every search is some kind of "trial-and-error" procedure. Let's consider, for example, procedure of finding a number which is equal to given number "a".

Code: Select all

FOR ALL ELEMENTS bi IN THE SET "B" DO
    IF bi = a     /* Trial */
        THEN EXIT
        ELSE CONTINUE SEARCH     /* Error */
    END
END

Is't it T&E method?

Obviously, this has nothing to do with T&E. It's mere linear scanning of a list, with testing for a condition.
I think you need to read the definition of T&E.

Inference engines use search (i.e. T&E) too, but one using this method don't code search sequence exactly. So, I don't understand what is the principal difference between your solver and other logic solvers. You can add new rule in more general and simple way, yes?

Firstly, "search" and "T&E" are not the same thing. T&E is a well-defined procedure. "Search" can be any type of search.

Secondly, the way a new rule is added is different ("simple" depends on one's knowledge), it is closer to its logical definition (indeed the rule in CLIPS is just a variant of its FOL syntax)

Thirdly, Inference engines don't use search at the same level as T&E does.
One elimination of a candidate C in T&E is the (possible) result of applying a lot of constraints and Singles. It works or not, depending on C.
One elimination in SudoRules is the result of matching the conditions of some resolution rule with the current set of facts. The above whip[3] is only one step in SudoRules. Of course, you can write procedural code to do the same pattern-matching; but in CLIPS I need not do it.

I think it may be clearer if I write the pseudo-code for the above whip[3] rule:

Code: Select all

(defrule whip[3]
   if there is a partial-whip[2] with
      target = ?zzz
      list of llcs = $?llcs
      list of rlcs = $?rlcs
      list of csp-vars = $?csp-vars
      last-rlc = ?last-rlc
   
   ;;; ?new-llc
   and if there is a candidate ?new-llc
       which in not a previous llc or rlc
      and which is linked to ?last-rlc
   
    ;;; ?new-csp
    and if ?new-llc is a label for some csp-variable ?csp-var

   ;;; condition for elimination
    and if all the other candidates for ?csp-var are linked to ?zzz or to a previous rlc
=>
    then eliminate ?cand
   and print what this
)

This is exactly what is given to the inference engine; nothing more, nothing less; in particular no procedure telling it how to check these conditions and no procedure telling it how to apply the rules.

[Serg]

Hi, Denis!

I think you need to read the definition of T&E.

Where can I find the definition of T&E?

I am trying to split 2 entities - your method of Sudoku puzzles solving (whips, braids, etc.) and your implementation of this method (CLIPS). I think your method can be used by humans in manual solving, right? One can built his own solver using your method (and using some procedural programming language) - yet another logical Sudoku solver. But you used non-procedural programming language to describe the task of puzzle solving. Namely this feature (non-procedural programming) differs your solver from others, right?

I think it's the shame that nobody can propose Sudoku solver based on logic being more efficient than backtracking ("brute force") solver. Let's consider square equation x^2 - 2x + 1 = 0. One can try to solve it by T&E method, scanning all integer numbers from -1000000 to +1000000. This method accidentally gives right result, but in very ineffective way. Opposite to this "brute force" method, one can use a formula for solving this equation. This method is fast and correct in contrast to T&E method. "Brute force" Sudoku solvers are fastest because there is no adequate mathematical methods for Sodoku solving.

Serg

[Mathimagics]

Hi Serg!

"Brute force" in my understanding is generally misused - it simply refers to any search method that enumerates all possibilities, testing each case for the conditions defined by the search.

Brute force search should not be confused with backtracking, where large sets of solutions can be discarded without being explicitly enumerated (as in the textbook computer solution to the eight queens problem).

Backtracking implies a method where a search algorithm (tree) can be "pruned" when conditions allow large sections of the solution space to be discarded.

So really, there is no such thing as a "brute force Sudoku solver" - by definition this would involve testing all possible solutions. The typical recursive solvers like dobrichev's FSSS are backtracking solvers.

[denis_berthier]

Hi, Denis!

I think you need to read the definition of T&E.

Where can I find the definition of T&E?

In my book "Pattern-Based Constraint Satisfaction" available as free pdf inside CSP-Rules or on ReasearchGate

I am trying to split 2 entities - your method of Sudoku puzzles solving (whips, braids, etc.) and your implementation of this method (CLIPS). I think your method can be used by humans in manual solving, right?

Yes. The definition of rules such as whips... is totally independent of their implementation and using them is as adapted to human solvers as Subsets can be.

One can built his own solver using your method (and using some procedural programming language) - yet another logical Sudoku solver. But you used non-procedural programming language to describe the task of puzzle solving. Namely this feature (non-procedural programming) differs your solver from others, right?

Yes, in SudoRules, rules can be implemented directly as such (with some syntactic formatting). Other solvers use a lower level procedural language (generally C, C++ or Java); one could also code them directly in assembly or even machine language.

I think it's the shame that nobody can propose Sudoku solver based on logic being more efficient than backtracking ("brute force") solver. Let's consider square equation x^2 - 2x + 1 = 0. One can try to solve it by T&E method, scanning all integer numbers from -1000000 to +1000000. This method accidentally gives right result, but in very ineffective way. Opposite to this "brute force" method, one can use a formula for solving this equation. This method is fast and correct in contrast to T&E method. "Brute force" Sudoku solvers are fastest because there is no adequate mathematical methods for Sodoku solving.

Sticking to Sudoku, if there was an equation able to give the solution, nobody would ever have heard of this game.
Solving a sudoku in a pattern-based way (as most players want) and solving it fast (as is required in generators) are totally different (and in fact contradictory) goals. As a result, there's no mystery that different techniques are required.

PS: I agree with Mathimagics: brute force is not the right name. Backtracking is better; but this is indeed only some part of very different structured search algorithms: DFS, BFS, T&E...

[Serg]

Hi, Mathimagics!
It's generally accepted that backtracking solvers are faster than logical Sudoku solvers. But I have slightly different experience.

Years ago I wrote my own Sudoku solver and found that "pure" backtracking solver too often encounters contradictions (and forced back by those contradictions). So, frequent contradictions slowed down my backtracking solver substantially. Then I added naked/hidden singles detection, and solver worked faster, because contradictions happened less often. Futher adding slightly harder techniques, such as naked/hidden pairs, made the solver slower because of additional processing overhead. So, I found that fastest solvers must be "hybrid" - they must use backtracking combined with some logical techniques.

You investigated FSSS, which is one of the fastest Sudoku solvers. Is it pure backtracking solver or it detects naked/hidden singles, i.e. uses some logical techniques?

Serg

[denis_berthier]

Hi, Mathimagics!
It's generally accepted that backtracking solvers are faster than logical Sudoku solvers. But I have slightly different experience.
Years ago I wrote my own Sudoku solver and found that "pure" backtracking solver too often encounters contradictions (and forced back by those contradictions). So, frequent contradictions slowed down my backtracking solver substantially. Then I added naked/hidden singles detection, and solver worked faster, because contradictions happened less often.

In constraints propagation solvers, when we consider (any kind of) backtracking, it's generally understood that we include basic constraints propagation + Singles (and sometimes whips[1]).

Futher adding slightly harder techniques, such as naked/hidden pairs, made the solver slower because of additional processing overhead. So, I found that fastest solvers must be "hibrid" - they must use backtracking combined with some logical techniques.

It's a matter of vocabulary. Sure, basic constraints propagation and Singles are logical techniques, but that doesn't make a solver very hybrid.

[Serg]

Hi, Denis!

Futher adding slightly harder techniques, such as naked/hidden pairs, made the solver slower because of additional processing overhead. So, I found that fastest solvers must be "hibrid" - they must use backtracking combined with some logical techniques.

It's a matter of vocabulary. Sure, basic constraints propagation and Singles are logical techniques, but that doesn't make a solver very hybrid.

I disaree with you. It's very important fact that some logical techniques can speed up backtracking solver. Maybe there exist some logical techniques being able to boost Sudoku solver performance further. Why not?

From a practical point of view - we should warn newbies that even a backtracking ("brute-force") solver should use simplest logical techniques to have good performance.

Serg

[denis_berthier]

Hi Serg,

Futher adding slightly harder techniques, such as naked/hidden pairs, made the solver slower because of additional processing overhead. So, I found that fastest solvers must be "hibrid" - they must use backtracking combined with some logical techniques.

It's a matter of vocabulary. Sure, basic constraints propagation and Singles are logical techniques, but that doesn't make a solver very hybrid

I disaree with you. It's very important fact that some logical techniques can speed up backtracking solver. Maybe there exist some logical techniques being able to boost Sudoku solver performance further. Why not?
From a practical point of view - we should warn newbies that even a backtracking ("brute-force") solver should use simplest logical techniques to have good performance.

Oh, I agree with that. But I don't think there are many "newbies" who don't know that backtracking and basic constraints propagations must be intertwined. If you don't do this and thus loose any possibility of detecting a contradiction, how do you know that you have to backtrack?
As for Singles, they mean that a variable is decided. It'd be rather absurd not to take this information into account before trying to go one level deeper and find a contradiction that could have been found earlier.
Using techniques as elementary as direct constraints propagation and singles isn't enough IMO to call a solver "hybrid".

[tdillon]

... we should warn newbies that even a backtracking ("brute-force") solver should use simplest logical techniques to have good performance.

Putting aside informal usage in the Sudoku community, in CS the normal distinction between a brute force algorithm and a backtracking algorithm is that a brute force algorithm can accept or reject only fully instantiated solution candidates, while a backtracking algorithm can reject partial solutions that already violate some constraint thereby ruling out many possible fully instantiated candidates at once. Bitcoin mining is an example of brute force algorithm because there is no way to evaluate partial solutions. But Sudoku solving is pretty much always done with backtracking and not brute force because you *can* evaluate partial solutions, and it would be ridiculously and infeasibly costly to not take advantage of this.

But backtracking is also more of a strategy or meta-heuristic than a specific algorithm, and as Denis mentioned above it’s been generally understood since at least the 60s that practical backtracking algorithms will go beyond the most basic template to incorporate efficient forms of constraint propagation. DLX and DPLL are both examples of this sort of backtracking algorithm, and when applied to Sudoku they effectively do backtracking with naked and hidden singles.

Certainly if you want to write a fast backtracking solver you’ll have to explore which forms of inference you can incorporate to achieve the best balance of cost vs reduction in search. The fastest solvers so far all do naked singles, hidden singles, and locked candidates (though tdoku also handles certain cardinality constraints). And if you peruse the benchmarks here you’ll see that solver performance characteristics really tend to group by these choices, and by the intimately connected choice of primary representation.

Maybe there exist some logical techniques being able to boost Sudoku solver performance further. Why not?

Maybe! There are some real reasons why singles + locked candidates seem to be especially useful, but maybe there's another point in the design space of representations and inference techniques that strikes a better balance of cost and utility.

[Mathimagics]

You investigated FSSS, which is one of the fastest Sudoku solvers. Is it pure backtracking solver or it detects naked/hidden singles, i.e. uses some logical techniques?

Hi Serg!

FSSS is a simple backtracking solver with naked single + hidden single checking as the fundamental search-tree pruning method.

It gets its speed advantage by a highly efficient representation of the current puzzle state, using bitmaps. This is designed in such a way as to make the testing for hidden singles more efficient.

Mladen then produced an FSSS2, which made the bitmap handling much more efficient by using 128-bit registers. There are CPU instructions that can do logical operations (and, or, xor etc) on these double-width bitmaps.

It is true that implementing more exotic techniques can wind up slowing down your backtracking solver, but this is because these simple solvers (like FSSS) are highly efficient for the 9x9 Sudoku grid. For 16x16, however, they usually take a huge performance hit, mainly because of the exponential growth of the size of the search tree.

So adding extras like naked/hidden pairs might slow down 9x9 solving, but will be much faster for a 16x16 grid - the gains made by pruning the search tree become much greater than the cost of implementing the techniques.


Cheers
MM

[rjamil]

Hi,

Let me add my 2 cents regarding difference between Brute-Force and T&E/Guessing for solving Sudoku as what I understand (irrespective of valid/proper Sudoku).

First of all, thanks to SudokuWiki site that helps me a lot to elaborate my point of view.

Just go to Sudoku Solver page. Here, you will see puzzle in two different grids, i.e., small grid contains puzzle clues/givens only; and large grid contains puzzle clues and all 1-9 digits as pencilmark for each unsolved cell (without applying auto update pencilmark).

From here, let's try digit 1-9 one by one from first unsolved cell as solved in small grid and see if it contradicts (become red) in large grid. If not then continue to try digit 1-9 one by one to another unsolved cell as solved and check contradiction. Otherwise, try next digit, or if all digits exhausted then reinstate cell as unsolved; place all 1-9 digits as pencilmark and go back to previous/first cell and try next digit. (Assuming the order of picking unsolved cell and digit are any sequential order).

The above scenario of solving Sudoku may be called Brute-Force solving.

For T&E/guessing solving scenario, just simply press [Take step] button twice for "Show possibilities" before start solving the puzzle and each time putting digit in to unsolved cell of small grid by choosing possible digit from large grid. Continue to next unsolved cell if no contradiction found. Otherwise, remove contradicted digit from unsolved cell, reinstate pencilmark and go back to previous/first unsolved cell.

Hope the above explanation is worth to the context of this topic. Please ignore and accept my apology if not.

R. Jamil

[Serg]

Hi, Mathimagics!

It is true that implementing more exotic techniques can wind up slowing down your backtracking solver, but this is because these simple solvers (like FSSS) are highly efficient for the 9x9 Sudoku grid. For 16x16, however, they usually take a huge performance hit, mainly because of the exponential growth of the size of the search tree.

Thank you for this interesting information! Did you add some logical rules for 16 x 16 Sudoku solver?

Serg

[Serg]

Hi, tdillon!
Did you checked use of other logical solving rules (beyond naked/hidden singles and locked candidates) in your "tdoku" solver?

Serg