The block world problem is one of the most famous planning domains in artificial intelligence. The goal is to build one or more vertical stacks of blocks, turn the initial state into the goal state. Only one block may be moved at a time, it may be placed either on the table or on top of another block. A block may not be moved if there is another block on top of it.

This Python project implements an agent that can solve Block World problems optimally(in the minimum number of moves) for an arbitrary initial arrangement of blocks (A-Z, 26 blocks maximum). The technique behind the agent is: first use Generate & Test to generate a possible state, then use Means-Ends Analysis to choose the best state to move to.

The agent was designed to always try firstly moving the top block of the left stack to the right stack, followed by checking if the difference has been reduced. If it is, then this is the optimal move. If not, move the top block to the table, skip if a block is already on the table alone, then use this state as the new state. The agent will keep this operation for each block of the left stack until the difference reaches zero, which means it has reached the goal state. Such method could ensure the optimal moves have always been chosen

class BlockWorldAgent:
def __init__(self):
#If you want to do any initial processing, add it here.
pass

def solve(self, initial_arrangement, goal_arrangement):
#Add your code here! Your solve method should receive
#as input two arrangements of blocks. The arrangements
#will be given as lists of lists. The first item in each
#list will be the bottom block on a stack, proceeding
#upward. For example, this arrangement:
#
#[[A, B, C], [D, E]]
#
#represents two stacks of blocks: one with B on top
#of A and C on top of B, and one with E on top of D.
#
#Your goal is to return a list of moves that will convert
#the initial arrangement into the goal arrangement.
#Moves should be represented as 2-tuples where the first
#item in the 2-tuple is what block to move, and the
#second item is where to put it: either on top of another
#block or on the table (represented by the string Table).
#
#For example, these moves would represent moving block B
#from the first stack to the second stack in the example
#above:
#
#(C, Table)
#(B, E)
#(C, A)
pass