| View previous topic :: View next topic |
| Author |
Message |
| mrmarky2
| | Joined: 13 Jan 2007 | | Posts: 64 | | : | |
Items |
|
 Posted: Sun Jul 06, 2008 5:19 pm Post subject: |
 |
|
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 |
|
 |
| mrmarky2
| | Joined: 13 Jan 2007 | | Posts: 64 | | : | |
Items |
|
| Posted: Sun Jul 06, 2008 5:34 pm Post subject: |
|
|
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 |
|
|
| m_b_metcalf
| | Joined: 13 Mar 2006 | | Posts: 210 | | : | | Location: Berlin |
Items |
|
| Posted: Sun Jul 06, 2008 7:05 pm Post subject: |
|
|
[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 |
|
|
| m_b_metcalf
| | Joined: 13 Mar 2006 | | Posts: 210 | | : | | Location: Berlin |
Items |
|
| Posted: Sun Jul 06, 2008 7:05 pm Post subject: |
|
|
| 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 |
|
|
| mrmarky2
| | Joined: 13 Jan 2007 | | Posts: 64 | | : | |
Items |
|
| Posted: Sun Jul 06, 2008 7:54 pm Post subject: |
|
|
| 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 |
|
|
| m_b_metcalf
| | Joined: 13 Mar 2006 | | Posts: 210 | | : | | Location: Berlin |
Items |
|
| Posted: Mon Jul 07, 2008 7:55 am Post subject: |
|
|
| 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 |
|
|
| m_b_metcalf
| | Joined: 13 Mar 2006 | | Posts: 210 | | : | | Location: Berlin |
Items |
|
| Posted: Tue Aug 26, 2008 1:07 pm Post subject: |
|
|
| 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 |
|
|
| wustvn
| | Joined: 29 Aug 2008 | | Posts: 12 | | : | | Location: Bali - Indonesia |
Items |
|
| Posted: Sat Sep 06, 2008 1:56 pm Post subject: |
|
|
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 |
|
|
| m_b_metcalf
| | Joined: 13 Mar 2006 | | Posts: 210 | | : | | Location: Berlin |
Items |
|
| Posted: Sat Sep 06, 2008 2:50 pm Post subject: |
|
|
| 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 |
|
|
| tarek
| | Joined: 31 Dec 2005 | | Posts: 153 | | : | | Location: London, UK |
Items |
|
| Posted: Sat Sep 06, 2008 6:31 pm Post subject: |
|
|
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 |
|
|
| wustvn
| | Joined: 29 Aug 2008 | | Posts: 12 | | : | | Location: Bali - Indonesia |
Items |
|
| Posted: Sun Sep 07, 2008 11:50 am Post subject: |
|
|
Hi too tarek...
Is it called HITORI?
Thx. |
|
| Back to top |
|
|
| tarek
| | Joined: 31 Dec 2005 | | Posts: 153 | | : | | Location: London, UK |
Items |
|
|
| Back to top |
|
|
| wustvn
| | Joined: 29 Aug 2008 | | Posts: 12 | | : | | Location: Bali - Indonesia |
Items |
|
| Posted: Mon Sep 08, 2008 11:09 am Post subject: |
|
|
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 |
|
|
| tarek
| | Joined: 31 Dec 2005 | | Posts: 153 | | : | | Location: London, UK |
Items |
|
| Posted: Tue Sep 09, 2008 5:55 pm Post subject: |
|
|
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 |
|
|
| wustvn
| | Joined: 29 Aug 2008 | | Posts: 12 | | : | | Location: Bali - Indonesia |
Items |
|
| Posted: Wed Sep 10, 2008 12:47 pm Post subject: |
|
|
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 |
|
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in
Log in to check your private messages
