The New Sudoku Players' Forum

[mwalimu]

What is the minimum number of givens that a well-formed 16*16 puzzle could have? How about a 12*12 (with 3*4 blocks)?

[Pat]

What is the minimum number of givens that a well-formed 16*16 puzzle could have?

for a box-size of 4x4,
gsf (2006.Feb.10) reports a 77-clue puzzle

[gsf]

for a box-size of 4x4,
gsf (2006.Feb.10) reports a 77-clue puzzle

here is one of three from around that time

Code: Select all

5...|3...|.BF.|4..8
...4|..D6|..E.|...3
..1.|...2|....|....
.6..|5...|..21|....
----+----+----+----
.F.3|.1..|.7.2|.6..
.C4.|A7.B|...5|E...
.2..|..4.|6D..|378.
8...|.C..|.4..|.9D1
----+----+----+----
....|....|..46|B.72
D..5|..A3|C...|....
4...|....|.37.|1..6
..A8|...D|....|.F.4
----+----+----+----
.8..|.51.|.2..|....
.A6.|....|7..3|F...
....|4.C.|.5..|..3.
....|....|..1.|....


[Pat]

here is one of three from around that time

thanks, gsf,
3 are better than 1 --
how many minimal puzzles did you generate in order to find 3 77s?

and was the maximum number of clues still 93?
the maximum number of clues is also of interest!

. - . - . - . - . - . - . - . - . - . - . - . - . - . - . - . - . - . - . - . - . - . - . - . - . - . - . - . - . - . - . - . - . - . - . - . - . - . - . - . - . - . - . - . - .
update 2011 -- great news --
T_Shirakawa (2011.May.7) has posted one with only 56 cells given

~ Pat

[ton]

Here is one with 55 clues.
http://www.amazon.co.jp/dp/4873102235

[coloin]

I cant verify that 55-puzzle -
However it has highlighted the fact that we lost the thread in the programmers forum - where the 56-puzzles were published.
I think tarek had a backup.
C

[m_b_metcalf]

Here is one with 55 clues.
http://www.amazon.co.jp/dp/4873102235

I had big problems reading the puzzle, but with some aid, finally got it right:

Code: Select all

  .  .  .  9  .  .  .  .  .  3  .  .  .  .  .  2
  .  .  .  . 15  .  . 12 16  .  .  .  . 10  .  8
  .  4  .  5  .  .  .  .  .  9  .  .  .  .  .  .
  .  .  .  .  .  .  . 10  .  . 13  .  .  .  . 15
  .  .  8  .  .  .  .  .  .  .  .  .  .  .  . 16
  .  .  .  .  .  5  .  .  .  .  .  .  .  .  .  .
 10  . 15  .  .  .  .  .  .  .  .  .  .  .  . 12
  .  .  .  .  . 13  9  .  .  4  .  .  .  .  7  .
  .  .  .  . 16  .  . 14  .  .  .  .  .  .  .  .
  .  5  .  4  .  .  .  .  .  7  . 11  1 13  9  .
  .  .  .  3  .  .  .  .  .  1  .  .  5  .  4  .
  .  .  .  . 10  .  . 15  .  .  .  .  .  .  .  .
 15  . 16  .  .  .  .  .  8  . 10  .  .  .  . 14
  .  .  .  .  .  1  4  .  .  .  .  .  2  .  5  .
  8  .  .  .  .  .  .  . 12  . 16  .  .  .  .  .
  .  .  .  .  .  9  7  3  .  .  .  .  .  .  1  .

It's fairly easy and the solution is below.

HTH

Mike Metcalf

Hidden Text: Show

13 15 12 9 5 8 16 4 6 3 14 10 7 1 11 2
1 14 7 2 15 6 13 12 16 11 4 5 9 10 3 8
6 4 10 5 7 11 3 1 15 9 2 8 14 12 16 13
3 16 11 8 9 14 2 10 1 12 13 7 4 5 6 15
5 7 8 11 4 15 12 6 3 10 1 2 13 9 14 16
4 13 9 12 2 5 10 11 7 16 6 14 8 3 15 1
10 1 15 6 3 16 14 7 5 8 9 13 11 4 2 12
14 2 3 16 1 13 9 8 11 4 12 15 10 6 7 5
7 8 6 15 16 3 1 14 4 13 5 9 12 2 10 11
16 5 14 4 6 12 8 2 10 7 15 11 1 13 9 3
12 10 2 3 13 7 11 9 14 1 8 16 5 15 4 6
9 11 1 13 10 4 5 15 2 6 3 12 16 14 8 7
15 9 16 1 11 2 6 13 8 5 10 4 3 7 12 14
11 6 13 14 12 1 4 16 9 15 7 3 2 8 5 10
8 3 4 7 14 10 15 5 12 2 16 1 6 11 13 9
2 12 5 10 8 9 7 3 13 14 11 6 15 16 1 4

Edit: attached file corrected.

[Pat]

we lost the thread in the programmers forum - where the 56-puzzles were published.

i did save the 56
but if methods were discussed i have no recollection

56 cells given — posted by T_Shirakawa (2011.May.7): Show

