Sudoku 16x16 (PW) Sample

For fans of Killer Sudoku, Samurai Sudoku and other variants

Sudoku 16x16 (PW) Sample

Postby Mathimagics » Fri Dec 21, 2018 4:07 pm

.
If you have a few idle hours over the end-of-year break, try this P&P challenger!

As explained elsewhere, SudokuPW combines both SudokuP and SudokuW (Windoku) modes. So here we want to fill in the grid with values {0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F} so that all rows, columns, and 4x4 boxes have different values in each cell, as per normal Sudoku rules, and in addition:

  • all cells with the same box Position have different values
  • all cells in the same Window (shaded 4x4 areas) have different values

Hidden windows:
  • along with the 9 normal (shaded) windows, there are 7 "hidden" windows. One is indicated by being shaded in a slightly different colour (so perhaps not hidden at all!). These are the 16 cells that are diagonally adjacent to the corners of the 9 normal windows.
  • the unshaded cells also correspond to 6 hidden windows. Each set of 3 shaded windows in a row or column (ie. a window-band or window stack) has 4 sets of 4 white cells that separate the shaded windows. Each of these 4 sets of 4 white cells in the same band/stack position is also a hidden window.
  • knowing the hidden windows is not necessary to solve the puzzle, but when the solution is filled in, every hidden window will have all different values in each cell, so it helps in solving if you know in advance that this is so. Especially on this size grid.

This puzzle's 68 clues are in a fully symmetric pattern, and the puzzle can be solved using singles only. So technically it's "easy"! ;)

Puzzle image:
Hidden Text: Show
Sudoku16-PW-S3.png
Sudoku16-PW-S3.png (37.22 KiB) Viewed 228 times


Puzzle text:
Hidden Text: Show
Code: Select all
 +---------+---------+---------+---------+
 | . C 7 . | . 1 6 . | . 4 8 . | . 5 3 . |
 | 9 . . . | . . . . | . . . . | . . . D |
 | F . 0 . | . . . . | . . . . | . 6 . B |
 | . . . . | . 4 . F | E . 0 . | . . . . |
 +---------+---------+---------+---------+
 | . . . . | . . . . | . . . . | . . . . |
 | A . . 4 | . . 8 . | . 0 . . | 2 . . E |
 | E . . . | . D 2 . | . B 7 . | . . . 5 |
 | . . . B | . . . A | 9 . . . | 1 . . . |
 +---------+---------+---------+---------+
 | . . . 5 | . . . D | C . . . | 0 . . . |
 | 1 . . . | . 6 3 . | . F B . | . . . C |
 | 4 . . D | . . B . | . 1 . . | A . . 2 |
 | . . . . | . . . . | . . . . | . . . . |
 +---------+---------+---------+---------+
 | . . . . | . F . 1 | B . 4 . | . . . . |
 | 6 . 4 . | . . . . | . . . . | . 8 . 1 |
 | C . . . | . . . . | . . . . | . . . 7 |
 | . 3 E . | . 9 D . | . 7 5 . | . F C . |
 +---------+---------+---------+---------+


Solution:
Hidden Text: Show
Code: Select all
 +---------+---------+---------+---------+
 | D C 7 2 | A 1 6 E | F 4 8 B | 9 5 3 0 |
 | 9 1 A 8 | C 2 0 B | 7 3 6 5 | F 4 E D |
 | F 4 0 E | D 3 5 8 | 2 C 1 9 | 7 6 A B |
 | 5 6 B 3 | 7 4 9 F | E A 0 D | C 2 1 8 |
 +---------+---------+---------+---------+
 | 7 2 F 9 | 5 E 1 6 | 4 D C 8 | 3 B 0 A |
 | A 5 1 4 | B C 8 9 | 3 0 F 6 | 2 D 7 E |
 | E 0 C 6 | 3 D 2 4 | 1 B 7 A | 8 9 F 5 |
 | 3 D 8 B | F 0 7 A | 9 5 2 E | 1 C 6 4 |
 +---------+---------+---------+---------+
 | 8 7 2 5 | 1 A E D | C 6 9 4 | 0 3 B F |
 | 1 E 9 A | 4 6 3 0 | 8 F B 2 | D 7 5 C |
 | 4 F 6 D | 9 7 B C | 5 1 3 0 | A E 8 2 |
 | 0 B 3 C | 2 8 F 5 | D E A 7 | 6 1 4 9 |
 +---------+---------+---------+---------+
 | 2 9 5 7 | 6 F A 1 | B 8 4 C | E 0 D 3 |
 | 6 A 4 F | E B C 7 | 0 9 D 3 | 5 8 2 1 |
 | C 8 D 1 | 0 5 4 3 | 6 2 E F | B A 9 7 |
 | B 3 E 0 | 8 9 D 2 | A 7 5 1 | 4 F C 6 |
 +---------+---------+---------+---------+


Grid W-cell assignments:
Hidden Text: Show
Code: Select all
 All cells with the same number belong to the same window:

 +---------+---------+---------+---------+
 | 0 1 1 1 | 1 0 2 2 | 2 2 0 3 | 3 3 3 0 |
 | 4 5 5 5 | 5 4 6 6 | 6 6 4 7 | 7 7 7 4 |
 | 4 5 5 5 | 5 4 6 6 | 6 6 4 7 | 7 7 7 4 |
 | 4 5 5 5 | 5 4 6 6 | 6 6 4 7 | 7 7 7 4 |
 +---------+---------+---------+---------+
 | 4 5 5 5 | 5 4 6 6 | 6 6 4 7 | 7 7 7 4 |
 | 0 1 1 1 | 1 0 2 2 | 2 2 0 3 | 3 3 3 0 |
 | 8 9 9 9 | 9 8 A A | A A 8 B | B B B 8 |
 | 8 9 9 9 | 9 8 A A | A A 8 B | B B B 8 |
 +---------+---------+---------+---------+
 | 8 9 9 9 | 9 8 A A | A A 8 B | B B B 8 |
 | 8 9 9 9 | 9 8 A A | A A 8 B | B B B 8 |
 | 0 1 1 1 | 1 0 2 2 | 2 2 0 3 | 3 3 3 0 |
 | C D D D | D C E E | E E C F | F F F C |
 +---------+---------+---------+---------+
 | C D D D | D C E E | E E C F | F F F C |
 | C D D D | D C E E | E E C F | F F F C |
 | C D D D | D C E E | E E C F | F F F C |
 | 0 1 1 1 | 1 0 2 2 | 2 2 0 3 | 3 3 3 0 |
 +---------+---------+---------+---------+


Grid P-cell assignments:
Hidden Text: Show
Code: Select all
 All cells with the same number belong to the same P-set:

 +---------+---------+---------+---------+
 | 0 1 2 3 | 0 1 2 3 | 0 1 2 3 | 0 1 2 3 |
 | 4 5 6 7 | 4 5 6 7 | 4 5 6 7 | 4 5 6 7 |
 | 8 9 A B | 8 9 A B | 8 9 A B | 8 9 A B |
 | C D E F | C D E F | C D E F | C D E F |
 +---------+---------+---------+---------+
 | 0 1 2 3 | 0 1 2 3 | 0 1 2 3 | 0 1 2 3 |
 | 4 5 6 7 | 4 5 6 7 | 4 5 6 7 | 4 5 6 7 |
 | 8 9 A B | 8 9 A B | 8 9 A B | 8 9 A B |
 | C D E F | C D E F | C D E F | C D E F |
 +---------+---------+---------+---------+
 | 0 1 2 3 | 0 1 2 3 | 0 1 2 3 | 0 1 2 3 |
 | 4 5 6 7 | 4 5 6 7 | 4 5 6 7 | 4 5 6 7 |
 | 8 9 A B | 8 9 A B | 8 9 A B | 8 9 A B |
 | C D E F | C D E F | C D E F | C D E F |
 +---------+---------+---------+---------+
 | 0 1 2 3 | 0 1 2 3 | 0 1 2 3 | 0 1 2 3 |
 | 4 5 6 7 | 4 5 6 7 | 4 5 6 7 | 4 5 6 7 |
 | 8 9 A B | 8 9 A B | 8 9 A B | 8 9 A B |
 | C D E F | C D E F | C D E F | C D E F |
 +---------+---------+---------+---------+
