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   

Need 4x4 sudoku
Goto page Previous  1, 2, 3  Next
 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Exotic sudoku
View previous topic :: View next topic  
Author Message
mrmarky2

Joined: 13 Jan 2007
Posts: 64
:

Items
PostPosted: Sun Jul 06, 2008 5:19 pm    Post subject: Reply with quote

This is what I thought I was doing, sort of.
My function goes through layer by layer filling the later with random numbers, if it tries more than 5 times to fill a layer then it starts again from the beggining.
It worked really quick for 4x4 and 3x3, and 3x4, but then I used it on the 5x5 and then it doesn't work.
I'm gonna see if i can get it working.

Mark
Back to top
View user's profile Send private message
mrmarky2

Joined: 13 Jan 2007
Posts: 64
:

Items
PostPosted: Sun Jul 06, 2008 5:34 pm    Post subject: Reply with quote

Seems I have it working, it takes about the same time to generate a full grid as it takes you to generate a puzzle!
Dont know whether you could improve on this code or not.. its written in c++
Could you show me your code to generate a full grid?
If not, never mind, I did mine by doing a horizontal 'chute' at a time, and working on each row until that row was finished, if it took too many times to finish it then I started the chute again because it was probably deadlocked.

Just wandering, but how long does it take to generate a 4x4, 6x6 and 7x7?
I'm possibly thinking of going that high, but the generate speed on the 5x5 is pretty bad, so I'm not sure.

Quote:
Here's another. They take about 6s each at 1.6GHz (using Fortran 95 array features and a highly optimizing compiler). You might need to implement naked and hidden triplets too.


I'm going to add another difficulty to my sudoku programs that uses Hidden Pairs, Swordfish and Naked Triples. I really don't like solving puzzles with hiddens in, except for hidden singles, so i'll probably miss on the Hidden Triples.

Thanks
Mark
Back to top
View user's profile Send private message
m_b_metcalf

Joined: 13 Mar 2006
Posts: 210
:
Location: Berlin

Items
PostPosted: Sun Jul 06, 2008 7:05 pm    Post subject: Reply with quote

[delete duplicate message]

Last edited by m_b_metcalf on Sun Jul 06, 2008 7:20 pm; edited 1 time in total
Back to top
View user's profile Send private message
m_b_metcalf

Joined: 13 Mar 2006
Posts: 210
:
Location: Berlin

Items
PostPosted: Sun Jul 06, 2008 7:05 pm    Post subject: Reply with quote

mrmarky2 wrote:

Just wandering, but how long does it take to generate a 4x4, 6x6 and 7x7?
I'm possibly thinking of going that high, but the generate speed on the 5x5 is pretty bad, so I'm not sure.


Using the latest version, I measure:

4x4: <0.01s

5x5: ~0.05s

6x6: ~0.8s

7X7: ~ some minutes. At this level there are high-level deadlocks that I've not programmed for, so many restarts are necessary. For lower values deadlocks are detected before they happen, and the chute restarted. A simple example for 3x3 is
Code:

  1
  2
  3
  4 5 6
  7 8 9
  x x x

It is easy to see at row 5 that row 6 is deadlocked and start again at row 4 without wasting time. Higher order deadlocks occur for each increase in size, and over an increasing number of columns.


Please note that, as of tomorrow and for six weeks, I will see the Forum only intermittently and from internet cafes, and so can reply only from memory. I'd happily show you my code, but fear that I won't have time to prepare a suitable version before leaving.

Regards,

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

Joined: 13 Jan 2007
Posts: 64
:

Items
PostPosted: Sun Jul 06, 2008 7:54 pm    Post subject: Reply with quote

Quote:
Please note that, as of tomorrow and for six weeks, I will see the Forum only intermittently and from internet cafes, and so can reply only from memory. I'd happily show you my code, but fear that I won't have time to prepare a suitable version before leaving.


Thanks very much. I wont be carrying on with increasing the size I dont think. Because of the way I'm generating the puzzles it will take a long time to test it.

Quote:
Using the latest version, I measure:

4x4: <0.01s

5x5: ~0.05s

6x6: ~0.8s

