exocet pattern in hardest puzzles

Advanced methods and approaches for solving Sudoku puzzles

Re: bi bi pattern in hardest puzzles

Postby ronk » Fri May 18, 2012 6:24 pm

daj95376 wrote:Here is the puzzle with sequence number 226 in file "02 index.txt".
Code: Select all
98.7..6..5..9..7......84...6..5..9......7..3.....2...61......97.65...1.....1.....;226

Here is the puzzle with sequence number 226 in file "03 E Exocet seen.txt".
Code: Select all
1......8...71....6.9.....5...56....7..17.4..5......34.57.2.............2..2.61...;226
;elev;91;3;4;r7c5 r7c6 r8c1 r8c3;r7c5 r7c6 r8c3 r9c9;r9c1 r9c2 r7c9 r8c4;;;

Unfortunately, not all puzzles in the 03E-file are in row MinLex format.

While normalizing all puzzles in both files to row MinLex format, I lost access to the sequence numbers and Exocet information. From now on, I'll only be presenting bare puzzles in row MinLex format. :(

IMO publishing puzzles in row-minlex format is not a good idea. It's a bit like posting puzzles with the first 10 cells already solved.

Until proven otherwise, I think we should assume that champagne's use of row minlex in one of his files, but not in another, is a bookkeeping error which he will correct in his next publication of the Hard11.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: bi bi pattern in hardest puzzles

Postby champagne » Sat May 19, 2012 8:35 am

daj95376 wrote:FWIW: Anomalies

There is an inconsistency in the puzzles across Champagne's files in folder Hard_11.

Here is the puzzle with sequence number 226 in file "02 index.txt".

Code: Select all
98.7..6..5..9..7......84...6..5..9......7..3.....2...61......97.65...1.....1.....;226

Here is the puzzle with sequence number 226 in file "03 E Exocet seen.txt".

Code: Select all
1......8...71....6.9.....5...56....7..17.4..5......34.57.2.............2..2.61...;226
;elev;91;3;4;r7c5 r7c6 r8c1 r8c3;r7c5 r7c6 r8c3 r9c9;r9c1 r9c2 r7c9 r8c4;;;

Unfortunately, not all puzzles in the 03E-file are in row MinLex format.

Normally, it wouldn't matter if the two files matched ... provided ... all of the Exocet puzzles in the 02-file were present in the 03E-file. However, there are 7,393 more puzzles in the 02-file than the 03E-file ... and ... there are at least 1,273 Exocet puzzles among them.

While normalizing all puzzles in both files to row MinLex format, I lost access to the sequence numbers and Exocet information. From now on, I'll only be presenting bare puzzles in row MinLex format. :(



as explained in the readme file, the "02 Index.." is the max text form and the corresponding internal number
other files contains usually the first known entry for that max text form

so both puzzles are morphs of the same "ED" puzzle.

Regarding the "03 file for exocets", I made a partial update so I have to look more to see exactly what is the situation.

more precise answer to-day

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

Re: bi bi pattern in hardest puzzles

Postby David P Bird » Sat May 19, 2012 9:19 am

To elaborate the point I was trying to make earlier: For those one-band Exocets that champagne has found that don't satisfy the JExocet pattern criteria, some will turn out to be very simple Almost JExocets that can be established with very short chains, others may involve more elaborate chains embedding such things as Almost Deadly Patterns, which could still be found by manual methods, and finally there will be those that can only be proved using net-based methods/templating, which would be above my ceiling.

Reviewing the defining post and taking the various points on board, will this re-work pass muster?

- o - o - o -

The different cell pairs occur in different boxes in the same band (the JExcoet band). The three cross-lines intercept this band as shown, passing through the target cell pairs but not the base cell pair.

