The New Sudoku Players' Forum

[Mathimagics]

Hi blue!

That was a clever idea!

While I was getting my PW mode randomiser working you have solved its "seed" problem!

We can use a Pittenger-style cyclic-perturbation function (operating in PW mode) to produce endless pseudo-randomised grid variations quickly given a valid starting point.

Sample PW 25x25: Show

Code: Select all

08:33:08 Randomiser: Loaded last SudokuPW25
08:33:09 Randomiser: Applying 100 perturbations

 +-----------+-----------+-----------+-----------+-----------+
 | S E L O N | I J B M T | X G C D W | K Y A H R | V Q F P U |
 | B M I J T | D X G W C | R K H A Y | U V Q F P | E O S N L |
 | D G W C X | R K H A Y | U Q V F P | E S O N L | I B M T J |
 | R Y A K H | U Q P F V | O E S N L | T B M I J | C D X W G |
 | U F Q P V | E O N L S | M B T I J | D X W C G | H K A R Y |
 +-----------+-----------+-----------+-----------+-----------+
 | E N O L S | B M J T I | D X W C G | R H K A Y | F V Q U P |
 | I B T M J | X G C D W | Y A K H R | F Q P V U | L S E O N |
 | W C D X G | K H A Y R | Q P F U V | N L E S O | J I B M T |
 | K R H A Y | Q P U V F | L N E S O | B I J M T | G X W C D |
 | Q P V U F | N L E S O | B J I T M | C W G X D | K R H Y A |
 +-----------+-----------+-----------+-----------+-----------+
 | N L S E O | J B T I M | W C G X D | H K Y R A | P F U Q V |
 | J I B T M | W C D X G | K H Y R A | Q P F U V | S E N L O |
 | X W C G D | Y A R H K | P F Q V U | O E S L N | M T J I B |
 | A K Y H R | F V Q P U | S L N O E | M T B J I | X W D G C |
 | F Q U V P | L S O N E | T M B J I | X G D W C | R A Y K H |
 +-----------+-----------+-----------+-----------+-----------+
 | L O N S E | M T I J B | G D X W C | Y A R K H | U P V F Q |
 | M T J B I | G D W C X | A Y R K H | V F U P Q | N L O S E |
 | G D X W C | A Y K R H | F V U P Q | S N L O E | B M T J I |
 | Y H K R A | P F V U Q | E S O L N | J M I T B | D C G X W |
 | V U P F Q | O N S E L | I T J M B | W D C G X | Y H R A K |
 +-----------+-----------+-----------+-----------+-----------+
 | O S E N L | T I M B J | C W D G X | A R H Y K | Q U P V F |
 | T J M I B | C W X G D | H R A Y K | P U V Q F | O N L E S |
 | C X G D W | H R Y K A | V U P Q F | L O N E S | T J I B M |
 | H A R Y K | V U F Q P | N O L E S | I J T B M | W G C D X |
 | P V F Q U | S E L O N | J I M B T | G C X D W | A Y K H R |
 +-----------+-----------+-----------+-----------+-----------+


Hmm .. on closer inspection it hasn't changed the repeating minirows property …

I'll try it with your later production …

[Mathimagics]

.
Phew, that's a relief! Thought I had a bug.

With more exotic variants, it gets harder to find compatible cyclic swap candidates (each cycle has to span a balanced set of everything boxes, psets, windows). All those repeating minirows simply proved irresistible to it, it just kept finding the easy way out!

Your second grid made a much better seed …

Randomised PW25 v2: Show

