Topic: Creating Sudoku 3x3x3x3 (Page 1 of 1) Pages that link to <a href="http://ozoneasylum.com/backlink?for=33324" title="Pages that link to Topic: Creating Sudoku 3x3x3x3 (Page 1 of 1)" rel="nofollow" >Topic: Creating Sudoku 3x3x3x3 <span class="small">(Page 1 of 1)</span>\

 
warjournal
Maniac (V) Mad Scientist

From:
Insane since: Aug 2000

IP logged posted posted 03-16-2019 09:29 Edit Quote

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



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



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



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



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



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



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



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

warjournal
Maniac (V) Mad Scientist

From:
Insane since: Aug 2000

IP logged posted posted 03-16-2019 15:55 Edit Quote

Okay, so here is some code that starts with the template and does the
Deadly Pattern thing.

I completely stripped the code of all non-essentials (including comments)
and hard-coded a few parts here-n-there. Noticed that the only import is
'random' and the rest is stock Python.

Another thing to notice is that my main data structure is 4d. I did this
because interating over a block is so much easier than doing 2d acrobatics.
Egads, I can't imagine trying to do this in 2d. This is why I titled this
thread 3x3x3x3.

One thing that I did not include is a way to validate that the state is
a valid sudoku grid. They are all valid because of the way that this
algorithm works. No need to validate. Boom.

Another thing that I did not include is permutations.... to an extent.
No row/col swaps, mirroring, et al. I'll get into this later. However,
I did include value re-mapping because it is inconsquential to do so
on several levels. Value re-mapping is whatever in terms of code and
symbols. Completely cheeky, so why not?

I'll get into the other perms later. Things like rol/col swaps, mirroring,
flips, and all that. Later. Nerd rant me thinks.

Pretty much do whatever with this code and/or algorithm in general.
Give it a few runs, modify, and share. I think it would be great if
somebody implemented in their own way and really gave it a go.

code:
#!/usr/bin/env python
import random

dr_inter=30

def cout(cme):

   bseq=['1','2','3','4','5','6','7','8','9']
   random.shuffle(bseq)

   f=''

   print('')
   for by in range(3):
      for cy in range(3):
         c=''
         for bx in range(3):
            for cx in range(3):
               c=c+bseq[cme[by][bx][cy][cx]]
               f=f+bseq[cme[by][bx][cy][cx]]
            c=c+' '
         print(c)
      print('')

   print(f)
   print('')

   return

def deadly_scan(drgrid):

   cas=[[0, 1], [0, 2], [1, 2]]

   sdr=[]

   for by in range(3):

      for cy in cas:
         cy0=cy[0]
         cy1=cy[1]

         for bx in cas:
            bx0=bx[0]
            bx1=bx[1]

            for cx0 in range(3):

               for cx1 in range(3):

                  t0=drgrid[by][bx0][cy0][cx0]
                  t1=drgrid[by][bx1][cy1][cx1]

                  t2=drgrid[by][bx0][cy1][cx0]
                  t3=drgrid[by][bx1][cy0][cx1]

                  if (t0==t1) and (t2==t3):
                     if t0<t2:
                        sdr.append([ by,bx0,cy0,cx0, by,bx1,cy1,cx1, t0,t2 ])
                     else:
                        sdr.append([ by,bx0,cy0,cx0, by,bx1,cy1,cx1, t2,t0 ])


   for bx in range(3):

      for cx in cas:
         cx0=cx[0]
         cx1=cx[1]

         for by in cas:
            by0=by[0]
            by1=by[1]

            for cy0 in range(3):

               for cy1 in range(3):

                  t0=drgrid[by0][bx][cy0][cx0]
                  t1=drgrid[by1][bx][cy1][cx1]

                  t2=drgrid[by0][bx][cy0][cx1]
                  t3=drgrid[by1][bx][cy1][cx0]

                  if (t0==t1) and (t2==t3):
                     if t0<t2:
                        sdr.append([ by0,bx,cy0,cx0, by1,bx,cy1,cx1, t0,t2 ])
                     else:
                        sdr.append([ by0,bx,cy0,cx0, by1,bx,cy1,cx1, t2,t0 ])

   return sdr