Conditions:
1) The base cells must be restricted to a set of three or four digits (the base candidates)
2) Target pairs must have one cell that contains at least one base candidate (the target cell) and the other that contains none of them (the empty companion cell)
3) Outside the JExocet band no base digit should be capable of simultaneously occupying more than two of the cross-line cells .
This is satisfied when the all occurrences of a digit in these external cells, including any that are given or solved, can be covered by no more than two lines.

The pattern is described by identifying by candidates in the base cells and the location of the two target cells
eg (abcd)JExocet:r1c12,r2c4,r3c7

- o - o - o -

PS champagne It's good to know you're still with us!
David P Bird
2010 Supporter
 
Posts: 960
Joined: 16 September 2008
Location: Middle England

Re: bi bi pattern in hardest puzzles

Postby champagne » Sat May 19, 2012 9:58 am

David P Bird wrote:
PS champagne It's good to know you're still with us!


I have been locked 2 weeks on other tasks, and what I read does not seem to require my contribution.

It's good to see others discussing freely on specific puzzles around the exocet and rank0 logic issues and I had no time to get out of general cases.

My next duty is to continue to work on the resume thread unless I see some adjustments to do in the existing code.

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

Re: bi bi pattern in hardest puzzles

Postby ronk » Sat May 19, 2012 12:00 pm

champagne wrote:as explained in the readme file, the "02 Index.." is the max text form and the corresponding internal number
other files contains usually the first known entry for that max text form

OK, so if an author publishes in row minlex (canonicalized) form, that's the puzzle we're given and should probably stay with.

However, what is the "max text form?". Is it the result of yet another canonicalization** method? If so, 1) where is this method defined, and 2) is there a publicly available program that performs this method?

** To clarify, a canonicalization method applied to equvalent, i.e., not essentially-different, puzzles will yield identical results.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: bi bi pattern in hardest puzzles

Postby champagne » Sat May 19, 2012 12:22 pm

ronk wrote:OK, so if an author publishes in row minlex (canonicalized) form, that's the puzzle we're given and should probably stay with.
** To clarify, a canonicalization method applied to equvalent, i.e., not essentially-different, puzzles will yield identical results.


yes the published puzzle has the priority (unless I made a mistake picking it up when several morphs have been published)


ronk wrote:
However, what is the "max text form?". Is it the result of yet another canonicalization** method? If so, 1) where is this method defined, and 2) is there a publicly available program that performs this method?

** To clarify, a canonicalization method applied to equvalent, i.e., not essentially-different, puzzles will yield identical results.


I already explained why I am using the maxtext form.

In fact, I wanted to have only one canonical form in my programs and, working sometimes on partial puzzles (generation step by step), I found more efficient to use the maxtext.
The corresponding process is part of my multi purpose program.

So far, that program is not public. I intend to load it in the same form as skfr, but up to now, nobody showed interest to go in that direction.

champagne

PS: I recently changed the process to use the more efficient one published in that forum, looking first for the "best pair of rows/columns"
champagne
2017 Supporter
 
Posts: 5680
Joined: 02 August 2007
Location: France Brittany

Re: bi bi pattern in hardest puzzles

Postby ronk » Sat May 19, 2012 1:20 pm

champagne wrote:
ronk wrote:However, what is the "max text form?". Is it the result of yet another canonicalization** method? If so, 1) where is this method defined, and 2) is there a publicly available program that performs this method?
I already explained why I am using the maxtext form. In fact, I wanted to have only one canonical form in my programs and, working sometimes on partial puzzles (generation step by step)
...
So far, that program is not public. I intend to load it in the same form as skfr, but up to now, nobody showed interest to go in that direction.

Perhaps "nobody showed interest to go in that direction" because nobody knows "what" it is, which is my question rather than "why."

BTW isn't an algorithm that can canonicalize partial puzzles ("sub-puzzles") slower than one that can canonicalize only puzzles with a unique solution? [edit: I tried this with gsf's program. Canonicalization using "-f%#.c" and "f%#mc" run at virtually the identical rate - 280 puzzles/GHz/sec using your "03 E exocet seen.txt" file.]
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: bi bi pattern in hardest puzzles

