Sudoku 16x16 (PW) Sample

For fans of Killer Sudoku, Samurai Sudoku and other variants

Re: Sudoku 16x16 (PW) Sample

Postby hkociemba1 » Mon Jan 21, 2019 8:45 am

Mathimagics wrote: a, (a+3) mod 3 and (a+6) mod 3

mod 9 of course
User avatar
hkociemba1
 
Posts: 60
Joined: 08 August 2018

Re: Sudoku 16x16 (PW) Sample

Postby Mathimagics » Mon Jan 21, 2019 10:26 am

.
Fake news! I did not write that at all! :lol:
User avatar
Mathimagics
2017 Supporter
 
Posts: 1262
Joined: 27 May 2015
Location: Canberra

Re: Sudoku 16x16 (PW) Sample

Postby hkociemba1 » Mon Jan 21, 2019 10:49 am

Mathimagics wrote:.
Fake news! I did not write that at all! :lol:


No idea how that happended. And still false since rows are not zerobased. I almost give up. Last try: rows 1,4,7 or 2,5,8 or 3,6,9
User avatar
hkociemba1
 
Posts: 60
Joined: 08 August 2018

PWX v Minirow Repetition

Postby Mathimagics » Mon Jan 21, 2019 5:27 pm

.
I tried a simple approach similar to what I use to find UA's. Remove clues randomly from a full grid until a multiple-solution situation is encountered, then choose one of these solutions as the next grid.

A "random PWX generator" such as this will quickly encounter some isotope of every one of the 2922 grids in the PWX catalog in about 10-15s.


For N=5, our case in point, I don't have the luxury of a fast solver like fsss2, of course, but confident that this method at least has the advantage of favouring any solver which does eliminations in the conventional sense, so doesn't have to spend much time at all guessing/DFS-ing.


I have a crude solver only, but still had little trouble breaking out of that N=5 starting pattern of only 5 different minirow digit combinations, here is a sample from the sequence that has 53 different minirow digit combinations:

PWX 25x25: Show
Code: Select all
 +-----------+-----------+-----------+-----------+-----------+
 | E A B C D | F G H I J | L M N K O | R Q S T P | U V W X Y |
 | P J F G H | K L T M O | X S E R W | I Y U V C | B D N A Q |
 | X L O M N | P S Y R Q | U B T V C | H D E A W | K F J I G |
 | I Q R S T | X U N V W | P D Y A G | K B J F M | H L E O C |
 | K U V W Y | D B A C E | J I H F Q | X L O N G | T P R S M |
 +-----------+-----------+-----------+-----------+-----------+
 | D B A E C | I J F G H | K L O N M | P S T R Q | V U X Y W |
 | F G H I J | L M O N K | Q R S T P | U W V X Y | C B D E A |
 | N M K L O | S T R Q P | W U V X Y | C A D E B | G I F J H |
 | S P Q T R | U W V X Y | C A D E B | F G I J H | L M O N K |
 | U V W Y X | A C B E D | I G F H J | N O M L K | P Q S T R |
 +-----------+-----------+-----------+-----------+-----------+
 | A E C D B | G I J H F | N O M L K | S T Q P R | Y W U V X |
 | G H I J F | N O K L M | S T Q P R | V U W Y X | A E C D B |
 | L K N O M | Q R P T S | V W U Y X | D E B C A | F J H G I |
 | R S T P Q | V Y U W X | E C A B D | J I H G F | M O K L N |
 | V W Y X U | C E D A B | H J I G F | L M K O N | Q S P R T |
 +-----------+-----------+-----------+-----------+-----------+
 | C D E B A | J H G F I | M K L O N | Q R P S T | X Y V W U |
 | M F G H I | R K L O N | Y Q P S T | E V X W U | J A B C D |
 | J O L N K | M Q S P T | R V X W U | Y C A B D | E G I H F |
 | Q T P R S | W V X Y U | D E B C A | G J F H I | N K L M O |
 | Y X U V W | B A E D C | F H G J I | O K N M L | R T Q P S |
 +-----------+-----------+-----------+-----------+-----------+
 | H C D A E | T N I J G | O P K M S | B F R Q V | W X Y U L |
 | O I J F G | H P M K L | T N R Q E | W X Y U S | D C A B V |
 | T N M K L | O X Q S R | B Y W U V | A P C D E | I H G F J |
 | B R S Q P | Y F W U V | A X C D L | T H G I J | O N M K E |
 | W Y X U V | E D C B A | G F J I H | M N L K O | S R T Q P |
 +-----------+-----------+-----------+-----------+-----------+

