The New Sudoku Players' Forum

by **1to9only** » Fri Jun 04, 2021 5:54 pm

denis_berthier wrote:I think the best way is to consider there are two systems of coordinates: (r, c) and (d, a) (or other letters).

Simple is best: (r/c) and (r\c) would be good enough for me. :idea:

Website · by **denis_berthier** » Fri Jun 04, 2021 6:32 pm

1to9only wrote:
denis_berthier wrote:I think the best way is to consider there are two systems of coordinates: (r, c) and (d, a) (or other letters).

Simple is best: (r/c) and (r\c) would be good enough for me.

You're missing my point. We need to be able to refer to precise diagonals and anti-diagonals, in the same way as we need to be able to refer to precise blocks in Sudoku (and to precise places in a block).
Diagonals and anti-diagonals must be numbered. The simplest way to do this is to consider them as a second system of coordinates.
As it seems there's no standard for this, we're trying to define one.

If by (r/c), you mean the anti-diagonal passing through (r, c), this is neither simple nor unique for the diagonal.

by **creint** » Fri Jun 04, 2021 8:55 pm

Previous discussion:
http://forum.enjoysudoku.com/sudoku-coordinate-systems-t38136.html

Just giving cell locations is fine for most cases because you can manually find the constraint that can be used.
But for your solving system everything must be named.
I am against introducing new names, because it makes reading harder when you don't know the meaning.
You are probably not planning to define those names in your solve result.
Name and cell index could be used but then there must be a definition on how to interpret the cell index. Left cell first or top cell first.

Website · by **denis_berthier** » Sat Jun 05, 2021 3:13 am

creint wrote:Previous discussion:
http://forum.enjoysudoku.com/sudoku-coordinate-systems-t38136.html
Just giving cell locations is fine for most cases because you can manually find the constraint that can be used.
But for your solving system everything must be named.
I am against introducing new names, because it makes reading harder when you don't know the meaning.
You are probably not planning to define those names in your solve result.
Name and cell index could be used but then there must be a definition on how to interpret the cell index. Left cell first or top cell first

Even for the simplest bivalue-chains (basic AICs), you need names for the CSP-variables (in your jargon, the strong links) they rely on. Not having them for diagonals would make them totally eligible.
In my system, print-names can be anything and can easily be changed; they are different from internal representations. I use easy-to-read print-names for clarity.

[Edit] Indeed, even for Hidden Singles, if you want to be precise, you have to name the diagonal for which they are Hidden.

Website · by **denis_berthier** » Sat Jun 05, 2021 4:48 pm

Mathimagics wrote: here is a 29-clue version which you might try:
Code: Select all
.....9...CD.....2.........A.8..5...9..........2......A......1.............3......4........1..........CD.3...9..........D...........6.............A.6..............B..57..

That'll be my first Pandiag puzzle.

Solved in W3.
Diagonals are named d1, d2, d3, ... starting respectively from (r1, c1), (r2, c1), (r3,c1)... and extending to the north-east
Anti-diagonals are named a1, a2, a3, ... starting respectively from (r1, c1), (r1, c2), (r1,c3)... and extending to the south-west

(solve ".....9...CD.....2.........A.8..5...9..........2......A......1.............3......4........1..........CD.3...9..........D...........6.............A.6..............B..57..")

Hidden Text: Show

Code: Select all: Resolution state after Singles: 124567B 124578B 13457B 13678AB 457B 9 234578A 134678A 24678AB C D 123458B 2345678AB 1456789BCD 134579BCD 1345679BC 2 3478 478BC 14678ACD 4789ABC 3568AD 14678AB 13458AB 3678BC 345689BCD A 12347BCD 8 367C 1347BCD 5 47C 16BD 347BC 9 2346B 123467B 267BC 16789BC 13459BD 34567C 135679ABCD 13478ABCD 14678ABCD 13689AD 2 4578ABC 478AB 134568 1456789ABC 34578BD 4567BD A 234569BC 36789BCD 247BCD 2368BD 3456789C 3478B 1 24678BD 24589B 234578C 23456789BCD 245678C 124578BD 12679BC 1689BCD 1258ABD 1467ABC 124578AC 45678ABCD 246789BD 3 12458B 245789ABC 4567AD 25678CD 23789BCD 267B 4 358BC 2378ABC 23567ACD 356789BCD 56789ABCD 278BD 589B 567AB 1 24789B 12478 123569B 135678AB 12378B 23468B 123456789 145679AB 2345789B 14678AB C D 245678AB 3 258B 14567C 1578ABC 9 12678BC 124568CD 14578BCD 24567ABCD 1467ABD 4568 124678AB 478BC 589B 14578BC D 35678AC 1234578BC 124678AB 123789C 1345689BC 345679AB 2467 12345689AB 1346789ABC 246789AB 14789B 6 2457BC 35789BC 124578ACD 123478BCD 1234578AD 1379B 23458C 12478ABD 12349AB 124789ABC 3589ABD 14578BC 23478BD A 1578BCD 6 123478CD 134579D 34578 23789BC 1248BD 12489B 12359B 345789BC 2468CD 13489CD 12469 89C 1248ACD 34A B 134689ACD 23468AD 5 7 134689AC 234AC 995 candidates, 15689 csp-links and 15689 links. Density = 3.17%