User avatar
Mathimagics
2017 Supporter
 
Posts: 1095
Joined: 27 May 2015

Re: Sudoku 16x16 (PW) Sample

Postby tarek » Sun Jan 06, 2019 2:01 am

Player:
This is a lovely puzzle …

When the puzzle space gets complicated I prefer easier puzzles & therefore the singles only puzzle would also be my preference.

I'm not that good with P puzzles because I don't solve that many & at this grandest of scales means that I have to spend more time even if it's singles because it is a 16x16.

Programmer:
The different layers & symmetry are things I like & would feature in puzzle that I'd create too.

I would avoid using 0 in clues as many machine assistants recognise 0 as empty cells & therefore better for the clues when you present the puzzle to be 1-G & not 0-F

My hardware struggled to generate a minimal puzzle (I just need a better computer & better programming skills :D ). Here is a very difficult 16x16 PW puzzle that shares the same solution as your puzzle:
Hidden Text: Show
With many guesses needed to solve this is not intended to be solved by humans
Code: Select all
+---------+---------+---------+---------+
| . . . 2 | A . . . | . . . . | 9 . . . |
| . 1 . . | . . . . | . 3 . . | . . E . |
| . . . E | D . . . | . . . . | . . . . |
| 5 . . . | . . . F | E . . . | . 2 . 8 |
+---------+---------+---------+---------+
| . . . . | . E . . | . . C . | . B . A |
| . . . . | B . . . | . . . 6 | . . . . |
| . G . . | . . 2 . | . B . . | . . . . |
| . . . B | . . . . | . . . . | 1 . . . |
+---------+---------+---------+---------+
| . . . 5 | . . . . | . . . . | G . . . |
| . . . . | . . 3 . | . F . . | . . 5 . |
| . . . . | 9 . . . | . . . G | . . . . |
| G . 3 . | . 8 . . | . . A . | . . . . |
+---------+---------+---------+---------+
| 2 . 5 . | . . . 1 | B . . . | . . . 3 |
| . . . . | . . . . | . . . 3 | 5 . . . |
| . 8 . . | . . 4 . | . . . . | . . 9 . |
| . . . G | . . . . | . . . 1 | 4 . . . |
+---------+---------+---------+---------+
User avatar
tarek
 
Posts: 2898
Joined: 05 January 2006

Re: Sudoku 16x16 (PW) Sample

Postby enxio27 » Sun Jan 06, 2019 4:09 am

Oh, cool! I've never seen a variant of a 16x16 before! Personally, I prefer to use just letters (A-P) for 16x16 puzzles, but that's down in the noise.
User avatar
enxio27
 
Posts: 484
Joined: 13 November 2007

Re: Sudoku 16x16 (PW) Sample

Postby Mathimagics » Sun Jan 06, 2019 3:37 pm

.
Thanks enxio27 and tarek, for the kind feedback! 8-)

Re: using "1..9A..G"?

I'm a programmer, so when I see something like "29A3G7E" something in my brain clicks, clearly it's a hex string, but what on earth is that "G" doing in there?

So I'm probably leaning more towards enxio27's suggestion of "A...P", and in the one-line specs using lowercase for the jigsaw patterns (I like them to be clearly distinguishable from solution strings).

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

As for solvers, progress is lagging somewhat here. I used VB6 to develop the puzzle, using a generic DLX solver function for testing. Then I built a faster version of this DLX solver in C.

Trickier, and thus not happening real soon, is the job of adapting dobrichev's FSSS2 (128-bit) solver ... it's speed relies on the fact that each cell's vital attributes, "affected cell list" + "house membership list", can be expressed as a 128-bit mask (81 for cells + 9xD for the houses, where D = # of dimensions, ie R,C,B etc).

for 16x16, we need 256 bits for 16x16 just to represent the affected cell list, plus 16xD for the house bits.

But it will happen, eventually …

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

Re: difficulty

