On zero solutions

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

On zero solutions

Postby m_b_metcalf » Mon Nov 28, 2011 2:11 am

In the Patterns Game, it is useful to be able to determine whether a puzzle lies above or below some SE
rating. For instance, if a puzzle can be solved using X-wing, we know its rating is 3.2 and we can retain or reject it depending on
what we are looking for. The trouble is that, as we enter the region of higher ratings, the algorithms required become ever more
complicated to code and require ever more time to execute. However, many of these algorithms depend on testing for contradictions:
a candidate value is asserted to be the true value and a more or less complicated chain of logic determines whether this
assumption is true or not, i.e. whether the candidate value can be retained or is certainly wrong. In the context of the Patterns Game,
however, the details of these chains are of no interest, we simply want to know whether a candidate value is valid or not.
But, in fact, a contradiction is equivalent to there being zero solutions to the puzzle, and that can be determined more simply by other means.

The easiest to implement is simply to use a solver to count the number of solutions, but counting up to zero turns out to be, typically,
dreadfully slow. Another way is to make a series of logical tests on the candidate puzzle; for instance, if there exists a cell containing
exactly three candidate values and each of these values occur only once in the corresponding r/c or b, then
there is a clash and there are zero solutions. An algorithm for removing invalid candidate values thus looks like this:

Code: Select all
1) Solve the puzzle as far as possible with simple methods.

2) For each unsolved cell

     For each candidate remaining

        Set the candidate value to be the solution value (removing the other candidates in the cell and making the
           other basic elimininations)

        a) Solve this version of the puzzle further using singles, once, (fast) OR
        b) Solve this version of the puzzle as far as possible using simple methods (slow)

        Pass the incomplete puzzle to a procedure (not a solver) that checks whether there are definitely zero
           solutions

        If there are zero solutions, remove the candidate definitively from the partially solved puzzle

        Otherwise restore the candidate and take the next one

3) Resume solving the puzzle, now with fewer candidate values, using simple methods.

4) Iterate until completion, or until no further progress.

It turns out that the fast version of this method solves most puzzles up to about SE=8.5 and beyond, and the slow version
up to an SE value of about 9.9. That's quite useful as a filter.

Regards,

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

Re: On zero solutions

Postby coloin » Mon Nov 28, 2011 10:45 pm

Yes Mike that looks a good filter...........

It reminded me of a completely off-the -wall theory i had

Take a hard puzzle [GN}
Code: Select all
+---+---+---+
|...|...|.39|
|...|..1|..5|
|..3|.5.|8..|
+---+---+---+
|..8|.9.|..6|
|.7.|..2|...|
|1..|4..|...|
+---+---+---+
|..9|.8.|.5.|
|.2.|...|6..|
|4..|7..|...|
+---+---+---+

add a wrong clue - a 2@r1c1
you get no solution .....

except there are many "grid solutions" like this one

Code: Select all
+---+---+---+
|251|876|439|
|986|341|725|
|743|259|861|
+---+---+---+
|538|197|246|
|674|532|918|
|192|468|573|
+---+---+---+
|319|684|.5.|
|827|915|6..|
|465|723|...|
+---+---+---+


This is a grid with 8/9 valid boxes

Ive had a go manually - there dont seem to be many of these in easy puzzles - but loads in hard puzzles.

Wouldnt have a clue how to code it either ........

C
coloin
 
Posts: 1638
Joined: 05 May 2005

Re: On zero solutions

Postby champagne » Tue Nov 29, 2011 7:44 am

Hi Mike,

New approach. Two main questions raise

any solver does similar things, so the first question is "how fast" is that process compared to a solver

The second one is more complex.
As long as you are looking for high ratings, this works
If you want to play the pattern game, such method has IMO some drawbacks.
No way to detect UR possibilities that influence very much the game
Same for "BUG's" "Aligned xxx"
So how do you sort out puzzles to fight in that area

Before I worked so hard on skfr, I was using my own solver to filter the puzzles.
Although skfr deviates from serate, I got a significant improvement using it


regards

champagne
champagne
2017 Supporter
 
Posts: 5742
Joined: 02 August 2007
Location: France Brittany

