Minimum givens on larger puzzles

Everything about Sudoku that doesn't fit in one of the other sections

Re: Minimum givens on larger puzzles

Postby m_b_metcalf » Fri Aug 31, 2018 10:24 am

qiuyanzhe wrote:An obvious 25*25 is like this:
[snip]
just like the minimal grid in Latin Squares. It has 156 givens.

Very nice. Here's a more readable version:
Code: Select all
  1  2  3  4  5  6  7  8  9 10 11 12  .  .  .  .  .  .  .  .  .  .  .  .  .
  6  7  8  9 10 11 12  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
 11 12  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  . 25 24 23
  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  . 25 24 23 22 21 20 19 18
  2  3  4  5  6  7  8  9 10 11 12  .  .  .  .  .  .  .  .  .  .  .  .  .  .
  7  8  9 10 11 12  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
 12  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  . 25 24 23 22
  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  . 25 24 23 22 21 20 19 18 17
  3  4  5  6  7  8  9 10 11 12  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
  8  9 10 11 12  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  . 25 24 23 22 21
  .  .  .  .  .  .  .  .  .  .  .  .  .  .  . 25 24 23 22 21 20 19 18 17 16
  4  5  6  7  8  9 10 11 12  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
  9 10 11 12  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  . 25
  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  . 25 24 23 22 21 20
  .  .  .  .  .  .  .  .  .  .  .  .  .  . 25 24 23 22 21 20 19 18 17 16 15
  5  6  7  8  9 10 11 12  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
 10 11 12  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  . 25 24
  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  . 25 24 23 22 21 20 19
  .  .  .  .  .  .  .  .  .  .  .  .  . 25 24 23 22 21 20 19 18 17 16 15 14
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 9383
Joined: 15 May 2006
Location: Berlin

Re: Minimum givens on larger puzzles

Postby hkociemba1 » Fri Sep 07, 2018 1:17 am

qiuyanzhe's method is really a great improvement compared to what I did. Very nice. An adaption to the default grid I use now also gives Floor(N^2/4) clues, here the cases N=16 and N=25.
Code: Select all
 +-------------+-------------+-------------+-------------+
 |  1  2  3  4 |  5  6  7  . |  .  .  .  . |  .  .  .  . |
 |  5  6  7  . |  .  .  .  . |  .  .  .  . |  .  .  .  . |
 |  .  .  .  . |  .  .  .  . |  .  .  .  . |  .  .  .  8 |
 |  .  .  .  . |  .  .  .  . |  .  .  .  8 |  9 10 11 12 |
 +-------------+-------------+-------------+-------------+
 |  2  3  4  5 |  6  7  .  . |  .  .  .  . |  .  .  .  . |
 |  6  7  .  . |  .  .  .  . |  .  .  .  . |  .  .  .  . |
 |  .  .  .  . |  .  .  .  . |  .  .  .  . |  .  .  8  9 |
 |  .  .  .  . |  .  .  .  . |  .  .  8  9 | 10 11 12 13 |
 +-------------+-------------+-------------+-------------+
 |  3  4  5  6 |  7  .  .  . |  .  .  .  . |  .  .  .  . |
 |  7  .  .  . |  .  .  .  . |  .  .  .  . |  .  .  .  . |
 |  .  .  .  . |  .  .  .  . |  .  .  .  . |  .  8  9 10 |
 |  .  .  .  . |  .  .  .  . |  .  8  9 10 | 11 12 13 14 |
 +-------------+-------------+-------------+-------------+
 |  4  5  6  7 |  .  .  .  . |  .  .  .  . |  .  .  .  . |
 |  .  .  .  . |  .  .  .  . |  .  .  .  . |  .  .  .  . |
 |  .  .  .  . |  .  .  .  . |  .  .  .  . |  8  9 10 11 |
 |  .  .  .  . |  .  .  .  . |  8  9 10 11 | 12 13 14 15 |
 +-------------+-------------+-------------+-------------+
64 givens, 1706 candidates(pencilmarks).