whip[1]: d9n13{r4c6 .} ==> r4c4 ≠ 13
whip[1]: c4n13{r12 .} ==> r12c10 ≠ 13
whip[1]: r3n13{c8 .} ==> r6c5 ≠ 13, r13c5 ≠ 13

Code: Select all: Resolution state after Singles and whips[1]: 124567B 124578B 13457B 13678AB 457B 9 234578A 134678A 24678AB C D 123458B 2345678AB 1456789BCD 134579BCD 1345679BC 2 3478 478BC 14678ACD 4789ABC 3568AD 14678AB 13458AB 3678BC 345689BCD A 12347BCD 8 367C 1347BCD 5 47C 16BD 347BC 9 2346B 123467B 267BC 16789BC 13459BD 34567C 135679ABC 13478ABCD 14678ABCD 13689AD 2 4578ABC 478AB 134568 1456789ABC 34578BD 4567BD A 234569BC 36789BCD 247BCD 2368BD 3456789C 3478B 1 24678BD 24589B 234578C 23456789BCD 245678C 124578BD 12679BC 1689BCD 1258AB 1467ABC 124578AC 45678ABCD 246789BD 3 12458B 245789ABC 4567AD 25678CD 23789BCD 267B 4 358BC 2378ABC 23567ACD 356789BCD 56789ABCD 278BD 589B 567AB 1 24789B 12478 123569B 135678AB 12378B 23468B 123456789 145679AB 2345789B 14678AB C D 245678AB 3 258B 14567C 1578ABC 9 12678BC 124568CD 14578BCD 24567ABCD 1467ABD 4568 124678AB 478BC 589B 14578BC D 35678AC 1234578BC 124678AB 123789C 1345689BC 345679AB 2467 12345689AB 1346789ABC 246789AB 14789B 6 2457BC 35789BC 124578ACD 123478BCD 1234578AD 1379B 23458C 12478ABD 12349AB 124789ABC 3589ABD 14578BC 23478BD A 1578BCD 6 123478CD 134579D 34578 23789BC 1248B 12489B 12359B 345789BC 2468CD 13489CD 12469 89C 1248AC 34A B 134689ACD 23468AD 5 7 134689AC 234AC

Hidden Text: Show

by **Mathimagics** » Sat Jun 05, 2021 5:05 pm

Well done, Denis! 8-)

It will be interesting to see how many clues you can remove ...

by **Mathimagics** » Sat Jun 05, 2021 6:55 pm

creint wrote:Given up reducing this 13 given grid after 10500 seconds, only 6 cells left to be checked for minimal. Probably minimal.

I've been busy working on my alternative method, so I hadn't noticed something that should be obvious!

You only needed to test one clue! You have 12 different cell values, and the only one appearing twice is the "9". So you really were the first to find a 13-clue puzzle, congratulations! 8-)

My idea for a quicker minimality test works a treat. Here is the result for your 13-clue puzzle:

Dodgy test results: Show

[ EDIT ]
My results indicate, quite wrongly, that 2 clues were removable! Not so, of course ... the puzzle is in fact minimal, as the corrected version below shows.

This was a fault in my minimality-tester, and has now been fixed.

The Correct test results are:

Code: Select all: Testing clue removals from 13-c puzzle 17:26:42 . clue( 1, 6) = 9: ns = 2 17:26:42 . clue( 1,10) = C: ns = 2 17:26:42 . clue( 2, 4) = 2: ns = 2 17:26:42 . clue( 3, 1) = A: ns = 2 17:26:42 . clue( 3, 3) = 8: ns = 2 17:26:42 . clue( 3, 6) = 5: ns = 2 17:26:42 . clue( 3,10) = 9: ns = 2 17:26:42 . clue( 6,10) = 3: ns = 2 17:26:42 . clue( 7, 4) = 4: ns = 2 17:26:42 . clue( 7,13) = 1: ns = 2 17:26:42 . clue( 8,12) = D: ns = 2 17:26:42 . clue(11, 2) = 6: ns = 2 17:26:42 . clue(13,11) = 7: ns = 2

~~Ergo, either "9" can be removed for a 12-clue puzzle ... assuming the method is valid, of course~~ :oops:

Website · by **denis_berthier** » Sun Jun 06, 2021 4:26 am

Mathimagics wrote:Well done, Denis!

Thanks. It took me a few hours to introduce into LatinRules the additions necessary for the Pandiagonal variant. This gives me full access to the generic rules in CSP-Rules.
However, the Subset Rules remain restricted to the LatinSquares Subset rules, because, as I mentioned before, there are too many possible patterns.

Mathimagics wrote:It will be interesting to see how many clues you can remove ...

I'll try this, in order to find longer whips.

After working on this, I think this variant will never become a popular game, for two reasons:
- the grids it requires are too large: the smallest interesting ones are 13x13, which makes more than 2 times the number of cells in Sudoku;
- the diagonals are visually very unfriendly - unless one wants to play on a tyre or a rubber ring in his swimming pool; seems to be the right time to sell this idea before summer holidays

On the other hand, two reasons I might be wrong are:
- the interplay between rows, columns and diagonals may be interesting;
- there's a potentially infinite variety of exotic fish patterns.

Website · by **denis_berthier** » Sun Jun 06, 2021 5:39 am

Here is a slightly more difficult variant, obtained by deleting first and last candidates. t-whips[3] and whips[3] appear, when only z-chains[3] were needed in the original puzzle.
Still relatively easy - W3 would be easy for Sudoku, but on a larger board, there are many more possible chains and complexity increases faster with the length of chains.

(solve "..........D.....2.........A.8..5...9..........2......A......1.............3......4........1..........CD.3...9..........D...........6.............A.6..............B......")
whip[1]: d9n13{r4c6 .} ==> r4c4 ≠ 13
whip[1]: c4n13{r12 .} ==> r12c10 ≠ 13
whip[1]: r3n13{c8 .} ==> r6c5 ≠ 13, r13c5 ≠ 13

Code: Select all: Resolution state after Singles and whips[1]: 1245679BC 1245789BC 134579BC 136789AB 457B 246789C 2345789AC 134678AC 2456789ABC 125678ABC D 1234578BC 2345678ABC 1456789BCD 134579BCD 1345679BC 2 3478 4789BC 146789ACD 45789ABC 35678ACD 145678ABC 134578AB 35678BC 3456789BCD A 12347BCD 8 367C 1347BCD 5 47C 167BCD 347BC 9 23467B 123467BC 267BC 156789BC 134579BD 345679C 135679ABC 13478ABCD 146789ABCD 136789AD 2 4578ABC 4578ABC 1345678 1456789ABC 34578BCD 4567BD A 2345679BC 36789BCD 2457BCD 236789BCD 3456789C 3478B 1 245678BCD 245789B 234578C 23456789BCD 2456789C 124578BCD 12679BC 156789BCD 12578ABC 14679ABC 124578AC 45678ABCD 246789BD 3 1245789B 245789ABC 4567AD 25678CD 23789BCD 2567BC 4 3578BC 2378ABC 23567ACD 356789BCD 56789ABCD 278BD 5789B 5679AB 1 24789B 124578 1235679B 135678AB 123578B 234678B 123456789 145679AB 2345789B 145678AB C D 2456789AB 3 2578BC 14567C 1578ABC 9 12678BC 1245678CD 14578BCD 24567ABCD 14567ABD 45678 124678AB 478BC 5789BC 145789BC D 35678AC 1234578BC 124678ABC 1235789C 13456789BC 345679AB 24567C 123456789AB 1346789ABC 246789AB 14789B 6 2457BC 35789BC 124578ACD 1234789BCD 1234578ACD 13579B 2345789C 124578ABCD 123479AB 1245789ABC 35789ABCD 14578BC 23478BD A 15789BCD 6 123478CD 134579D 34578C 235789BC 12478BC 1245789B 123579BC 345789BC 245678CD 1345789CD 124679 5789C 124578AC 3479A B 13456789ACD 234678ACD 125678C 12356789 13456789AC 23457AC

