![]() ![]() ![]() |
![]() ![]() |
Eight
Solution Judge's input Judge's output Clarifications Comments
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 x
where the only legal operation is to exchange 'x' with one of the tiles with which it shares an edge. As an example, the following sequence of moves solves a slightly scrambled puzzle:
1 2 3 4
1 2 3 4 1 2 3 4
1 2 3 4
5 6 7 8
5 6 7 8 5 6 7 8
5 6 7 8
9 x 10 12
9 10 x 12 9 10 11 12 9 10 11
12
13 14 11 15 13 14 11 15
13 14 x 15 13 14 15 x
r-> d->
r->
The letters in the previous row indicate which neighbor of the 'x' tile is swapped with the 'x' tile at each step; legal values are 'r','l','u' and 'd', for right, left, up, and down, respectively.
Not all puzzles can be solved; in 1870, a man named Sam Loyd was famous
for distributing an unsolvable version of the puzzle, and
frustrating many people. In fact, all you have to do to make
a regular puzzle into an unsolvable one is to swap two tiles (not counting
the missing 'x' tile, of course).
In this problem, you will write a program for solving the less well-known
8-puzzle, composed of tiles on a three by three
arrangement.
1 2 3
x 4 6
7 5 8
is described by this list:
1 2 3 x 4 6 7 5 8
#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\n";
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 <<
"\n";
return 0;
}
The judge's test case requires 31 moves to solve. This test case was generated by starting the breadth first search from the solution and working backwards until every legal configuration had been explored; this is the last of those configurations.
The most creative solution used randomness to search blindly for either the solution or a particular infeasible configuration. There was some discussion about whether this answer should be accepted, even if it worked, because it might not work on some case. We searched but never found the case that could whip it - that is, make it run beyond 30 seconds. It's interesting to consider whether a hybrid approach, that used both memory and randomness, could solve the 15 puzzle in a reasonable time.
In case you wondered, the generalized 15-puzzle (that is, the n-puzzle,
where n is one less than some perfect square) is very hard, as proven in
a paper: D. Ratner and M. Warmuth, Finding a shortest solution for the
N*N-extension of the 15-puzzle is intractable, J. Symb. Comp. 10 (1990)
111-137