def scan_dr(mgrid):

   dr_sig=[]

   for i in range(dr_inter):

      rlist=[]
      rlist2=deadly_scan(mgrid)
      random.shuffle(rlist2)
      for dr in rlist2:
         if dr not in dr_sig:
            rlist.append(dr)

      rmask=[[[[1,1,1],[1,1,1],[1,1,1]],[[1,1,1],[1,1,1],[1,1,1]],[[1,1,1],[1,1,1],[1,1,1]]],
             [[[1,1,1],[1,1,1],[1,1,1]],[[1,1,1],[1,1,1],[1,1,1]],[[1,1,1],[1,1,1],[1,1,1]]],
             [[[1,1,1],[1,1,1],[1,1,1]],[[1,1,1],[1,1,1],[1,1,1]],[[1,1,1],[1,1,1],[1,1,1]]]]

      for dr in rlist:

         by0=dr[0];bx0=dr[1]
         cy0=dr[2];cx0=dr[3]

         by1=dr[4];bx1=dr[5]
         cy1=dr[6];cx1=dr[7]

         val0=dr[8];val1=dr[9]

         if by0==by1:

            m0=rmask[by0][bx0][cy0][cx0]
            m1=rmask[by1][bx1][cy1][cx1]
            m2=rmask[by0][bx0][cy1][cx0]
            m3=rmask[by1][bx1][cy0][cx1]

            mbit=m0&m1&m2&m3

            if mbit:

               nval0=mgrid[by0][bx0][cy0][cx0]
               nval2=mgrid[by0][bx0][cy1][cx0]

               mgrid[by0][bx0][cy0][cx0]=nval2
               mgrid[by1][bx1][cy1][cx1]=nval2
               mgrid[by0][bx0][cy1][cx0]=nval0
               mgrid[by1][bx1][cy0][cx1]=nval0

               rmask[by0][bx0][cy0][cx0]=0
               rmask[by1][bx1][cy1][cx1]=0
               rmask[by0][bx0][cy1][cx0]=0
               rmask[by1][bx1][cy0][cx1]=0

               dr_sig.append(dr)

         else:

            m0=rmask[by0][bx0][cy0][cx0]
            m1=rmask[by1][bx1][cy1][cx1]
            m2=rmask[by0][bx0][cy0][cx1]
            m3=rmask[by1][bx1][cy1][cx0]

            mbit=m0&m1&m2&m3

            if mbit:

               nval0=mgrid[by0][bx0][cy0][cx0]
               nval2=mgrid[by0][bx0][cy0][cx1]

               mgrid[by0][bx0][cy0][cx0]=nval2
               mgrid[by1][bx1][cy1][cx1]=nval2
               mgrid[by0][bx0][cy0][cx1]=nval0
               mgrid[by1][bx1][cy1][cx0]=nval0

               rmask[by0][bx0][cy0][cx0]=0
               rmask[by1][bx1][cy1][cx1]=0
               rmask[by0][bx0][cy0][cx1]=0
               rmask[by1][bx1][cy1][cx0]=0

               dr_sig.append(dr)

   return mgrid

def main():

   state=[[[[1,0,5],[6,4,2],[3,8,7]],[[4,3,8],[0,7,5],[6,2,1]],[[7,6,2],[3,1,8],[0,5,4]]],
          [[[2,1,3],[7,5,0],[4,6,8]],[[5,4,6],[1,8,3],[7,0,2]],[[8,7,0],[4,2,6],[1,3,5]]],
          [[[0,2,4],[8,3,1],[5,7,6]],[[3,5,7],[2,6,4],[8,1,0]],[[6,8,1],[5,0,7],[2,4,3]]]]

   state=scan_dr(state)

   cout(state)

   return 0

if __name__ == '__main__':
   main()



Up next: Perms and Nerd Rant

warjournal
Maniac (V) Mad Scientist

From:
Insane since: Aug 2000

IP logged posted posted 03-16-2019 20:13 Edit Quote

Okay, ranting.

Let's start with back-tracking to create sudoku grids. I do not take
issue with back-tracking in general. It has it's uses. For example,
to create mazes. It can also be a quick way to come up with valid
solutions for further study. However, I do take issue with using
back-tracking as the only way to create sudoku grids. It is a good
starting point, but stopping at back-tracking does not suit me at
all. Why? Because sudoku has rules and patterns, and that is what
I am after. Insight and deeper understanding. For me, back-tracking
is a starting point and not an end.

And now permutations. Yes and no. But mostly no.

When perming a sudoku grid, you can swap rows and columns on two
levels. You can swap row/col of entire blocks. And you can swap row/col
of cells within the same block. I'm going to assume that this is
evident or easy enough to not show any explicit examples of this.

However, let's take a look at some notes to show some of the reasons
why I take issue with how some folks use row/col swaps.

There are 3 blocks. Within each block, there are 3 cells. So, let's
talk about shuffling 3 things.

I couldn't tell you how many times I read people saying to do bunches
and bunches of row/col swaps. But you are dealing with 3 things at
a time and doing bunches-n-bunches of swaps is a waste of time. That is,
more swaps of 3 things is not going to mix things up even more. Ugh!

Simple perm of 3 things:

code:
(0,1,2) (1,0,2) (2,0,1)
(0,2,1) (1,2,0) (2,1,0)



No matter how many times you do swaps, you are going to end up with
one of those solutions. Cut to the chase and go straight to one of
those solutions. It's a small set and no prob at all to hard-code.

And one thing that people tend to leave out is the fact that the
original starting point is a possibility in the final output. No
matter how many times you do this-n-that, you can still end up right
back where you started. More ugh!

You have 3 things and you want to shuffle them.
Rule #1: you can't have the orininal as a solution
Rule #2: all values must be different

code:
(0,1,2) original
(1,2,0) valid
(2,0,1) valid


If those are your rules, then only two valid solutions.
(Do those nums as a group look familiar? There is another avenue in
there to be explored. Heh.)

You have 3 things and you want to shuffle them.
Rule #1: you can't have the original as a solution
Rule #2: at least two must be different

code:
------- (1,0,2) (2,0,1)
(0,2,1) (1,2,0) (2,1,0)


And there they are. Same as the perms above sans original.

Refine your chaos, people. Give it a hint of shape. Just a
tad is all it takes.

My data structure for sudoku grids is 4d. Doing those row/col swaps
is ridiculously easy compared to doing the same to a 2d structure.

What about re-mapping or perming the values? Trivial and cheeky.

I see so many people getting caught-up in the symbols themselves.
It's not the symbols that matter when it comes to the kind of math
I enjoy doing the most. What matters are their properties as a group
and/or their relationships.

"Just change all of the values and you've got a whole new sudoku
puzzle!"

No.

"Just do a bunch of rol/col swaps, flip it