nested lists as arrays

[Michael Spencer]

Terry Reedy wrote:
> <benjamin.cordes at blawrc.de> wrote in message 
> news:1108402043.941832.34110 at f14g2000cwb.googlegroups.com...
> 
>>   def setRandomState(self):
>>      # container for the elements to pick from
>>      container = [1,2,3,4,5,6,7,8,-1]
>>
>>      # create elements of puzzle randomly
>>      i = 0
>>      j = 0
>>      while i <= self.dim-1:
>>          while j <= self.dim-1:
>>              if len(container) > 0:
>>                  randomindex = random.randint(0,len(container)-1)
>>                  self.elements[j][i] = container[randomindex]
>>                  del container[randomindex]
>>                  j=j+1
>>              else:
>>                  break
>>          j=0
>>          i=i+1
> 
> 
> Without reading closely, I believe that the above can generate any possible 
> position.  Are you aware that half are unsolvable?  If that matters, you 
> need to either find a book or site that explains the parity test for 
> solvability or generate the start position from the goal position by a 
> series of random moves.
> 
> Terry J. Reedy
> 
This covers the test for solvability - enjoy ;-): 
http://www.cs.tcd.ie/publications/tech-reports/reports.01/TCD-CS-2001-24.pdf

BTW, just because your puzzle looks like a grid doesn't neceesarily mean that 
representing the data as nested arrays is easiest.  A flat list might be just as 
good here.  It simplifies some of the operations (creating a random ordering 
becomes a one-liner), at the expense of a little more complexity in some others:

import random
class n2grid(object):
     """A grid for the n squared puzzle"""
     def __init__(self,dim = 4):
        self.cells = range(dim*dim)
        self.dim = dim
        self.pos = (0,0)
     def shuffle(self):
         random.shuffle(self.cells)
         self.pos = divmod(self.cells.index(0),self.dim)
     def show(self):
         for row in self._asarray():
             print "".join("[%2s]" % (cell or "") for cell in row)
     def _move(self,dy,dx):
         dim = self.dim
         cells = self.cells
         oldy, oldx = self.pos
         newy, newx = oldy + dy, oldx + dx
         if 0 <= newx < dim and 0 <= newy < dim:
             ix = newy * dim + newx
             ox = oldy * dim + oldx
             cells[ix], cells[ox] = cells[ox], cells[ix]
             self.pos = newy,newx
         else:
             raise Exception, "Illegal move to: (%s,%s)" % (newy, newx)
     def move(self, dx, dy):
         try:
             self._move(dx,dy)
             self.show()
         except:
             pass

     def _asarray(self): #create the array representation when needed
         cells = iter(self.cells)
         dim = self.dim
         return [[cells.next() for j in range(dim)] for i in range(dim)]

     def __repr__(self):
         return repr(self._asarray())




  >>> p = n2grid()
  >>> p.show()
  ...
[  ][ 1][ 2][ 3]
[ 4][ 5][ 6][ 7]
[ 8][ 9][10][11]
[12][13][14][15]
  >>> p.shuffle()
  >>> p.show()
[ 3][15][ 6][ 7]
[10][  ][12][ 5]
[ 4][ 1][14][ 8]
[ 2][11][13][ 9]
  >>> p.move(1,1)
[ 3][15][ 6][ 7]
[10][14][12][ 5]
[ 4][ 1][  ][ 8]
[ 2][11][13][ 9]
  >>> p.move(1,0)
[ 3][15][ 6][ 7]
[10][14][12][ 5]
[ 4][ 1][13][ 8]
[ 2][11][  ][ 9]
  >>> p.move(1,0) # illegal (does nothing)
  >>>

Cheers
Michael