All evidence so far suggests that what is EASY in standard Sudoku (eg singles-only) gets progressively less easy (for P&P) as we add dimensions and/or increase the grid size.

Thus, most of those exotic ichthyologically-named solving techniques become less and less relevant, assuming we wish to create puzzles that can be solved with P&P. Increasing grid size and/or dimensions makes most of them either impracticable or not applicable.

tarek has kindly provided a much tougher version of our example puzzle which should serve as a good benchmark for any solver. I say this because my 'C' DLX solver is taking quite a long time to crack it … [Added] it took 2 hours!
User avatar
Mathimagics
2017 Supporter
 
Posts: 1095
Joined: 27 May 2015

Re: Sudoku 16x16 (PW) Sample

Postby hkociemba1 » Wed Jan 16, 2019 1:13 pm

I added support for SudokuW to my SAT-solver, which was very easy since I more or less only had to write the code which adds some clauses to the cnf-file which took a couple of hours. I did not implement code yet which supports basic methods (singles, pairs etc.) for the windows part. So up to now the program works great for solving hard puzzles but is not suited to generate "simple" SudokoW puzzles.

Tareks puzzle took 2.3 s solving time. The PW-puzzle can be reduced further, I reduced it from 48 to 44 givens within maybe 1/2 h. Solving this harder version takes about 4 min, showing uniqueness about 8 min.

Hidden Text: Show
Code: Select all
 +-------------+-------------+-------------+-------------+
 |  .  .  .  2 | 10  .  .  . |  .  .  .  . |  9  .  .  . |
 |  .  1  .  . |  .  .  .  . |  .  3  .  . |  .  . 14  . |
 |  .  .  . 14 | 13  .  .  . |  .  .  .  . |  .  .  .  . |
 |  5  .  .  . |  .  .  . 15 | 14  .  .  . |  .  2  .  8 |
 +-------------+-------------+-------------+-------------+
 |  .  .  .  . |  .  .  .  . |  .  . 12  . |  .  .  . 10 |
 |  .  .  .  . | 11  .  .  . |  .  .  .  6 |  .  .  .  . |
 |  . 16  .  . |  .  .  2  . |  . 11  .  . |  .  .  .  . |
 |  .  .  .  . |  .  .  .  . |  .  .  .  . |  1  .  .  . |
 +-------------+-------------+-------------+-------------+
 |  .  .  .  5 |  .  .  .  . |  .  .  .  . | 16  .  .  . |
 |  .  .  .  . |  .  .  3  . |  . 15  .  . |  .  .  5  . |
 |  .  .  .  . |  9  .  .  . |  .  .  . 16 |  .  .  .  . |
 | 16  .  3  . |  .  8  .  . |  .  . 10  . |  .  .  .  . |
 +-------------+-------------+-------------+-------------+
 |  2  .  .  . |  .  .  .  1 | 11  .  .  . |  .  .  .  3 |
 |  .  .  .  . |  .  .  .  . |  .  .  .  3 |  5  .  .  . |
 |  .  8  .  . |  .  .  4  . |  .  .  .  . |  .  .  9  . |
 |  .  .  . 16 |  .  .  .  . |  .  .  .  1 |  4  .  .  . |
 +-------------+-------------+-------------+-------------+

44 givens, 1846 candidates(pencilmarks)

I wonder how long other solvers need to solve this version. I will see if it is possible to generate a minimal version within a reasonable time.
Btw., the program also works for larger box sizes. In principle the program also works for rectangular box sizes - but I see no way how it could be possible to define windows if the box is not a square, so W-puzzles seem to be restricted to quadratic box sizes.
User avatar
hkociemba1
 
Posts: 58
Joined: 08 August 2018

Re: Sudoku 16x16 (PW) Sample

Postby hkociemba1 » Wed Jan 16, 2019 1:26 pm

Just for fun:

Code: Select all
 +-----+-----+
 | . 4 | . . |
 | 1 . | . . |
 +-----+-----+
 | . . | . . |
 | . 3 | . . |
 +-----+-----+


is a 4x4 grid which is a valid X-Sudoku, a valid PW-Sudoku, but neither a valid P-Sudoku nor a valid W-Sudoku
User avatar
hkociemba1
 
