Implement an interactive 8-tile puzzle. The program will first generate a 3*3 pu

Question

Implement an interactive 8-tile puzzle. The program will first generate a 3*3 puzzle, with eight tiles numbered from 1 to 8 randomly distributed in the nine slots without repeated numbers, and an empty slot. Then the user can press the following button on the keyboard to move the puzzle or quit (both upper-case and lower-case letters are allowed): The Up button or W: If there is a tile that can be moved up one slot, move it up. Otherwise, do nothing. The Down button or S: If there is a tile that can be moved down one slot, move it down. Otherwise, do nothing. The Left button or A: If there is a tile that can be moved left one slot, move it left. Otherwise, do nothing. The Right button or D: If there is a tile that can be moved right one slot, move it right. Otherwise, do nothing. Q: Quit the program immediately. Note. Please use at least a two-dimension array in your program. Hints: How to generate a random permutation of number 0 to 8 without repeated numbers: Initialize an int array: int a[9] = {0, 1, 2, 3, 4, 5, 6, 7, 8}. For each element except the last one, randomly generate a number n. ranging from 0 to "the number of elements later in the array", and then swap the element with the element "n cells later". E.g. if you are dealing with a[3]. randomly generate a number from 0 to 5. If the number is 2, swap a[3] and a[3 + 2] (that is, a[5]). You can use the functions time, stand and rand for randomization. Use the system call system("cls"); to clear the screen. Instead of using scanf or getchar, you can use getch to directly get a character from keyboard. [Usage: char ch = getch(); (It can be used only in Windows systems.) The ASCII code of the Up, Down, Left and Right buttons are 72, 80, 75 and 77, respectively. Here's an example theme of how the program will execute:

Explanation / Answer

This will help u :

#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;
}

rgds & plz rate

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

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