PROGRAMMING Design an agent to solve the n-puzzle game (i. 8-puzzle game generalized to an n n array). Visit mypuzzle.org/sliding for a refresher of...

PROGRAMMING

Design an agent to solve the n-puzzle game (i.e. 8-puzzle game generalized to an n × n array). Visit for a refresher of the game's rules. You will implement and compare several search algorithms, and collect some statistics related to their performances.

Please read all sections carefully:

Introduction
Algorithm Review
What You Need To Submit
What Your Program Outputs
Implementation and Testing
Before You Finish

I. Introduction

The N-puzzle game consists of a board holding N = m^2 − 1 distinct movable tiles, plus one empty space. There is one tile for each number in the set {1, ..., m^2 − 1}. In this assignment, we will represent the blank space with the number 0 and focus on the m = 3 case (8-puzzle).

In this combinatorial search problem, the aim is to get from any initial board state to the configuration with all tiles arranged in ascending order ⟨0, 1,..., m^2 − 1⟩ -- this is your goal state. The search space is the set of all possible states reachable from the initial state. Each move consists of swapping the empty space with a component in one of the four directions {'Up', 'Down', 'Left', 'Right'}. Give each move a cost of one. Thus, the total cost of a path will be equal to the number of moves made.

II. Algorithm Review

Recall from lecture that search begins by visiting the root node of the search tree, given by the initial state. Three main events occur when visiting a node:

- First, we remove a node from the frontier set.
- Second, we check if this node matches the goal state.
- If not, we then expand the node. To expand a node, we generate all of its immediate successors
and add them to the frontier, if they (i) are not yet already in the frontier, and (ii) have not been
visited yet.
This describes the life cycle of a visit, and is the basic order of operations for search agents in this assignment—(1) remove, (2) check, and (3) expand. We will implement the assignment algorithms as described here. Please refer to lecture notes for further details, and review the lecture pseudo-code before you begin.
IMPORTANT:You may encounter implementations that attempt to short-circuit this order by performing the goal-check on successor nodes immediately upon expansion of a parent node. For example, Russell & Norvig's implementation of BFS does precisely this. Doing so may lead to edge-case gains in efficiency, but do not alter the general characteristics of complexity and optimality for each method. For simplicity and grading purposes in this assignment, do not make such modifications to algorithms learned in lecture.

III. What You Need To Submit

Your job in this assignment is to write ,which solves any 8-puzzle board when given an arbitrary starting configuration. The program will be executed as follows:

The method argument will be one of the following. You must implement all three of them: (Breadth-First Search)

(Depth-First Search)

(A-Star Search)

The board argument will be a comma-separated list of integers containing no spaces. For example, to use the bread-first search strategy to solve the input board given by the starting configuration {0,8,7,6,5,4,3,2,1}, the program will be executed like so (with no spaces between commas):

IMPORTANT: If you are using Python 3, please name your file driver_3.py, so we use the correct version while grading. If you name your file driver.py, the default version for our box is Python 2.

IV. What Your Program Outputs

Your program will make and/or write to a file called , containing the following statistics:

: the sequence of moves taken to reach the goal

: the number of moves taken to reach the goal

: the number of nodes that have been expanded

: the depth within the search tree when the goal node is found

: the maximum depth of the search tree in the lifetime of the algorithm

: the total running time of the search instance, reported in seconds

: the maximum RAM usage in the lifetime of the process as measured by the ru_maxrss attribute in the resource module, reported in megabytes