Minimum givens on larger puzzles

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

Minimum givens on larger puzzles

Postby mwalimu » Tue Sep 05, 2006 11:15 pm

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)?
mwalimu
 
Posts: 1
Joined: 27 August 2006

re: Minimum givens on larger puzzles

Postby Pat » Wed Sep 06, 2006 10:23 am

mwalimu wrote: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
User avatar
Pat
 
Posts: 3653
Joined: 18 July 2005

Re: re: Minimum givens on larger puzzles

Postby gsf » Wed Sep 06, 2006 3:46 pm

Pat wrote: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.|....
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

re: 4x4 with 77 clues

Postby Pat » Mon Sep 18, 2006 12:59 pm

gsf wrote: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
User avatar
Pat
 
Posts: 3653
Joined: 18 July 2005

Re: Minimum givens on larger puzzles

Postby ton » Wed Apr 01, 2015 2:15 am

Here is one with 55 clues.
http://www.amazon.co.jp/dp/4873102235
ton
 
Posts: 3
Joined: 26 October 2010

Re: Minimum givens on larger puzzles

Postby coloin » Thu Apr 02, 2015 10:27 am

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
coloin
 
Posts: 1737
Joined: 05 May 2005

Re: Minimum givens on larger puzzles

Postby m_b_metcalf » Thu Apr 02, 2015 12:01 pm

ton wrote: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.
Attachments
samples16.xls
(18.5 KiB) Downloaded 139 times
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 9286
Joined: 15 May 2006
Location: Berlin

re: 56

Postby Pat » Mon Apr 06, 2015 8:46 am

coloin wrote:

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

User avatar
Pat
 
Posts: 3653
Joined: 18 July 2005

Postby Pat » Tue Feb 28, 2017 1:12 pm

      mwalimu wrote:

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

        How about a 12*12 (with 3*4 blocks)?
m_b_metcalf wrote:
ton (2015.Apr.1) wrote: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 ) ??
User avatar
Pat
 
Posts: 3653
Joined: 18 July 2005

Re: Minimum givens on larger puzzles

Postby ton » Sat Apr 01, 2017 1:50 am

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  .|  .  .  .  .  .|
+---------------+---------------+---------------+
ton
 
Posts: 3
Joined: 26 October 2010

Re: Minimum givens on larger puzzles

Postby hkociemba1 » Sat Aug 25, 2018 4:34 pm

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

Postby Pat » Thu Aug 30, 2018 11:51 am

hkociemba1 wrote:

    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
User avatar
Pat
 
Posts: 3653
Joined: 18 July 2005

25 x 25

Postby m_b_metcalf » Thu Aug 30, 2018 12:56 pm

Pat wrote:
hkociemba1 wrote:

    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
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 9286
Joined: 15 May 2006
Location: Berlin

Re: Minimum givens on larger puzzles

Postby coloin » Thu Aug 30, 2018 1:16 pm

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]
coloin
 
Posts: 1737
Joined: 05 May 2005

Re: Minimum givens on larger puzzles

Postby qiuyanzhe » Fri Aug 31, 2018 7:15 am

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.
qiuyanzhe
 
Posts: 23
Joined: 21 August 2017
Location: China

Next

Return to General