Code: Select all


 .  .  5  .  4  3  .  .  .  .  2  .  .  .  .  .
 4  .  3  .  .  5  .  .  .  . 10  .  .  .  .  9
 .  .  .  .  .  .  .  .  .  .  .  6  7  .  .  8
 .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
 . 15  .  .  . 11  .  .  . 12  .  9  6  .  .  .
 .  6  .  9  .  .  .  .  7 13  .  8 12  .  .  .
 .  .  .  . 14  .  .  .  .  .  .  .  .  .  .  .
 2  .  .  .  5  4  .  .  .  .  .  .  . 11  .  .
 .  .  .  .  .  .  1  . 11  4  5  .  .  3  .  .
 .  .  .  .  .  .  8  .  .  .  3  .  .  4  .  .
 .  9  .  6 13  .  7 12  .  .  .  .  .  .  .  .
 .  7  .  .  .  .  6  .  .  .  .  .  .  .  .  .
11  .  .  .  . 10  .  .  .  .  .  .  .  5  3  .
 .  .  .  .  .  . 12  .  .  .  . 13  .  .  .  .
 .  .  . 13  .  .  9  8 12 16  .  7  .  .  .  .
 .  .  .  .  .  .  .  .  .  .  .  .  .  2  .  .



[Pat]

What is the minimum number of givens that a 16*16 puzzle could have?

How about a 12*12 (with 3*4 blocks)?

Here is one with 55 clues.
http://www.amazon.co.jp/dp/4873102235

55: Show

Code: Select all

  .  .  .  9  .  .  .  .  .  3  .  .  .  .  .  2
  .  .  .  . 15  .  . 12 16  .  .  .  . 10  .  8
  .  4  .  5  .  .  .  .  .  9  .  .  .  .  .  .
  .  .  .  .  .  .  . 10  .  . 13  .  .  .  . 15
  .  .  8  .  .  .  .  .  .  .  .  .  .  .  . 16
  .  .  .  .  .  5  .  .  .  .  .  .  .  .  .  .
 10  . 15  .  .  .  .  .  .  .  .  .  .  .  . 12
  .  .  .  .  . 13  9  .  .  4  .  .  .  .  7  .
  .  .  .  . 16  .  . 14  .  .  .  .  .  .  .  .
  .  5  .  4  .  .  .  .  .  7  . 11  1 13  9  .
  .  .  .  3  .  .  .  .  .  1  .  .  5  .  4  .
  .  .  .  . 10  .  . 15  .  .  .  .  .  .  .  .
 15  . 16  .  .  .  .  .  8  . 10  .  .  .  . 14
  .  .  .  .  .  1  4  .  .  .  .  .  2  .  5  .
  8  .  .  .  .  .  .  . 12  . 16  .  .  .  .  .
  .  .  .  .  .  9  7  3  .  .  .  .  .  .  1  .

that's for box=4x4
( puzzle of 16-squared cells )

what do we know about box=3x4
( puzzle of 12-squared cells ) ??

[ton]

10x10(2x5), 22-clue

Code: Select all

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

12x12(2x6), 32-clue

Code: Select all

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

12x12(3x4), 30-clue

Code: Select all

+------------+------------+------------+
|  .  .  .  .|  .  .  .  2|  .  .  .  .|
|  .  .  .  .|  .  .  5 11|  .  .  .  3|
|  7  .  9  .|  .  .  .  .|  .  . 10  .|
+------------+------------+------------+
|  .  5  .  2|  .  .  .  .|  .  .  .  .|
|  .  .  .  6|  .  .  .  .|  .  .  8  .|
|  .  .  .  .|  .  .  .  .| 10  9  7  .|
+------------+------------+------------+
|  .  .  . 11|  .  .  .  .|  . 12  .  2|
|  .  .  .  .|  8 10  .  1|  .  .  .  .|
|  .  .  .  .|  9  7  .  .|  .  .  .  4|
+------------+------------+------------+
| 10  .  7  .|  1  .  .  .|  .  .  .  .|
| 12  .  .  .|  .  .  .  .|  .  .  .  .|
|  .  .  .  .|  .  .  .  3|  .  2  .  5|
+------------+------------+------------+

15x15(3x5), 48-clue

Code: Select all

+---------------+---------------+---------------+
|  .  .  .  .  .|  .  .  .  1  .| 11  .  9  .  .|
|  . 12 10  .  .|  .  .  8  2  .|  .  .  7  .  .|
|  7  .  .  .  .|  .  .  .  .  .|  5  . 15  .  6|
+---------------+---------------+---------------+
|  .  .  .  .  .|  9 11  .  .  7|  4  .  .  .  .|
|  . 10 12  .  .|  6  .  .  .  .|  .  .  .  .  .|
|  .  8  2  .  .|  .  .  .  .  .|  .  .  .  3  .|
+---------------+---------------+---------------+
|  4  .  .  .  .|  .  .  .  .  .|  .  .  .  .  .|
|  .  .  .  .  .|  .  . 12  3  .|  .  2  . 13  .|
| 11  .  .  5  9|  .  .  .  .  .|  6  .  .  .  .|
+---------------+---------------+---------------+
|  .  .  .  .  .|  .  .  .  .  .|  .  .  . 10  .|
|  .  .  3  .  .|  .  .  .  .  .|  . 14  .  2  .|
|  9  .  .  .  .| 11  .  .  .  .|  .  .  .  .  .|
+---------------+---------------+---------------+
|  .  .  .  .  .|  . 12  2  8 10|  .  .  .  .  .|
|  6  .  . 15 11|  .  .  .  .  .|  9  .  5  .  .|
|  5  .  .  .  .|  .  .  . 13  .|  .  .  .  .  .|
+---------------+---------------+---------------+

