The New Sudoku Players' Forum

by **champagne** » Sun Oct 27, 2013 1:42 pm

The search of hardest puzzles used pattern scanning at the very beginning, mainly in the area 20_22 clues.

Later on, the main tool used has been the vicinity search, with a lot of variations.

The study of the so called "potential hardest" puzzles has shown that most of them had a limited number of "exotic properties", mainly

Exocet pattern
SK loop pattern
rank 0 logic pattern.

Anybody having tried to find new "hardest" using the vicinity search knows that one major difficulty is to find seeds.

I am for long thinking that a kind of reverse search, starting from a given pattern of given and trying to find a specific exotic property is one good way to create new seeds (and, why not, to find directly puzzles of the potential hardest family)

I tested with good preliminary results the pattern of the first puzzle in the potential hardest data base

11.1.....1.....1....1.1.....1...1.1...11..1......1...1..11..1......1...1.....1.1.;1;GP;champagne dry;

That pattern has been deeply searched, so I got no fresh high rating (11.0 and more), but I generated new seeds.

I open that thread to share experience on that process

by **champagne** » Sat Nov 02, 2013 3:34 pm

I continue investigations to try to design a scan process generating plenty of potential hardest puzzles.

I am working so far on patterns where an Jexocet has been found.

I found 519341 such patterns out of 894628 puzzles.

Most of the patterns have only one matching puzzle, but some have many

This is the top list sorted by number of puzzles matching with the pattern.

column 2 is the sequence number in the base, colum 3 the number of puzzles and column 4 the number of clues.

Hidden Text: Show

I tested a pattern of 24 clues with 94 puzzles matching to the pattern in the data base.

I started the generation on the 2 morphs above with the following assumption

The base of the exocet is in r1c12
The targets are r3c4 and r2c7

Code: Select all: ..1 ..1 .1. 11. 1.. ... 11. .1. 1.. 1.. ..1 .1. .1. ... ..1 ... .1. 1.. .1. ..1 .1. ... .1. 1.. ... 1.. ..1

Code: Select all: ..1 ... ... 11. 1.. ... 11. .1. 1.. 1.. ..1 .1. .1. ... ..1 ..1 1.. 1.. 1.. ..1 .1. ..1 1.. 1.. ... .1. ..1

The assumptions for the scan are

4 or 5 given in box 1
base 4 digits
no base digit in band 1,
no base digit columns 3;4;7
maximum of 3 given in boxes 4+7 columns 1+2
possible base digits keeping valid the base in columns 1;2

Expanding the first morph has been very very long and gave nothing.
Expanding the second morph has been relatively fast and I got

3270 new seeds
73 puzzles new to load in the potential hardest base.

The first morph has several properties that could explain the bad result

the column 3 has no given in boxes 4;7
column 4 has only one given in boxes 5;8

Defining the relevant filters should lead to an acceptable performance to use that scan in the search

by **David P Bird** » Fri Nov 08, 2013 11:24 am

Champagne, I don't pretend to understand your approach but I'd be interested in any Almost JExocets which turn out to make some or all of the regular eliminations anyway.

I think we've found that when there is a single spoiler in the partial fish cells it's usually possible to use supporting inference chains to make at least some of the eliminations, but I believe we've yet to finish analysing what can be done with spoilers in the JE band itself.

The most obvious example would be the common eliminations that can be made when one of the base cells contains a spoiler digit
a) when it's false (from JExocet)
b) when it's true (from a supporting chain or alternative pattern)
When these produce a contradiction, then one or the other will be proved to be true.

From what you write, I don't think you'll find any suitable examples (but I could be wrong) but it may be worth considering later.

David

by **champagne** » Fri Nov 08, 2013 1:01 pm

Hi David,

I stopped for a while analysis of existing puzzles and I am working on new ways to generate new potential hardest.
The fact that I am first working on patterns that can produce JE's can be confusing.

In fact, I am currently working on patterns that should produce pure JE's.
I should be in a position to make in the next days a summary of the results in the 21 clues field.

This is relatively far from your points of interest, although the work on JE's has been a key step in that design.

some comments on your post

David P Bird wrote:The most obvious example would be the common eliminations that can be made when one of the base cells contains a spoiler digit
a) when it's false (from JExocet)
b) when it's true (from a supporting chain or alternative pattern)
When these produce a contradiction, then one or the other will be proved to be true.
David

This is quite new as concept if I catch your point. None of us has studied so far spoiler digits in the base.
I have difficulties to imagine what can come out of that
Could you explain a little more what you have in mind.

David P Bird wrote:I think we've found that when there is a single spoiler in the partial fish cells it's usually possible to use supporting inference chains to make at least some of the eliminations, but I believe we've yet to finish analysing what can be done with spoilers in the JE band itself.

I guess the JE band is the band/stack where is located the expected base. I did not follow all your discussions with sultan vinegar, but This could be continued in the same thread.
With precise requirements, I could try to extract the relevant puzzles;

by **champagne** » Sat Nov 09, 2013 9:47 am

I made a test of the new generation code creating hard puzzles in the near vicinity of exocets.

