<[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED]This covers the test for solvability - enjoy ;-): http://www.cs.tcd.ie/publications/tech-reports/reports.01/TCD-CS-2001-24.pdf
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
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
-- http://mail.python.org/mailman/listinfo/python-list