Please and thank you in advanced Write a program to solve the 8-Tiles Puzzle usi

Question

Please and thank you in advanced

Write a program to solve the 8-Tiles Puzzle using the best first search algorithm. You need to compare between using the following heuristics to estimate the distance to the goal:

·h1= 0 (this will be the breadth first search) ·

h2= number of misplaced tiles ·

h3= sum of distances heuristic                    

· Your program will prompt the user to enter a starting state (you can use the number zero to represent the blank).

· The output of your program will show the required movements to reach the goal state, the total number of states in the search, and the path length.

· Test your program on the following two starting states:

Starting state 1 at column 2 row and Starting state 2 will be column 1 row 3 with the     Goal state state at the center of the tiles

· For each heuristic on each of the above test states, determine:

· T: total number of states in the search. ·

L: path length.

I am trying to create a c++ program and would like some assistance with this.

Explanation / Answer

the code is c++

#include <iostream.h>
#include <fstream.h>

#define BITS_PER_WORD (8*sizeof(unsigned))

#define ROW_SIZE 3
#define PERM_SIZE (ROW_SIZE*ROW_SIZE)

template <class T>
inline void swap (T& a, T& b)
{ T t = a; a = b; b = t; }

void itop(unsigned perm[], unsigned n)
{
perm[0] = 0;
for (unsigned i = 1; i < PERM_SIZE; ++i)
    {
      unsigned p = i - n % (i+1);
      perm[i] = perm[p];
      perm[p] = i;
      n /= i+1;
    }
}

unsigned ptoi(unsigned const perm[])
{
unsigned n = 0;
unsigned i, pcpy[PERM_SIZE], invp[PERM_SIZE];

for (i = 0; i < PERM_SIZE; ++i)
    {
      pcpy[i] = perm[i];
      invp[perm[i]] = i;
    }

for (i = PERM_SIZE-1; i > 0; --i)
    {
      unsigned p = invp[i];
      pcpy[p] = pcpy[i];
      pcpy[i] = i;
      invp[pcpy[p]] = p;
      invp[i] = i;
      n *= i+1;
      n += i - p;
    }

return n;
}

struct Arrangement
{
unsigned permCode;
unsigned parent;
};

void addToQueue(unsigned parent, unsigned perm[],
                unsigned bitset[],
                Arrangement permBuffer[], unsigned& last)
{
unsigned code = ptoi(perm);
unsigned m = code/BITS_PER_WORD;
unsigned n = code%BITS_PER_WORD;
if ( (bitset[m] >> n) & 1)
    return;

bitset[m] |= 1 << n;
permBuffer[last].parent = parent;
permBuffer[last++].permCode = code;
}

int main()
{
ifstream in("eight.inp");
unsigned initperm[PERM_SIZE];
unsigned factorial = 1;
unsigned i;
for (i = 0; i < PERM_SIZE; ++i)
    {
      unsigned n;
      in >> n;

      if (in.good())
        initperm[i] = n-1;
      else
        {
          initperm[i] = PERM_SIZE-1;
          in.clear();
          char x;
          in.get(x);
        }
      factorial *= i+1;
    }

unsigned initcode = ptoi(initperm);

unsigned maskSize = (factorial + BITS_PER_WORD - 1) / BITS_PER_WORD;
unsigned* bitset = new unsigned[maskSize];
for (i = 0; i < maskSize; ++i)
    bitset[i] = 0;

bitset[initcode/BITS_PER_WORD] |= 1 << (initcode % BITS_PER_WORD);

unsigned first = 0;
unsigned last = 0;
Arrangement* permBuffer = new Arrangement [factorial/2];
permBuffer[last].parent = -1;
permBuffer[last++].permCode = initcode;

unsigned code;
while ((code = permBuffer[first].permCode) > 1 &&
         first < factorial/2)
    {
      unsigned perm[PERM_SIZE];
      itop(perm, code);

      // find the blank
      unsigned i;
      for (i = 0; perm[i] != PERM_SIZE-1 && i < PERM_SIZE; ++i)
        {}

      unsigned blank_row = i / ROW_SIZE;
      unsigned blank_col = i % ROW_SIZE;

      if (blank_row > 0)
        {
          swap (perm[i], perm[i-ROW_SIZE]);
          addToQueue(first, perm, bitset, permBuffer, last);
          swap (perm[i], perm[i-ROW_SIZE]);
        }

      if (blank_row < ROW_SIZE-1)
        {
          swap (perm[i], perm[i+ROW_SIZE]);
          addToQueue(first, perm, bitset, permBuffer, last);
          swap (perm[i], perm[i+ROW_SIZE]);
        }

      if (blank_col > 0)
        {
          swap (perm[i], perm[i-1]);
          addToQueue(first, perm, bitset, permBuffer, last);
          swap (perm[i], perm[i-1]);
        }

      if (blank_col < ROW_SIZE-1)
        {
          swap (perm[i], perm[i+1]);
          addToQueue(first, perm, bitset, permBuffer, last);
          swap (perm[i], perm[i+1]);
        }
      ++first;
    }

if (permBuffer[first].permCode == 1)
    {
      cout << "unsolvable ";
      return 0;
    }

char revpath[1000];
unsigned nextChar = 0;

unsigned p;
unsigned* perm = new unsigned[PERM_SIZE];
itop(perm, permBuffer[first].permCode);
unsigned blank;
for (blank = 0; perm[blank] != PERM_SIZE-1; ++blank)
    {}

unsigned* par_perm = new unsigned[PERM_SIZE];
while ((p = permBuffer[first].parent) != -1)
    {
      itop(par_perm, permBuffer[p].permCode);

      unsigned par_blank;
      for (par_blank = 0; par_perm[par_blank] != PERM_SIZE-1; ++par_blank)
        {}

      char c;
      if (par_blank > blank)
        if (par_blank == blank + ROW_SIZE)
          c = 'u';
        else
          c = 'l';
      else
        if (par_blank == blank - ROW_SIZE)
          c = 'd';
        else
          c = 'r';

      revpath[nextChar++] = c;

      swap(perm, par_perm);
      blank = par_blank;
      first = p;
    }

while (nextChar--)
    cout << revpath[nextChar];
cout << " ";

return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.