Code: Select all

 +-----------+-----------+-----------+-----------+-----------+
 | M F K D Y | A X H S O | J P L T B | Q I E V U | C N W R G |
 | N Q C X B | D Y L T V | K F E M A | O J W R G | U H S I P |
 | G L W U E | N J I P B | S O H R Q | F C Y X D | M V K T A |
 | S V P O R | G K W Q E | C X U I N | B T H M A | Y L J F D |
 | I T A J H | F C U M R | G Y W D V | S P K L N | E O B X Q |
 +-----------+-----------+-----------+-----------+-----------+
 | O K S M I | Y T A H J | N D F L E | U G X B P | R Q C W V |
 | Y U X C J | Q N F V D | I R B W O | M S A E L | H P T G K |
 | B G F V N | I R E L P | T U Q K C | Y H D O W | A X M J S |
 | A E D T W | O G X C K | M H Y S P | I R Q J V | N B F L U |
 | L H Q R P | U M S B W | A G X V J | T N F C K | O D E Y I |
 +-----------+-----------+-----------+-----------+-----------+
 | D J B K A | S H O Y Q | F V T E X | G L M N C | I R U P W |
 | F X Y L M | C V J D N | R I K B W | A O U P S | T G Q H E |
 | P I T W V | L F B E U | Q N A C G | R K J H Y | D S X M O |
 | E O G N Q | T P K R X | U S M Y H | D F B W I | L C A V J |
 | C R H S U | W I G A M | P J D O L | X V T Q E | K F Y N B |
 +-----------+-----------+-----------+-----------+-----------+
 | T Y V A D | X S Q O H | L C G J K | E M I F R | B W P U N |
 | X M I F C | J L D N Y | B E V A U | P W G K H | S T O Q R |
 | U P L B K | E A V F I | W T O N R | C Q S Y J | X M G D H |
 | Q N E H O | R W T K G | X M S P Y | V U L D B | F J I A C |
 | J W R G S | M B P U C | D Q I H F | N A O T X | V K L E Y |
 +-----------+-----------+-----------+-----------+-----------+
 | H A J Q F | K O Y I T | V B N X S | W E R G M | P U D C L |
 | W C N Y T | V D M J F | E K R U I | L B P S Q | G A H O X |
 | V B U I X | H E R G L | O W P Q T | K D C A F | J Y N S M |
 | K D O E L | P Q N X S | H A C G M | J Y V U T | W I R B F |
 | R S M P G | B U C W A | Y L J F D | H X N I O | Q E V K T |
 +-----------+-----------+-----------+-----------+-----------+


I could put something in there to warn when repeating minirows look like getting to be problem, but it's hard to imagine it will ever find itself in that condition again, given the size of the solution space, and the demand for PW25's !

[blue]

We can use a Pittenger-style cyclic-perturbation function (operating in PW mode) to produce endless pseudo-randomised grid variations quickly given a valid starting point.

(...)

Hmm .. on closer inspection it hasn't changed the repeating minirows property …
I'll try it with your later production …

With more exotic variants, it gets harder to find compatible cyclic swap candidates (each cycle has to span a balanced set of everything boxes, psets, windows). All those repeating minirows simply proved irresistible to it, it just kept finding the easy way out!

I wondered about that, with so many "house" types.

Your second grid made a much better seed …

I'm not so sure. It looks like most of the swaps, still amounted to relabeling transformations only.
If you relabel one of the grids, so that our top rows match, then they only differ in 18 cells -- two (4-cell,2-digit) UA's, and one (10-cell,2-digit) UA

[Mathimagics]

I wondered about that, with so many "house" types.
...
If you relabel one of the grids, so that our top rows match, then they only differ in 18 cells -- two (4-cell,2-digit) UA's, and one (10-cell,2-digit) UA

Dang it, I really should have known better!

I think you are right, it's probably a dimension too far for the perturbation method …

Hmmm … we need a solver that can dig a little deeper with that clue-removal method of yours …

625 cells, 625 houses. An fsss2 solver? How hard could it be?

[hkociemba1]

The 25x25 analog of this problem, has PW solutions that SAT finds easily:

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 |
| 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 |
| 789 789 789 | 123 123 123 | 456 456 456 |
+-------------+-------------+-------------+

If you like, row 1 can be preset to "12345..."

Thanks! I will try to implement this method and also explore up to which N this method gives back results. Since my Sudoku knowledge is rather limited just one question: How do you know that the restrictions for the candidates given above always includes a solution with the W property?

[Mathimagics]

blue, I seem to recall noticing that the special transformations for SudokuP (D, E, F, G) and SudokuW (W) are all PW-preserving …

That could be a way of getting more variety …

[blue]

Thanks! I will try to implement this method and also explore up to which N this method gives back results. Since my Sudoku knowledge is rather limited just one question: How do you know that the restrictions for the candidates given above always includes a solution with the W property?

Checking N's > 5 will be a good idea.
I didn't know until I tried them with a SAT solver, that N=4 (16x16) and N=5 (25x25), would work.
I hit on the PM problem for 9x9, by luck, after following up on an hunch.

The hunch was that there might be a vanilla sudoku grid with a large automorphism count, that was "vanilla"-isomorphic to a PW grid with non-trivial automorphisms. This (PW-minlex) PW grid came up, and it turned out to have repeating minicolumns, with the same sets of numbers in each stack.

Hidden Text: Show

Code: Select all

