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   



COMPULSORY UPGRADE!!! Request an upgrade NOW! 32+ Pre-installed Modifications! 3 Server Locations to choose from: USA, UK and JAPAN.

11th December 2012 - setBB: All servers are upgraded to run using SSD drive. Click Here to report problems!
Minimum number of clues for 16x16 (4x4)
Goto page Previous  1, 2
 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Exotic sudoku
View previous topic :: View next topic  
Author Message
blue

Joined: 12 May 2010
Posts: 318
:

Items
PostPosted: Fri Mar 11, 2011 1:15 pm    Post subject: Reply with quote
Pat wrote:
blue wrote:
I suspect that if a 61 can be produced from a 63 with {-3,+1}, then there's a good chance that the original 63, is part of a large set of {-1,+1}-related 63s.

where a 63 produces a 61 via -3 +1,
we know that the original 63 has
3 neighbouring 63s within -1 +1

Do we ? (I don't).
Can we say what they are, if P is the 63 and Q = (P-a-b-c+d) is the 61 ?

Pat wrote:
blue wrote:
---only looking for puzzles solvable with singles and line-box eliminations

why??
    where i say -3 +1 (or -1 +1, etc)
    i mean any and all relevant possibilities
    (regardless of the difficulty of the resulting puzzle)

My (brute force) solver can't even complete a "for real" {-2,+1} test. It gets hung up in nested levels of guessing, at some point. It typically gets hung up like that, even for a {-1,+1} test. I let it go for ~8 hours once, on a single {-1,+1} test, and it never finished.

There are no bugs in the code. I sometimes wonder if the fault lies in the code that chooses the next "constraint" to use in guessing. It's uses the standard approach for 9x9 code, though -- choose (one of) the constraint(s) with the fewest options.

I've found that the SAT solver that I mentioned in a post up above, can at least complete the tests -- 100% of the time, so far. The bad thing, is that it takes ~2 minutes to do a {-1,+1} test, and a little under an hour to do a {-2,+1} test. A {-3,+1} would take days.
Back to top
View user's profile Send private message
m_b_metcalf

Joined: 13 Mar 2006
Posts: 329
:
Location: Europe

Items
PostPosted: Fri Mar 11, 2011 4:46 pm    Post subject: Reply with quote
Pat,
Also, as I pointed out:
m_b_metcalf already wrote:
Do we have a similar situation as with 9x9, where 80% of 17-clue puzzles are solvable with singles, and hard ones tend to be in the lower 20s?


So it's probably a waste of effort using slow techniques to search for small clue numbers.

Regards,

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

Joined: 06 Sep 2006
Posts: 242
:

Items
PostPosted: Sun Mar 13, 2011 7:27 am    Post subject: Reply with quote
blue wrote:
Can we say what they are,
if P is the 63 and Q = (P-a-b-c+d) is the 61 ?

add to the 61
any 2 of the {a,b,c}
    sorry i should've said,
    3 non-minimal 63s
blue wrote:
the SAT solver that I mentioned in a post up above, can at least complete the tests -- 100% of the time, so far.
    The bad thing,
    is that it takes ~2 minutes to do a {-1,+1} test,
    and a little under an hour to do a {-2,+1} test.
    A {-3,+1} would take days.

very sorry to hear that
    i'd guess 20 hours
    but even that is too much
Back to top
View user's profile Send private message
blue

Joined: 12 May 2010
Posts: 318
:

Items
PostPosted: Sun Mar 13, 2011 8:31 am    Post subject: Reply with quote
Pat wrote:
blue wrote:
Can we say what they are,
if P is the 63 and Q = (P-a-b-c+d) is the 61 ?

add to the 61
any 2 of the {a,b,c}
    sorry i should've said,
    3 non-minimal 63s

I wondered if that's what you were thinking.
That won't work if 'd' is incompatible with two or more of {a,b,c}.

Pat wrote:
blue wrote:
the SAT solver that I mentioned in a post up above, can at least complete the tests -- 100% of the time, so far.
    The bad thing,
    is that it takes ~2 minutes to do a {-1,+1} test,
    and a little under an hour to do a {-2,+1} test.
    A {-3,+1} would take days.

very sorry to hear that
    i'd guess 20 hours
    but even that is too much

You're right, 20 hour ballpark.
Back to top
View user's profile Send private message
coloin

Joined: 05 May 2005
Posts: 186
:

Items
PostPosted: Sun Mar 13, 2011 11:54 pm    Post subject: Reply with quote
Excellent work on getting a 63 blue

A non-minimal 63 implies at least a 62 [which you havent found yet !]

Anyhow - simplistically maybe trying another method might yield better results at producing more 63s - and one might be non-minimal ?

Select the clue value with the highest frequency in the puzzle. Complete the template to 16 clues - see if you can remove again the same number of clues a different way.

or on a similar vein complete all the clues in the most populous box - and see if you can complete the puzzle by removing clues from that box a different way.

or more difficultly remove all the clues from the most populous box - and see if you can complete the puzzle with the same number of different clues.

C
Back to top
View user's profile Send private message
blue

Joined: 12 May 2010
Posts: 318
:

Items
PostPosted: Tue Mar 15, 2011 12:31 am    Post subject: Reply with quote
coloin wrote:
Select the clue value with the highest frequency in the puzzle. Complete the template to 16 clues - see if you can remove again the same number of clues a different way.

or on a similar vein complete all the clues in the most populous box - and see if you can complete the puzzle by removing clues from that box a different way.

I tried those two, and the extension of the 2nd to rows and columns. It didn't produce anything new. "Candidates" made 65s & up, boxes made 67s & up, rows made 66s & up, and columns made 65s & up ... nothing reduced to a 64 even, when the other clues were checked for being redundant. This was using the SAT solver throughout.

For Pat,
It wasn't {-3,+1}, but I did get around to running the "for real" {-2,+1} test on the small number of 63s. No luck. I did get one more 63 in the {-1,+1} part of the testing.
Back to top
View user's profile Send private message
T_Shirakawa

Joined: 31 Mar 2011
Posts: 2
:

Items
PostPosted: Thu Mar 31, 2011 3:13 pm    Post subject: Reply with quote
Here is one with 57 clues.
Code:

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

I search for 56 clues puzzle now.
And probably there is it.
Back to top
View user's profile Send private message
blue

Joined: 12 May 2010
Posts: 318
:

Items
PostPosted: Thu Mar 31, 2011 4:20 pm    Post subject: Reply with quote
T_Shirakawa wrote:
Here is one with 57 clues.

Excellent Exclamation

It has about the same ratio of clues to cells as an 18 clue 9x9 puzzle: 81*(57/256)= 18.035

Good luck with the 56.
Back to top
View user's profile Send private message
m_b_metcalf

Joined: 13 Mar 2006
Posts: 329
:
Location: Europe

Items
PostPosted: Thu Mar 31, 2011 4:44 pm    Post subject: Reply with quote
blue wrote:
T_Shirakawa wrote:
Here is one with 57 clues.

Excellent Exclamation

It has about the same ratio of clues to cells as an 18 clue 9x9 puzzle: 81*(57/256)= 18.035

Simply astonishing! And, once again, it's simple to solve.

Regards,

Mike Metcalf

blue, could you please give the last puzzle I posted on the other thread a spin? It seems to have peculiar properties. Thanks.
Back to top
View user's profile Send private message
T_Shirakawa

Joined: 31 Mar 2011
Posts: 2
:

Items
PostPosted: Sat May 07, 2011 9:41 am    Post subject: Reply with quote
Here is one with 56 clues.
Code:

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

There are not the mathematical grounds,
but I think that this is smallest.


Grid which is near to a solution of 55 clues.
However, I can not improve it.
Code:

 6  .  1  .  2  3  .  .  .  . 13  .  .  .  .  .
 3  .  5  .  .  1  .  .  .  .  .  .  .  .  .  .
 .  .  .  .  .  .  4  .  .  .  .  8  9  .  . 11
 .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
 . 15  .  .  .  5  .  .  .  .  .  7  .  6  .  .
 .  8  . 14  .  .  .  .  9  .  . 11  7  .  .  .
 .  .  .  . 12  .  .  .  .  .  .  .  .  .  .  .
 .  . 12  .  1  2  .  .  .  .  .  .  .  .  .  .
 .  .  .  .  .  .  .  .  5  2  1  .  .  3  .  .
 .  .  .  .  .  .  8  .  .  .  3  .  .  2  .  .
 . 11  .  8  4  .  9  7  .  .  .  .  .  .  .  .
 .  9  .  .  .  . 11  .  .  .  .  .  .  .  .  .
 .  .  6  .  .  .  . 10  .  .  .  . 13  1  3  .
 .  .  .  .  .  . 14  .  .  .  .  4  . 12  .  .
 .  4  .  .  .  .  7 11 12 14  .  9  .  .  .  .
 .  .  .  .  .  .  .  .  .  .  .  .  .  5  2  .
Back to top
View user's profile Send private message
m_b_metcalf

Joined: 13 Mar 2006
Posts: 329
:
Location: Europe

Items
PostPosted: Sun May 08, 2011 11:57 am    Post subject: Reply with quote
T_Shirakawa wrote:

Grid which is near to a solution of 55 clues.

Interesting. If I've counted correctly, your pseudo-puzzle has 732 solutions and 204 common clues:
Code:

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

There are three unavoidable 4-sets uncovered at:

Uncovered on pass 1 at rows 10 12 cols 3 15
Uncovered on pass 1 at rows 10 11 cols 10 15
Uncovered on pass 1 at rows 14 16 cols 2 11

But I'm sure you know all that already.

Regards,

Mike Metcalf
Back to top
View user's profile Send private message
coloin

Joined: 05 May 2005
Posts: 186
:

Items
PostPosted: Tue Jun 28, 2011 9:20 pm    Post subject: Reply with quote
interesting to have found a puzzle with so few clues.

Taking an example from the 9*9 model :
If you restrict the givens to one of the 6 bands - it takes 18 clues within a band to define a band [in all cases]

What is the minumum number of clues to define one of the [8] bands in the 16 * 16 case.

Well i got round to [manually] showing that this band
Code:
 x  8  7  9 |14  x  4  3 |11 10 12  1| 15 13  6  x
16 13  x 15 | 6  x  7  2 | 8  x 14  9|  x 11  5  3
10  6  x  5 |12  8  9 11 | 13 3 15 16|  x  7  2  1
 x  1 14 11 |10  13 1516 | 5  x  7  2|  4  8  x 12

probably easily improved on

is defined by 64-12 clues = 52

and this one is 64-14
Code:
 x  8  7  9 |14  x  4  3 |11 10 12  1| 15 13  6  x
16 13  x 15 | 6  x  7  2 | 8  x 14  9|  x 11  5  3
10  6  x  5 |12  x  9 11 | 13 3 15 16|  x  7  2  1
 x  1 14 11 |10  x 15 16 | 5  x  7  2|  4  8  x 12


approaching 64-16 perhaps.

anyway - so that debunks that for now.

C
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 Previous  1, 2
Page 2 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