Another with 51:
Hidden Text: Show
Code: Select all
 +-----------+-----------+-----------+-----------+-----------+
 | E A B C D | F G H I J | L M N K O | Q R S T P | U V W Y X |
 | I J F G H | X L M N O | P S T R W | K U Y V C | A B D E Q |
 | P L N M O | K S R Q T | B U Y V G | X D E A W | F H J I C |
 | X Q R S T | P U V W Y | J D E A C | B H I F M | K L N O G |
 | K U W Y V | D B A C E | X I H F Q | J L O N G | S P R T M |
 +-----------+-----------+-----------+-----------+-----------+
 | D B C A E | I J G F H | K L O N M | P S T R Q | V U Y X W |
 | F G H I J | L M O K N | Q R S T P | U W V Y X | B D E C A |
 | N K L O M | S T Q P R | U W V X Y | A C D E B | G F I J H |
 | S P Q T R | U W Y X V | C A D E B | I G F J H | L M O N K |
 | U V X W Y | A C B E D | I G F H J | N O M L K | Q T P S R |
 +-----------+-----------+-----------+-----------+-----------+
 | A E D B C | G I J H F | O N M L K | S T Q P R | X W U V Y |
 | G H I J F | N O K L M | S T Q P R | W V U X Y | D E C A B |
 | L M O K N | Q R P T S | W V U Y X | D E B C A | J G F H I |
 | R S T P Q | V Y W U X | E C A B D | H I J G F | O K L M N |
 | V W Y U X | C E D A B | H J I G F | L M K O N | R Q S P T |
 +-----------+-----------+-----------+-----------+-----------+
 | C D A E B | J H F S I | M K L O N | R Q P W T | Y X V G U |
 | J F G H I | M K N O L | R Q P S T | V Y X B U | E C A W D |
 | M O K N L | R Q T G P | V Y X W U | E A C S D | I J H B F |
 | Q T P R S | W V X Y U | D E B C A | F J G H I | M N K L O |
 | Y X U V W | B A E D C | F H G J I | O K N M L | P R T Q S |
 +-----------+-----------+-----------+-----------+-----------+
 | B C E Q A | H P I J G | N O K M S | T F R D V | W Y X U L |
 | O I J F G | T N L M K | Y P R U E | C X W Q S | H A B D V |
 | H N M L K | O X S R Q | T B W D V | Y P A U E | C I G F J |
 | T R S D P | Y F U V W | A X C Q L | G B H I J | N O M K E |
 | W Y V X U | E D C B A | G F J I H | M N L K O | T S Q R P |
 +-----------+-----------+-----------+-----------+-----------+


All the evidence so far suggests that repeating minirows might be a feature, not a bug. The reason why they are hard to shake off might be because they are endemic, and if so, the missing W transform might be a relevant factor.

If I can find the time, perhaps I'll get a more efficient solver going (this one's just a VB6 hack) and get a bigger sample.
User avatar
Mathimagics
2017 Supporter
 
Posts: 1262
Joined: 27 May 2015
Location: Canberra

Re: Sudoku 16x16 (PW) Sample

Postby blue » Thu Jan 24, 2019 8:59 pm

hkociemba1 wrote:Are there any known transformations which preserve X but do not necessarily preserve P ?

"Swap rows 4&6, swap columns 4&6", is one.

For a given P-grid created with your method it easy to generate a different valid grid by just swapping N pairs of cells. In case of N=3 you can take for example the rows a, (a+3) mod 3 and (a+6) mod 3 and swap in each row the elements of two columns in the same stack, for example column 7 and 8. But this surely is nothing new for you. This operation always destroys the X-property so this way round it is no problem.

Nicely spotted !
I hadn't noticed it.

