boardGen.py

import random
import math

def moveBlank(boardValue, row, col):
	temp = boardValue[row * 3 + col]
	boardValue = boardValue.replace('9', ' ')
	boardValue = boardValue.replace(temp, '9')
	boardValue = boardValue.replace(' ', temp)
	return boardValue
	
def checkBounds(row, col):
	if (row < 3 and row >= 0 and col < 3 and col >= 0):
		return True
	else:
		return False

def findBlank(boardValue):
	return [boardValue.index('9') / 3, boardValue.index('9') % 3]

def getDirection(direction):
	if direction == 'D':
		return [1,0]
	if direction == 'U':
		return [-1, 0]
	if direction == 'R':
		return [0,1]
	if direction == 'L':
		return [0, -1]

def reverseDirection(direction):
	return "UDLR"["DURL".index(direction)]
	
def sortFactor(boardValue):
	result = 0;
	solution = "123456789";
	
	for x in range(0, len(boardValue)):
		result += abs(solution.index(boardValue[x]) - x)
	return result

def reverse(string):
	result = []
	for x in range(len(string) - 1, -1, -1):
		result.append(string[x])
	return ''.join(result)
	
def boardGen(moveLimit):
	testBoard = "123456789"
	direction = ''
	path = ""
	moves = 0

	blankPosition = findBlank(testBoard)
	while moves < moveLimit:
		direction = random.choice("UDLR")
		if(path != ""):
			while(direction == path[-1]):
				direction = random.choice("UDLR")
		row, col = getDirection(direction)
		if(checkBounds(blankPosition[0] + row, blankPosition[1] + col)):
			blankPosition = [blankPosition[0] + row, blankPosition[1] + col]
			testBoard = moveBlank(testBoard, blankPosition[0], blankPosition[1])
			path = ''.join([path, reverseDirection(direction)])
			print "%s\t%s" % (path[moves], sortFactor(testBoard))
			moves += 1
	return testBoard, path

board, path = boardGen(10)
print
print reverse(path)
print board