OZONE Asylum
Forums
Server-Side Scripting - Oh my!
Creating Sudoku 3x3x3x3
This page's ID:
33324
Search
QuickChanges
Forums
FAQ
Archives
Register
Edit Post
Who can edit a post?
The poster and administrators may edit a post. The poster can only edit it for a short while after the initial post.
Your User Name:
Your Password:
Login Options:
Remember Me On This Computer
Your Text:
Insert Slimies »
Insert UBB Code »
Close
Last Tag
|
All Tags
UBB Help
Going to do a little bit of rapid fire posting on this subject. Some rapid, and not so much rapid. Planning on some code and some ranting. -------- This is one of those things that I have been meaning to talk about for a very long time. But I have been refraining because it hits a little to close to some of the other things that I have been working on. But I think I'm finally far enough removed from those things to give this a chat. When I first started looking into making my own sudoku squares, I was only interested in the final solution. I hit Google and I started reading everything. Unfortunately, none of it struck my fancy. Fortunately, the lack of anything interesting sent me down a completely different path. (Yes, I take issue with the ways that other folks make sudoku grids. I could totally nerd rant about this for hours.) One day I was on lunch at my regular job. I pulled out my little book of sudoku and started doing the zen thing. I was looking for a transform in the numbers that I could use and that wasn't a same-old-same-old transform that I had already read about so many times. And I saw it. It looks like this: [code] 7 . . . . . 4 . . - . . . . . . . . 4 . . . . . 7 . . [/code] Those values can be swapped and the grid remains valid. I had found a transform that wasn't a simple row/col swap. I could so totally use this to mix-up a sudoku grid in a way that isn't... uninteresting. * I later found out that is called The Deadly Pattern. The bane of many sudoku players/creators. I am comletely befuddled as to why this hasn't been exploited in other ways before. Herm. I whipped out Terminal and Geany. Started doing the Python thing. OMG looking for those was a lot harder than I expected. Not hard exactly, just difficult for me to see the interators required - and they are *deep*. It took me about two weeks to get it all straight. But once I did, I was off and running. I threw in some known grids, did a bunch of Deadly Pattern swaps, and compared. Worked like a charm. Damn near all of the static patterns in the original grid were completely gone. This is so far removed from doing row/col swaps and other "regular/mundane" transforms. Happy Happy Joy Joy As good as that is, it still left me with having to come up with a starting point. I mean, I didn't want to keep tossing in known grids because that would defeat the purpose of creating my own grids. I could now shuffle like a mofo, but I still needed that initial starting point. Enter: Putting the Pattern In Instead of putting in someone else's grid, I came up a template that is rife with The Deadly Pattern. Check this out: [code] 1 0 5 4 3 8 7 6 2 6 4 2 0 7 5 3 1 8 3 8 7 6 2 1 0 5 4 2 1 3 5 4 6 8 7 0 7 5 0 1 8 3 4 2 6 4 6 8 7 0 2 1 3 5 0 2 4 3 5 7 6 8 1 8 3 1 2 6 4 5 0 7 5 7 6 8 1 0 2 4 3 [/code] Maybe not a ton of TDP, but that's the most that I can pack in given the size of the grid. There are a total of 36 in that little gem. And I can create that using pure code, or just hard-code it in. Now, I usually don't like to hard-code such things, but no prob in this case because the pattern in that pattern is in it's purest and reduced form. If you scan that template for TDP, you will find 36 of them. However, you will only be able to do 9 of them at the most. Why? Because when you swap some TDP, you will invalidate other TDPs. For example: [code] . 0 5 4 . . . 4 . 0 . . . . . . . . . . . . 5 0 . . . [/code] If you swap one of those TDPs, then the other one is no longer a TDP. Make sense? Something you will have to take into account if you decide to implement. But there is no reason to stop at 9 at the most. After you do the first round of scanning and swapping, do it another round of scanning and swapping. And again and again, almost as many times as you want. Yeah, *almost* as many times as you want. One thing that threw me for a loop was letting my code do the same swaps over and over again. [code] . 0 . 4 . . . 4 . 0 . . . . . . . . [/code] If you swaps those two values for those two blocks, don't swap them again. My first trial with this, I had 3 comps running for 9 hours, and I was expecting awesomeness. However, I got next to nowhere because my code was swapping one round, then unswapping the next. Once I threw the swaps into a signature list and pruned against that, I got the awesomeness that I was hoping for. I was also topping-out the swaps. Just because it's fun, take a look at some data: [code] R# F SP SD RT ---------------------- 0 36 36 9 9 1 12 3 3 12 2 11 3 3 15 3 13 6 4 19 4 10 4 3 22 5 11 4 4 26 6 14 7 4 30 7 12 6 5 35 8 15 9 5 40 9 10 3 3 43 10 16 8 5 48 11 15 9 6 54 12 14 7 5 59 13 14 7 5 64 14 13 6 5 69 15 10 5 4 73 16 10 6 6 79 17 14 7 4 83 18 9 3 3 86 19 10 5 4 90 20 10 4 3 93 21 6 3 2 95 22 5 2 1 96 23 2 0 0 96 24 2 0 0 96 052 861 473 768 534 210 413 027 568 370 642 851 684 715 302 521 308 647 137 486 025 206 153 784 845 270 136 [/code] R# = the round number for scanning and swapping F = how many TDPs found SP = TDPs found pruned against signature list SD = how many swaps were actually done RT = running total of swaps done Followed by the final output. At the very end, just after it tops-out, notice that two TDPs are found. However, they are pruned out because those two swaps had already been done. Without the signatures, just running and running in circles (3 comps @ 9 hrs each in my case, yech). Where it tops-out is *highly* variable. I've seen some top-out at 15, and others at around 30. That is way too much variance for me to want to do the math on. I can't imagine trying to build that tree. I've had this coded for quite a long time, but I haven't done any real speed tests. I know it's less than 1s, and that's good enough for me. And that's using Python without any optimizing at all. Hang on. Let me cobble this real quick... [code] 0.00922799110413 0.00858306884766 0.00903797149658 0.00894093513489 0.00897789001465 0.00830316543579 0.00907111167908 [/code] There you go. A handful of cobbled speed tests on a laptop using unoptimized code in Python 2.7. Yeah, less than a second. * Just for fun, I did a few more speed tests. Using Python3, times went up about 1.5x. Using numpy, speeds went up around 3.5x. And here is the last one that I did: [code] 372 548 106 481 670 325 065 213 748 106 385 274 537 426 081 824 701 653 250 164 837 713 852 460 648 037 512 [/code] Set for 30 rounds, and it didn't top-out just yet. But I do think the next round would have been it. Now you have a *very* different way of making 9x9 sudoku grids. One simple little pattern (TDP) and all of this awesomeness explodes right out of it. Up next: code in Python
Loading...
Options:
Enable Slimies
Enable Linkwords
« Backwards
—
Onwards »
Maximum Security
OZONE
DHTML/Javascript
Server-Side Scripting - Oh my!
CSS - DOM - XHTML - XML - XSL - XSLT
Stupid Basic HTML
Visual Therapy
Photoshop
Photoshop Pong, Anyone?
***WARNING*** BIG SIG APPROACHING
Photography
3D Modelling & Rendering
Multimedia/Animation
Print Graphics
Holding Pens
Philosophy and other Silliness
Outpatient Counseling
Site reviews!
Mad Scientists' Laboratory
Getting to know the Grail