Dobrichev's Solver - UA Collection

Programs which generate, solve, and analyze Sudoku puzzles

Dobrichev's Solver - UA Collection

Postby Mathimagics » Thu Jul 26, 2018 5:40 pm

.
dobrichev suggested that his (excellent) Sudoku solver can be used to identify UA sets as follows:

  • assume we have a multi-solution puzzle
  • identify the unsolved cells at the point of the last guess made
  • this set is invariably a minimal UA

I think this might not always be the case, and will provide what I believe are counter-examples.

I have tested both normal Sudoku and SudokuP solvers. Examples here are using normal Sudoku.

Our test grid:
Code: Select all
123456789456897231978312456247638915385149672691725843862571394714963528539284167


I generated test cases by removing random clues until the first occurrence of multiple-solutions. The UA (last set of unsolved cells) was then tested in the normal way by:

  • setting grid X = full solution grid minus those clues identified in the UA
  • testing whether every individual UA clue when added to X gave a unique solution

Most of the time the UA was valid, but in about 25% of cases some clues did not pass the test. Here are 3 examples of when the test failed. P is the puzzle selected by random reduction, U is the UA identified from the solver's last guess.

The UA clues marked "?" are clues in the UA that failed the test, "X" indicates a valid UA clue:

Code: Select all

P: ...45..8.4.689.2.......2...2.76.89...851.96.2..1.25.43....7......49....8539.8.167
U: X....X..X.?......?X?..X..?X.......??.........??........X...X...?X..X.............

P: ...4.6..9..6..7.3..78..245..4.6..9153......72.9.72....86...1.94...9635..5......6.
U: ?X?.X..X..X.X..X.X.........X.X..........................XXX.?..X?.....XX.?.XX.X.X

P: .23..678...689.....7...2....4...8..53....9.72.91......8...71.947...63.2.539..41.7
U: X..?....?X......XX?..XX.X.XX..XX.......XX.X..X...X..XX...........................


In order to verify that the dodgy UA's weren't simply an artefact created by failure to identify the "last guess" point correctly, I ran the test with the solver set to record ALL guesses, then scanned this list testing each unsolved clue set, but this did not turn up any other valid UA set.


I'm hoping I have made some elementary error in this process, because having to filter the UA's to remove invalid entries is an overhead, so it would be nice if this was not needed.

Either way, it is still a nice easy way of getting UA's.
Last edited by Mathimagics on Thu Jul 26, 2018 6:12 pm, edited 1 time in total.
User avatar
Mathimagics
2017 Supporter
 
Posts: 760
Joined: 27 May 2015

Re: Dobrichev's Solver - UA Collection

Postby champagne » Thu Jul 26, 2018 5:51 pm

this set is invariably a minimal UA

change this by

this is a "relatively smalll UA" with a good chance to be minimal

and you'll be in the good way.

In such a process, you still have to check for subsets/supersets.
champagne
2017 Supporter
 
Posts: 6703
Joined: 02 August 2007
Location: France Brittany

Re: Dobrichev's Solver - UA Collection

Postby Mathimagics » Thu Jul 26, 2018 6:15 pm

.
Yes, well I didn't examine the issue of whether the UA is minimal or not, since this a moot point when the UA is NOT in fact a UA!
User avatar
Mathimagics
2017 Supporter
 
Posts: 760
Joined: 27 May 2015

Re: Dobrichev's Solver - UA Collection

Postby dobrichev » Thu Jul 26, 2018 6:37 pm

Mathimagics wrote:.
dobrichev suggested that his (excellent) Sudoku solver can be used to identify UA sets as follows:

  • assume we have a multi-solution puzzle
  • identify the unsolved cells at the point of the last guess made
  • this set is invariably a minimal UA


    You should read the above in a bit different way
  • assume we have a multi-solution puzzle, having one of the solutions the grid we are interested in
  • identify the unsolved cells at the point of the last (deepest) guess made, where one of the branches leads to the grid of interest, and other branch(es) lead to at least one valid solution
  • this set is a minimal UA for the grid of interest since it identifies one of the minimal differences between this grid and other valid solution grid(s).
dobrichev
2016 Supporter
 
Posts: 1622
Joined: 24 May 2010

Re: Dobrichev's Solver - UA Collection

Postby Mathimagics » Thu Jul 26, 2018 6:45 pm

.
Say U is a set of clues {U[k]}, and G is the solution grid.

If U has these properties:

  • G - U has multiple solutions
  • G - U + U[k] has unique solution, for every k