Posts: 58
Joined: 08 August 2018

Re: Sudoku 16x16 (PW) Sample

Postby tarek » Wed Jan 16, 2019 2:04 pm

hkociemba1 wrote:Just for fun:

Code: Select all
 +-----+-----+
 | . 4 | . . |
 | 1 . | . . |
 +-----+-----+
 | . . | . . |
 | . 3 | . . |
 +-----+-----+


is a 4x4 grid which is a valid X-Sudoku, a valid PW-Sudoku, but neither a valid P-Sudoku nor a valid W-Sudoku

As you can see the X constraint will force all candidates that occupy the single W window position to be different & will force from my prelim inspection also the cells in the P positions to be different so in theory a 4x4 Sudoku X is also a sudoku PWX.

You can construct a puzzle where one of those constraints can solve, 2 can solve or only the 3 constraints are needed to solve

tarek
User avatar
tarek
 
Posts: 2898
Joined: 05 January 2006

Re: Sudoku 16x16 (PW) Sample

Postby Mathimagics » Wed Jan 16, 2019 2:43 pm

hkociemba1 wrote:I see no way how it could be possible to define windows if the box is not a square, so W-puzzles seem to be restricted to quadratic box sizes.

I don't think that there is any real barrier to SudokuW for rectangular boxes, we just have to accept that the layout won't be "neat" like we get with square boxes.

If our box size is N x M, then we can always place (N-1) x (M-1) boxes in the interior, but they won't be nicely arranged unless N=M.
Code: Select all
 +---------+---------+---------+
 | . . . . | . . . . | . . . . |
 | . A A A | A . B B | B B . . |
 | . A A A | A . B B | B B . . |
 +---------+---------+---------+
 | . A A A | A . B B | B B . . |
 | . . . . | . . . . | . . . . |
 | . C C C | C . D D | D D . . |
 +---------+---------+---------+
 | . C C C | C . D D | D D . . |
 | . C C C | C . D D | D D . . |
 | . . . . | . . . . | . . . . |
 +---------+---------+---------+
 | . E E E | E . F F | F F . . |
 | . E E E | E . F F | F F . . |
 | . E E E | E . F F | F F . . |
 +---------+---------+---------+

Here we have 2 "blemishes" - we have two columns left over on the RHS, and vertically we find that 2 of the boxes don't overlap the Sudoku boxes.

But these are purely aesthetic considerations. The fundamental principle still applies, I think. There will still be a full set of "hidden windows" implied, and every cell will belong to one of these windows, thus the windows still constitute a proper "dimension" (ie a division of the grid into 12 houses).
User avatar
Mathimagics
2017 Supporter
 
Posts: 1095
Joined: 27 May 2015

Re: Sudoku 16x16 (PW) Sample

Postby Mathimagics » Wed Jan 16, 2019 3:08 pm

hkociemba1 wrote:Tareks puzzle took 2.3 s solving time. The PW-puzzle can be reduced further, I reduced it from 48 to 44 givens within maybe 1/2 h. Solving this harder version takes about 4 min, showing uniqueness about 8 min.


I think that testing/finding for minimal puzzles is going to be a real problem for any solver in a grid of this size, and become practically infeasible for higher levels (eg 25 x 25).

No matter how fast the solver can solve singles-only (strong) puzzles, or even weaker puzzles like tarek's hard example, it will inevitably disover in the general minimal-puzzle testing case that puzzles which are very weak (have very low singles counts) will result in serious time problems.
User avatar
Mathimagics
2017 Supporter
 
Posts: 1095
Joined: 27 May 2015

Re: Sudoku 16x16 (PW) Sample

Postby enxio27 » Wed Jan 16, 2019 11:30 pm

So far, it's all singles and a few pairs, but I messed something up and have to start over. Maybe I'll try it without pencil marks.
User avatar
enxio27
 
Posts: 484
Joined: 13 November 2007

Re: Sudoku 16x16 (PW) Sample

Postby hkociemba1 » Thu Jan 17, 2019 8:59 am