Hidden Text: Show

by **Mathimagics** » Sun Jun 06, 2021 7:27 am

denis_berthier wrote:After working on this, I think this variant will never become a popular game, for two reasons:
- the grids it requires are too large: the smallest interesting ones are 13x13, which makes more than 2 times the number of cells in Sudoku;
- the diagonals are visually very unfriendly

I don't think the grid size is an issue so much as the diagonals. Sudoku 16x16 and 25x25, while not wildly popular, do have their fans. I used to enjoy doing the Sudoku 25x25's produced by Gareth Moore, in the "SudokuXtra" magazine (now defunct). These are always singles-only puzzles, so would have very low software rating, but the human degree of difficulty is much higher because of the grid size.

As for the diagonals, a simple cell-corner labelling system (like the cage sums in Killer Sudoku) can probably mitigate this problem ... I intend to try this out sometime, but for the moment I am preoccupied with the mathematical properties of these intriguing combinatorial objects.

But I will concede, however, that iOS/Android developers will not be rushing into production any time in the foreseeable future :lol:

Website · by **denis_berthier** » Sun Jun 06, 2021 10:02 am

Mathimagics wrote:
denis_berthier wrote:After working on this, I think this variant will never become a popular game, for two reasons:
- the grids it requires are too large: the smallest interesting ones are 13x13, which makes more than 2 times the number of cells in Sudoku;
- the diagonals are visually very unfriendly

I don't think the grid size is an issue so much as the diagonals. Sudoku 16x16 and 25x25, while not wildly popular, do have their fans. I used to enjoy doing the Sudoku 25x25's produced by Gareth Moore, in the "SudokuXtra" magazine (now defunct). These are always singles-only puzzles, so would have very low software rating, but the human degree of difficulty is much higher because of the grid size.

What I meant about grid size is strongly related to the branching factor - the number of links from each candidate. When you consider only Singles, what counts is roughly the number of cells. But when you consider chains what counts is the number of candidates and the branching factor.
It's easy to see that in Sudoku(N) this factor is 3N-1+2sqr(N), but in PDLS(N) it is 4(N-1), which gives:
Sudoku(9): 22
Sudoku(16): 41
Sudoku(25): 66
PDLS(13): 51 (which puts it between Sudoku(16) and Sudoku(25))
PDLS(15):59
Moreover, this branching factor has to be applied twice between chain length p and p+1, which means a potential increase of complexity for each new chain length (for fixed target):
in Sudoku(9): 484
in Sudoku(16): 1681
in Sudoku(25): 4356
in PDLS(13): 2601
in PDLS(15): 3481
Of course, others factors modify these figures in practice, but this gives a rough idea. Moreover, this has to be multiplied by the number of candidates.

by **Mathimagics** » Sun Jun 06, 2021 11:59 am

denis_berthier wrote:What I meant about grid size is strongly related to the branching factor - the number of links from each candidate.

Indeed.

We also call this the "visible cells" count ... aka "affected cells" ...

BTW, for Sudoku(N), if N = n^2, then the count is 2(N-1) + (n-1)^2, I think. That's 20 for N=9, and 39 for N=16.

For PDLS 4(N-1) is correct, but this gives 48 for N=13, 64 for N = 17 (there are no PDLS(15) squares) ...

Website · by **denis_berthier** » Sun Jun 06, 2021 1:43 pm

Mathimagics wrote:
denis_berthier wrote:What I meant about grid size is strongly related to the branching factor - the number of links from each candidate.

BTW, for Sudoku(N), if N = n^2, then the count is 2(N-1) + (n-1)^2, I think.

Same formula.

by **creint** » Sun Jun 06, 2021 9:27 pm

denis_berthier your format from:

Here is a slightly more difficult variant, obtained by deleting first and last candidates. t-whips[3] and whips[3] appear, when only z-chains[3] were needed in the original puzzle.
Still relatively easy - W3 would be easy for Sudoku, but on a larger board, there are many more possible chains and complexity increases faster with the length of chains.

Problem 1 missing target digit:

