The New Sudoku Players' Forum

[blue]

If it could be shown that not-necessarily-minimal instances of the "pattern", could be verified in polynomial time in the puzzle size, it would follow that (P = NP).
If it could be shown that minimal instances of the "pattern" ("his patterns"), could be verified in polynomial time in the puzzle size, it would follow that (Co-NP = NP).

Yes, but... would you engage in such an adventure?

I would not. A minimal instance is very much like a "minimal unsatisfiable core" for an unsatisfiable SAT problem, and there's no low hanging fruit on that tree.

BTW, the conjecture is not P = NP, but P <> NP. From a formal POV, it may seem to be the same thing. But, in practice, a vast majority of people dealing with it believe that NP <> P. [OK, maths isn't a matter of polling].

Right, the prevailing view is that (P = NP) is false.

As for proving P<>NP, it's a lifetime job and I'll keep it for some future life if any - but not the next, nor even the second next; there are so many other things I'd like to do before! Indeed, if I had to work on this, what'd I'd probably try to prove is not P<>NP, but that it is undecidable.

I'll admit to spending a few days each year, thinking about what it would take to prove it false, and what "dead ends" in such attempts, might imply about it's decidability.

If I had to make a correct guess to save my life, I would hope that "it's either false or undecidable" is an available option.
I'ld be quite distressed, if I had to choose between false and undecidable.
With eternal bliss and instant death as the possible outcomes, I still wouldn't jump at a chance to choose between "true" and "false or undecidable".

Regards,
Blue.

[denis_berthier]

With eternal bliss and instant death as the possible outcomes, I still wouldn't jump at a chance to choose between "true" and "false or undecidable".

But what's the outcome of not choosing?

[blue]

But what's the outcome of not choosing?

Excellent question ! A concert in the park ?
Not a requirement to choose another question and guess it's answer.

Cheers,
Blue.

[StrmCkr]

im a bit late to the game on these but might as well chime in with my 2cents

Code: Select all

Partial Fish Sets

Code: Select all
      *-------*-------*-------*
      | . . . | . . . | . . . |
      | . . . | . . . | . . . |
      | . . . | . . . | . . . |
      *-------*-------*-------*
      | . . 6 | 6 . . | / . . |
      | . . / | / . . | / . . |
      | . . / | / . . | / . . |
      *-------*-------*-------*
      | . . 6 | 6 . . | 6 . . |
      | . . / | / . . | / . . |
      | . . / | / . . | / . . |
      *-------*-------*-------*

linking partial fish to information out side the pattern can lead to exclusions based on digits requiring to complete the fish pattern or be contained with in the linked cells, chains or function.

strong-links-within-fish-patterns-t30392.html {my brief idea on it some might call it a kraken fish, but i think its the foundation blocks for these advanced monster's}

even more advanced variations could link multiple partial fish patterns for same/different digits to a chain/function/pattern: containing both digits whereby either the fish's to be completed or the digit to be with in the chain/function/pattern.

which is how i view these flying fishes and junior fishes and some /most rank "0" logic sets.

[denis_berthier]

In order to eliminate remaining ambiguities, I've slightly modified the definition here: http://forum.enjoysudoku.com/jexocet-pattern-defintion-t31133-12.html.
I've also added a few words (inside parenthesis) in the proof.

[David P Bird]

StrmCkr, Thanks for your response.

I've studied your earlier thread and conclude that your topic is similar but different to partial fish. Your examples use one fish digit at a time. My aim however was to set the rules for examining several fish for different digits together as in JExocet. To do this they must all share the same set of base rows or columns.

By the way, I found that in your X wing examples grids, you need to exclude the fish digit from several extra cells for the eliminations to be sound. [Edit - Sorry, on re-visiting it, I find I was mistaken about that]

David

[denis_berthier]

Hi David,

As you've spent some time on JExocet, you may be able to answer the question I raised in the other thread:

what's the easiest (smallest SER) known puzzle with a JExocet? (or do you have a short list of "easy" or "moderate" ones?)

[champagne]

I made a quick test on a sample file of puzzles coming out of the pattern games 1_127 to see what happens in low ratings.

The lowest SER I got with a positive response, having first solved the singles, was a SER 1.7. This was a severely down graded form of JEXOCET, having no interest

Here is a list of puzzles in the range 7.7 to 9.6 (SER) with a more classical JEXOCET form. I checked the first (rating 7.7), it is a basic JEXOCET.
One appears with a double exocet (I did not check the PM)

The sample is highly biased (pattern game ...) but the ratio of puzzles having a JEXOCET is relatively low in that lot of a little more than 10 000 puzzles, far from the 80% seen for "potential hardest" puzzles

Code: Select all

5..........46..9...8..4..1..2.9.6.....6.7.3.....3...2..1..2..5...9..37..........8; ;1;1;r4c5 r6c5 r2c6 r8c4 158
1..........23..1...4..5..6..6.7.5.....8.6.9.....4...5..8..4..9...1..23..........7; ;1;0;r5c4 r5c6 r6c2 r4c8 123
4..........57..6...1..5..2..8.6.9.....3.7.9.....3...4..2..8..1...7..35..........2; ;1;0;r4c5 r6c5 r2c6 r8c4 124
4..........97..6...1..5..2..8.9.6.....3.7.9.....3...4..2..8..1...7..38..........5; ;1;0;r4c5 r6c5 r2c6 r8c4 124
8..........72..3...1..4..5..2.6.9.....3.7.6.....3...1..5..2..8...6..79..........4; ;1;0;r4c5 r6c5 r2c6 r8c4 158
..1.....2.3...4.5.6...7.8.......9....7..5..3....3.......2.4...1.4.5...9.8.....6..; ;1;5;r4c5 r6c5 r2c4 r8c6 1268
...1.2.....1.3.4...5.6....2..7....89....7....34....7..7....1.6...4.9.8.....5.8...;D;2;44;r4c1 r4c2 r6c5 r5c7 1256;r6c8 r6c9 r5c3 r4c5 1256
1..........23..4...5..6..7..6.1.4.....8.3.1.....8...9..9..2..5...3..82..........7; ;1;0;r4c5 r6c5 r2c6 r8c4 579
9..........47..3...1..2..5..8.9.6.....3.7.6.....3...1..2..4..8...6..74..........5; ;1;0;r4c5 r6c5 r2c6 r8c4 158
..1.....2.3...4.5.6...7.8.......3....7..5..9....9.......2.4...1.4.5...3.8.....6..; ;1;5;r4c5 r6c5 r2c4 r8c6 1268
..4.....7.9...8.1.6...1.2.......3....5..8..9....5.......2.9...4.8.3...5.7.....6..; ;1;5;r4c5 r6c5 r2c4 r8c6 2467

[denis_berthier]

Champagne, thanks for this list.

I guess the 4 cells and the series of 3 or 4 digits represent respectively:
the 2 base cells
the 2 target cells (from which the companion cells can easily be deduced)
the 3/4 base digits

Don't you also need to specify the 3 S columns (or at least the 2 of them not cutting the base block) in order to fully define the pattern?

What are the two digits (0 to 5) appearing after the space or the D?

[champagne]

I guess the 4 cells and the series of 3 or 4 digits represent respectively:
the 2 base cells
the 2 target cells (from which the companion cells can easily be deduced)
the 3/4 base digits

right
Note: in case of twin JEXOCETS, you have more cells in the target

Don't you also need to specify the 3 S columns (or at least the 2 of them not cutting the base block) in order to fully define the pattern?

"subject to a possible bug in the program", these are supposed to be a JEXOCET pattern. If I got your point the cross lines are then perfectly defined.

What are the two digits (0 to 5) appearing after the space or the D?

The first digit is the number of JEXOCETS seen
The second one qualify for my process the exocet(s) properties. (3/4 digits, twin/not twin, abi loop potential or not)

[David P Bird]

Hi David,
As you've spent some time on JExocet, you may be able to answer the question I raised in the other thread:

what's the easiest (smallest SER) known puzzle with a JExocet? (or do you have a short list of "easy" or "moderate" ones?)

I'm afraid not. I've voiced my suspicions before that because Champagne has only been sampling the hardest puzzles, his frequencies are higher than would be expected from the general population.

If anyone feels inclined to check this using a fast batch solver approach, I'd be a lot more interested in determining the frequency of the rank-0 partial fish inference pattern which is a necessary component of JExocet. I'd like to see if there are any other inference patterns it can be combined with.

I'll make this observation too: Part of my solving approach is to determine which digits don't appear as givens in each stack and tier. Amongst other things this helps identify potential JE base digit sets as there must be 3 or 4 absent digits in a JE band. It's a convenient once-only check.

[denis_berthier]

Don't you also need to specify the 3 S columns (or at least the 2 of them not cutting the base block) in order to fully define the pattern?

"subject to a possible bug in the program", these are supposed to be a JEXOCET pattern. If I got your point the cross lines are then perfectly defined

I'm not questioning your program or the fact that there are indeed JExocets in the puzzles, with the base cells, target cells and base digits specified after the puzzle.
What I mean is that 2 of the S columns (and BTW also the 2 cross lines for each of the base digits) are not specified in your output. But that's OK. The given data are enough to deduce the eliminated candidates.

[denis_berthier]

Hi David,
As you've spent some time on JExocet, you may be able to answer the question I raised in the other thread:

what's the easiest (smallest SER) known puzzle with a JExocet? (or do you have a short list of "easy" or "moderate" ones?)

I'm afraid not. I've voiced my suspicions before that because Champagne has only been sampling the hardest puzzles, his frequencies are higher than would be expected from the general population.

The sample is highly biased (pattern game ...) but the ratio of puzzles having a JEXOCET is relatively low in that lot of a little more than 10 000 puzzles, far from the 80% seen for "potential hardest" puzzles

Speaking of frequencies, is there an estimate of the ratio JExocet/Exocet (in the "potential hardest" list if there's nothing less biased)?

[logel]

Hi David
Yet another discussion rule vs pattern.

Inventing/finding new rules seem to be an endless story without any prospect to be completed.

If I summarize the discussion correctly, the JExocet fit to a precise rule definition now.

The JE+ looks like some hybrid, neither rule nor pattern. I would say its a pattern where some parts are determined by rules and some are not. So its some kind of rule fragment. This is an interesting idea and can maybe applied to other scenarios too. But without saying for what purpose it is intended, it will provoke controversy.

a) If you intend to include JE+ in the standard tool box of rules, all sub-rules for the variants have to be worked out the same way as for JE. Otherwise you cannot determine their solving strength. On top of that confusing discussions arise about what is real JE+ or only JE+ alike.

b) If you instead intend to use JE+ in a pragmatic way to find some more eliminations you can't get otherwise, its completely OK. In this case I would rather start with assuming the potential targets TRUE and perform a limited number of local eliminations. If you find a contradiction there is a hit. Theoretical arguments about complexity are missing the point in this case.

I always like clear goals.

[David P Bird]

Hi Logel

If you have followed the exchanges between Denis and I you will appreciate that I consider that there are two roles for patterns 1) to provide instant eliminations and 2) to provide inferences that can be assembled together Lego fashion into a more complex elimination patterns. JExocet falls into both those categories because once the basic eliminations have been made, it can be re-used later to show that the two target cells must hold different digits.

So regarding which option do I choose out of your two alternatives, the answer is both!

I have tried but failed to produce a precise definition of a Sudoku pattern. At every attempt, wherever I tried to draw a boundary line, I found I was either excluding acceptable patterns or including unacceptable ones. Consequently now I just resort to the spirit of the intention.

However you and I have different goals, for you it's an efficient computer solver and for me it's logical constructs that can be applied by someone with sufficient patience to look for them in favour of guessing or using brute force. What defeats me on practical grounds, may be possible for you given a large amount of memory to hold a catalogue of pre-analysed patterns.

Note I use the term 'guessing' where you have used the phrase "assuming the potential targets true and performing a limited number of eliminations". Trial and Error, like assuming a unique solution, is something that you're either prepared to employ or not. For me it's equivalent to cheating at patience. But it's a wide church and there's room for both of us.