7X7: ~ some minutes. At this level there are high-level deadlocks that I've not programmed for, so many restarts are necessary. For lower values deadlocks are detected before they happen, and the chute restarted.


I didn't ask my question right, I did actually meant how long it took to generate a 4x4 6x6 and 7x7 puzzle, not a finished grid.

I think I'll move on now too multi sudoku, thanks for your time and help.
My generate method is inefficient, I might come back to it later and improve it, as it is it takes just over a minute to generate a 5x5.

Have a nice trip
Thanks
Mark
Back to top
View user's profile Send private message
m_b_metcalf

Joined: 13 Mar 2006
Posts: 210
:
Location: Berlin

Items
PostPosted: Mon Jul 07, 2008 7:55 am    Post subject: Reply with quote

mrmarky2 wrote:
I didn't ask my question right, I did actually meant how long it took to generate a 4x4 6x6 and 7x7 puzzle, not a finished grid.


4 x 4 is ~ 0.4 s

5 x 5 is 6 - 8 s

6 x 6 is ~ 1 min

7 x 7 is ~ 12 min (starting from a full grid).

Regards,

Mike Metcalf

[Edit: all these timings should be reduced by a factor of 2 to 3, following an improvement in the algorithm.]


Last edited by m_b_metcalf on Wed Nov 05, 2008 2:52 pm; edited 1 time in total
Back to top
View user's profile Send private message
m_b_metcalf

Joined: 13 Mar 2006
Posts: 210
:
Location: Berlin

Items
PostPosted: Tue Aug 26, 2008 1:07 pm    Post subject: Reply with quote

m_b_metcalf wrote:

7 x 7 is ~ 12 min (starting from a full grid).


I'm having to test my programs on a new PC, so here's a sample 49 x 49, with left-right/up-down symmetry. It just fits on my wide screen. To solve it, my solver requires 3.7s.

Regards,

Mike Metcalf