Then U is a UA, and must be minimal, since any subset U* would fail the first test, is that not true?
User avatar
Mathimagics
2017 Supporter
 
Posts: 760
Joined: 27 May 2015

Re: Dobrichev's Solver - UA Collection

Postby Mathimagics » Thu Jul 26, 2018 6:49 pm

Hi Mladen,

Oh, you have quickly identified my (inevitable) elementary mistake, I think!

I forgot the target grid!!

I will change my tests ...

My comment above was for champagne ... if we have a UA and I test it thus, it will be minimal ...
User avatar
Mathimagics
2017 Supporter
 
Posts: 760
Joined: 27 May 2015

Re: Dobrichev's Solver - UA Collection

Postby dobrichev » Thu Jul 26, 2018 6:57 pm

champagne wrote:this set is invariably a minimal UA

change this by

this is a "relatively smalll UA" with a good chance to be minimal

In this context minimal means irreducible.
Running a solver after all small-sized UA sets are hit wouldn't produce another small-sized one.

To Mathimagics:
The solver fsss implemented in gridchecker is very old. Faster solvers were developed in the last years - fsss2 is at least 2 times faster, same for ZSolver.
gridchecker's solver have mode where it always branches firstly to the given solution. In this mode it would be easier to you in intercepting the right branch.
dobrichev
2016 Supporter
 
Posts: 1622
Joined: 24 May 2010

Re: Dobrichev's Solver - UA Collection

Postby Mathimagics » Thu Jul 26, 2018 7:55 pm

.
Ok, now I'm really confused! :?

I've not heard of any of those solver versions, but the solver I have was created by you (Mladen) from Brian Turner's solver, and adapted by me to solve SudokuP.

The original file has no date, sadly, but is commented "A Fast Simple Sudoku Solver by Mladen Dobrichev".

OK, I see now where fsss comes from, so I have the old one?

There is no sign of using known solution in it.

Conversion to SudokuP was painless because of table-driven approach used by BT. I'm a bit wary of "faster" solvers that assume standard Sudoku ...

Where are "fss2" and/or "Zsolver" to be found?

Do you have SudokuP versions of either one?

Sorry to ask so many questions!! :)
User avatar
Mathimagics
2017 Supporter
 
Posts: 760
Joined: 27 May 2015

Re: Dobrichev's Solver - UA Collection

Postby champagne » Thu Jul 26, 2018 8:37 pm

dobrichev wrote:
champagne wrote:this set is invariably a minimal UA

change this by

this is a "relatively smalll UA" with a good chance to be minimal

In this context minimal means irreducible.

right not necessary small, but irreductible :oops:
champagne
2017 Supporter
 
Posts: 6703
Joined: 02 August 2007
Location: France Brittany

Re: Dobrichev's Solver - UA Collection

Postby Mathimagics » Thu Jul 26, 2018 9:55 pm

.
Mladen,

I have downloaded gridchecker-master from your github page, and see that the solver there is much longer than my version.

Is this the fsss2 that you referred to?

I tried to compile solver.cpp, and got an error in function getFFFF:

Code: Select all
t_128.h: line 320: _mm_undefined_si128 not declared in this scope


A search found no other reference to/definition of this symbol anywhere in the code/header files, so perhaps a recent change?

I notice that only fClueIterator.cpp references getFFFF, so I commented it out of the t_128 header and achieved successful compilation of the solver module. I'm using g++ v4.8.3 as it's the only GNU gcc Win-64 executable version I could find.

I will attempt to make a SudokuP version based on the same table extensions I used with the old solver.
User avatar
Mathimagics
2017 Supporter
 
Posts: 760
Joined: 27 May 2015

Re: Dobrichev's Solver - UA Collection

Postby dobrichev » Thu Jul 26, 2018 10:30 pm

Mathimagics wrote:I've not heard of any of those solver versions, but the solver I have was created by you (Mladen) from Brian Turner's solver, and adapted by me to solve SudokuP.

This is not quite correct. fsss is written from scratch.
I got two key points from Brian Turner - the identification of a single candidate in a house and the sufficiency to run the slower elimination algorithms only once prior to the first guess.
JSolver is very close to the original Brian Turner's solver. Ask Jason, the forum administrator, for details.
Here is the page for fsss.

Mathimagics wrote:There is no sign of using known solution in it.

OK, I will help you by extracting here 3 lines (out of 38) from file solver.h
Code: Select all
extern unsigned long long solve(const int* gridBM, const char* in, const unsigned long long maxSolutions);
extern unsigned long long solve(const int* gridBM, const char* in, const unsigned long long maxSolutions, char* out);
extern unsigned long long solve(const int* gridBM, const char* in, uaCollector *theCollector);