+-------+-------+-------+
| 1 2 3 | 4 5 6 | 7 8 9 |
| 4 8 6 | 7 2 9 | 1 5 3 |
| 7 5 9 | 1 8 3 | 4 2 6 |
+-------+-------+-------+
| 5 3 4 | 2 9 7 | 8 6 1 |
| 2 6 7 | 8 3 1 | 5 9 4 |
| 8 9 1 | 5 6 4 | 2 3 7 |
+-------+-------+-------+
| 9 4 2 | 3 1 8 | 6 7 5 |
| 3 7 8 | 6 4 5 | 9 1 2 |
| 6 1 5 | 9 7 2 | 3 4 8 |
+-------+-------+-------+

[blue]

I seem to recall noticing that the special transformations for SudokuP (D, E, F, G) and SudokuW (W) are all PW-preserving …

That could be a way of getting more variety …

Only (D and) W preserved all of the properties.
(A post by you: SudokuPW - Analysis).

I don't know if anything like W exists, for N > 3.
There's are transformations that map boxes to windows (and rows to rows, columns to coumns, and, I think, p-sets to p-sets).
It doesn't seem like any of them map windows to boxes, though. Don't take my word on that. I haven't checked in any depth.

[Mathimagics]

A post by you: SudokuPW - Analysis).

I knew I'd seen that around here somewhere!

I don't know if anything like W exists, for N > 3.

Seems to me if it works for N = 3 it should work for any N > 3.

I haven't checked in any depth.

Better get on with it, then! Expand our knowledge base, etc etc

[tarek]

Joining the 25x25 part late here. I tried to solve the empty grid & my solver also stalled hkociemba1.

The method that blue suggested is very good. Anything to narrow down the exhaustive recursive process in this madness of constraints that is the 25x25 PW & PWX

Here is a partial puzzle taken from blue's posted PW grid

Partial 25x25 Sudoku PW grid: Show

Code: Select all

+-----------+-----------+-----------+-----------+-----------+
| . . . . . | . . . . . | . . . . . | . . . . . | . . . . . |
| . . . . . | . . . . . | . . . . . | . . . . . | . . . . . |
| . . . . . | . . . . . | . . . . . | . . . . . | . . . . . |
| . . . . . | . . . . . | . . . . . | . . . . . | . . . . . |
| . . . . . | . . . . . | . . . . . | . . . . . | . . . . . |
+-----------+-----------+-----------+-----------+-----------+
| . . . . . | . . . . . | . . . . . | . . . . . | . . . . . |
| . . . . . | . . . . . | . . . . . | . . . . . | . . . . . |
| . . . . . | . . . . . | . . . . . | . . . . . | . . . . . |
| . . . . . | . . . . . | . . . . . | . . . . . | . . . . . |
| . . . . . | . . . . . | . . . . . | . . . . . | . . . . . |
+-----------+-----------+-----------+-----------+-----------+
| . . . . . | . . . . . | F E G I H | M B 6 J 7 | C P L N O |
| . . . . . | . . . . . | P C K D O | 5 1 L N 2 | G M 3 4 I |
| . . . . . | . . . . . | 3 J 5 7 M | P K A 4 9 | 8 2 H 6 1 |
| . . . . . | . . . . . | L 2 6 9 4 | 8 F D O C | B 7 5 E A |
| . . . . . | . . . . . | N A 8 1 B | I E G 3 H | K F 9 J D |
+-----------+-----------+-----------+-----------+-----------+
| . . . . . | . . . . . | B 7 M A K | H 6 C F P | D O N L J |
| . . . . . | . . . . . | D I E 5 L | N O M K 4 | 2 G 1 3 P |
| . . . . . | . . . . . | O G 1 J P | 7 3 2 9 A | I 6 M 8 4 |
| . . . . . | . . . . . | H 6 2 N 9 | E L B 8 D | F A C 5 7 |
| . . . . . | . . . . . | 8 3 C 4 F | J 5 1 G I | E K B H 9 |
+-----------+-----------+-----------+-----------+-----------+
| . . . . . | . . . . . | E D J H 2 | O I P M 6 | N L 8 7 F |
| . . . . . | . . . . . | I K P L C | B D N 2 3 | M 5 4 1 H |
| . . . . . | . . . . . | 1 O N 3 G | K 8 7 5 F | A 9 J 2 6 |
| . . . . . | . . . . . | 4 5 7 M 6 | A 9 E L G | O C P D B |
| . . . . . | . . . . . | 9 B A F 8 | 4 H J C 1 | 3 I E K G |
+-----------+-----------+-----------+-----------+-----------+


