Created
September 4, 2015 18:15
-
-
Save SaptakS/a51c37cf0d60073027e5 to your computer and use it in GitHub Desktop.
8 puzzle using iterative deepening
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# -*- coding: utf-8 -*- | |
""" | |
Created on Fri Sep 04 23:10:25 2015 | |
@author: SAPTAK | |
""" | |
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 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 goal(self): | |
goal = [] | |
for i in range (1, len(self.board)): | |
goal.append(i) | |
goal.append(-1) | |
return str(goal) | |
def solved(self): | |
return str(self.board) == self.goal() | |
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 | |
#iterative deepening algorithm | |
def it_solver(self): | |
import itertools | |
def solver(fringe, visited, depth): | |
c = 0 | |
if depth == 0: | |
#print " here" | |
return | |
else: | |
#print "came" | |
while fringe and c < depth: | |
'''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())) | |
#print "reached" | |
for depth in itertools.count(): | |
#print "inside for" | |
board = self.start.board | |
fringe = collections.deque([Node(self.start)]) | |
visited = set() | |
visited.add(str(fringe[0].state())) | |
path = solver(fringe, visited, depth) | |
#print path | |
if path: | |
return path | |
##input to be take here.... | |
#board = [-1,2,3,1,4,5,7,8,6] | |
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.it_solver() | |
#print(solved_p) | |
for path in reversed(solved_p): | |
soln = '' | |
for elem in path: | |
soln += str(elem)+' ' | |
print(soln) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment