AI 1 - Problem Solving (Artificial intelligence)

First lets code the State class. This state will hold all the code and variables used to manipulate our grid. Lets call it CState and put it I its own header file. (From here on, I will be using C++ Code)

// First of all Lets enumerate all the possible Operators (The Blank can Move North East South or West)
// You will see why we need the ‘NONE’ later
enum DIRECTION { NONE, NORTH, EAST, SOUTH, WEST };

// Now the class.
class CState {
private:
   // use index 1 to 9, type char uses less memory than an int
   char Grid[10];    char Depth;

   // we need to remember what operator was applied to
   // the parent state to get this state. There is no point
   // in moving north if the last move was south right ???
   DIRECTION OperatorApplyed;
   
   // We need a pointer to the parent state(the state
   // which made this state, so that when the problem is
   // solved, we can trace our steps and report the answer.
   CState *PrevState;
   
   // Find where the Blank is within the Grid array.
   inline int FindBlank(char Search=0) {

       int Blank=1;
       while (Grid[Blank] != Search) {
           Blank++;
       }
       return Blank;
   }
   
   // Code to move the blank
   void MoveBlank(DIRECTION Direction) {
       
       int Blank = FindBlank();
       // remember, we need to know the last operator
       // that was applied
       OperatorApplyed = Direction;
       
       // move the numbers depending on what direction
       // parameter was passed.
       switch (Direction) {
       case NORTH:
           Grid[Blank] = Grid[Blank - 3];
           Grid[Blank - 3] = 0;
           break;

       case EAST:
           Grid[Blank] = Grid[Blank + 1];
           Grid[Blank + 1] = 0;
           break;

       case SOUTH:
           Grid[Blank] = Grid[Blank + 3];
           Grid[Blank + 3] = 0;
           break;

       case WEST:
           Grid[Blank] = Grid[Blank - 1];
           Grid[Blank - 1] = 0;
           break;
       }
   }
   
   // This Will be used as 1 as part of 1 of our heuristics…
   // It gets the distance in squares between 2
   // index places.. it will be used to find the
// distance between where a number is, and where
// it should be !
   int GetDistanceBetween(int Tile1, int Tile2) {
       
       int X1, X2;
       int Y1, Y2;
       int temp=0;
       
       // convert a grid position into an X,Y coordinate.
       Y1 = 1;
       Y2 = 2;
       X1 = Tile1;
       X2 = Tile2;
       if(Tile1 > 3) { Y1 = 2; X1 = Tile1 - 3; }
       if(Tile1 > 6) { Y1 = 3; X1 = Tile1 - 6; }
       if(Tile2 > 3) { Y2 = 2; X2 = Tile2 - 3; }
       if(Tile2 > 6) { Y2 = 3; X2 = Tile2 - 6; }

       // make sure we are going to subtract the smaller
// number from the larger one.
       if(Y1 - Y2 < 0) {
           temp = Y1;
           Y1 = Y2;
           Y2 = temp;
       }
       if(X1 - X2 < 0) {
           temp = X1;
           X1 = X2;
           X2 = temp;
       }

       return ((Y1 - Y2) + (X1 - X2));

   }
// Now out public functions
public:
   // Possible Error’s to throw (ignore for now)
   class ERROR_ILLEGAL_MOVE{};
   class ERROR_NO_MORE_DIRECTIONS{};
   class ERROR_OUT_OF_BOUNDS{};
   // again to be used as a heuristic, it represents
   // the distance in moves between the current state
   // and the initial state, the fewer the better.
int GetDepth() {
       return Depth;
   }
   
   // 0 parameter constructor, this is only called
   // when we are creating out initial state, so set
   // up the grid array as needed, this initial config
   // will take about 25 moves to complete…
   // for slower machines change the values to a more
   // simple problem.
   CState() {
       Depth   = 0;
       Grid[1] = 6; // for slower machines use 4
       Grid[2] = 1; // for slower machines use 1
       Grid[3] = 7; // for slower machines use 3
       Grid[4] = 3; // for slower machines use 2
       Grid[5] = 0; // for slower machines use 0
       Grid[6] = 4; // for slower machines use 5
       Grid[7] = 5; // for slower machines use 8
       Grid[8] = 8; // for slower machines use 7
       Grid[9] = 2; // for slower machines use 6
       
       // this is a pointer to the parent state, this is
       // the first, so there is no parent.
       PrevState = 0;

       // there is no previous operator, THIS is why we need
       // to enumerate a NONE into the direction variable
       OperatorApplyed = NONE;
   }
   
