HotLink Menu in RightSide Column 
Wal Mart Online → Best Selection 


8puzzleThe 8puzzle, an illustration of which is depicted in Figure Agent4, is composed of a 3 Χ 3 board with eight numbered tiles and a blank space. A tile adjacent to the blank space can slide into the space. The object is to reach a specified goal state, such as the diagram illustrated on the right side of the figure:
The object is to reach a specified goal state, such as the one shown on the right of the figure. The standard formulation is as follows:
The actions above are abstracted to their beginning and final states only. The intermediate locations of when the block is sliding are ignored. Abstracted actions would include shaking the board when the pieces get stuck, extracting the pieces with a screwdriver and pounding them back in with a hammer and so on. This leaves us with a description of the rules of the puzzle, and allowing us to ignore the details of physical manipulation. The 8puzzle belongs to the family of slidingblock puzzles, which are often used as test problems for new search algorithms in AI. This family is known to be NPcomplete, so we are not expecting to methods significantly better than the search algorithms described later in this guide. However, if you would like to make a significant contribution to AI, you can come up with a more efficient search algorithm than those presented here. The 8puzzle has has 9!/2 or 181,440 reachable states so is easily solved. Next, is the 15puzzle which is the 4 χ 4 board giving 1.3 trillion states. The best search algorithms can solve this puzzle optimally in a few milliseconds. The 24puzzle (on a 5 chi; 5 board) has around 10^{25} states, and random instances can take several hours to solve optimally. In order to decrease the time you need to optimally solve some of your pesky algorithms, you can develop your own more efficient algorithms, and be entered into the AI Hall of Fame, or simply follow the links below to purchase a more powerful machine with increased processing power and more memory at incredible savings for you: Centurion Online → Computers → Laptops8Queens ProblemThe goal of the 8queens problem is to place eight queens on a chessboard such that no queen attacks any other. (A queen attacks any piece in the same row, column or diagonal.) Figure Agent5 shows an attempted solution that fails since the queen in the rightmost column is attacked by the queen at the top left.
Although efficient specialpurpose algorithms exist for this problem and for the whole NQueens family, it remains a useful test problem for search algorithms. There are two main kinds of formulation. An incremental formulation involves operators that augment the state description, starting with an empty state; for the 8Queens problem, this means that each action adds a queen to the state. A completestate formulation starts with all 8 queens on the board and moves them around. In either case, the path cost is of no interest because only the final state counts. The first incremental formulation one might try is the following: Although efficient specialpurpose algorithms exist for this problem and for the whole NQueens family, it remains a useful test problem for search algorithms. There are two main kinds of formulation:
In either case, the path cost is of no consequence since only the final state is relevant. An example incremental formulation might be:
In this formulation we have 64 * 63 * 62 ... *57 ==> 1.8 x 10^{14} possible sequences to investigate. A better formulation would prohibit placing a queen in any square that is already attacked: In this formulation we have 64 * 63 * 62 .. * 57 → 1.8 X 10^{14} possible sequences requiring investigation. A better heuristic would prohibit placing a queen in any square that is already attacked:
This formulation reduces the 8Queens space from 1.8 x 10^{14} to just 2,057 and solutions are easy to find. On the other hand, for 100 queens the reduction is from roughly 10^{400} state to about 10^{52} states. A big improvement, but not enough to make the problem tractable. The Knuth SequenceThis final toy problem was devised by Donald Knuth in 1964 and illustrates how infinite spaces can arise. Knuth conjectured that one can start with the number 4, apply a sequence of factorial, square root, and floor operations, and arrive at any desired positive integer. For example:
To our knowledge there is no bound on how large a number might be constructed in the process of reaching a given target  for example, 620,448,401,733,239,439,360,000 is generated in the expression for 5  so the state space for this problem is infinite. Such state spaces arise very frequently in tasks involving the generation of mathematical expressions, circuits, proofs, programs, and other recursively defined objects.
Real World ProblemsRoute Finding ProblemsWe have already seen how the routefinding problem is defined in terms of specified locations and transitions along links between them. Routefinding algorithms are used in a variety of applications. Some, such as Web sites and incar systems that provide driving directions, are relatively straightforward extensions of the Romania example. Others, such as routing video streams in computer networks, military operations planning, and airline travel planning systems, involve much more complex speciifcations. Consider the airline travel problems that must be solved by a travel planning Web site: Recalling our session with Intelligent Agents we have seen how routefinding problems can be defined in terms of specified locations and transitions along links between them. Routefinding algorithms are used in a variety of applications. Some, such as Web sites and incar systems that provide driving directions, are a relatively straightforward extension of the Romanian map problem. Others, such as routing video streams in computer networks, military operations planning and airline travel planning systems, involve much more complex specifications. These and other fascinating AI topics are discussed and solved in much greater detail and can be found by following the links above at: Centurion Online → Books → Computer ScienceConsider the airline travel problems that must be solved by a travel planning Web site:
Commercial travel advice systems use a problem formulation of this kind, with many additional complications to handle the byzantine fare structures that airlines impose, e.g. They want to charge me for a whole row when I forget to put on my deodorant. If it is such a big deal, then why don't they just have a community antiperspirant, that we all could share? As any seasoned traveler knows, however, that not all air travel goes according to plan. A really good system should include contingency plans  such as backup reservations on alternate flights  to the extent that these are justified by the cost and likelihood of failure of the original plan. Touring ProblemsTouring Problems are closely related to routefinding problems, but, with an important, very important, difference. Consider, just consider, for a moment, if you will, the problem "Visit every city in Figure Agent2 at least once, starting and ending in Bucharest." As with route finding, the actions correspond to trips between adjacent cities. The state space, however is quite different. Each state must include not just the current location but also the set of cities Agent Smart has visited. So, the initial state would be: In(Bucharest), Visited({Bucharest}), a typical intermediate state would be: In(Vaslui), Visited({Bucharest, Urziceni, Vaslui}), and the goal test would check whether Agent Smart is in Bucharest and has visited all 20 cities. Traveling Salesperson ProblemThe Traveling Salesperson Problem (TSP) is a touring problem in which each city must be visited exactly once. The aim is to find the shortest tour. The problem is known to NPhard, but an enormous amount of effort has been expended to improve the capabilities of TSP algorithms. In addition to planning trips for traveling salespersons, these algorithms have been used for tasks such as planning movements of automatic circuit board drills and of stocking machines on shop floors. VLSI LayoutA VLSI layout problem requires positioning millions of components and connections on a chip to minimize area, minimize circuit delays, minimize stray capacitances, and maximize manufacturing yield. The layout problem comes after the logical design phase, and is usually split into two parts: cell layout and channel routing. In cell layout, the primitive components of the circuit are grouped into cells, each of which performs some recognized function. Each cell has a fixed footprint (size and shape) and requires a certain number of connections to each of the other cells. The aim is to place the cells on the chip so that they do not overlap and so that there is room for the connecting wires to be placed between the cells. Channel routing finds a specific route for each wire through the gaps between the cells. These search algorithms are extremely complex, but definitely worth solving. Robot NavigationRobot Navigation is a generalization of the routefinding problem described earlier. Rather than a discrete set of routes, a robot can move in a continuous space with (in principle) an infinite set of possible actions and states. For a circular robot moving on a flat surface, the space is essentially twodimensional. When the robot has arms and legs or wheels that must also be controlled, the search space becomes manydimensional. Advanced techniques are required just to make the search space finite. In addition to the complexity of the problem, real robots must also deal with errors in their sensor readings and motor controls. Automatic Assembly SequencingAutomatic assembly sequencing of complex objects by a robot was first demonstrated by Freddy. Progress since then has been slow but sure, to the point where the assembly of intricate objects such as electric motors is economically feasible. In assembly problems, the aim is to find an order in which to assemble the parts of some object. If the wrong order is chosen, there will be no way to add some part later in the sequence without undoing some of the work already done. Checking a step in the sequence for feasibility is a difficult geometrical search problem closely related to robot navigation. Thus, the generation of legal actions is the expensive part of assembly sequencing. Any practical algorithm must avoid exploring all but a tiny fraction of the state space. Another important assembly problem is protein design, in which the goal is to find a sequence of amino acids that will fold into a threedimensional protein with the right properties to cure some disease. In order to continue with this guide, and continue the discussion on Romanian Map Problems and Solutions: Press the Button below: 
Last Updated 7272010Big O Notation NP Completeness Intelligent Agents Formulating Problems Toy Problems Vacuum World 8 Queens The Knuth Sequence Real World Problems Route Finding Problems Touring Problems Traveling Salesperson Problem VLSI Layout Robot Navigation Automatic Assembly Sequencing Search Algorithm Infrastructure Child Node Creation Measuring Algorithm Performance BreadthFirst Search BreadthFirst Characteristics C++ BreadthFirst Search Code BreadthFirst Data Structure BreadthFirst Make Map BreadthFirst Make Neighbor BreadthFirst Point of Origin BreadthFirst Initial Listing BreadthFirst Get Child City C++ BreadthFirst Search Code UniformCost Search DepthFirst C++ Solution DepthFirst Data Structure DepthFirst Display Data DepthFirst Initial Listing DepthFirst Path Record DepthFirst Main() DepthLimited Search Bidirectional Search Comparing Strategies Greedy BestFirst A* Search Optimality of A* A* Search Data Structure A* Search Data Entry C++ Min Priority Queue C++ A* Headers & Prototypes C++ A* Search Main() 