I have currently 10684 puzzles with 21 clues in the potential hardest data base.
21 clues puzzles have been deeply investigated, so I was not expecting a good yield.

I processed all patterns with some corresponding hard puzzles with JExocets.

I got 1718 fresh seeds (skfr 10.0 and more), among them 108 puzzles directly eligible to the data base of potential hardest.

This is much more than expected on my side.

The highest fresh rating is only ER 11.3. This would confirm the feeling that most of the highest ratings have been found in explored patterns.

I'll run a classical +-3 in +-1 out generation to see if more puzzles are coming.

In parallel, I start the same task in the 22 clues area.

Another search way would be to generate new patterns out of existing ones and to try to create hard puzzles in that way.

by **dobrichev** » Sat Nov 09, 2013 12:17 pm

Hi Champagne,

It seems worth to look around the JE "cores". I am still not sure if the JE presence would give more cheaper results than investigating vicinity of any kind of "core" with high difficulty rating.

champagne wrote:...21 clues puzzles have been deeply investigated, so I was not expecting a good yield.

To my knowledge there is plenty of 10+/1.2/1.2 puzzles, including in 21 area, which are not investigated up to closure at {-1+1} vicinity. The same is true even for 10.6+/x/x. It is fact that they rarely give 11+ rating. I wouldn't boldly claim this area is deeply investigated.

For the 11.5+ area this is not the case. I personally scanned the entire -+1 vicinity maybe with few exceptions like the 11.8 puzzle identified by coloin.

by **champagne** » Sat Nov 09, 2013 1:17 pm

Hi Mladen,

dobrichev wrote:To my knowledge there is plenty of 10+/1.2/1.2 puzzles, including in 21 area, which are not investigated up to closure at {-1+1} vicinity. The same is true even for 10.6+/x/x. It is fact that they rarely give 11+ rating. I wouldn't boldly claim this area is deeply investigated.

may be the easiest point.
I agree that any statement in that field can appear false later, but several remarks

I have in cache more than 90 000 seeds rating 10.0 and more with 21 clues. Many 1+/1.2/1.2 puzzles are included in it
All these seeds have been expanded in" +-3in" and "+-1out" vicinity mode.

As far as I know, but coloin knows more, years ago, players investigated what appeared at that time as "promising pattern" in full scan mode

And from my experience in the pattern game, I would agree that you have better chances to catch a high rating in the vicinity of say a 9.x/9.x/9.x (may be x>5) than in the vicinity of a 10+/1.2/1.2

dobrichev wrote:Hi Champagne,

It seems worth to look around the JE "cores". I am still not sure if the JE presence would give more cheaper results than investigating vicinity of any kind of "core" with high difficulty rating.

Surely right, but the JE has been seen in so many "potential hardest" that it is a good start.

I am testing the pattern of the game 215 as an alternative. The properties of high ratings are not so evident.

The strong point in my view is that working on a JE core, you can still try a scan with a guided scan of depth 15 to 19.

In blind mode, a vicinity depth of 5 to 6 is already a very high limit.

I have another comparison. to start in the 26 clues area, I use a (change 2 in add 1) process. it is very very slow, and I am thinking of a switch to a JE family pattern guided expansion. I have first to check whether this remains feasible when the number of clues grows. I am currently testing the 22 cleus area;

by **David P Bird** » Sun Nov 10, 2013 11:14 am

Hi Champagne.

Champagne wrote:This is quite new as concept if I catch your point. None of us has studied so far spoiler digits in the base.
I have difficulties to imagine what can come out of that
Could you explain a little more what you have in mind.

To elaborate on the analysis of a spoiler cell in the partial fish (or 'S' cells) that we discussed: When a Double JE pattern was spoilt because one extra 'S' cell existed, the JE pattern would have to be true when that cell held a non-base digit. We then used un-branched chains to see what eliminations would be true whether the cell held a base digit or not. In some cases we could show the spoiler cell couldn't hold a base digit so the Double JE had to be true, and in others we found some common eliminations that could be made whether it that could be proved or not.

A more powerful computer-based method was to investigate different cases assuming the possible base digits were true in each of the sets of base cells.

(Unfortunately, in the puzzles you listed a Double JE was true in every one of them which limited the findings.)

This made me think of cases where the base cells contained an extra spoiler digit that either occurred in a companion cell as well or didn't satisfy the 'S' cell requirements. The Double JE would be proved true if the spoiler could be eliminated from the base cells, but even if this couldn't be shown for sure, there may still be some JE eliminations that could be made.

Of course, the problem with these investigations is that the further we take them, the less frequently these special case will occur. I therefore wouldn't put them very high on a to-do list.