Meanwhile the reducing process finished. With 42 givens the puzzle now is minimal.
Hidden Text: Show
Code: Select all
 
 +-------------+-------------+-------------+-------------+
 |  .  .  .  2 | 10  .  .  . |  .  .  .  . |  9  .  .  . |
 |  .  1  .  . |  .  .  .  . |  .  3  .  . |  .  . 14  . |
 |  .  .  . 14 | 13  .  .  . |  .  .  .  . |  .  .  .  . |
 |  5  .  .  . |  .  .  . 15 | 14  .  .  . |  .  2  .  8 |
 +-------------+-------------+-------------+-------------+
 |  .  .  .  . |  .  .  .  . |  .  . 12  . |  .  .  . 10 |
 |  .  .  .  . | 11  .  .  . |  .  .  .  6 |  .  .  .  . |
 |  . 16  .  . |  .  .  2  . |  . 11  .  . |  .  .  .  . |
 |  .  .  .  . |  .  .  .  . |  .  .  .  . |  1  .  .  . |
 +-------------+-------------+-------------+-------------+
 |  .  .  .  5 |  .  .  .  . |  .  .  .  . | 16  .  .  . |
 |  .  .  .  . |  .  .  3  . |  . 15  .  . |  .  .  5  . |
 |  .  .  .  . |  9  .  .  . |  .  .  . 16 |  .  .  .  . |
 |  .  .  3  . |  .  8  .  . |  .  . 10  . |  .  .  .  . |
 +-------------+-------------+-------------+-------------+
 |  2  .  .  . |  .  .  .  1 | 11  .  .  . |  .  .  .  . |
 |  .  .  .  . |  .  .  .  . |  .  .  .  3 |  5  .  .  . |
 |  .  8  .  . |  .  .  4  . |  .  .  .  . |  .  .  9  . |
 |  .  .  . 16 |  .  .  .  . |  .  .  .  1 |  4  .  .  . |
 +-------------+-------------+-------------+-------------+


42 givens, 1881 candidates(pencilmarks).
Puzzle is minimal- no other givens can be removed.

Solving this puzzle takes less than 2 min, that it is faster than with the 44 givens. So less givens do not automatically lead to longer solving times, there surely is some randomness how "lucky" the SAT-solver is to find the right values for the variables. But that the puzzle is harder is reflected in the time to show uniqueness which takes about 13 min now.
I would not even try to solve this by hand. I tried to "solve" a 25x25 SudokuPW with no givens at all (just to create a valid grid) and it does not seem that the program returns a result. Is there some different easy construction to generate a valid N^2*N^2 SudokuPW grid?

Concerning the SudokoW with rectangular boxsizes: The irregular positions of the proposed windows within the puzzle are not nice from an aesthetic point of view so I do not think it is fruitful to pursue this idea further.
User avatar
hkociemba1
 
Posts: 58
Joined: 08 August 2018

Re: Sudoku 16x16 (PW) Sample

Postby tarek » Thu Jan 17, 2019 3:26 pm

Hi hkociemba1,

Great work. Certainly even SAT struggles in the bigger Puzzle space but should be quicker that our regular Recursive solvers. I'm confident that your solver would be at a prime position to reduce the minimum number of clues known for some of the valid popular bigger puzzles like 16x16, 25x25 sudoko & Samurai

Solving an empty grid should give you multiple puzzles. I'm not expert on how you code your SAT instances but my feeling is that there could be a mixup/mistake in coding the constraints that resulted in a no solution.

BTW could you use a single Symbol per clue 1-G or A-P as it makes it easier to copy/paste?

Thanks

tarek
User avatar
tarek
 
Posts: 2898
Joined: 05 January 2006

Re: Sudoku 16x16 (PW) Sample

Postby Mathimagics » Thu Jan 17, 2019 3:59 pm

Fine work, guys!

It's certainly true about the phenomenon of "getting lucky" with SAT, I've noticed it too. And of course you can get different luck with different SAT solvers, they are not all the same ...

Anyway, I will try and find a 25x25 SudokuPW grid for hkociemba1

BTW: Just noticed some guy at Andrew Stuart's SudokuWiki website who mentioned he was playing with low-clue SudokuPWX puzzles (9x9)!