+----------------+----------------+----------------+----------------+----------------+
 |  1  2  3  4  5 |  6  7  8  9 10 | 11 12  .  .  . |  .  .  .  .  . |  .  .  .  .  . |
 |  6  7  8  9 10 | 11 12  .  .  . |  .  .  .  .  . |  .  .  .  .  . |  .  .  .  .  . |
 | 11 12  .  .  . |  .  .  .  .  . |  .  .  .  .  . |  .  .  .  .  . |  .  .  .  .  . |
 |  .  .  .  .  . |  .  .  .  .  . |  .  .  .  .  . |  .  .  .  .  . |  .  . 13 14 15 |
 |  .  .  .  .  . |  .  .  .  .  . |  .  .  .  .  . |  .  . 13 14 15 | 16 17 18 19 20 |
 +----------------+----------------+----------------+----------------+----------------+
 |  2  3  4  5  6 |  7  8  9 10 11 | 12  .  .  .  . |  .  .  .  .  . |  .  .  .  .  . |
 |  7  8  9 10 11 | 12  .  .  .  . |  .  .  .  .  . |  .  .  .  .  . |  .  .  .  .  . |
 | 12  .  .  .  . |  .  .  .  .  . |  .  .  .  .  . |  .  .  .  .  . |  .  .  .  .  . |
 |  .  .  .  .  . |  .  .  .  .  . |  .  .  .  .  . |  .  .  .  .  . |  . 13 14 15 16 |
 |  .  .  .  .  . |  .  .  .  .  . |  .  .  .  .  . |  . 13 14 15 16 | 17 18 19 20 21 |
 +----------------+----------------+----------------+----------------+----------------+
 |  3  4  5  6  7 |  8  9 10 11 12 |  .  .  .  .  . |  .  .  .  .  . |  .  .  .  .  . |
 |  8  9 10 11 12 |  .  .  .  .  . |  .  .  .  .  . |  .  .  .  .  . |  .  .  .  .  . |
 |  .  .  .  .  . |  .  .  .  .  . |  .  .  .  .  . |  .  .  .  .  . |  .  .  .  .  . |
 |  .  .  .  .  . |  .  .  .  .  . |  .  .  .  .  . |  .  .  .  .  . | 13 14 15 16 17 |
 |  .  .  .  .  . |  .  .  .  .  . |  .  .  .  .  . | 13 14 15 16 17 | 18 19 20 21 22 |
 +----------------+----------------+----------------+----------------+----------------+
 |  4  5  6  7  8 |  9 10 11 12  . |  .  .  .  .  . |  .  .  .  .  . |  .  .  .  .  . |
 |  9 10 11 12  . |  .  .  .  .  . |  .  .  .  .  . |  .  .  .  .  . |  .  .  .  .  . |
 |  .  .  .  .  . |  .  .  .  .  . |  .  .  .  .  . |  .  .  .  .  . |  .  .  .  . 13 |
 |  .  .  .  .  . |  .  .  .  .  . |  .  .  .  .  . |  .  .  .  . 13 | 14 15 16 17 18 |
 |  .  .  .  .  . |  .  .  .  .  . |  .  .  .  . 13 | 14 15 16 17 18 | 19 20 21 22 23 |
 +----------------+----------------+----------------+----------------+----------------+
 |  5  6  7  8  9 | 10 11 12  .  . |  .  .  .  .  . |  .  .  .  .  . |  .  .  .  .  . |
 | 10 11 12  .  . |  .  .  .  .  . |  .  .  .  .  . |  .  .  .  .  . |  .  .  .  .  . |
 |  .  .  .  .  . |  .  .  .  .  . |  .  .  .  .  . |  .  .  .  .  . |  .  .  . 13 14 |
 |  .  .  .  .  . |  .  .  .  .  . |  .  .  .  .  . |  .  .  . 13 14 | 15 16 17 18 19 |
 |  .  .  .  .  . |  .  .  .  .  . |  .  .  . 13 14 | 15 16 17 18 19 | 20 21 22 23 24 |
 +----------------+----------------+----------------+----------------+----------------+
156 givens, 6567 candidates(pencilmarks).

The method even works for rectangular boxes, here a 3x4 and 5x3 box. The number of clues for NxM boxes is Floor(N^2*M^2/4)

Code: Select all
 +-------------+-------------+-------------+
 |  1  2  3  4 |  5  .  .  . |  .  .  .  . |
 |  5  .  .  . |  .  .  .  . |  .  .  .  . |
 |  .  .  .  . |  .  .  .  . |  .  6  7  8 |
 +-------------+-------------+-------------+
 |  2  3  4  5 |  .  .  .  . |  .  .  .  . |
 |  .  .  .  . |  .  .  .  . |  .  .  .  . |
 |  .  .  .  . |  .  .  .  . |  6  7  8  9 |
 +-------------+-------------+-------------+
 |  3  4  5  . |  .  .  .  . |  .  .  .  . |
 |  .  .  .  . |  .  .  .  . |  .  .  .  6 |
 |  .  .  .  . |  .  .  .  6 |  7  8  9 10 |
 +-------------+-------------+-------------+
 |  4  5  .  . |  .  .  .  . |  .  .  .  . |
 |  .  .  .  . |  .  .  .  . |  .  .  6  7 |
 |  .  .  .  . |  .  .  6  7 |  8  9 10 11 |
 +-------------+-------------+-------------+
36 givens, 710 candidates(pencilmarks).

 +----------+----------+----------+----------+----------+
 |  1  2  3 |  4  5  6 |  7  .  . |  .  .  . |  .  .  . |
 |  4  5  6 |  7  .  . |  .  .  . |  .  .  . |  .  .  . |
 |  7  .  . |  .  .  . |  .  .  . |  .  .  . |  .  .  . |
 |  .  .  . |  .  .  . |  .  .  . |  .  .  . |  .  8  9 |
 |  .  .  . |  .  .  . |  .  .  . |  .  8  9 | 10 11 12 |
 +----------+----------+----------+----------+----------+
 |  2  3  4 |  5  6  7 |  .  .  . |  .  .  . |  .  .  . |
 |  5  6  7 |  .  .  . |  .  .  . |  .  .  . |  .  .  . |
 |  .  .  . |  .  .  . |  .  .  . |  .  .  . |  .  .  . |
 |  .  .  . |  .  .  . |  .  .  . |  .  .  . |  8  9 10 |
 |  .  .  . |  .  .  . |  .  .  . |  8  9 10 | 11 12 13 |
 +----------+----------+----------+----------+----------+
 |  3  4  5 |  6  7  . |  .  .  . |  .  .  . |  .  .  . |
 |  6  7  . |  .  .  . |  .  .  . |  .  .  . |  .  .  . |
 |  .  .  . |  .  .  . |  .  .  . |  .  .  . |  .  .  8 |
 |  .  .  . |  .  .  . |  .  .  . |  .  .  8 |  9 10 11 |
 |  .  .  . |  .  .  . |  .  .  8 |  9 10 11 | 12 13 14 |
 +----------+----------+----------+----------+----------+
56 givens, 1427 candidates(pencilmarks).


It seems that you can solve all these grids by either naked singles or also by hidden singles only.
User avatar
hkociemba1
 
Posts: 33
Joined: 08 August 2018

Previous

Return to General