Sudoku Programmers

Re: minimum number of clues for sudoku 6*6

Afmob — Tue Nov 01, 2011 9:11 am

Author: Afmob

Posted: Tue Nov 01, 2011 9:11 am

Exciting news!

I can now verify that the minimum number of clues needed for a uniquely solvable 2x4 Sudoku is indeed 14. I'll later post some stats on the research but probably in another thread since this one is misleading because of its title.

Re: minimum number of clues for sudoku 6*6

Afmob — Mon Sep 19, 2011 4:12 pm

Author: Afmob

Posted: Mon Sep 19, 2011 4:12 pm

Time for another update.

I've investigated 31.8 % of all 2x4 13 clues patterns with no uniquely solvable Sudoku found so far. Since I go through all patterns using a minlex approach I was able to prove that if a 2x4 13 clues Sudoku has a given in each row then it has no unique solution.

So despite there still being 22 millions of patterns to examine it is unlikely we find one that has only one solution.

On another note, I currently have 1634 essentially different 2x4 14 clues sudokus (with a unique solution) and I've only gone through 95,000 patterns. So I expect there are far more (> 100,000?).

Re: minimum number of clues for sudoku 6*6

Afmob — Tue Mar 22, 2011 4:53 pm

Author: Afmob

Posted: Tue Mar 22, 2011 4:53 pm

Some news on the 2x4 front. I have proven that there is no (uniquely solvable) 2x4 Sudoku with 12 given clues.

So the only question remains if there is one with 13 clues or if all 2x4 Sudokus with 14 clues are minimal.

Re: minimum number of clues for sudoku 6*6

Afmob — Fri Jul 09, 2010 6:38 pm

Author: Afmob

Posted: Fri Jul 09, 2010 6:38 pm

I'm getting less optimistic on finding a uniquely solvable 2x4 Sudoku with 13 Clues. There are still tons of puzzles to check but a lot of promising ones have already been dealt with.

Here's a recent one with 34 solutions (add R4C5 = 8 to make it unique):

Code:

.... ...1
...2 ..3.

..... ..4
..56 ....

.... .56.
.7.. ....

.... 4.5.
71.. ....

number of 2x4 puzzles

Pat — Tue Jun 08, 2010 6:24 am

Author: Pat

Posted: Tue Jun 08, 2010 6:24 am

kjellfp (2005.Oct.17) wrote:

Red Ed 2005.Oct.16) wrote:

...and I think I've calculated
that the number of 2x4 sudokus is 8! * 722631131136 = 2.91e16
(but this needs checking).

Confirmed.

For a prime factorization, you have

722631131136 = 2^18 * 3^3 * 23^2 * 193

Re: minimum number of clues for sudoku 6*6

Afmob — Fri Apr 02, 2010 8:59 am

Author: Afmob

Posted: Fri Apr 02, 2010 8:59 am

That's impressive! I'll only look for 13 clue Sudokus with few solutions for fun since it doesn't seem to help finding one with a unique solution.

Of course, my main program stops when it finds a second possible solution for a puzzle. Otherwise it would take too long going through all possible Sudokus.

Re: minimum number of clues for sudoku 6*6

Pat — Fri Apr 02, 2010 6:50 am

Author: Pat

Posted: Fri Apr 02, 2010 6:50 am

Afmob wrote:

I thought it wasn't important enough
since I had even found 13-Clues 2x4 Sudokus with less solutions
(15 or 17, if I remember correctly)
but I didn't keep them.

elsewhere, Pat (2007.May.25) wrote:

above, gfroyle (2007.May.17) wrote:

So what I do is to keep any pseudo-puzzle that has "few" completions (say less than 10 or maybe 20) hoping that a subsequent "move" from one of those will land us back onto a real puzzle with a unique completion...

a small number of answers
may be irrelevant --
see: Megaclue

~ Pat

[ edited to adjust URLs for new forum ]

Re: minimum number of clues for sudoku 6*6

Afmob — Sun Mar 28, 2010 1:41 pm

Author: Afmob

Posted: Sun Mar 28, 2010 1:41 pm

I didn't want to make a new post because I thought it wasn't important enough since I had even found 13 Clues 2x4 Sudokus with less solutions (15 or 17, if I remember correctly) but I didn't keep them.

Concerning you're question: Add R4C6 = 7

Code:

.... ...1
..23 ....

.... ..4.
56.. .7..

.... 65..
...4 ....

