5*5 is the smallest size for Latin Squares to contain chains, and I think it is small enough for us to find out all puzzles requiring chains.
I used JSudoku to generate such puzzles(setting 1+ guess) and got several non-equivalent puzzles. I wonder if there are more.
Hard 5*5 Latin Squares
10 posts
• Page 1 of 1
Hard 5*5 Latin Squares
by qiuyanzhe » Wed Sep 19, 2018 4:22 pm
- qiuyanzhe
- Posts: 94
- Joined: 21 August 2017
- Location: China
Re: Hard 5*5 Latin Squares
by qiuyanzhe » Wed Sep 19, 2018 5:54 pm
As rows, columns, digits can be switched each other to make isomorphic puzzles that "look quite different", only one of each equivalence class is shown.
If no extra marks, the puzzles can be solved by Pairs, X-wings and 5-step chains.
When a grid has multiple automorphisms, number of automorphisms is marked(titled "Symmetry"), including identity transformation.
The puzzle grids are after singles and normalization(shape first, then digits)
If no extra marks, the puzzles can be solved by Pairs, X-wings and 5-step chains.
When a grid has multiple automorphisms, number of automorphisms is marked(titled "Symmetry"), including identity transformation.
The puzzle grids are after singles and normalization(shape first, then digits)
- Code: Select all
pattern 1: 7 givens
12...
2.3..
.4...
...1.
....5
//Uniqueness Allowed: Gurth's_Symmetrical_Placement
//Symmetry:6
//Uniqueness Disabled: (unknown)
- Code: Select all
pattern 2: 8 givens
123..
34...
..5..
...1.
....2
- Code: Select all
pattern 3: 8 givens
12...
34...
..12.
..4..
....5
//Symmetry: 2
- Code: Select all
pattern 4: 10 givens
123..
45.3.
..42.
..5..
....3
- Code: Select all
pattern 5: 12 givens
12345
31...
4.2..
2..3.
5....
//Symmetry: 2
- qiuyanzhe
- Posts: 94
- Joined: 21 August 2017
- Location: China
Re: Hard 5*5 Latin Squares
by Mathimagics » Wed Dec 26, 2018 3:59 pm
qiuyanzhe wrote:5*5 is the smallest size for Latin Squares to contain chains, and I think it is small enough for us to find out all puzzles requiring chains.
I used JSudoku to generate such puzzles(setting 1+ guess) and got several non-equivalent puzzles. I wonder if there are more.
I assume by "puzzles requiring chains" you mean puzzles that can't be solved with singles alone? In Latin Square parlance, these would be uniquely completable partial LS's (ie. valid puzzles) that are not strong?
I take it also that we are only interested in minimal puzzles (ie. critical sets). We can certainly find all such puzzles in reasonable time. Using one representative from each of the 2 main classes of 5x5 Latin Squares, I obtained the following results:
- Code: Select all
Grid CSZ NCS SCS TW PW
-----------------------------------
5.1 6 50 50
5.1 7 1000 1000
5.1 8 30900 30900
5.1 9 18800 18800
5.1 10 2500 2500
5.2 7 600 588 12
5.2 8 21588 20904 36 648
5.2 9 23718 23718
5.2 10 2340 2268 36 36
5.2 11 216 216
CSZ = Critical set size, SCS = # of strong CS (singles only), TW = # of totally weak CS (no singles), PW = partially weak (these all had 2 or 4 singles).
The 7-clue case is interesting, the only puzzles that aren't strong, are totally weak.
The 12 x 7-clue TW cases might all be the "same" puzzle by your definition. I have listed them here just in case:
Hidden Text: Show
Last edited by Mathimagics on Thu Dec 27, 2018 6:26 am, edited 1 time in total.
-
Mathimagics - 2017 Supporter
- Posts: 1926
- Joined: 27 May 2015
- Location: Canberra
Re: Hard 5*5 Latin Squares
by qiuyanzhe » Thu Dec 27, 2018 4:02 am
Wow, thanks for yor work!
These 7-clue puzzles are isomorphic, so we've got that it is the only weak 7-clue puzzle!
As for 8-clue, it turns out that my second grid is not minimal(r1c2 redundant), and according to the symmetry group size(72),.we can conclude that patterns 2&3 are the only weak 8-clue puzzles.
Patterns 4&5 are not minimal, and seems there are so many ways to erase the redundant givens. Also I didn't expect the 11s. Sharing a few of your results may help knowing the whole thing.
Cheers!
These 7-clue puzzles are isomorphic, so we've got that it is the only weak 7-clue puzzle!
As for 8-clue, it turns out that my second grid is not minimal(r1c2 redundant), and according to the symmetry group size(72),.we can conclude that patterns 2&3 are the only weak 8-clue puzzles.
Patterns 4&5 are not minimal, and seems there are so many ways to erase the redundant givens. Also I didn't expect the 11s. Sharing a few of your results may help knowing the whole thing.
Cheers!
- qiuyanzhe
- Posts: 94
- Joined: 21 August 2017
- Location: China
Re: Hard 5*5 Latin Squares
by Mathimagics » Thu Dec 27, 2018 5:38 am
qiuyanzhe wrote:Wow, thanks for your work!
You're welcome! I just can't figure out why I missed your original post (but I was not alone it seems).
qiuyanzhe wrote:Sharing a few of your results may help knowing the whole thing.
Happy to do that, just tell me what you need?
-
Mathimagics - 2017 Supporter
- Posts: 1926
- Joined: 27 May 2015
- Location: Canberra
Re: Hard 5*5 Latin Squares
by qiuyanzhe » Thu Dec 27, 2018 6:18 am
Hi Mathimagics,
I think some examples for weak critical sets of other size would be useful, by isomorphs we may know all such critical sets.
Your new post is quite informative to me. From the first file I got that adding some digits to the 7-clue puzzle can make more weak puzzles.
(two more:(+r1c3+r4c35+r5c1) (+r1c3+r5c4))
A chart could be found in Pg.6 of the second file.
No 11-cell TW critical set was reported there.. did I misread something?
I think some examples for weak critical sets of other size would be useful, by isomorphs we may know all such critical sets.
Your new post is quite informative to me. From the first file I got that adding some digits to the 7-clue puzzle can make more weak puzzles.
(two more:(+r1c3+r4c35+r5c1) (+r1c3+r5c4))
A chart could be found in Pg.6 of the second file.
- Code: Select all
LS Size #CS #Iso#Main#NS#Strong#TW
5.1 6 50 1 1 1 1 0
7 1000 10 4 4 4 0
8 30900 312 57 57 57 0
9 18800 188 37 37 37 0
10 2500 25 6 6 6 0
5.2 7 600 50 11 10 10 1
8 21588 1802 322 311 311 1
9 23718 1981 348 348 348 0
10 2340 198 39 38 36 2
11 216 18 4 4 4 0
No 11-cell TW critical set was reported there.. did I misread something?
- qiuyanzhe
- Posts: 94
- Joined: 21 August 2017
- Location: China
Re: Hard 5*5 Latin Squares
by Mathimagics » Thu Dec 27, 2018 6:46 am
qiuyanzhe wrote:No 11-cell TW critical set was reported there.. did I misread something?
No, I just transcribed the results from my logs incorrectly when making my table. I have corrected this above, the weak counts for 5.2.11 should have been for 5.2.10.
Thanks for spotting that!
Here are my weak (TW or PW) lists. I did not reduce the minimal puzzles by isomorphism (as Adams et al did), but you can do that. You should find that these reductions lead to counts that match their table exactly (for TW anyway).
Each puzzle is tagged with the number of singles (0 for totally weak).
5.2.7
Hidden Text: Show
5.2.8
Hidden Text: Show
5.2.10
Hidden Text: Show
-
Mathimagics - 2017 Supporter
- Posts: 1926
- Joined: 27 May 2015
- Location: Canberra
Re: Hard 5*5 Latin Squares
by qiuyanzhe » Thu Dec 27, 2018 9:53 am
- Code: Select all
Min/After Singles Code Symmetry Count Comment
7/7: 12....14......2...3.5.... 6 12
8/8: 12.....4.....12...3.53... 2 36
10/10: 123..214..3..........312. 3 24
123..214...4...4.2.1..... 6 12 The two 10/10s are only different in a UR in the givens.
TOTAL-------------------------------------84
8/10: 12.......3..51.45......2. 1 72
10/12: 12.45.1.5..4..245........ 2 36 These /12's are essentially the same.
8/12: 123...1.5.....24.....3... 2 36
.23.5...5..4..24.....3... 2 36
123.....5..4..24.....3... 1 72
1.34....5..4..24.....3... 1 72
1.34..1.5.....24.....3... 1 72
1.3.5...5..4..24.....3... 1 72
1..45.1.5.....24.....3... 1 72
1..45...5..4..24.....3... 1 72
..345.1.5.....24.....3... 1 72
TOTAL------------------------------------684
More:(Puzzles that cannot be deduced from a minimal puzzle)
11 123...14....512.5.3.5.... 3 24
9 123...14......2...315.... 2 36
8 123...14......2...3.5.... 1 72
edit: corrected more(8)
- qiuyanzhe
- Posts: 94
- Joined: 21 August 2017
- Location: China
Re: Hard 5*5 Latin Squares
by jco » Wed Jan 31, 2024 9:51 pm
pattern 1: 7 givens
- Code: Select all
12...
2.3..
.4...
...1.
....5
//Uniqueness Allowed: Gurth's_Symmetrical_Placement
//Symmetry:6
//Uniqueness Disabled: (unknown)
Difficulty rating: SER = 8,3
- Code: Select all
.------------------.
|1 2 . . . |
|2 . 3 . . |
|. 4 . . . |
|. . . 1 . |
|. . . . 5 | uniqueness allowed (Gurth's symmetrical placement)
'------------------'
Rows are labelled 1 to 5 from bottom to top.
Columns are labelled a to e from left to right.
After no placements
STEP 1
- Code: Select all
.----------------------.
| 1 2 45 345 34 |
| 2 *15 3 *45 14 |
| 35 4 125 235 123 |
| 345 35 245 1 23-4|
|*34 *13 124 23-4 5 |
'----------------------'
1. (4=5)d4 - (5=1)b4 - (1=3)b1 - (3=4)a1 => -4 d1 [& -4 e3 by symmetry]
-------
STEPS 2,3
- Code: Select all
.-------------------------.
|1 2 45 (3)4-5 (34)|
|2 (1)5 3 45 (14)|
|35 4 125 235 123|
|345 35 245 1 2-3|
|34 (13) 124 2-3 5 |
'-------------------------'
2. (3=1)b1 - (1)b4 = (1-4)e4 = (4-3)e5 = (3)d5 => -3 d1 (+2d1, +2 e2 by symmetry)
3. (3)d5 = (3-4)e5 = (4)e4 - (4=5)d4 => -5 d5 [-5 a2 by symmetry; lclste]
------------ solving without using symmetry and uniqueness -------------
STEP 1
- Code: Select all
+----------------------+
| 1 2 45 345 34 |
| 2 b15 3 a45 14 |
| 35 4 125 235 123 |
| 345 35 245 1 234 |
|d34 c13 124 23-4 5 | LS
+----------------------+
-----
STEP 2
- Code: Select all
+-----------------------+
| 1 2 45 345 a34 |
| 2 c15 3 45 b14 |
| 35 4 125 235 123 |
| 345 d35 245 1 24-3|
| 34 13 124 23 5 | LS
+------ ----------------+
-------
STEP 3
- Code: Select all
+----------------------------+
| 1 2 45 45-3 cC34 |
| 2 15 3 45 14 |
| 35 4 A[2]15 235 B123 |
| 345 35 a[2]45 1 b24 |
| 34 13 u[2]14 v23 5 | LS
+----------------------------+
(2)c1 - (2=3)d1
(2)c2 - (2=4)e2 - (4=3)e5
(2-1)c3 = (1-3)e3 = (3)e5
--------
STEP 4
- Code: Select all
+-----------------------------+
| 1 2 f45 e45 *3 |
| 2 c15 3 d45 14 |
| 35 4 215 23 12 |
|a345 b35 245 1 24 |
|h4-3 13 g124 23 5 | LS
+-----------------------------+
--------
STEP 5
- Code: Select all
+----------------------------+
| 1 2 45 45 *3 |
| 2 15 3 45 14 |
| 35 4 b215 35-2 a12 |
| 35 35 24 1 24 |
|*4 13 c12 d23 5 | LS
+----------------------------+
Nice puzzle!
@1to9only: thank you! (LatinExplainer NxN [SER] available!).
EDIT: added description of chess notation at the beginning.
Last edited by jco on Mon Feb 05, 2024 8:46 pm, edited 1 time in total.
JCO
- jco
- Posts: 741
- Joined: 09 June 2020
Re: Hard 5*5 Latin Squares
by denis_berthier » Fri Feb 02, 2024 12:04 pm
.
solved in Z4:
solved in Z4:
- Code: Select all
Resolution state after Singles:
1 2 45 345 34
2 15 3 45 14
35 4 125 235 123
345 35 245 1 234
34 13 124 234 5
- Code: Select all
biv-chain[4]: c1n5{r3 r4} - r4c2{n5 n3} - r5c2{n3 n1} - c3n1{r5 r3} ==> r3c3≠5
biv-chain[4]: c2n3{r4 r5} - r5n1{c2 c3} - r3c3{n1 n2} - r4n2{c3 c5} ==> r4c5≠3
biv-chain[4]: r2c4{n4 n5} - c2n5{r2 r4} - r4n3{c2 c1} - r5c1{n3 n4} ==> r5c4≠4
z-chain[4]: c4n4{r1 r2} - c4n5{r2 r3} - r3c1{n5 n3} - c5n3{r3 .} ==> r1c4≠3
hidden-single-in-a-row ==> r1c5=3
naked-pairs-in-a-row: r3{c3 c5}{n1 n2} ==> r3c4≠2
singles ==> r5c4=2, r3c4=3, r3c1=5
biv-chain[4]: r1n5{c3 c4} - c4n4{r1 r2} - c5n4{r2 r4} - r4n2{c5 c3} ==> r4c3≠5
stte
- denis_berthier
- 2010 Supporter
- Posts: 4205
- Joined: 19 June 2007
- Location: Paris
10 posts
• Page 1 of 1