Code: Select all: t-whip[2]: a4{r7c10 r6c9} - a12n13{r6c4 .} ==> r7c7 ≠ 13

a4{r7c10 r6c9}

You target cells but no pencil marks, should the pencil mark from exclusion be used because it is a single digit chain? In other parts you give the pencil mark why not here?

Problem 2 range notation:
I have seen formats where you use no separator like:

Code: Select all: g-whip[11]: b4n3{r6c2 r456c1} - r2n3{c1 c3} - r7n3{c3 c5} - c6n3{r9 r6} - r6n6{c6 c4} - b5n2{r6c4 r4c4} - b5n9{r4c4 r5c456} - c3n9{r5 r3} - c7n9{r3 r2} - c7n6{r2 r7} - c2n6{r7 .} ==> r9c2 ≠ 3

b4n3{r6c2 r456c1}
How to be sure it is r13 and not r1 and r3? (Parsing issue)

Problem 3 missing used constraints

Code: Select all: whip[1]: c4n13{r12 .} ==> r12c10 ≠ 13

Here it says D locked in column 4, but it uses row+diagonal+anti-diagonal. If you are not mentioning all the constraints then it is not much different from just saying 13c4 -> -13r12c10. You still need to look for constraints to verify it is correct. (Future link-line drawing issue)

Website · by **denis_berthier** » Mon Jun 07, 2021 2:50 am

creint wrote:Problem 1 missing target digit:
Code: Select all
t-whip[2]: a4{r7c10 r6c9} - a12n13{r6c4 .} ==> r7c7 ≠ 13
a4{r7c10 r6c9}

Right. Thanks for noticing. I had forgotten this in the output function of anti-diagonal CSP-Variables (but it was there for the diagonals). It's now corrected.

I hadn't put the resolution state after whips[1] because you need a large screen to see it properly. I've added it. Tell me how it looks like. I haven't yet a pretty-print function that would make it more compact.

creint wrote:Problem 2 range notation:
I have seen formats where you use no separator like:
Code: Select all
g-whip[11]: b4n3{r6c2 r456c1} - r2n3{c1 c3} - r7n3{c3 c5} - c6n3{r9 r6} - r6n6{c6 c4} - b5n2{r6c4 r4c4} - b5n9{r4c4 r5c456} - c3n9{r5 r3} - c7n9{r3 r2} - c7n6{r2 r7} - c2n6{r7 .} ==> r9c2 ≠ 3
b4n3{r6c2 r456c1}
How to be sure it is r13 and not r1 and r3? (Parsing issue)

As of now, I haven't yet coded g-labels for Pandiags and there is no ambiguity.
Of course, the right thing to do is to print the solution with the original symbols 12...9AB..., as I do in the resolution state. This should be easy to do.
I don't know yet if I'll spend more time on this game and if I'll code g-labels. A big problem with this game is the branching factor. Not as bad as in Slitherlink, but quite bad. Using g-whips may very fast lead to combinatorial explosion.

creint wrote:Problem 3 missing used constraints
Code: Select all
whip[1]: c4n13{r12 .} ==> r12c10 ≠ 13

Here it says D locked in column 4, but it uses row+diagonal+anti-diagonal. If you are not mentioning all the constraints then it is not much different from just saying 13c4 -> -13r12c10. You still need to look for constraints to verify it is correct. (Future link-line drawing issue)

This notation says all that is needed. z- and t- candidates are never written in my chains and this will not change. The CSP-Variable is c4n13, the target is n13r12c10, the llc is n13r12c4. The mention whip[1] at the start says that any other candidate is linked to the target by some link.
Maybe your problem is about the various types of links one needs to check (row+diagonal+anti-diagonal). But it is not a problem with my notation. It's a problem with this game. As I said before, diagonal constraints are very unfriendly to the player.

The New Sudoku Players' Forum

Pandiagonal #1

Re: Pandiagonal #1

Re: Pandiagonal #1

Re: Pandiagonal #1

Re: Pandiagonal #1

Re: Pandiagonal #1

Re: Pandiagonal #1

Re: Pandiagonal #1

Re: Pandiagonal #1

Re: Pandiagonal #1

Re: Pandiagonal #1

Re: Pandiagonal #1

Re: Pandiagonal #1

Re: Pandiagonal #1

Re: Pandiagonal #1

Re: Pandiagonal #1