Sudoku Programmers Forum Index

 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister   ProfileProfile   Log inLog in          Games  Calendar

Log in to check your private messagesLog in to check your private messages   

NEWS:
minimum number of clues for sudoku 6*6
Goto page 1, 2  Next
 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Exotic sudoku
View previous topic :: View next topic  
Author Message
xcormier

Joined: 05 Mar 2010
Posts: 3
:

Items
PostPosted: Fri Mar 05, 2010 5:26 pm    Post subject: minimum number of clues for sudoku 6*6 Reply with quote

I am french,and I found a sudoku 6*6 with exactly 8 clues which has an unique solution :

040 003
000 060

000 004
006 002

030 010
000 000

I wonder if an other person has found less clues than me.
but we can see that the minimum number of clues for a 6*6 is inferior or egal to 8.

NB: I have made an application for generating and solving sudokus on a mathematic application called MAPLE.
maplesoft->application center->Mathematics->General->maplet de sudoku version 4.(xavier cormier).
Back to top
View user's profile Send private message
Pat

Joined: 06 Sep 2006
Posts: 243
:

Items
PostPosted: Sun Mar 07, 2010 12:55 pm    Post subject: Reply with quote

xcormier wrote:
I found a sudoku 6*6 with exactly 8 clues which has an unique solution :
Code:

.4. ..3
... .6.

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

.3. .1.
... ...

I wonder if an other person has found less clues than me.


going back 4 years [ edited to adjust URL for new forum ] --
      Red Ed (2006) wrote:

        Unless my coding let me down,
        the minimum number of clues for the 3x2 case (M=6) is 8.


Last edited by Pat on Tue Jun 08, 2010 6:07 am; edited 1 time in total
Back to top
View user's profile Send private message
Pat

Joined: 06 Sep 2006
Posts: 243
:

Items
PostPosted: Tue Mar 09, 2010 9:54 am    Post subject: 2x4 Reply with quote


    so the 2x3 is known --

    now what do we know about the minimum number of clues for 2x4 ??
Back to top
View user's profile Send private message
xcormier

Joined: 05 Mar 2010
Posts: 3
:

Items
PostPosted: Tue Mar 09, 2010 10:45 am    Post subject: sudoku 4x2 with 18 clues Reply with quote

I have found with my program several (minimum) sudokus 4*2 with 18 clues.
here is an example:

0000 6000
0208 0040

4000 0051
7060 0020

0301 0070
0070 0000

8003 0000
0000 0402
Back to top
View user's profile Send private message
Afmob

Joined: 09 Mar 2010
Posts: 73
:

Items
PostPosted: Tue Mar 09, 2010 11:30 am    Post subject: Reply with quote

Here is a symmetric 2x4 Sudoku with 14 clues:

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

Running my programm through all possible 2x4 Sudokus with only 11 clues, I was able to prove that the true minimum is either 12,13 or 14. I haven't found one with 12 or 13 clues so far.
Back to top
View user's profile Send private message
Pat

Joined: 06 Sep 2006
Posts: 243
:

Items
PostPosted: Tue Mar 09, 2010 11:39 am    Post subject: Reply with quote

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!
Back to top
View user's profile Send private message
Afmob

Joined: 09 Mar 2010
Posts: 73
:

Items
PostPosted: Tue Mar 09, 2010 12:12 pm    Post subject: Reply with quote

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

By the way, there is no rotational symmetric 12 Clues 2x4 Sudokus (search took about 200 hours).
Back to top
View user's profile Send private message
Pat

Joined: 06 Sep 2006
Posts: 243
:

Items
PostPosted: Sun Mar 14, 2010 12:14 pm    Post subject: re: 2x4 Reply with quote


      hi Afmob,

      welcome to the forum!
      where have you been hiding?

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

so, how many 14-clue puzzles have you found?
    symmetry is not required


          in a post now lost,
          RW (2009.Dec.9) wrote:

            Interestingly, the minimum amount of clues for 2x2, 3x2 and 3x3
            appears to be exactly (total amount of cells-1)/5+1.

              Obviously, this cannot be the case for 2x4,
              but if the trend holds
              I would guess on a minimum of 13 clues for a grid of that size.


          [ edited to show post has been lost ]


Last edited by Pat on Tue Jun 08, 2010 6:12 am; edited 1 time in total
Back to top
View user's profile Send private message
Afmob

Joined: 09 Mar 2010
Posts: 73
:

Items
PostPosted: Sun Mar 14, 2010 2:26 pm    Post subject: Reply with quote

I probably hid for too long. Laughing

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

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


Last edited by Afmob on Sun Mar 21, 2010 2:25 pm; edited 1 time in total
Back to top
View user's profile Send private message
pseudo coup

Joined: 28 Aug 2005
Posts: 8
:

Items
PostPosted: Sun Mar 21, 2010 7:51 am    Post subject: re: 2x4 Reply with quote

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

Back to top
View user's profile Send private message
Pat

Joined: 06 Sep 2006
Posts: 243
:

Items
PostPosted: Sun Mar 28, 2010 1:10 pm    Post subject: Reply with quote


    pretty.

    but when i go to solve the puzzle,
    i like to see box-separators

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

Back to top
View user's profile Send private message
Pat

Joined: 06 Sep 2006
Posts: 243
:

Items
PostPosted: Sun Mar 28, 2010 1:15 pm    Post subject: Reply with quote

Afmob wrote:

    Edit:
      Here is a 13-clue
      with 40 solutions:

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.
Back to top
View user's profile Send private message
Afmob

Joined: 09 Mar 2010
Posts: 73
:

Items
PostPosted: Sun Mar 28, 2010 1:41 pm    Post subject: Reply with quote

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. Smile
Back to top
View user's profile Send private message
Pat

Joined: 06 Sep 2006
Posts: 243
:

Items
PostPosted: Fri Apr 02, 2010 6:50 am    Post subject: Reply with quote


      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 ]


Last edited by Pat on Tue Jun 08, 2010 6:17 am; edited 1 time in total
Back to top
View user's profile Send private message
Afmob

Joined: 09 Mar 2010
Posts: 73
:

Items
PostPosted: Fri Apr 02, 2010 8:59 am    Post subject: Reply with quote

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.
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Exotic sudoku All times are GMT
Goto page 1, 2  Next
Page 1 of 2

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
Sudoku Programmers topic RSS feed 


Powered by phpBB © 2001, 2005 phpBB Group

Igloo Theme Version 1.0 :: Created By: Andrew Charron
FREE FORUM HOSTING by AtFreeForum. Terms of Service - Privacy Policy
FASHION ACCESSORIES - BLING BLING - LADIES WATCHES - KOREAN CHILDREN CLOTHING - ONLINE BARGAIN STORE - FASHION JEWELLERIES