Postby champagne » Sat May 19, 2012 3:13 pm

ronk wrote:
champagne wrote:
ronk wrote:However, what is the "max text form?". Is it the result of yet another canonicalization** method? If so, 1) where is this method defined, and 2) is there a publicly available program that performs this method?
I already explained why I am using the maxtext form. In fact, I wanted to have only one canonical form in my programs and, working sometimes on partial puzzles (generation step by step)
...
So far, that program is not public. I intend to load it in the same form as skfr, but up to now, nobody showed interest to go in that direction.

Perhaps "nobody showed interest to go in that direction" because nobody knows "what" it is, which is my question rather than "why."

BTW isn't an algorithm that can canonicalize partial puzzles ("sub-puzzles") slower than one that can canonicalize only puzzles with a unique solution? [edit: I tried this with gsf's program. Canonicalization using "-f%#.c" and "f%#mc" run at virtually the identical rate - 280 puzzles/GHz/sec using your "03 E exocet seen.txt" file.]



1) I run the same test on my 2.4 GHz labtop
24411 puzzles 0.973 second
it seems that we are not in the same order of magnitude.

2) The process is more or less the following

a) build the table of "maxrow" equivalences in pattern mode (including band/stack permutations)

b) build the table of max "bande/stack" partial value
just keeping the max lex 27

c) then build the table of "max 2 bands"
just keeping the max lex 54

d) finally process the third band

for the symmetry processing, equivalent max text results are kept

I don't see in that process a possible influence of the number of solutions (if any) of the puzzle.
The worst case is likely a fully diagonal 27 clues puzzle

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

Re: bi bi pattern in hardest puzzles

Postby champagne » Sat May 19, 2012 3:50 pm

daj95376 wrote:FWIW: Anomalies


Normally, it wouldn't matter if the two files matched ... provided ... all of the Exocet puzzles in the 02-file were present in the 03E-file. However, there are 7,393 more puzzles in the 02-file than the 03E-file ... and ... there are at least 1,273 Exocet puzzles among them.



I rechecked the position.

The "03 file " has been reworked using only "band" search, as said in the attached text files, but I had formerly only one exocet not located in a band and it is included in the "03... file".

So I guess that the trouble comes from your assumption that the puzzle in the "02" file and in the "03" file should be the same morph.
As explained, "02"... contains the canonical maxtext form.

If this is not correct, can you give one example

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

Re: bi bi pattern in hardest puzzles

Postby daj95376 » Sat May 19, 2012 5:18 pm

Welcome back Champagne.

[Withdrawn: difference in results explained below.]
Last edited by daj95376 on Sat May 19, 2012 10:12 pm, edited 1 time in total.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Re: bi bi pattern in hardest puzzles

Postby ronk » Sat May 19, 2012 6:27 pm

champagne wrote:
ronk wrote:BTW isn't an algorithm that can canonicalize partial puzzles ("sub-puzzles") slower than one that can canonicalize only puzzles with a unique solution? [edit: I tried this with gsf's program. Canonicalization using "-f%#.c" and "f%#mc" run at virtually the identical rate - 280 puzzles/GHz/sec using your "03 E exocet seen.txt" file.]
1) I run the same test on my 2.4 GHz labtop
24411 puzzles 0.973 second
it seems that we are not in the same order of magnitude.

That's impressive. I may be using gsf's program in an inefficient manner. I'll ask him via PM.

champagne wrote:2) The process is more or less the following

a) build the table of "maxrow" equivalences in pattern mode (including band/stack permutations)
...

Thanks for the "more or less" but, while I know what 'tables' are and can probably accurately guess what 'pattern mode' means, I'm immediately lost with ""maxrow" equivalences" in the first step. Is there not a definition or an extended discussion of this "maxtext" canonicalization method somewhere on the internet already? With a different name perhaps?