was introduced into the solver and it starts singing quickly!!!

He is one of the grids in the output preserving the original partial section

25x25 sudoku PW grid: Show

Code: Select all

+-----------+-----------+-----------+-----------+-----------+
| J 4 D 8 5 | 9 K A 1 M | 2 F H G 3 | 6 C I E B | 7 N O P L |
| 6 3 I E 7 | 8 N C F B | K L D P 1 | 9 J O A M | 4 H 2 G 5 |
| 9 P F A H | L E O G 3 | M N I B 7 | 2 4 8 1 5 | J D 6 C K |
| G B 1 K 2 | 6 H 4 I P | J 8 O C 5 | D N 3 7 L | 9 E F A M |
| L O N M C | D J 5 2 7 | 6 9 4 E A | F G H P K | 1 8 I B 3 |
+-----------+-----------+-----------+-----------+-----------+
| 8 J 5 4 9 | G 2 1 D E | A H F 6 I | L M K B N | P 3 7 O C |
| 3 F A 6 E | H 9 8 7 K | C P B O D | 1 2 5 I J | L 4 G M N |
| C 7 L P O | F M 3 N J | 5 1 9 K E | G A 4 H 8 | 6 B D I 2 |
| 1 D H G K | C 4 I B O | 7 M L 2 N | 3 P 9 6 E | 5 J A F 8 |
| B 2 M I N | 5 P L A 6 | G 4 3 8 J | C 7 F D O | H 1 K 9 E |
+-----------+-----------+-----------+-----------+-----------+
| 5 8 4 9 1 | 3 A 2 K D | F E G I H | M B 6 J 7 | C P L N O |
| F E 6 B A | J 7 H 8 9 | P C K D O | 5 1 L N 2 | G M 3 4 I |
| D C G O I | B F E L N | 3 J 5 7 M | P K A 4 9 | 8 2 H 6 1 |
| N K J H 3 | I G M P 1 | L 2 6 9 4 | 8 F D O C | B 7 5 E A |
| 2 M P 7 L | O C 6 5 4 | N A 8 1 B | I E G 3 H | K F 9 J D |
+-----------+-----------+-----------+-----------+-----------+
| I G E 2 4 | 1 5 9 3 8 | B 7 M A K | H 6 C F P | D O N L J |
| 7 6 9 C 8 | A B J H F | D I E 5 L | N O M K 4 | 2 G 1 3 P |
| H 5 B F D | N L K E C | O G 1 J P | 7 3 2 9 A | I 6 M 8 4 |
| M 1 K 3 J | P O G 4 I | H 6 2 N 9 | E L B 8 D | F A C 5 7 |
| A L O N P | M D 7 6 2 | 8 3 C 4 F | J 5 1 G I | E K B H 9 |
+-----------+-----------+-----------+-----------+-----------+
| 4 9 3 5 G | K 1 B C A | E D J H 2 | O I P M 6 | N L 8 7 F |
| O A 7 J 6 | E 8 F 9 G | I K P L C | B D N 2 3 | M 5 4 1 H |
| E H C D B | 4 I P M L | 1 O N 3 G | K 8 7 5 F | A 9 J 2 6 |
| K I 8 1 F | 2 3 N J H | 4 5 7 M 6 | A 9 E L G | O C P D B |
| P N 2 L M | 7 6 D O 5 | 9 B A F 8 | 4 H J C 1 | 3 I E K G |
+-----------+-----------+-----------+-----------+-----------+


tarek

[hkociemba1]

I implemented blues method and it really scales very good! It seems to work also for N>5. I tried up to N=12.
Here are the creation times for the SAT solver N | time in s;
3| 0.4; 4 | 0.5; 5| 0.7; 6 | 0.9; 7 | 1.4; 8 | 2.4; 9 | 6.3; 10 | 19.8; 11 | 49.3; 12 | 158.1

For a PWX grid the times are more or less the same. Here the output for the N=6 PWX-grid

Hidden Text: Show