   // well, as always, you gotta use public functions
   // to get as private variables
   void SetPrevState(CState *Set) {
       PrevState = Set;
   }
   // same as above
   CState* GetPrevState() {
       return PrevState;
   }
   
   // Used to determine weather a move would be legal.
   // eg, you cant move east if the blank is in the most
   // right position.
   bool CanBlankMove(DIRECTION Direction) {
       int Blank = FindBlank();

       switch (Direction) {
       case NORTH:
           if (Blank > 3) {
               return true;
           }
           else {
               return false;
           }
           break;

       case EAST:
           if (Blank != 3 && Blank != 6 && Blank != 9) {
               return true;
           }
           else {
               return false;
           }
           break;

       case SOUTH:
           if (Blank < 7) {
               return true;
           }
           else {
               return false;
           }    
           break;

       case WEST:
           if (Blank != 1 && Blank != 4 && Blank != 7) {
               return true;
           }
           else {
               return false;
           }
           break;

       default:
           return false;
           break;
       }
   }
   
   // again, public functions to get at private variables
   void setgrid(int index, int value) {
       Grid[index] = value;
   }
   
   // if this returns true, This state IS the solution.
   // and its prev state pointer can be used to trace back
   // and find the answer.
   bool Solution() {

       if (Grid[1] == 1 && Grid[2] == 2 && Grid[3] == 3 && Grid[4] == 8 && Grid[5] == 0 &&
           Grid[6] == 4 && Grid[7] == 7 && Grid[8] == 6 && Grid[9] == 5) {

           return true;
       }
       else {
           return false;
       }
   }
   // again, public function to grab private variables
   char GetGridValue(int Index) {

       if (Index < 1 || Index > 9) {
           throw ERROR_OUT_OF_BOUNDS();
       }
       else {
           return Grid[Index];
       }
   }

   // Single parameter constructor.
   // Using adding a state pointer as a parameter
   // when createing a new state causes this construcor
   // to be used, It makes this state identicle to
   // the state that the parameter points to !
   CState(CState* Init) {
       // Make an IDENTICLE copy of Init
       Depth = (Init->GetDepth());

       OperatorApplyed = Init->GetLastOperator();
       PrevState = Init->GetPrevState();

       for (int n=1; n<=9; n++) {
           Grid[n] = Init->GetGridValue(n);
       }
   }
   
   // GRRR again, public function to grap private variable
   // yes it would be easyer to put those variables in
   // public space, but this is good programming pratice.
   DIRECTION GetLastOperator() {
       return OperatorApplyed;
   }
   
// Double Parameter Constructor. This constructor is
// used when a new state is created using 2 parameters
// It first makes the state identicle to the state the
// first parameter points to, THEN performs the operator
// in the second parameter.
   CState(CState* Init, DIRECTION Direction) {
       // Make an Identicle copy, then apply an operator.
       
       int n;
       
       PrevState = Init;

       Depth = (Init->GetDepth() + 1);

       for (n=1; n<=9; n++) {
           Grid[n] = Init->GetGridValue(n);
       }

       MoveBlank(Direction);
   }
   

   // Anouther heuristic, Counts the number of tiles in the
// wrong position.
   int GetWrongTiles() {

       return ((Grid[1] != 1) +
               (Grid[2] != 2) +
               (Grid[3] != 3) +
               (Grid[4] != 3) +
               (Grid[5] != 3) +
               (Grid[6] != 3) +
               (Grid[7] != 3) +
               (Grid[8] != 3) +
               (Grid[9] != 3) +
               (Depth      )); // also use the depth as
                           // a second heuristic. (A*)
   }
   
   // ManhattanDistance is the technical term for
   // the sum of all the distances of where a square is
   // from where it should be,
   int GetManhattanDistance() {

       int Result=0;
       
       Result =          GetDistanceBetween(1, FindBlank(1));
       Result = Result + GetDistanceBetween(2, FindBlank(2));
       Result = Result + GetDistanceBetween(3, FindBlank(3));
       Result = Result + GetDistanceBetween(4, FindBlank(8));
       Result = Result + GetDistanceBetween(5, FindBlank(0));
       Result = Result + GetDistanceBetween(6, FindBlank(4));
       Result = Result + GetDistanceBetween(7, FindBlank(7));
       Result = Result + GetDistanceBetween(8, FindBlank(6));
       Result = Result + GetDistanceBetween(9, FindBlank(5));

       Result = Result + Depth;//use depth as second heuristic(A*)

       return Result;
   }
};

Well, as you can see, that was a HUGE class, however, there is nothing in there that is especially complcated. Just simple data manipulation. The hard part, is keeping track of all the states, and using them in the correct order. Which we are going to do next !!!!

SO, onto page 4, where we will code our List Class.