daj95376 wrote:
Code: Select all
*) 31,804 puzzles in maxtest form  in "02 index.txt".
*) 24,411 puzzles in various forms in "03 E Exocet seen.txt".
...
...
Results: 1,273 Exocet puzzles.

The difference is likely due to champagne having processed only the first 30,000 of the 31,804 puzzles. Don't know to which 31,804-sized file this applies though. Moreover, he might have said puzzles with indices 1 thru 30,000 rather than the first 30,000 puzzles of a file.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: bi bi pattern in hardest puzzles

Postby daj95376 » Sat May 19, 2012 6:59 pm

ronk wrote:
daj95376 wrote:
Code: Select all
*) 31,804 puzzles in maxtest form  in "02 index.txt".
*) 24,411 puzzles in various forms in "03 E Exocet seen.txt".
...
...
Results: 1,273 Exocet puzzles.

The difference is likely due to champagne having processed only the first 30,000 of the 31,804 puzzles. Don't know to which 31,804-sized file this applies though. Moreover, he might have said puzzles with indices 1 thru 30,000 rather than the first 30,000 puzzles of a file.

Yes, I noticed that the sequence indicies in the "03 E ..." file stopped at 29,999; but I didn't act upon it until reading your message. Yes, I found 1,273 Exocet puzzles in the remaining puzzles. Anomaly resolved. Thanks!
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Re: bi bi pattern in hardest puzzles

Postby champagne » Sat May 19, 2012 9:14 pm

ronk wrote:That's impressive. I may be using gsf's program in an inefficient manner. I'll ask him via PM.


I am not so sure this comes from a bad use of gsf's program.

I had similar results with the prior version. Dobrichev pushed me to revise my code. Gridchecked was much better, (but in "pattern" mode)
I used fresh ideas coming from a thread claiming canonicalisation trough pairs of rows was much faster, but I lost the thread link
And the new code uses all optimised tools prepared in skfr

ronk wrote:
Thanks for the "more or less" but, while I know what 'tables' are and can probably accurately guess what 'pattern mode' means,
I'm immediately lost with ""maxrow" equivalences" in the first step. Is there not a definition or an extended discussion of this "maxtext" canonicalization method somewhere on the internet already? With a different name perhaps?



There is nearly no difference between the minlex and the maxtext process, except for the comparison to find the "text lower" / "text higher" morph.

AFAIK the maxtext option has not been discussed.

IMO, for random puzzles, both forms should be generated nearly with the same cpu consumption at equal process.

but

the minlex process does not like empty rows or columns,
the maxtext process does not like rows or columns with the maximum number of clues having an identical pattern.

so with a tailor made sample, you can get different results.

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

Re: bi bi pattern in hardest puzzles

Postby ronk » Sat May 19, 2012 10:54 pm

champagne, I just realized you've jumped from the "why" to the "how" of maxtext, skipping my "what is it?" question yet again. :( I was looking for a definition of a sudoku puzzle or sub-puzzle canonicalized via maxtext.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: bi bi pattern in hardest puzzles

Postby champagne » Sun May 20, 2012 4:17 am

ronk wrote:champagne, I just realized you've jumped from the "why" to the "how" of maxtext, skipping my "what is it?" question yet again. :( I was looking for a definition of a sudoku puzzle or sub-puzzle canonicalized via maxtext.


I was not waiting for a problem at that point;

As my english is not very good, I tried to find the minlex definition in sudopedia, but i failed, so let me try to word it simply

Just consider all morphs of a puzzle re labelled from the left to the right (81 bytes row 1 to row 9 unknown cell '0' or '.' )

. using in priority the digits in order 123456789 on one side
. using in priority the digit 987654321 on another side.

you have the minlex canonical form in the first case taking the morph(s) with the smallest value using the classical comparison order of the 81 bytes field (.123456789 or 0123456789)

you have the maxtext canonical form in the second case taking the morph(s) with the highest value using the same comparison order


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

PreviousNext

Return to Advanced solving techniques