queue = []
goal_grid = {
1: [0, 0],
2: [0, 1],
3: [0, 2],
4: [1, 0],
5: [1, 1],
6: [1, 2],
7: [2, 0],
8: [2, 2]
}
sol = 0
visited = []
class State:
def __init__(self, state, h=0, parent=None):
self.state = state
self.h = h
self.parent = parent
def getState(self):
return self.state
def getParent(self):
return self.parent
def setH(self, h):
self.h = h
def find_h(state):
grid = state.getState()
h = 0
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == 0:
continue
correct_positon = goal_grid[grid[i][j]]
h = h + abs(correct_positon[0]-i) + \
abs(correct_positon[1] - j)
return h
def generateChildren(state):
i, j = blank_i, blank_j
# move up
if 0 <= i-1 < 3 and 0 <= j < 3:
new_state = State(state, 0, state)
grid = new_state.state
grid[i-1][j], grid[i][j] = grid[i][j], grid[i-1][j]
new_state.h = find_h(new_state)
queue.append(new_state)
# move down
if 0 <= i+1 < 3 and 0 <= j < 3:
grid = state.getState()
grid[i+1][j], grid[i][j] = grid[i][j], grid[i+1][j]
h = find_h(state)
new_state = State(grid, h, state)
queue.append(new_state)
# move left
if 0 <= i < 3 and 0 <= j-1 < 3:
new_state = State(state, 0, state)
grid = new_state.state
grid[i][j -
1], grid[i][j] = grid[i][j], grid[i][j-1]
new_state.h = find_h(new_state)
queue.append(new_state)
# move right
if 0 <= i-1 < 3 and 0 <= j < 3:
new_state = State(state, 0, state)
grid = new_state.state
grid[i][j +
1], grid[i][j] = grid[i][j], grid[i][j+1]
new_state.h = find_h(new_state)
queue.append(new_state)
def goalstate(state, goal):
return state.state == goal
def traceback(state):
while state.getParent():
for items in visited:
if state.getParent() == items.getState():
print(state.state)
state = items
def inVisited(state):
for items in visited:
if items.getState() == state.getState():
return True
return False
def driver():
goal = [[1, 2, 3], [4, 5, 6], [7, 8, 0]]
start_grid = [[3, 7, 6], [8, 4, 2], [0, 1, 5]]
start = State(start_grid)
h = find_h(start)
start.setH(h)
global sol
queue.append(start)
while queue:
queue.sort(key=lambda x: x.h)
current_state = State(queue.pop(0))
if goalstate(current_state, goal):
sol += 1
traceback(current_state)
else:
if (inVisited(current_state)):
continue
generateChildren(current_state)
blank_i = int(input("Enter the i of blank: "))
blank_j = int(input("Enter the j of blank: "))
driver()
Here state is a 2d array. So I get the state from the class instance using getState() and save it in some variable. But the type of that variable becomes <class 'main.State'> and I cannot perform any list operations on it. It shows this error. TypeError: 'State' object is not subscriptable. Why is it not returning a list as it was provided before and how to fix this issue?
queue is a global list that is used to keep track of visited states
Another thing is that inside the find_h() function, where the heuristic value is calculated, the grid obtained by doing state.getState() does not give any error and after checking its type is shown as <class 'list'>
This is the whole o/p I get once the code is executed and input is provided i=2,j=0
Traceback (most recent call last):
line 122, in driver()
line 115, in driver generateChildren(current_state)
in generateChildren grid[i-1][j], grid[i][j] = grid[i][j], grid[i-1][j]
TypeError: 'State' object is not subscriptable
The problem you are facing is fairly simple to counter.
def driver():
goal = [[1, 2, 3], [4, 5, 6], [7, 8, 0]]
start_grid = [[3, 7, 6], [8, 4, 2], [0, 1, 5]]
start = State(start_grid)
h = find_h(start)
start.setH(h)
global sol
queue.append(start)
while queue:
queue.sort(key=lambda x: x.h)
current_state = State(queue.pop(0))
if goalstate(current_state, goal):
sol += 1
traceback(current_state)
else:
if (inVisited(current_state)):
continue
generateChildren(current_state)
In the above function, you are creating an object of State .i.e : current_state by using the constructor parameter state as queue.pop(0) which is, in turn, an object of State class since queue appends start which is an object itself.
Hence, current_state is an object of State, that contains self.state, which, again, is an object of State. So, in simpler terms: current_state.state is not a list, but an object of State class.
A simple solution would be to use: current_state = State(queue.pop(0).getState()).
Similarly, use: generateChildren(current_state.getState()) as the same problem occurs for generateChildren function.
Also, as you asked, why does find_h function works fine, is because in: start = State(start_grid), start_grid is a list and not an object of State.
Hope you understood the problem as well as the solution approach. Feel free to ask, if any doubts!