Code:

  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  . 10  . 24 13 41  .  .  . 37  .  .  .  1 34 30  . 38  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
  .  .  .  .  .  .  .  .  .  .  .  . 32  .  .  6  . 33  . 28  8 21 18  7 35  5  3 29 44 11  . 27  . 16  .  . 40  .  .  .  .  .  .  .  .  .  .  .  .
  . 47  .  .  .  7  . 28 25  9  5  .  . 11 49  .  .  .  . 42  . 13  .  . 19  .  . 31  . 29  .  .  .  . 15  4  .  . 30 16 27  2  . 34  .  .  .  3  .
  .  .  . 21 48  . 43  4 24  . 46 22  .  . 11  .  3 37 25  .  . 42 40 49 14 15 16 23  .  . 20  7  5  . 35  .  . 13  8  . 31 12 26  . 41 38  .  .  .
  . 35  . 41  . 37 33 17  1 12 16  8  3 27  . 14  .  . 15 43 47  .  . 39  2 25  .  . 45 21 19  .  . 32  . 48 28 49 42 26 29  6 11 44  . 40  . 23  .
 40  3 27  8  .  . 26 37  .  . 29 35 31 41  . 22 39  .  7  . 30 32 48  .  .  . 24 28  4  . 49  . 25 10  . 17 11 18 20  .  . 34 13  .  . 36 21  5 19
  .  .  . 23  . 10 28  . 19  .  .  .  .  .  .  . 29  .  .  .  .  .  .  . 13  .  .  .  .  .  .  . 24  .  .  .  .  .  .  . 35  . 16  9  . 27  .  .  .
  9  .  .  . 47  . 15 14  .  . 41  .  . 46  .  . 18  . 38  . 19  . 17  6  4 26 28  . 16  .  2  .  7  .  .  1  .  . 13  .  . 21 35  . 32  .  .  . 23
 35  . 12 19  .  . 46 10 11 23  . 13 22  .  . 42  .  .  5  .  . 39 49  .  .  .  8 47  .  .  3  .  . 20  .  . 16 40  . 29  9 30 38  .  .  2  4  . 15
 11 22  8  .  4 29  .  . 48 44  . 45 16  1  . 12 32 28  .  . 13  .  7  . 24  . 33  . 37  .  . 31 35 38  . 18  6 42  . 39 17  .  . 47 14  . 26 43 40
  3 40 26 16  .  . 32  .  . 28  2 15  .  . 45 43  . 17  . 33  .  1  . 46 22 35  . 19  . 23  . 10  . 42  6  .  . 11 47  5  .  . 29  .  . 30 48 44 34
 41 34  .  . 17  . 36  .  7  5 43  . 47 38 35  .  4  .  1  2 48 30  . 16  . 37  . 27 32 25 39  . 49  . 13 10 12  . 26 46 14  . 22  . 20  .  . 18 45
  .  2 24 49  . 43  .  . 17  4 26  3  6 35  .  . 21 11  9 44 16 14 32 10  . 45 23  5 29  1 34 48 27  .  . 28 19 22 37 36 20  .  . 31  . 39 13 46  .
 22  .  .  . 31 25 37  .  .  . 12 19  . 26  .  . 49  6 43  . 20  .  . 17  9 11  .  . 15  . 21 47 32  .  .  5  .  2 18  .  .  . 48 38 45  .  .  . 44
 24  1  2  . 49  .  .  . 15 32  .  . 29  .  . 13  . 23  .  9  .  . 25  .  3  . 21  .  . 30  . 41  . 17  .  . 35  .  . 44 45  .  .  . 39  . 11 26 14
  .  . 20  . 32 34  . 22 10  . 18  4 23 45 19 15 16  7 44  .  .  . 37 28  8 41 40  .  .  .  9 24 14  3  5 33 31 21 36  . 39  1  . 35  2  . 49  .  .
 13 44  . 46 40 45  4  . 20  . 42  . 43  . 22 29  . 26  . 21  . 19  .  . 36  .  . 39  . 48  . 23  . 34 18  . 24  . 49  . 41  .  7 37 27 32  . 33  1
  . 12  . 15 21  . 47 11 49  . 36  . 39  . 42 17 45  1  4 31  . 34 43 26  5 22 48 16  . 20  7 40  6 35 44  .  8  . 29  . 19 38 46  .  3 25  . 30  .
 33  . 16  9  . 14 48 21 40  1  . 27 37  . 39  . 30 41 34  .  .  . 44  . 20  . 18  .  .  .  4 13 10  .  8  . 25 26  .  3 46  7 31 15  . 29 17  . 47
 10 41  . 39 35  .  6  5  9 16 44  .  2 14 47 11 25  . 37  . 33  . 45 32  . 13  1  . 22  . 31  . 12 29 19 43 15  . 27 42 48 17 18  . 24 34  .  8 36
  .  9 22 11 42 38 44  . 41 27  .  . 35  .  .  .  . 29 40 34 36 45 14  .  .  . 46 33  8 28 18 43  .  .  .  .  4  .  .  6 15  . 32 48 17 49 16  7  .
 28  .  1 30  . 33 10  .  . 37  8 42 49  .  .  . 27 24 23 12 26 35  2  .  6  . 47 32 48 14 46 11  9  .  .  . 39 20 45 43  .  . 15 13  . 19 31  .  5
 47 27  . 34  . 17  .  9 13 15 11 20 30  .  8  . 37 14 21  .  1 43 38  . 23  . 44  4  7  . 10 22 19  . 12  . 26 48  2 18 40 32  . 29  . 45  . 41 28
  . 31  .  .  8 46 23  3  .  .  . 16 25  . 33  . 28 10  6  4  . 29 19  1  . 49 42 37  . 13  5 45 15  . 40  . 22 14  .  .  . 44  9 39 12  .  . 24  .
  2 49  . 40  . 26  . 32 28 46 10 34 18  .  7  . 20 48  3  . 45 15  5  . 39  . 22 11 23  . 35 16 41  .  4  . 37 38 33  9 42 29  . 27  . 47  . 14 21
 14  . 48  6  .  4 19  .  .  2 23 36 45  .  .  . 11 35 42 18 49  7 20  . 40  . 31 34 30 27 24 38 29  .  .  . 13 41 28  1  .  . 44 33  . 46  8  . 22
  . 15 45  5  7 21 20  .  4 39  .  . 19  .  .  .  .  9 22 32 31 48  3  .  .  . 27 13 36 47 37  1  .  .  .  . 10  .  .  8 49  . 34  2 23 26 18 35  .
 15 23  . 31 11  .  9  1 42 22 30  .  5 21 10 45 41  . 26  . 38  . 46 43  . 34  4  . 47  . 29  . 48 13 14 40 33  . 25 35 18 37 20  . 19 16  . 28  3
  7  .  4 14  .  3 40 19 31 45  . 43 46  . 44  . 42 18 35  .  .  .  1  . 49  .  5  .  .  . 41 34 17  . 10  . 23 15  . 48 11 20 25 30  . 21 47  . 39
  . 21  . 45 22  . 13 24  3  .  9  .  7  . 34 31 36  8 11  6  . 10 28 44 18 23 26 41  . 16  1 25 37  4 46  . 30  . 17  . 32 39 33  . 38 42  . 29  .
 38 19  . 17 39 18 41  . 16  . 15  .  4  . 14  9  .  5  . 40  . 37  .  . 11  .  .  7  . 31  . 49  . 24 27  .  2  .  1  . 12  . 36 23 10 43  . 34  6
  .  . 34  . 12 49  . 35 39  . 32 38 17 18 24  7 33  3 13  .  .  . 31 21 16 27 25  .  .  . 23 30 20 36 28 22 45  6 44  . 43 10  .  5 26  . 46  .  .
 16 28 47  . 27  .  .  . 26 11  .  . 10  .  . 19  . 46  . 49  .  . 12  . 42  . 20  .  .  7  . 44  . 43  .  . 38  .  . 21 34  .  .  . 31  . 22 13 32
  6  .  .  . 44  2 25  .  .  . 33 28  . 36  .  . 43 20 16  . 12  .  . 48 47 19  .  . 21  . 38  9 22  .  . 13  . 31  4  .  .  . 40 11  8  .  .  .  7
  . 18 44  1  . 16  .  . 33 17 22 23 24 39  .  . 13 32 28 41 40  6 26 19  . 21 10 42  3  2 12 35 11  .  . 47 29 45 43 34 36  .  .  8  .  9 38 48  .
 25 29  .  .  6  . 49  . 12 31 28  . 42 20 27  . 15  . 39 48 17 23  .  3  .  7  . 18 43 38 47  . 34  .  1 14 46  . 19  4  8  . 37  . 16  .  .  2 11
 37 10 43 22  .  . 45  .  . 40 27 46  .  . 20 38  . 42  .  7  . 12  . 31 48 28  .  9  .  5  . 18  . 21 36  .  .  1 15 11  .  . 47  .  . 14 41 19 29
 19 14 46  . 24 47  .  .  5  7  .  9  8 34  . 36  6 44  .  . 10  . 16  . 43  .  2  . 41  .  . 28 39 37  . 21 27 35  . 22 38  .  . 17 13  . 12 32 49
  4  . 28  7  .  . 38 30 32 10  . 14 44  .  . 21  .  . 18  .  . 49 41  .  .  . 11 45  .  . 27  .  .  9  .  . 42 24  . 20  6 48 23  .  . 35 34  . 26
 36  .  .  . 15  . 21 13  .  . 37  .  . 48  .  . 12  . 45  . 23  . 34  5 29 14 32  . 24  . 22  . 46  .  . 16  .  . 39  .  . 49 27  . 43  .  .  .  4
  .  .  . 48  . 27 17  . 43  .  .  .  .  .  .  . 31  .  .  .  .  .  .  . 15  .  .  .  .  .  .  . 45  .  .  .  .  .  .  . 10  . 42 25  .  3  .  .  .
  1 20 29  4  .  . 16 48  .  . 17 10 21 28  . 24 22  . 19  . 11 18 15  .  .  . 49 40 14  . 25  . 42 23  .  7 43 34 32  .  . 36 41  .  . 12  2  6 31
  . 38  . 26  . 24 22  7 44 35  4 12  9 23  .  1  .  .  2  5 34  .  . 11 41 30  .  . 20 18  8  .  . 27  .  6 47 29 48 40 33 31 39 16  . 13  . 49  .
  .  .  .  2 41  . 14 46 45  .  3 37  .  . 31  . 44 16 36  .  . 33 10 27  1 32 34 12  .  . 13  6  4  . 39  .  . 19 11  . 21 28 30  . 35 24  .  .  .
  . 42  .  .  . 32  . 26 34 29 39  .  .  5  6  .  .  .  . 15  . 31  .  . 44  .  . 35  . 36  .  .  .  . 11 45  .  . 10 24 37 22  . 46  .  .  .  1  .
  .  .  .  .  .  .  .  .  .  .  .  . 40  .  . 18  . 45  .  3 32  8 22 14 38  9  7 17 10 41  .  5  . 28  .  .  1  .  .  .  .  .  .  .  .  .  .  .  .
  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  . 35  . 41 20 28  .  .  . 46  .  .  . 17 24 45  .  1  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .

 No. fixed: 1308


