Sudoku 16x16 (PW) Sample

For fans of Killer Sudoku, Samurai Sudoku and other variants

Re: Sudoku 16x16 (PW) Sample

Postby Mathimagics » Thu Jan 17, 2019 9:43 pm

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 …
User avatar
Mathimagics
2017 Supporter
 
Posts: 1926
Joined: 27 May 2015
Location: Canberra

Re: Sudoku 16x16 (PW) Sample

Postby Mathimagics » Thu Jan 17, 2019 10:15 pm

.
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 ! 8-)
User avatar
Mathimagics
2017 Supporter
 
Posts: 1926
Joined: 27 May 2015
Location: Canberra

Re: Sudoku 16x16 (PW) Sample

Postby blue » Thu Jan 17, 2019 11:03 pm

Mathimagics wrote: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 :(
blue
 
Posts: 975
Joined: 11 March 2013

Re: Sudoku 16x16 (PW) Sample

Postby Mathimagics » Fri Jan 18, 2019 4:06 am

blue wrote: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? :lol:
User avatar
Mathimagics
2017 Supporter
 
Posts: 1926
Joined: 27 May 2015
Location: Canberra

Re: Sudoku 16x16 (PW) Sample

Postby hkociemba1 » Fri Jan 18, 2019 11:26 am

blue wrote: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?
User avatar
hkociemba1
 
Posts: 60
Joined: 08 August 2018

Re: Sudoku 16x16 (PW) Sample

Postby Mathimagics » Fri Jan 18, 2019 12:33 pm

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 …
User avatar
Mathimagics
2017 Supporter
 
Posts: 1926
Joined: 27 May 2015
Location: Canberra

Re: Sudoku 16x16 (PW) Sample

Postby blue » Fri Jan 18, 2019 4:26 pm

hkociemba1 wrote: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
 
Posts: 975
Joined: 11 March 2013

Re: Sudoku 16x16 (PW) Sample

Postby blue » Fri Jan 18, 2019 4:42 pm

Mathimagics wrote: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.
blue
 
Posts: 975
Joined: 11 March 2013

Re: Sudoku 16x16 (PW) Sample

Postby Mathimagics » Fri Jan 18, 2019 6:31 pm

blue wrote:A post by you: SudokuPW - Analysis).

I knew I'd seen that around here somewhere! 8-)
blue wrote: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.
blue wrote:I haven't checked in any depth.

:shock: :o :shock:

Better get on with it, then! Expand our knowledge base, etc etc :lol:
User avatar
Mathimagics
2017 Supporter
 
Posts: 1926
Joined: 27 May 2015
Location: Canberra

Re: Sudoku 16x16 (PW) Sample

Postby tarek » Fri Jan 18, 2019 7:35 pm

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
User avatar
tarek
 
Posts: 3762
Joined: 05 January 2006

Re: Sudoku 16x16 (PW) Sample

Postby hkociemba1 » Fri Jan 18, 2019 11:30 pm

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).
User avatar
hkociemba1
 
Posts: 60
Joined: 08 August 2018

Re: Sudoku 16x16 (PW) Sample

Postby blue » Sat Jan 19, 2019 10:39 pm

Nice work hkociemba1 !
I'm glad you checked for PWX grids, too.
blue
 
Posts: 975
Joined: 11 March 2013

Re: Sudoku 16x16 (PW) Sample

Postby blue » Sat Jan 19, 2019 11:02 pm

Mathimagics wrote:
blue wrote:A post by you: SudokuPW - Analysis).

I knew I'd seen that around here somewhere! 8-)
blue wrote: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.
blue wrote: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.
blue
 
Posts: 975
Joined: 11 March 2013

Re: Sudoku 16x16 (PW) Sample

Postby Mathimagics » Sat Jan 19, 2019 11:48 pm

.
Ah, now I see ...

Elegantly put, blue. Thanks! 8-)

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

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!
User avatar
Mathimagics
2017 Supporter
 
Posts: 1926
Joined: 27 May 2015
Location: Canberra

Re: Sudoku 16x16 (PW) Sample

Postby hkociemba1 » Sun Jan 20, 2019 8:42 pm

blue wrote: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.
User avatar
hkociemba1
 
Posts: 60
Joined: 08 August 2018

PreviousNext

Return to Sudoku variants