(I have a sick computer at the moment as I lost my C: hard drive just after my last post so I'm in the middle of repairing the damage which will take me some time.)

David

by **champagne** » Mon Nov 11, 2013 7:57 am

David P Bird wrote:This made me think of cases where the base cells contained an extra spoiler digit that either occurred in a companion cell as well or didn't satisfy the 'S' cell requirements. The Double JE would be proved true if the spoiler could be eliminated from the base cells, but even if this couldn't be shown for sure, there may still be some JE eliminations that could be made.

Of course, the problem with these investigations is that the further we take them, the less frequently these special case will occur. I therefore wouldn't put them very high on a to-do list.

(I have a sick computer at the moment as I lost my C: hard drive just after my last post so I'm in the middle of repairing the damage which will take me some time.)

David

Hi David,

I hope your computer is back sane.

The closest existing process that seems to fit with your definition is the case of a double potential JE failing to meet the requirements for one digit. This is something I can easily extract. I have no code to process conjugated bases with different digits or more than 4 digits.

by **champagne** » Fri Nov 15, 2013 11:00 am

Some preliminary results in the 22 clues area

I processed about 1/4 of the 22 clues patterns having a potential for JE's (in fact existing JE's in the data base)

The current file of potential hardest has 73992 puzzles with 22 clues.

I found in total 14800 puzzles including 3461 new entries.
The highest new rating is 11.7/1.2/1.2
I got 45876 new seeds to process as usual.

The runtime with 22 clues is still acceptable, but more filter should be applied to work with more clues.

In parallel, I made a test using a tailor made code on the pattern of the game 215.
here, the runtime is just too long. this would not work in a game.
It could be that I did not find the right filter to focus on the area of value.
I am testing the seeds I got so far to see what comes out of it compared to blue's findings.

by **dukuso2** » Sat Nov 30, 2013 12:14 pm

has anyone tried larger sudokus ? or similar puzzles or just exact-cover problems
or SAT-instances

how the SK-loop or exocet or whatever can be found in them
how to use similar technics to search neighborhoods for
other hard instances

it might be a well-known phenomenon
and restricting to 9x9-sudokus may loose
the general picture of the problem and its properties
and variations

creating hard SAT-instances should be a well-known problem

by **dobrichev** » Sat Nov 30, 2013 8:11 pm

It would be interesting how the puzzles relaxed from "givens" to "pencilmarks" would behave in the nested chain complexity. It should be possible from a rating s/w to drop all techniques based on "givens" and make a try.

by **David P Bird** » Mon Dec 02, 2013 7:37 am

dobrichev wrote:It would be interesting how the puzzles relaxed from "givens" to "pencilmarks" would behave in the nested chain complexity. It should be possible from a rating s/w to drop all techniques based on "givens" and make a try.

Mentally toying with this concept:

Each given distinguishes the digit provided from each of the others in eight 2-digit unavoidable sets, yet many of those UAs are satisfied by other givens and much of the information is redundant. Typically the only purpose of some givens is to resolve a 4-cell UA (UR to the solver) which could be achieved by removing a single pencil mark from one of the cells.

To compose a puzzle using pencil marked cells, one line of approach therefore would be to list all the two digit UAs, and ensure that a false digit is removed in one cell for each of them, and then to repeat this for the remaining UAs with progressively more digits. This possibly could then reduce the redundancy in the clue set to a minimum and force a single solving path at the start.

The difficulty of these puzzles would then be governed by the complexity of the logic needed to make the first few eliminations and by the length of any forced solving path. Presumably this would be reflected in how long it takes a computer program to solve the puzzle. That then would seem to set the challenge between different puzzle composers and different solvers.

DPB

by **champagne** » Mon Dec 16, 2013 10:07 am

champagne wrote:Some preliminary results in the 22 clues area

I processed about 1/4 of the 22 clues patterns having a potential for JE's (in fact existing JE's in the data base)
The current file of potential hardest has 73992 puzzles with 22 clues.

I found in total 14800 puzzles including 3461 new entries.
The highest new rating is 11.7/1.2/1.2
I got 45876 new seeds to process as usual.

The runtime with 22 clues is still acceptable, but more filter should be applied to work with more clues.

I finished that first attempt to find new sees using exotic pattern properties in the 22 clues area and I started the 23 clues search with a more restrictive filter;

In the 22 clues area I got 236K new seed (skfr 10 and +).
The direct search gave 4295 new puzzles for the potential hardest file, and I am currently looking for the standard generation out of these new seeds.

I could have a good feeling this year of the global effect, but the first results are not bad. However, new ratings are not passing easily serate 11.5.

In the 23 clues area, the volume of new seeds seems high, but as the process is very long, I need more time to come to prliminary conclusions.

The next step will be to work on new patterns, but this will be for the next year.

The New Sudoku Players' Forum

scan for potential hardest using exotic patterns properties

scan for potential hardest using exotic patterns properties

Re: scan for potential hardest using exotic patterns propert

Re: scan for potential hardest using exotic patterns propert

Re: scan for potential hardest using exotic patterns propert

Re: scan for potential hardest using exotic patterns propert

Re: scan for potential hardest using exotic patterns propert

Re: scan for potential hardest using exotic patterns propert

Re: scan for potential hardest using exotic patterns propert

Re: scan for potential hardest using exotic patterns propert

Re: scan for potential hardest using exotic patterns propert

Re: scan for potential hardest using exotic patterns propert

Re: scan for potential hardest using exotic patterns propert

Re: scan for potential hardest using exotic patterns propert

Re: scan for potential hardest using exotic patterns propert