This problem is basically the same as that mentioned in this gist(https://gist.github.com/SaptakS/911d597fbff5796bfb62). The only variation here is in the goal. in this case, the goal can have 8 possible combinations obtained by rotating the goal_board by 90 degree or by rotating and then transposing.

n-PuzzleProblem-variation-in-goal.py

import math
import collections
class Node:
	def __init__(self, puzzle, parent=None, action=None):
		self.puzzle = puzzle
		self.parent = parent
		self.action = action

	def state(self):
		#print(self.puzzle.board)
		return self.puzzle.board

	
	
	def path(self):
		node, p = self, []
        	while node:
            		p.append(node.state())
            		node = node.parent
		#print(p)
		return p
        	#print(reversed(p))
	
	def solved(self):
		return self.puzzle.solved()

	def actions(self):
		return self.puzzle.actions()
 
class Environment:
	def __init__(self, board):
		self.board = board
		self.width = int(math.sqrt(len(self.board)))

	def transpose(self,matrix):
		return zip(*matrix)

	def rotate_clockwise(self,matrix, degree=90):
		return matrix if not degree else self.rotate_clockwise(zip(*matrix[::-1]), degree-90)

	def copy(self):
		board = []
		for element in self.board:
			board.append(element)
		return board

	def moved(self, (r,c),(i,j)):
		copy = self.copy()
		copy[r * self.width + c], copy[i * self.width + j] = copy[i * self.width + j], copy[r * self.width + c] 
		return copy

	def goals(self):
		goal_board = []
		for x in range(0, self.width):
			temp = []
			for y in range(0, self.width):
				temp.append(self.width * x + y + 1)
			goal_board.append(temp)
		goal_board[self.width - 1][self.width - 1] = -1
		#print(goal_board)
		#return str(goal)
		
		final = []
		for i in range(1, 5):
			goal = []
			matr_tr = []
			matrix =  self.rotate_clockwise(goal_board, (i * 90))
			for j in matrix:
				#print(j)
				temp = []
				for k in j:
					goal.append(k)
					temp.append(k)
				matr_tr.append(temp)

		#	print(matr_tr)
		#	print(goal)
			final.append(str(goal))
			goal = []
			matrix = self.transpose(matr_tr)	
		#	print transpose(matr_tr)
			for j in matrix:
				#print(j)
				temp = []
				for k in j:
				        goal.append(k)
		#	print(goal)
			final.append(str(goal))
		
		#print(final)
		return final


	def solved(self):
		for goal in self.goals():
			if str(self.board) == goal:
				return True
		return False

	def actions(self):
		block_pos = self.board.index(-1)
		block_r = block_pos / self.width
		block_c = block_pos % self.width
		moves = []

		directions = {"R":(block_r, block_c + 1),
			      "L":(block_r, block_c - 1),
			      "T":(block_r - 1, block_c),
			      "D":(block_r + 1, block_c)}
		for action, (i,j) in directions.items():
			if i >= 0 and j >= 0 and i < self.width and j < self.width:
				move = self.moved((block_r, block_c),(i,j)),action
				moves.append(move)
		return moves
				

	def showboard(self):
		newnode = Node(self.board)
		print(newnode.state()[0])
		return self.board

class Agent:
	def __init__(self, start):
		self.start = start

	def solver(self):
		board = self.start.board
		fringe = collections.deque([Node(self.start)])
		#print(Node(self.start).state())
		#print(fringe[0].puzzle)
		visited = set()
		visited.add(str(fringe[0].state()))
		#print(visited)
		'''k = 0'''
		while fringe:
			'''k = k + 1
			if k > 8:
				break'''
			node = fringe.pop()
			if node.solved():
				return node.path()
			for move, action in node.actions():
				child = Node(Environment(move), node, action)
				#print("Parent", node.state())
				#print(action, child.state()) 
				if str(child.state()) not in visited:
					#print("added to", child.state())
					fringe.appendleft(child)
					visited.add(str(child.state()))
		
		


##input to be take here....
'''
board = [3, 2, 1, 6, 5, 4, -1, 8, 7]
p = Environment(board)
p.solved()
print(p.solved())
'''
i = int(input())
for k in range(0, i):
	n = int(input())
	board = []
	for i in range(0, n):
		temp = []
		temp = [int(x) for x in raw_input().split()]
		#print(temp)
		for t in temp:
			board.append(t)
	#print(str(board))
	p = Environment(board)
	s = Agent(p)
	solved_p = s.solver()
	#print(solved_p)



	for path in reversed(solved_p):
		soln = ''
		for elem in path:
			soln += str(elem)+' '
		print(soln)
#print(p.solved())
#print(p.actions())