Last edited by m_b_metcalf on Wed Nov 05, 2008 2:43 pm; edited 1 time in total
Back to top
View user's profile Send private message
wustvn

Joined: 29 Aug 2008
Posts: 12
:
Location: Bali - Indonesia

Items
PostPosted: Sat Sep 06, 2008 1:56 pm    Post subject: Reply with quote

Hi Mike Metcalf,
Can I ask you a question?
Is it still named sudoku if the amount of rows doesn't same with amount of columns?
Thx
Back to top
View user's profile Send private message
m_b_metcalf

Joined: 13 Mar 2006
Posts: 210
:
Location: Berlin

Items
PostPosted: Sat Sep 06, 2008 2:50 pm    Post subject: Reply with quote

wustvn wrote:
Hi Mike Metcalf,
Can I ask you a question?
Is it still named sudoku if the amount of rows doesn't same with amount of columns?
Thx

I think not. A sudoku is n^2 x n^2, where n is the box size.

Regards,

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

Joined: 31 Dec 2005
Posts: 153
:
Location: London, UK

Items
PostPosted: Sat Sep 06, 2008 6:31 pm    Post subject: Reply with quote

a vanilla sudoku has 3*3 boxes in a 9*9 grid.

Sudoku variants can have boxes in any shape and size.

