The New Sudoku Players' Forum

[Mathimagics]

.
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.

[champagne]

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.

[Mathimagics]

.
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!

[dobrichev]

.
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).

[Mathimagics]

.
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?

[Mathimagics]

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 ...

[dobrichev]

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.

[Mathimagics]

.
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!!

[champagne]

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

[Mathimagics]

.
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.

[dobrichev]

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.

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);

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.

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"

Do you have SudokuP versions of either one?

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

[Mathimagics]

.
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

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

Why should that be hard to test?

[blue]

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.

[Mathimagics]

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 ...

[emerentius_]

.
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.