Re: On zero solutions

Postby m_b_metcalf » Tue Nov 29, 2011 8:04 am

champagne,
The answer to your first question is that I first wrote a zero-solution checking procedure because doing it with a (my) solver was occasionally very slow. I don't now have a timing, but maybe I'll make a test next week (after the next game).

And, to the second one, I use it only to look for high ratings at the beginning of a game.

Regards,

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

Re: On zero solutions

Postby champagne » Tue Nov 29, 2011 11:17 am

m_b_metcalf wrote:champagne,
The answer to your first question is that I first wrote a zero-solution checking procedure because doing it with a (my) solver was occasionally very slow. I don't now have a timing, but maybe I'll make a test next week (after the next game).

And, to the second one, I use it only to look for high ratings at the beginning of a game.

Regards,

Mike


I made a test on a lot of the last game (not processed, I turned off the game at that time)

I used skfr V1.2.0 with the command -n(2)9.2 selecting puzzles reaching quickly a rating > 9.2

The lot of more than 710 000 puzzles was processed at an average speed of 300 puzzles per sec (3GHz)
The upper fraction contains about 12 000 puzzles

champagne
champagne
2017 Supporter
 
Posts: 5742
Joined: 02 August 2007
Location: France Brittany

Re: On zero solutions

Postby denis_berthier » Thu Dec 08, 2011 1:15 pm

m_b_metcalf wrote:An algorithm for removing invalid candidate values thus looks like this:
Code: Select all
1) Solve the puzzle as far as possible with simple methods.

2) For each unsolved cell

     For each candidate remaining

        Set the candidate value to be the solution value (removing the other candidates in the cell and making the
           other basic elimininations)

        a) Solve this version of the puzzle further using singles, once, (fast) OR
        b) Solve this version of the puzzle as far as possible using simple methods (slow)

        Pass the incomplete puzzle to a procedure (not a solver) that checks whether there are definitely zero
           solutions

        If there are zero solutions, remove the candidate definitively from the partially solved puzzle

        Otherwise restore the candidate and take the next one

3) Resume solving the puzzle, now with fewer candidate values, using simple methods.

4) Iterate until completion, or until no further progress.

It turns out that the fast version of this method solves most puzzles up to about SE=8.5 and beyond, and the slow version
up to an SE value of about 9.9. That's quite useful as a filter.


Mike, this must surely be a useful filter.

Unless I'm missing some subtle point, the fast algorithm is T&E and the slow one is T&E("simple methods"), whatever "simple methods" means - according to my definition of T&E (which I first defined somewhere in the "fully supersymmetric chains" thread of the Player's forum and which I later recalled here: http://forum.enjoysudoku.com/abominable-trial-and-error-and-lovely-braids-t6390.html)
(I give this precision, because there are so many definitions or non-definitions of T&E around).
Have I missed any additional requirement in your algorithm ?

But then, I'm surprised by the bound you give for the fast algorithm. Whips solve up to SER 9.3 (sure it's a fuzzy boundary, but, in about 10,000,000 puzzles solved, I've seldom seen any 9.3 not solved by whips); braids (which are more powerful than whips) solve all that can be solved by T&E; therefore T&E should solve up to some SER > 9.3.

For the slow version, all depends on what you count as "simple methods". At first sight, given your 9.9 bound, I'd say it corresponds to gT&E (i.e. g-braids, i.e. "simple methods" = basic interactions), but I've never looked closely at this boundary.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Re: On zero solutions

Postby m_b_metcalf » Thu Dec 08, 2011 11:42 pm

denis_berthier wrote:But then, I'm surprised by the bound you give for the fast algorithm. Whips solve up to SER 9.3 (sure it's a fuzzy boundary, but, in about 10,000,000 puzzles solved, I've seldom seen any 9.3 not solved by whips); braids (which are more powerful than whips) solve all that can be solved by T&E; therefore T&E should solve up to some SER > 9.3.

Well, in fact, the boundary is quite fuzzy, depending a lot on the ED part of ER/EP/ED. I've seen it go up to 9.3.

Regards,

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


Return to General