Code: Select all

 +-------------------+-------------------+-------------------+-------------------+-------------------+-------------------+
 |  1  2  3  4  5  6 |  7  8  9 10 11 12 | 13 14 15 16 17 18 | 19 20 21 22 23 24 | 25 26 27 28 29 30 | 31 32 33 34 35 36 |
 | 10  7  9 11  8 12 | 14 13 16 18 17 15 | 23 22 21 20 19 24 | 28 30 26 29 25 27 | 33 31 32 36 35 34 |  1  2  6  5  4  3 |
 | 14 13 15 17 18 16 | 23 22 19 24 20 21 | 26 28 30 27 29 25 | 33 31 36 32 35 34 |  4  2  1  6  5  3 |  7  9 10 11  8 12 |
 | 23 21 19 20 24 22 | 26 28 27 29 25 30 | 33 31 36 35 34 32 |  2  1  4  6  5  3 |  7  8 11 10  9 12 | 13 18 14 16 17 15 |
 | 26 30 28 29 27 25 | 33 31 32 35 36 34 |  4  2  1  6  3  5 | 10  7 11  8  9 12 | 14 18 13 17 16 15 | 23 22 21 20 24 19 |
 | 33 31 32 35 36 34 |  4  2  1  6  5  3 | 10 11  7 12  9  8 | 18 14 13 17 15 16 | 21 22 24 23 20 19 | 29 28 26 25 30 27 |
 +-------------------+-------------------+-------------------+-------------------+-------------------+-------------------+
 |  4  3  1  5  6  2 | 10 11  8  7 12  9 | 14 13 18 17 15 16 | 21 22 23 24 20 19 | 29 28 30 26 25 27 | 32 33 35 31 36 34 |
 |  7  8 11  9 12 10 | 13 14 17 15 16 18 | 21 19 20 22 24 23 | 25 26 27 28 30 29 | 35 32 33 31 34 36 |  2  1  4  3  5  6 |
 | 18 14 16 13 17 15 | 20 24 21 22 23 19 | 28 27 29 26 25 30 | 35 34 32 36 31 33 |  6  3  5  2  4  1 | 11  7  9  8 12 10 |
 | 20 19 22 24 23 21 | 28 27 30 25 29 26 | 32 34 35 36 31 33 |  3  5  6  2  1  4 |  8  9 12 11  7 10 | 15 14 16 17 18 13 |
 | 28 29 26 25 30 27 | 32 34 33 31 35 36 |  3  6  5  2  4  1 |  9 12  8 11  7 10 | 16 15 17 18 14 13 | 20 19 24 21 23 22 |
 | 32 33 36 31 34 35 |  3  6  2  4  1  5 |  9 12  8 10 11  7 | 17 18 16 15 13 14 | 23 19 20 24 21 22 | 30 27 29 28 26 25 |
 +-------------------+-------------------+-------------------+-------------------+-------------------+-------------------+
 |  3  6  5  2  1  4 |  9 12 10  8  7 11 | 16 18 17 14 13 15 | 23 24 20 19 22 21 | 27 30 28 29 26 25 | 35 34 32 36 31 33 |
 |  9 10  7 12 11  8 | 18 16 15 17 14 13 | 20 24 23 21 22 19 | 29 27 28 30 26 25 | 32 34 36 35 31 33 |  5  4  2  6  3  1 |
 | 13 18 14 15 16 17 | 21 19 20 23 24 22 | 27 25 26 29 30 28 | 32 33 35 31 34 36 |  3  5  4  1  2  6 |  8 11 12 10  7  9 |
 | 19 22 20 23 21 24 | 29 26 28 27 30 25 | 34 36 31 32 33 35 |  5  4  1  3  6  2 | 10  7  9 12 11  8 | 14 15 18 13 16 17 |
 | 29 25 27 26 28 30 | 34 36 31 32 33 35 |  1  5  4  3  6  2 |  7 10 12  9 11  8 | 18 16 14 13 15 17 | 22 24 19 23 21 20 |
 | 34 32 31 33 35 36 |  5  1  6  2  3  4 | 12  7 10 11  8  9 | 13 16 18 14 17 15 | 22 21 23 19 24 20 | 26 30 25 27 29 28 |
 +-------------------+-------------------+-------------------+-------------------+-------------------+-------------------+
 |  5  4  2  6  3  1 | 12  7 11  9  8 10 | 18 16 13 15 14 17 | 22 23 19 21 24 20 | 26 25 29 27 30 28 | 33 31 36 35 34 32 |
 | 12  9  8  7 10 11 | 16 18 14 13 15 17 | 19 23 22 24 20 21 | 26 29 25 27 28 30 | 31 36 35 34 33 32 |  4  5  3  1  6  2 |
 | 16 15 17 14 13 18 | 19 23 24 21 22 20 | 29 26 25 30 28 27 | 34 36 31 35 33 32 |  1  4  3  5  6  2 | 12 10  7  9 11  8 |
 | 21 24 23 22 20 19 | 27 25 29 30 26 28 | 35 33 32 31 36 34 |  1  3  5  4  2  6 | 12 11  8  7 10  9 | 18 13 17 15 14 16 |
 | 30 27 29 28 25 26 | 31 32 35 36 34 33 |  2  3  6  1  5  4 |  8  9 10  7 12 11 | 15 17 16 14 13 18 | 19 20 23 24 22 21 |
 | 31 34 35 36 32 33 |  2  3  5  1  4  6 |  8 10  9  7 12 11 | 15 17 14 16 18 13 | 24 23 19 20 22 21 | 27 25 30 29 28 26 |
 +-------------------+-------------------+-------------------+-------------------+-------------------+-------------------+
 |  2  5  6  1  4  3 |  8 10 12 11  9  7 | 17 15 14 18 16 13 | 20 19 24 23 21 22 | 28 29 25 30 27 26 | 34 36 31 32 33 35 |
 |  8 11 12 10  7  9 | 17 15 13 14 18 16 | 24 20 19 23 21 22 | 30 28 29 25 27 26 | 34 33 31 32 36 35 |  3  6  5  2  1  4 |
 | 17 16 13 18 15 14 | 24 20 22 19 21 23 | 30 29 28 25 27 26 | 31 32 33 34 36 35 |  5  6  2  3  1  4 | 10 12  8  7  9 11 |
 | 24 23 21 19 22 20 | 30 29 25 26 28 27 | 31 32 33 34 35 36 |  6  2  3  5  4  1 |  9 10  7  8 12 11 | 16 17 13 14 15 18 |
 | 27 26 25 30 29 28 | 35 33 36 34 31 32 |  5  1  3  4  2  6 | 11  8  7 12 10  9 | 13 14 18 15 17 16 | 21 23 22 19 20 24 |
 | 36 35 33 34 31 32 |  6  4  3  5  2  1 | 11  9 12  8  7 10 | 16 15 17 13 14 18 | 20 24 21 22 19 23 | 28 26 27 30 25 29 |
 +-------------------+-------------------+-------------------+-------------------+-------------------+-------------------+
 |  6  1  4  3  2  5 | 11  9  7 12 10  8 | 15 17 16 13 18 14 | 24 21 22 20 19 23 | 30 27 26 25 28 29 | 36 35 34 33 32 31 |
 | 11 12 10  8  9  7 | 15 17 18 16 13 14 | 22 21 24 19 23 20 | 27 25 30 26 29 28 | 36 35 34 33 32 31 |  6  3  1  4  2  5 |
 | 15 17 18 16 14 13 | 22 21 23 20 19 24 | 25 30 27 28 26 29 | 36 35 34 33 32 31 |  2  1  6  4  3  5 |  9  8 11 12 10  7 |
 | 22 20 24 21 19 23 | 25 30 26 28 27 29 | 36 35 34 33 32 31 |  4  6  2  1  3  5 | 11 12 10  9  8  7 | 17 16 15 18 13 14 |
 | 25 28 30 27 26 29 | 36 35 34 33 32 31 |  6  4  2  5  1  3 | 12 11  9 10  8  7 | 17 13 15 16 18 14 | 24 21 20 22 19 23 |
 | 35 36 34 32 33 31 |  1  5  4  3  6  2 |  7  8 11  9 10 12 | 14 13 15 18 16 17 | 19 20 22 21 23 24 | 25 29 28 26 27 30 |
 +-------------------+-------------------+-------------------+-------------------+-------------------+-------------------+