[hkociemba1]

In the discussion here http://forum.enjoysudoku.com/giant-sudoku-s-16x16-25x25-36x36-100x100-t6578-150.html#p269539 puzzles for arbitrary N^2xN^2 sudoku are constructed which fill about 3/8 of the grid cells for N->infinity. This surely is not the minimum but I know of no other method which gives an estimation for arbitrary sizes.

[Pat]

for arbitrary N^2xN^2 sudoku---

so, would you care to try box-size 5x5 ?
( puzzle of 25-squared cells )

i wonder, what's the chance that this gets a response from ton

[m_b_metcalf]

for arbitrary N^2xN^2 sudoku---

so, would you care to try box-size 5x5 ?
( puzzle of 25-squared cells )

i wonder, what's the chance that this gets a response from ton

This is what I came up with quickly:

Code: Select all

  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  . 16 17 18 19 20
  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  6  7  8  9 10 11 12 13 14 15
  .  .  .  .  .  .  .  .  .  . 21 22 23 24 25  1  2  3  4  5  .  .  .  .  .
  .  .  .  .  . 11 12 13 14 15 16 17 18 19 20  .  .  .  .  .  .  .  .  .  .
  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  . 15 16 17 18 19
  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  5  6  7  8  9 10 11 12 13 14
  .  .  .  .  .  .  .  .  .  . 20 21 22 23 24 25  1  2  3  4  .  .  .  .  .
  .  .  .  .  9 10 11 12 13  . 15 16 17 18 19  .  .  .  . 24  .  .  .  .  .
  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  . 17 18  .  .  .  .  .
  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  . 14 15 16  .  .
  .  .  .  . 18  .  .  .  .  .  .  .  .  .  .  4  5  6  7  8  9 10 11 12 13
  .  .  . 12  .  .  .  .  .  . 19 20 21 22 23 24 25  1  2  3  .  .  .  7  8
  .  .  .  .  8  9 10 11  . 13 14 15 16 17  .  . 20  . 22  .  .  .  .  .  .
  .  .  .  .  .  .  .  .  .  .  .  .  .  . 12  .  . 15 16 17  .  .  .  . 22
  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  . 13 14  .  .  .
  .  .  .  . 17  .  .  .  .  .  .  .  .  .  .  3  4  5  6  7  8  9 10 11  .
  .  . 10 11  .  .  .  .  .  . 18 19 20 21 22 23 24 25  1  2  .  .  5  6  .
  .  .  .  .  7  8  9  .  . 12 13 14 15 16 17  . 19 20 21  .  .  .  .  .  .
  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  . 13 14 15  .  .  .  . 20 21
  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  . 12  .  .  .  .
  .  .  . 15 16  .  .  .  .  .  .  .  .  .  .  2  3  4  5  6  7  8  9  .  .
  .  8  9 10  .  .  .  .  .  . 17 18 19 20 21 22 23 24 25  1  .  3  4  5  6
  .  .  .  .  6  7  .  .  . 11 12 13 14  .  .  . 18 19 20 21  .  . 24 25  1

 No. fixed: 200

[coloin]

Being a simple soul the 3x3 and 9x9 is confusing !!! - 3x3 being clues in the box and 9x9 being the perimeter cells describing the sudoku puzzle we all know ...
however, when describing bigger puzzles it is not totally clear
is there a better way we can describe the layout of these puzzles - actually ton does it quite well .......

hkociemba1 has developed a way of easily removing clues from a canonical grid and got puzzles approaching the minimum
and gave us the 185 clue puzzle

Code: Select all

puzzle         generated      smallest puzzle found to date
9x9[3x3]        21 clues      [17 clues]    [20 in the MC grid]
16x16[4x4]      86 clues      [55 clues]
25x25[5x5]     185 clues      [185 clues]
........
400x400 [20x20]

[qiuyanzhe]

An obvious 25*25 is like this:

Code: Select all

123456789ABC.............
6789ABC..................
BC.......................
......................ONM
.................ONMLKJIH
23456789ABC..............
789ABC...................
C........................
.....................ONML
................ONMLKJIHG
3456789ABC...............
89ABC....................
.........................
....................ONMLK
...............ONMLKJIHGF
456789ABC................
9ABC.....................
........................O
...................ONMLKJ
..............ONMLKJIHGFE
56789ABC.................
ABC......................
.......................ON
..................ONMLKJI
.............ONMLKJIHGFED


just like the minimal grid in Latin Squares. It has 156 givens.
For any size it has floor(n^2/4) givens.