We are not alone, it seems … 8-)
User avatar
Mathimagics
2017 Supporter
 
Posts: 1095
Joined: 27 May 2015

Re: Sudoku 16x16 (PW) Sample

Postby hkociemba1 » Thu Jan 17, 2019 6:43 pm

hkociemba1 wrote:Great work. Certainly even SAT struggles in the bigger Puzzle space but should be quicker that our regular Recursive solvers. I'm confident that your solver would be at a prime position to reduce the minimum number of clues known for some of the valid popular bigger puzzles like 16x16, 25x25 sudoko & Samurai
Thanks. I put the new windows program version http://kociemba.org/themen/sudoku/program.html here. My program does not support Samurai though.
Mathimagics wrote:Anyway, I will try and find a 25x25 SudokuPW grid for hkociemba1 …
Thanks for trying. I am very sure that the constraints are coded correctly. It just seems to be very hard to find a correct PW-grid.
User avatar
hkociemba1
 
Posts: 58
Joined: 08 August 2018

Re: Sudoku 16x16 (PW) Sample

Postby blue » Thu Jan 17, 2019 6:50 pm

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..."

Have fun,
Blue.

PS: This is a 25x25 PWX grid (1-9,A-P), found using that method:
Hidden Text: Show
Code: Select all
+-----------+-----------+-----------+-----------+-----------+
| 5 4 3 2 1 | 6 7 9 A 8 | C D E B F | J H I K G | L N M P O |
| 9 A 6 7 8 | B C D E F | G J K I H | O P L M N | 4 5 2 1 3 |
| B D F E C | G J K I H | O L P M N | 4 5 2 1 3 | 6 9 A 8 7 |
| G H I J K | O L N M P | 2 4 5 3 1 | 8 9 A 6 7 | E C B F D |
| O L N M P | 4 2 1 3 5 | A 9 8 7 6 | B C F E D | K I G J H |
+-----------+-----------+-----------+-----------+-----------+
| 4 1 5 3 2 | 9 A 7 8 6 | B C F E D | G K J I H | O P L M N |
| 6 9 A 8 7 | C D F B E | I H J K G | M L N P O | 5 2 4 3 1 |
| F E B C D | J K I H G | L N M O P | 1 3 4 5 2 | 7 6 9 A 8 |
| J G K I H | L N P O M | 3 1 4 5 2 | 9 7 6 A 8 | D E F C B |
| L N P O M | 1 3 2 5 4 | 9 7 6 8 A | E F D C B | G J K H I |
+-----------+-----------+-----------+-----------+-----------+
| 1 5 2 4 3 | 7 9 8 6 A | E F D C B | K J H G I | M O N L P |
| 7 6 8 A 9 | F E B C D | J K H G I | L N M O P | 3 4 1 5 2 |
| C F E D B | H I G K J | N M L P O | 2 4 5 3 1 | A 8 7 6 9 |
| I J H K G | M P O L N | 5 3 1 2 4 | A 8 9 7 6 | B F C D E |
| M P O N L | 3 5 4 1 2 | 8 A 9 6 7 | C D B F E | J G H I K |
+-----------+-----------+-----------+-----------+-----------+
| 3 2 1 5 4 | A 8 6 7 9 | D B C F E | H I G J K | P M O N L |
| A 8 7 9 6 | D B E F C | H I G J K | P M O N L | 1 3 5 2 4 |
| D B C F E | I H J G K | M P O N L | 5 1 3 2 4 | 9 A 8 7 6 |
| H K J G I | N M L P O | 4 5 2 1 3 | 6 A 7 8 9 | C B D E F |
| P O M L N | 2 1 5 4 3 | 6 8 7 A 9 | F B E D C | H K I G J |
+-----------+-----------+-----------+-----------+-----------+
| 2 3 4 1 5 | 8 6 A 9 7 | F E B D C | I G K H J | N L P O M |
| 8 7 9 6 A | E F C D B | K G I H J | N O P L M | 2 1 3 4 5 |
| E C D B F | K G H J I | P O N L M | 3 2 1 4 5 | 8 7 6 9 A |
| K I G H J | P O M N L | 1 2 3 4 5 | 7 6 8 9 A | F D E B C |
| N M L P O | 5 4 3 2 1 | 7 6 A 9 8 | D E C B F | I H J K G |
+-----------+-----------+-----------+-----------+-----------+