tarek
Back to top
View user's profile Send private message
wustvn

Joined: 29 Aug 2008
Posts: 12
:
Location: Bali - Indonesia

Items
PostPosted: Sun Sep 07, 2008 11:50 am    Post subject: Reply with quote

Hi too tarek...
Is it called HITORI?
Thx.
Back to top
View user's profile Send private message
tarek

Joined: 31 Dec 2005
Posts: 153
:
Location: London, UK

Items
PostPosted: Sun Sep 07, 2008 8:45 pm    Post subject: Reply with quote

wustvn wrote:
Hi too tarek...
Is it called HITORI?

No, that is something else....

here is a link to the sudopedia page of sudoku variations

tarek
Back to top
View user's profile Send private message
wustvn

Joined: 29 Aug 2008
Posts: 12
:
Location: Bali - Indonesia

Items
PostPosted: Mon Sep 08, 2008 11:09 am    Post subject: Reply with quote

Ok. Thx tarek.
Would you mind taking a look at a table that I put at Mediafire.com (a file hosting service) and help me analyze it?
Thx.
Back to top
View user's profile Send private message
tarek

Joined: 31 Dec 2005
Posts: 153
:
Location: London, UK

Items
PostPosted: Tue Sep 09, 2008 5:55 pm    Post subject: Reply with quote

I'm not sure what exactly that you want.

If you post stuff here then other users (NOT just me) can be part of the discussion.

As this is a forum, my next reply is not guranteed, however somebody else may step in to deal with it.

tarek
Back to top
View user's profile Send private message
wustvn

Joined: 29 Aug 2008
Posts: 12
:
Location: Bali - Indonesia

Items
PostPosted: Wed Sep 10, 2008 12:47 pm    Post subject: Reply with quote

I have made more than 5 posts, now I can put a link.
I need help not just from you, tarek, but from all of the people here. If any of you interested in a table that I mentioned above, please see it at my original post under the tittle: This Is An Infinite Sudoku(?) in this Exotic sudoku section too. I have put the link there.
Thx.
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, 3  Next
Page 2 of 3

 
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