0,859 s total time.


And here is a 374 givens puzzle based on this grid. It is solved in about 16 s.

Hidden Text: Show

Code: Select all

 +-------------------+-------------------+-------------------+-------------------+-------------------+-------------------+
 |  .  2  .  4  .  . |  7  .  . 10  .  . |  .  .  . 16 17  . |  .  .  .  .  .  . |  .  . 27 28  .  . |  .  .  .  . 35  . |
 |  .  .  .  .  . 12 |  . 13 16 18  . 15 |  .  .  .  . 19  . | 28 30  .  .  .  . |  .  .  .  .  . 34 |  1  2  .  .  .  . |
 |  . 13  . 17  .  . |  .  .  .  . 20  . |  .  .  .  .  .  . |  .  . 36  .  .  . |  .  .  .  6  .  . |  .  .  . 11  8  . |
 | 23 21 19  .  .  . |  .  .  .  . 25  . |  .  . 36  .  . 32 |  2  .  .  .  .  3 |  .  .  .  .  .  . | 13  .  . 16  .  . |
 | 26  . 28 29  .  . | 33  .  .  . 36  . |  .  .  .  6  .  5 |  .  .  .  .  .  . |  .  .  . 17  . 15 |  . 22 21 20  . 19 |
 |  .  . 32  . 36  . |  4  2  .  .  .  3 |  .  .  7  .  .  . | 18  .  .  .  .  . | 21  . 24  .  .  . |  .  .  .  . 30 27 |
 +-------------------+-------------------+-------------------+-------------------+-------------------+-------------------+
 |  .  .  1  5  .  2 | 10 11  8  . 12  . | 14  . 18  . 15  . |  .  .  .  .  .  . | 29  . 30  .  .  . |  . 33 35  .  .  . |
 |  7  . 11  9 12 10 | 13 14  .  .  .  . |  . 19 20  . 24 23 | 25  . 27  .  .  . |  . 32 33  .  .  . |  .  1  .  3  5  . |
 | 18 14  .  .  .  . |  . 24  .  .  .  . |  .  .  .  .  .  . | 35  .  .  .  .  . |  .  .  .  .  .  1 | 11  .  .  8 12  . |
 |  .  .  .  .  . 21 | 28  . 30 25  .  . |  .  . 35  . 31  . |  .  .  6  .  1  . |  .  .  .  .  .  . |  .  .  . 17  .  . |
 |  .  .  .  . 30 27 | 32  .  . 31  .  . |  .  .  5  2  4  . |  9  .  .  .  .  . |  . 15  .  .  .  . |  . 19  .  .  .  . |
 |  .  . 36  .  .  . |  3  .  .  .  .  5 |  .  .  .  .  .  . | 17  .  . 15  .  . |  .  .  .  .  . 22 |  .  . 29 28  . 25 |
 +-------------------+-------------------+-------------------+-------------------+-------------------+-------------------+
 |  3  6  .  .  .  4 |  .  .  .  .  .  . |  .  .  .  .  .  . |  . 24  .  .  . 21 |  . 30  . 29  .  . |  .  .  . 36 31  . |
 |  .  .  .  .  .  . | 18  . 15  .  .  . |  .  .  . 21  .  . |  .  .  .  . 26  . |  . 34  .  .  .  . |  5  .  2  .  3  . |
 |  . 18  .  .  . 17 |  .  .  . 23  . 22 |  . 25  .  .  .  . |  . 33  .  .  .  . |  .  5  .  1  .  6 |  8  .  .  .  7  . |
 |  .  .  .  . 21  . |  .  . 28 27  .  . |  .  .  .  .  .  . |  .  .  1  .  .  . |  .  .  .  .  .  8 |  . 15 18  .  .  . |
 |  . 25  .  .  .  . | 34  .  .  .  . 35 |  .  .  .  .  .  . |  7  . 12  9 11  . | 18 16  .  .  .  . |  .  .  . 23  . 20 |
 | 34  .  . 33 35 36 |  5  .  .  2  .  . | 12  .  .  .  .  . |  . 16  .  .  . 15 |  .  . 23 19  . 20 | 26  . 25 27 29  . |
 +-------------------+-------------------+-------------------+-------------------+-------------------+-------------------+
 |  .  .  .  .  .  . |  .  7  .  9  8 10 |  .  .  .  .  . 17 |  .  .  . 21  .  . |  . 25  .  .  .  . |  .  . 36  .  .  . |
 |  .  .  8  .  .  . |  . 18  . 13  .  . |  .  . 22  .  .  . |  . 29  .  .  .  . | 31  .  .  .  . 32 |  .  .  3  1  6  2 |
 | 16  .  .  .  .  . |  .  . 24  .  . 20 |  .  .  . 30 28  . |  .  .  .  .  . 32 |  1  .  .  .  .  2 |  . 10  .  9  .  . |
 |  . 24 23  . 20  . |  .  .  .  . 26 28 |  .  .  .  .  .  . |  .  3  .  4  2  . | 12 11  .  .  .  . |  .  . 17 15  .  . |
 |  .  . 29 28 25  . | 31  .  .  . 34  . |  .  .  6  .  .  . |  8  .  .  .  . 11 | 15 17 16  .  .  . |  .  . 23  . 22  . |
 |  .  .  . 36  .  . |  .  .  .  .  4  . |  .  .  9  .  .  . | 15  .  .  . 18 13 |  .  .  . 20 22 21 | 27  .  .  .  .  . |
 +-------------------+-------------------+-------------------+-------------------+-------------------+-------------------+
 |  .  .  .  .  .  3 |  . 10 12  .  .  . |  .  .  .  .  .  . | 20  .  . 23  . 22 |  .  .  .  .  .  . | 34  .  . 32  .  . |
 |  .  .  .  .  7  9 | 17  .  .  . 18  . |  .  .  .  .  .  . |  . 28  .  .  .  . |  .  .  .  . 36  . |  .  .  5  .  1  . |
 |  .  .  .  .  . 14 |  .  .  .  .  .  . |  .  . 28  .  .  . |  .  .  .  . 36  . |  .  .  .  3  .  4 |  .  .  .  .  .  . |
 |  . 23  . 19  .  . |  . 29  .  .  .  . |  .  .  . 34 35  . |  .  2  .  .  .  . |  9  .  .  .  .  . |  .  .  .  . 15  . |
 |  .  .  . 30  .  . | 35 33  . 34  .  . |  .  1  .  .  2  . |  .  .  7  .  .  9 |  . 14  . 15 17  . | 21  .  . 19  . 24 |
 |  .  . 33  . 31  . |  .  .  .  .  .  . |  .  9  .  8  . 10 |  . 15  . 13 14  . |  .  .  . 22  .  . |  .  .  .  . 25  . |
 +-------------------+-------------------+-------------------+-------------------+-------------------+-------------------+
 |  6  .  4  .  .  . |  .  9  .  . 10  8 | 15  .  .  .  . 14 |  .  . 22  . 19  . |  .  .  .  . 28  . |  .  .  . 33 32  . |
 |  . 12  .  .  .  7 |  .  .  .  . 13 14 |  .  .  .  . 23  . |  .  .  .  .  . 28 | 36 35 34 33  . 31 |  .  3  .  4  .  . |
 | 15  . 18 16  .  . |  .  .  . 20 19  . |  .  . 27  .  . 29 | 36  .  .  . 32 31 |  .  .  .  .  3  . |  9  8 11  .  .  . |
 |  .  . 24  .  .  . |  .  .  .  .  .  . | 36  .  .  . 32  . |  .  .  .  .  .  . |  . 12 10  .  8  7 | 17  .  .  .  .  . |
 |  .  . 30  .  .  . |  . 35  .  . 32  . |  6  .  .  5  .  . |  . 11  9 10  .  7 |  .  .  .  .  .  . |  .  . 20  .  .  . |
 |  .  .  .  . 33  . |  .  .  .  3  6  2 |  .  .  .  9  .  . |  .  .  . 18  . 17 |  .  .  .  .  . 24 |  . 29  .  .  .  . |
 +-------------------+-------------------+-------------------+-------------------+-------------------+-------------------+