PPS: This grid is 25x25 PW (not PWX), but it's a more random looking grid.
Hidden Text: Show
Code: Select all
+-----------+-----------+-----------+-----------+-----------+
| 6 F K 8 9 | 5 H 4 2 1 | A N B G D | 3 C I E L | 7 J O P M |
| J 3 7 H D | 8 9 B G E | K F I 6 5 | 1 A O P M | L 4 2 C N |
| M B O L I | J A C N D | 2 1 4 P 3 | F 7 9 H 8 | 6 E K G 5 |
| 2 E N 1 P | M K L 3 I | 7 H O C J | D G 4 6 5 | 9 B A F 8 |
| C G 5 A 4 | F 7 O 6 P | M 9 L 8 E | 2 N K B J | H 1 D I 3 |
+-----------+-----------+-----------+-----------+-----------+
| 1 K 2 6 C | 9 G 5 4 A | J 8 F B I | L M H D N | P 3 7 O E |
| 9 L H 7 A | 3 J F E 8 | C P D O 1 | 6 2 5 I B | 4 N G M K |
| D M F E J | C P I B N | G L 3 K 7 | 9 4 8 1 O | 5 H 6 A 2 |
| 5 I 8 G O | 1 M H 7 K | 6 4 9 2 N | C P 3 A E | J D F B L |
| B 4 3 P N | L 6 2 D O | 5 M H E A | G J F 7 K | 1 8 I 9 C |
+-----------+-----------+-----------+-----------+-----------+
| 8 A D K 5 | 2 4 1 9 3 | F E G I H | M B 6 J 7 | C P L N O |
| F H 9 B 6 | 7 E A 8 J | P C K D O | 5 1 L N 2 | G M 3 4 I |
| N C G O E | B F D I L | 3 J 5 7 M | P K A 4 9 | 8 2 H 6 1 |
| I 1 M J 3 | G N K P H | L 2 6 9 4 | 8 F D O C | B 7 5 E A |
| 7 P 4 2 L | O C M 5 6 | N A 8 1 B | I E G 3 H | K F 9 J D |
+-----------+-----------+-----------+-----------+-----------+
| G 9 E 5 8 | I 2 3 1 4 | B 7 M A K | H 6 C F P | D O N L J |
| H 6 C F 7 | A B 8 J 9 | D I E 5 L | N O M K 4 | 2 G 1 3 P |
| L N B D K | H 5 E F C | O G 1 J P | 7 3 2 9 A | I 6 M 8 4 |
| 3 J I 4 1 | P O G K M | H 6 2 N 9 | E L B 8 D | F A C 5 7 |
| A O P M 2 | 6 D N L 7 | 8 3 C 4 F | J 5 1 G I | E K B H 9 |
+-----------+-----------+-----------+-----------+-----------+
| 4 5 A 3 B | K 1 9 C G | E D J H 2 | O I P M 6 | N L 8 7 F |
| O 7 J 9 G | E 8 6 A F | I K P L C | B D N 2 3 | M 5 4 1 H |
| E D L C H | 4 I P M B | 1 O N 3 G | K 8 7 5 F | A 9 J 2 6 |
| K 8 1 I F | N 3 J H 2 | 4 5 7 M 6 | A 9 E L G | O C P D B |
| P 2 6 N M | D L 7 O 5 | 9 B A F 8 | 4 H J C 1 | 3 I E K G |
+-----------+-----------+-----------+-----------+-----------+

It was made by producing a grid using the method above, and then repeatedly, clearing the clues in 11 or 12 consecutive columns, and letting the solver find its own solution. After a while, I switched up and did consecutive rows too.
At first, 12 rows was "too much" for quick SAT solution -- maybe 12 columns too (?), initially.
blue
 
Posts: 771
Joined: 11 March 2013

Next

Return to Sudoku variants