1998 ACM South Central USA Collegiate Programming Contest
Rice University

Eight

Solution  Judge's input     Judge's output   Clarifications   Comments

Scenario

The 15-puzzle has been around for over 100 years; even if you don't know it by that name, you've seen it.  It is constructed with 15 sliding tiles, each with a number from 1 to 15 on it, and all packed into a 4 by 4 frame with one tile missing.  Let's call the missing tile 'x'; the object of the puzzle is to arrange the tiles so that they are ordered as:

 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.

Input

You will receive, in ``eight.inp'', a description of a configuration of the 8 puzzle.  The description is just a list of the tiles in their initial positions, with the rows listed from top to bottom, and the tiles listed from left to right within a row, where the tiles are represented by numbers 1 to 8, plus 'x'.  For example, this puzzle

 1  2  3
 x  4  6
 7  5  8

is described by this list:

 1 2 3 x 4 6 7 5 8

Output

You will print to standard output either the word ``unsolvable'', if the puzzle has no solution, or a string consisting entirely of the letters 'r', 'l', 'u' and 'd' that describes a series of moves that produce a solution.  The string should include no spaces and start at the beginning of the line.

Sample Input

 2  3  4  1  5  x  7  6  8

Sample Output

ullddrurdllurdruldr

 

Solution

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

Judge's Input

6 4 7 8 5 x 3 2 1

Judge's Output

uldldrurdluulddrurulldrrulldrdr

Clarifications

The primary clarification we had to make on this problem concerned the format of the input: 3 lines or one line.  This is another case where I failed to realize how important this was to the Pascal programmers.

Comments

The solution above essentially implements a breadth-first search to find a shortest solution to the problem.  The fact that the number of puzzle configurations is not too large (eight factorial) means that there is enough storage for both the queue used in the search and the bitset used to identify configurations already searched.  Such a solution would not work for the 15-puzzle, which I originally intended to use for this problem, because there would not be enough memory to handle the data structures.

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