This probably, isn't important, but it doesn't quite "always" destroy the X-property.
For 9x9, swapping columns 1&3, or 4&6, or 7&9 in rows (2,5,8), would keep X intact.
blue
 
Posts: 837
Joined: 11 March 2013

Re: Sudoku 16x16 (PW) Sample

Postby hkociemba1 » Fri Jan 25, 2019 3:48 pm

blue wrote:"Swap rows 4&6, swap columns 4&6", is one.
Thanks, I also noticed this. But except from destroying part of the grid and searching for another solution there does not seem to be any obvious transformation which gets rid of the only 3 (or N in general ) minirow types.
User avatar
hkociemba1
 
Posts: 60
Joined: 08 August 2018

Re: Sudoku 16x16 (PW) Sample

Postby blue » Sat Jan 26, 2019 10:11 pm

Mathimagics wrote:An intriguing question arises. What happens to the relative population of PWX's as we increase the box size?

For example, we have 5.47 billion ED Sudoku grids (for N=3), but only 2922 ED PWX grids (and a much smaller set of isomorphic transformations).

What will happen with N=4, N=5 etc? Will the ability to form compatible intersections tend to grow? Diminish? Do we in fact have any prospect of ever knowing?

It will also be very interesting to find out (for N=3) whether these 2922 are in fact connected or not by Pittenger-moves. The fact that they are otherwise comparable to finding marbles in inter-planetary space does not absolutely exclude this possibility … that's one question that is at least accessible!

Assuming my code is functioning correctly, they are not connected -- they split into 655 connected components.
The largest component has 148 grids, and there are 231 grids that are completely isolated.

Only 4 of the 2922 have a transformation to a form with repeating mini-rows, and each is the lone grid in its component.
Three have transformations to a form matching the pencilmark problem that we've been using.
The 4th one, has a transformation to a solution to this PM problem:
Hidden Text: Show
Code: Select all
+-------------+-------------+-------------+
| 123 123 123 | 456 456 456 | 789 789 789 |
| 456 456 456 | 789 789 789 | 123 123 123 |
| 789 789 789 | 123 123 123 | 456 456 456 |
+-------------+-------------+-------------+
| 123 123 123 | 456 456 456 | 789 789 789 |
| 789 789 789 | 123 123 123 | 456 456 456 |
| 456 456 456 | 789 789 789 | 123 123 123 |
+-------------+-------------+-------------+
| 789 789 789 | 123 123 123 | 456 456 456 |
| 123 123 123 | 456 456 456 | 789 789 789 |
| 456 456 456 | 789 789 789 | 123 123 123 |
+-------------+-------------+-------------+

---

For "PW only" (no X), there were 177564 ED grids, with 306 of them having a transformation to a form with repeating minirows.
The 177564 grids split into 1451 connected components.
The largest component had 7387 grids, and 102 grids were completely isolated.
The 306 special grids, land in 6 of the components ... sizes 70, 70, 137, 137, 257 & 257.
None of the 6 components, contains only grids having a transformation to a form with repeating minirows.
The 4 PWX grids, land in 2 of the 6 PW components -- two in one, and two in the other.

Again, this is all assuming that the code is functioning correctly.
blue
 
Posts: 837
Joined: 11 March 2013

Re: Sudoku 16x16 (PW) Sample

Postby Mathimagics » Sun Jan 27, 2019 1:15 am

Great work, blue!

I assume that you restricted the procedure to Pittenger moves, ie just 2-symbol cycles + 3-symbol "pivot" joins?

Your results are consistent with expectations, I think. Many small dust clouds separated by large voids of interstellar space, which can only get worse, one imagines, as the grid size is increased.

My UA approach (which doesn't actually need to identify UA's, just find an MS case by clue removal) hit every one of these, so it could well prove to be effective for larger grids, like the 25x25 case ... certainly it should do better standard Pittenger moves!

Unfortunately I'm tied up doing other things, so I can't pursue this just now … it's up to you to blaze a trail!

Cheers!
User avatar
Mathimagics
2017 Supporter
 
Posts: 1262
Joined: 27 May 2015
Location: Canberra

Previous

Return to Sudoku variants