...1 ..2.
.7.. .6..

and you've got one with a unique solution.

Re: minimum number of clues for sudoku 6*6

Pat — Sun Mar 28, 2010 1:15 pm

Author: Pat

Posted: Sun Mar 28, 2010 1:15 pm

Afmob wrote:

Code:

.... ...1
..23 ....

.... ..4.
56.. ....

.... 65..
...4 ....

...1 ..2.
.7.. .6..

does it have any 14-clue puzzles?

note --
when you edit an existing post,
the Topic is not flagged for new material,
thus your edit might go un-noticed.

Re: minimum number of clues for sudoku 6*6

Pat — Sun Mar 28, 2010 1:10 pm

Author: Pat

Posted: Sun Mar 28, 2010 1:10 pm

123...........4.7..6...........36...........3..2.5...........678

Code:

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

..12..........3.4......5...16......78...3......45...........21..

Code:

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

re: 2x4

pseudo coup — Sun Mar 21, 2010 7:51 am

Author: pseudo coup

Posted: Sun Mar 21, 2010 7:51 am

Your first puzzle
is even prettier if we swap 57

Code:

1 2 3 . . . . .
. . . . . . 4 .
7 . . 6 . . . .
. . . . . . . 3
6 . . . . . . .
. . . . 3 . . 2
. 5 . . . . . .
. . . . . 6 7 8

For your second puzzle,
my preferred version is

Code:

. . 1 2 . . . .
. . . . . . 3 .
4 . . . . . . 5
. . . 1 6 . . .
. . . 7 8 . . .
3 . . . . . . 4
5 . . . . . . .
. . . . 2 1 . .

Re: minimum number of clues for sudoku 6*6

Afmob — Sun Mar 14, 2010 2:26 pm

Author: Afmob

Posted: Sun Mar 14, 2010 2:26 pm

I probably hid for too long.

I stopped looking for 14 clues Sudokus after I found this symmetric one. But after some rewrites of my programs and using a new canonical form (similar to but not the same as the popular minlex form) I found another one with 14 clues.

Code:

.... ...1
..23 ....

.... .23.
.4.. ....

...2 ..5.
.6.. 4...

...7 ..8.
.1.. 6...

Those two are the only ones which I've found so far. I might look for more if we know that 14 Clues is the minimum but I hope not.

My computer is currently looking for 13 Clues and 12 Clues (very unlikely) 2x4 Sudoku and of course the infamous 16 Clue Sudoku (3x3 of course).

I think that a 13 Clue Sudoku is possible since I found several ones with less than 100 possible solutions (but I didn't save them ).

By the way, I can verify Red Ed's calculation of 537 essentially different 2x3 Sudoku with 8 clues (takes about 2 minutes on a single 2 Ghz CPU).

Edit: Here is a 13 Clue 2x4 Sudoku with 40 possible solutions:

Code:

.... ...1
..23 ....

.... ..4.
56.. ....

.... 65..
...4 ....

...1 ..2.
.7.. .6..

re: 2x4

Pat — Sun Mar 14, 2010 12:14 pm

Author: Pat

Posted: Sun Mar 14, 2010 12:14 pm

Afmob

Afmob wrote:

I found it while going through all symmetric 14 Clues 2x4 Sudokus

so, how many 14-clue puzzles have you found?

not

in a post now lost

RW (2009.Dec.9) wrote:

(total amount of cells-1)/5+1

[ edited to show post has been lost ]

Re: minimum number of clues for sudoku 6*6

Afmob — Tue Mar 09, 2010 12:12 pm

Author: Afmob

Posted: Tue Mar 09, 2010 12:12 pm

I found it while going through all symmetric 14 Clues 2x4 Sudokus after about 100 hours. Going through all 12 Clues would take roughly 1,5 years and all 13 Clues 20 years, so it's kind of doable.

By the way, there is no rotational symmetric 12 Clues 2x4 Sudokus (search took about 200 hours).

Re: minimum number of clues for sudoku 6*6

Pat — Tue Mar 09, 2010 11:39 am

Author: Pat

Posted: Tue Mar 09, 2010 11:39 am

Afmob wrote:

Here is a symmetric 2x4 Sudoku with 14 clues:

Code:

1 2 3 . . . . .
. . . . . . 4 .

5 . . 6 . . . .
. . . . . . . 3

6 . . . . . . .
. . . . 3 . . 2

. 7 . . . . . .
. . . . . 6 5 8

wow!