Mathimagics wrote:Conversion to SudokuP was painless because of table-driven approach used by BT. I'm a bit wary of "faster" solvers that assume standard Sudoku ...

Almost all solvers are table driven. This is not hard to invent.

Mathimagics wrote:Where are "fss2" and/or "Zsolver" to be found?

fsss2 sources are in github, very close to gridchecker's sources.
Try google with sudoku+"zsolver"

Mathimagics wrote:Do you have SudokuP versions of either one?

No, but it is easy to be implemented (and hard to test) in fsss2.
dobrichev
2016 Supporter
 
Posts: 1622
Joined: 24 May 2010

Re: Dobrichev's Solver - UA Collection

Postby Mathimagics » Fri Jul 27, 2018 3:56 am

.
Ok, I have got fsss and fsss2 working as stand-alone C-callable functions.

Timings for 10 passes over 17C set (49157 puzzles) :

  • fsss0: 2.109s (my existing solver, from older GridChecker 1.18?)
  • fsss1: 3.141s (latest solver from GridChecker (1.31))
  • fsss2: 1.297s

Of course, being Windows, these times fluctuate with each run, but these are indicative.

Why does the old solver (fsss0) run faster than the current GridChecker version?

I think it is because of two things:

  • it is faster with LockedCandidates checking, whereas the GridChecker version does not run faster, in fact a little bit slower (and I see a comment to this effect in the code)
  • it also benefits from a modest but noticable improvement when compiled with -O3 than -O2, whereas the GridChecker version is the same for -O2 and -O3

dobrichev wrote:No, but it is easy to be implemented (and hard to test) in fsss2.


Why should that be hard to test?
User avatar
Mathimagics
2017 Supporter
 
Posts: 760
Joined: 27 May 2015

Re: Dobrichev's Solver - UA Collection

Postby blue » Fri Jul 27, 2018 5:01 am

Mathimagics wrote:Timings for 10 passes over 17C set (49157 puzzles) :
(...)

Why does the old solver (fsss0) run faster than the current GridChecker version?

I think it is because of two things:

  • it is faster with LockedCandidates checking, whereas the GridChecker version does not run faster, in fact a little bit slower (and I see a comment to this effect in the code)
(...)

Most of the 17's are solvable with naked and hidden singles.
I haven't seen the version in GridChecker, but for singles solvable puzzles, added code to allow for locked candiates checking ... even if the checks are never needed ... could only slow things down.

BTW: I'm pretty sure Mladen's code has been optimized, mainly for use in cases where puzzles are more likely to have 0 or 2+ solutions, than just one.
blue
 
Posts: 701
Joined: 11 March 2013

Re: Dobrichev's Solver - UA Collection

Postby Mathimagics » Sat Jul 28, 2018 10:13 pm

blue wrote:BTW: I'm pretty sure Mladen's code has been optimized, mainly for use in cases where puzzles are more likely to have 0 or 2+ solutions, than just one.


I can confirm that now.

I have got an fsss2 solver working for SudokuP. This involved generating new header files for the two tables: visibleCells (affected cells) and bitsForHouse = cells in row/col/box/pset, and some code tweaks needed to cope with increasing the # of "houses" from 27 to 36 (and thus no longer neatly fitting in a 32-bit chunk of the 128-bit vectors).

First I tested 1.45 million minimal 12-clue SudokuP puzzles, and got solve rates of 150K puzzles/second with the old solver, and 250K/s with the new. New solver was 1.7 times faster.

I then ran the same test with removal of two clues in each puzzle, and got rates of 80K/s with the old solver, and 220K/s with the new solver. New solver was 2.75 times faster.

I like it very much! And I think it will work for arbitrary PSET definitions, which is a bonus.

Hats off again to dobrichev for a neat bit of work ...
User avatar
Mathimagics
2017 Supporter
 
Posts: 760
Joined: 27 May 2015

Re: Dobrichev's Solver - UA Collection

Postby emerentius_ » Sun Jul 29, 2018 4:46 am

Mathimagics wrote:.
Conversion to SudokuP was painless because of table-driven approach used by BT. I'm a bit wary of "faster" solvers that assume standard Sudoku ...

Where are "fss2" and/or "Zsolver" to be found?


Looks like you already found a suitable replacement in fsss2. I just wanted to note that Zsolver would also be trivial to adapt. There are two places in the code that would need minor adaptations and all the information about solved cell position is already present.
emerentius_
 
Posts: 14
Joined: 09 January 2018

Next

Return to Software