374 givens, 9709 candidates(pencilmarks).


[blue]

Nice work hkociemba1 !
I'm glad you checked for PWX grids, too.

[blue]

A post by you: SudokuPW - Analysis).

I knew I'd seen that around here somewhere!

I don't know if anything like W exists, for N > 3.

Seems to me if it works for N = 3 it should work for any N > 3.

I haven't checked in any depth.

Better get on with it, then!

It's true: nothing like W exists for N > 3, assuming that "like W", means it's a transformation mapping boxes to windows and vica-versa.

To see it, consider that:

• If a cell is in the intersection of a window and a box, then its image under the hypothetical transformation, would be in the intersection of the image of the window (a box), and the image of the box (a window).
• The (hidden) window that includes the 4 corner cells, intersects each of the N*N boxes.
• Since distinct boxes should map to distinct windows, the hypothetical transformation would need to map that particular window, to a box that intersects each of the N*N windows.
• For N > 3, no such box exists.

[Mathimagics]

.
Ah, now I see ...

Elegantly put, blue. Thanks!

=======================================

Regarding the "how do I get a sample PWX grid of arbitrary size?", your method seems to be the only gig in town.

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!

[hkociemba1]

I'm glad you checked for PWX grids, too.

I realized that your method also works great to generate just a valid SudokuX grid. Here even for N=15 a grid is found within 2 min. Ok, the grid automatically also has the P-property. Are there any known transformations which preserve X but do not necessarily preserve P ?

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.