The New Sudoku Players' Forum

[champagne]

I have locked the specifications for this first version of the vicinity search.
For sure, the background is the tridagon threat, but the code has no reference to it.

The start is a valid puzzle with possible redundant clues.
The first step is to find all minimals and the set of small unavoidable sets of the solution grid.

Then a vicinity search is done on each of the "minimal" in 3 directions.

switch to another solution grid using one of the ED unvoidable sets of the table
Kill one cell and find new puzzles in the same solution grid
Kill one cell and find new puzzles in another solution grid.

In all cases, (except for the minimal found at start), The search of new puzzles will follow a similar path

take the relevant set of unavoidable sets and find new valid puzzles
search the list of minimal corresponding to this new valid.

In fact this is
-0+p-q in the first case
-1+p-q for the 2 other cases.

Any of these valid minimal new puzzles is then checked to see if it can be "solved easily". Only puzzles resisting to his test are written.

The current "easy test" leads more or less to puzzles rating over skfr 8.0 generally over skfr 9.0

[dobrichev]

Hi Champagne,

IMO it is worth to consider a 4-th direction - pattern preserving.
From the Patterns Game we know good patterns do exist, while good solution grids existence is more questionable. Dropping minimality requirement somehow lineary extends the search space and adds to results.
To my knowledge, exploring non-symmetrical patterns targeting hard puzzles has never been done.

Unless the pattern preserving approach is entirely incompatible to tridagons...

[champagne]

Hi Champagne,

IMO it is worth to consider a 4-th direction - pattern preserving.
From the Patterns Game we know good patterns do exist, while good solution grids existence is more questionable. Dropping minimality requirement somehow lineary extends the search space and adds to results.
To my knowledge, exploring non-symmetrical patterns targeting hard puzzles has never been done.

Unless the pattern preserving approach is entirely incompatible to tridagons...

Hi Mladen,

My next post was planned to tell more about my first direction;
If I am right, this is very very close to what you have in mind.

In the pattern game, you could change any number of cells of the pattern. The new puzzle had to be valid and minimal.
It’s obvious that for each new we had a different solution grid sharing one unavoidable set.

In the twin puzzle if I got it, you have something similar. Starting from the invert puzzle, you take (if any) one of the multiple solutions having all cells in the original pattern. For sure, the corresponding puzzle will be valid, but with a tiny chance to be minimal;

I am closer to the pattern game having in mind that we can change the pattern.

If you take any unavoidable set of the solution grid, you have one or more hits in your minimal” puzzle.
You can apply this unavoidable set to get the new solution grid. I do it trying to solve the invert puzzles, having cleared in the PM the source.
Up to now, this gave easily the new solution grid.

The new puzzle can still have multiple solutions, then the code uses the UAs describing the multiple solutions to add clues to get valid puzzles
But these new puzzles are often not “minimal”. You know what to do to get the list of minimals.

So the sequence for one minimal and one UA is

Find the new solution grid
Check if the pattern applied to the new solution grid is valid
If not, find all valid (in the limit of 2 added clues in my code) with no more redundant clue
Find minimal puzzles for each such puzzle.

I limit “UAs used” to UAs in the list of ED small UAs, with a maximum of 100 UAs

[dobrichev]

This just reminds me how useful an extension of the rating system would be, covering puzzles with no solution and puzzles with many solutions.

[champagne]

and in my wording for this direction , the -0+p-q is not very clear
the process is

kill "0' cell
change "n" cells depending on the UA
Add 'p' cells to have it valid
kill 'q' cells to have it minimal.

and 'n" is usually low but can have all clues of the UA

[champagne]

I continue the summary of the vicinity process with the groups B and C.

_____________________________________________________
One missing remark on the first group, valid for all groups

kill "0' cell
change "n" cells depending on the UA
Add 'p' cells to have it valid
kill 'q' cells to have it minimal.

In the last step kill 'q' cells to have it minimal, the cell can be (and will usually be) one cell of the original pattern, In fact, the final puzzle can have less cells than the original one.
_______________________

For groups B and C, the start is to kill cells of the original pattern. The process applied here could be done with more than one cell killed at the start, but as the vicinity is supposed to loop, one cell killed (as here) seems reasonable.

The process is applied to each cell of the original pattern. As we have several “minimal” sharing cells, a possibility to optimize the process exists, but difficult to implement.

For each cell killed, we can try to find new puzzles

In the same solution grid, this is group B
In another solution grid, this is group C.

In both cases, the first step is to get the unavoidable sets not hit. In the program, we work with the list of UAs with no subset given by the brute force applied to the original pattern. As we start from a minimal puzzle, this list cannot be empty.

And from here, group B and group C differ.

_____________________________________________________

In group B, we want a new puzzle in the same solution grid. We have to hit all UAs of our list and to check that the puzzle is valid (the brute force output is limited to 50 UAs).

This is done with a limit of 2 clues added. If one clue hit all UAs, 2 clues are also tried. The basis for 2 clues is the smallest UA of the list given by the brute force. Nothing is done if more than 2 clues are needed.

All such valid puzzles are again reduced to “minimal” if needed.

___________________________________________________________

Group C is slightly more complex. As we want to try another solution grid, the first task is to find it.
Our list of UAs given by the brute force defines the solution grids to try. As with UAs used in group A, the program finds the solution grid.
From here, the process is like what was done in group A

The brute force is called again with the new solution grid and the pattern (-1). In the new list of UAs, the cell killed must be ignored. We cannot reuse it.
And with this new list of UAs, one or 2 clues are added (if possible) to get a valid puzzle.