// Fifteen Puzzle solver

#include <iostream>
#include <string>
#include <sstream>
using namespace::std;

const int width = 4, height = 4, length = width * height;
int   squares[length];
int   blank = 0;
bool  initializing = true;
int   dont_touch_list[length];
int   sp = -1;

void   init();
void   move( int number );
void   display();
void   print_squares_array();
string format( int number );
int    find_location_of( int number );
bool   not_on_dont_touch_list( int position );
void   print_dont_touch_list( string preface );
void   swap( int one, int two );

void move_number( int current_number );
void move_to_x( int& position, int target_x );
void move_to_y( int& position, int target_y );
void move_blank_to( int destination );
void move_blank_to_x( int& blank_x, int& blank_y, int destination_x );
void move_blank_to_y( int& blank_x, int& blank_y, int destination_y );
void do_last_square_on_row( int vertical, int horizontal );
void do_top_number_of_column( int current_number );

int main( void ) {
   init();
   int current_number = 1;
   
   while (current_number < width * (height-2) + 1)
      move_number( current_number++ );

   // Do the last 2 rows, from left column to right      
   cout << "main: bottom 2 rows\n";
   for (int i=1; i < width - 1; i++) {
      // Do the bottom number of this column
      current_number = width * (height - 1) + i;
      cout << "main: first next is " << current_number << endl;
      move_number( current_number );
      
      // Do the top number of this column
      do_top_number_of_column( current_number - width );
   }
   
   // Do the last 2 columns of the last 2 rows
   // Put the top-left square in place
   move_number( width * (height - 1) - 1 );
   // Put the blank in the bottom-right corner
   move_blank_to( width * height - 1 );
}

void move_number( int current_number ) {
   int location, target_x, target_y;
   location = find_location_of( current_number );
   target_x = (current_number-1) % width;
   target_y = (current_number-1) / width;
   cout << "main: number " << current_number << ", location " << location
        << ", target_x " << target_x << ", target_y " << target_y << endl;
   dont_touch_list[++sp] = location;
   print_dont_touch_list( "main: next added     " );
   move_to_x( location, target_x );
   move_to_y( location, target_y );    // this has do_last_square_on_row() call
}

void move_to_x( int& position, int target_x ) {
   int current_x = position % width;
   if (current_x == target_x)
      return;
cout << "move_to_x: current_x " << current_x << ", target_x " << target_x << endl;
   int direction = (current_x < target_x) ? 1 : -1;
   while (current_x != target_x) {
      move_blank_to( position + direction );
      swap( position, position + direction );
      position = position + direction;
      // Update the last entry on the dont_touch_list
      dont_touch_list[sp] = position;
      current_x += direction;
}  }

void move_to_y( int& position, int target_y ) {
   int current_y = position / width;
   if (current_y == target_y)
      return;
   cout << "move_to_y: current_y " << current_y << ", target_y " << target_y << "     ";
   print_dont_touch_list( "" );
   bool last_square_on_row = false;
   int direction = (current_y < target_y) ? 1 : -1;
   //  1  2  3    
   //  5  6  8  4 
   // 13 11 15  7 
   //  9 14 10 12 
   // It is okay to "step on" (or "through") the square that needs to be moved, because
   // we are putting the square where it needs to go
   if (current_y-1 == target_y  &&  position-width == blank) {
      swap( position, blank );
      dont_touch_list[sp] = position-width;
      return;
   }
   // Check if last on row
   if (position % width == width - 1) {
      target_y++;
      cout << "     new target_y " << target_y << endl;
      last_square_on_row = true;
   }
   while (current_y != target_y) {
      move_blank_to( position + (direction * width) );
      swap( position, position + (direction * width) );
      position = position + (direction * width);
      // Update the last entry on the dont_touch_list
      dont_touch_list[sp] = position;
      current_y += direction;
   }
   if (last_square_on_row) {
      cout << "move_to_y: moving blank to " << (position + width) << endl;
      move_blank_to( position + width );
      do_last_square_on_row( width, 1 );
}  }

void move_blank_to( int destination ) {
   int blank_x = blank % width;
   int blank_y = blank / width;
   int destination_x = destination % width;
   int destination_y = destination / width;
   cout << "move_blank_to: blank - " << blank << " " << blank_x << " " << blank_y
        << ", destination - " << destination << " " << destination_x << " "
        << destination_y << endl;
   //  9  3  2 11 
   //  1  5 15  8 
   //     4 10  6 
   // 14 13  7 12 
   // 1st blank_to_x() returns immediately, blank_to_y() works, 2nd blank_to_x() works
   int entry_sp = sp;
   move_blank_to_x( blank_x, blank_y, destination_x );
   move_blank_to_y( blank_x, blank_y, destination_y );
   move_blank_to_x( blank_x, blank_y, destination_x );
   sp = entry_sp;
}

void move_blank_to_x( int& blank_x, int& blank_y, int destination_x ) {
   int direction = (blank_x < destination_x) ? 1 : -1;
   print_dont_touch_list( "move_blank_to_x: " );
   while (blank_x != destination_x) {
      if (not_on_dont_touch_list(blank + direction)) {
         cout << "move_blank_to_x: swap " << blank << " " << (blank + direction) << '\n';
         swap( blank, blank + direction );
         blank_x += direction;
      // Try moving up and around
      } else if (blank_y != 0  &&  not_on_dont_touch_list(blank - width)) {
         cout << "move_blank_to_x: move up and around\n";
         dont_touch_list[++sp] = blank;
         swap( blank, blank - width );
         blank_y = blank_y - 1;
         dont_touch_list[++sp] = blank;
         swap( blank, blank + direction );
         blank_x += direction;
      // Try moving down and around
      } else if (blank_y < height-1  &&  not_on_dont_touch_list(blank + width)) {
         cout << "move_blank_to_x: move down and around\n";
         dont_touch_list[++sp] = blank;
         swap( blank, blank + width );
         blank_y = blank_y + 1;
         dont_touch_list[++sp] = blank;
         swap( blank, blank + direction );
         blank_x += direction;
      } else {
         cout << "move_blank_to_x: could not get out of corner\nPress <Return>\n";
         string str;
         getline( cin, str );
}  }  }

void move_blank_to_y( int& blank_x, int& blank_y, int destination_y ) {
   int direction = (blank_y < destination_y) ? 1 : -1;
   cout << "move_blank_to_y: blank " << blank << " " << blank_x << " " << blank_y
        << "      dest y " << destination_y << endl;
   print_dont_touch_list( "move_blank_to_y: " );
   while (blank_y != destination_y) {
      if (not_on_dont_touch_list(blank + (direction * width))) {
         cout << "move_blank_to_y: swap " << blank << " "
              << (blank + (direction * width)) << '\n';
         swap( blank, blank + (direction * width) );
         blank_y = blank_y + direction;
      // Try moving right and around
      } else if (blank_x < width-1  &&  not_on_dont_touch_list(blank + 1)) {
         cout << "move_blank_to_y: move right and around\n";
         dont_touch_list[++sp] = blank;
         swap( blank, blank + 1 );
         blank_x = blank_x + 1;
         dont_touch_list[++sp] = blank;
         swap( blank, blank + (direction * width) );
         blank_y = blank_y + direction;
      // Try moving left and around
      } else if (blank_x != 0  &&  not_on_dont_touch_list(blank - 1)) {
         cout << "move_blank_to_y: move left and around\n";
         dont_touch_list[++sp] = blank;
         swap( blank, blank - 1 );
         blank_x = blank_x - 1;
         dont_touch_list[++sp] = blank;
         swap( blank, blank + (direction * width) );
         blank_y += direction;
      } else {
         cout << "move_blank_to_y: could not get out of corner\n";
}  }  }

void do_top_number_of_column( int current_number ) {
   int location = find_location_of( current_number );
   cout << "main: second next is " << current_number << ", location " << location << endl;
   // If the next number is already in place, move on
   if (current_number-1 == location)
      return;
   // If the next number is almost in place, swap and move on
   if (current_number == location  &&  blank == current_number-1) {
      dont_touch_list[++sp] = blank;
      swap( location, blank );
      return;
   }
   dont_touch_list[++sp] = location;
   move_to_x( location, (current_number-1) % width + 1 );
   move_to_y( location, (current_number-1) / width );
   move_blank_to( location + 1 );
   do_last_square_on_row( 1, -width );
}

void do_last_square_on_row( int vertical, int horizontal ) {
   cout << "do_last_square_on_row\n";
   swap( blank, blank - vertical );
   swap( blank, blank - vertical );
   swap( blank, blank - horizontal );
   swap( blank, blank + vertical );
   swap( blank, blank + horizontal );
   swap( blank, blank + vertical );
   swap( blank, blank - horizontal );
   swap( blank, blank - vertical );
   swap( blank, blank - vertical );
   swap( blank, blank + horizontal );
   swap( blank, blank + vertical );
   dont_touch_list[sp] -= vertical;
}

void init() {
   srand( time( 0 ) );
   for (int i=1; i < length; i++)
      squares[i-1] = i;
   squares[length-1] = 0;
   blank = length - 1;
   for (int i=0; i < 400; i++)
      move( rand() % (length-1) + 1 );
   initializing = false;
   //display();
}

void print_squares_array() {
   for (int i=0; i < length; i++)
      cout << squares[i] << ' ';
   cout << "--- " << blank << endl;
}

string format( int number ) {
   if (number == 0) return "   ";
   stringstream ss;
   ss << (number < 10 ? " " : "") << number << " ";
   return ss.str();
}

bool not_on_dont_touch_list( int position ) {
   for (int i=0; i <= sp; i++)
      if (dont_touch_list[i] == position)
         return false;
   return true;
}

void print_dont_touch_list( string preface ) {
   cout << preface;
   for (int i=0; i <= sp; i++)
      cout << dont_touch_list[i] << ' ';
   cout << endl;
}

int find_location_of( int number ) {
   for (int i=0; i < length; i++)
      if (squares[i] == number)
         return i;
   cout << "find_location_of: " << number << " was not found\n";
   return 0;
}

void display() {
   cout << '\n';
   print_squares_array();                // vlh
   for (int i=0; i < height; i++) {
      for (int j=0; j < width; j++)
         cout << format( squares[i * width + j] );
      cout << '\n';
   }
   string str;                           // vlh
   getline( cin, str );                  // vlh
}
void swap( int one, int two ) {
   int     temp = squares[one];
   squares[one] = squares[two];
   squares[two] = temp;
   if (squares[one] == 0)
      blank = one;
   else if (squares[two] == 0)
      blank = two;
   else
      cout << "swap: blank not here " << one << " " << two << endl;
   if (initializing)                     // vlh
      return;                            // vlh
   display();                            // vlh
}
bool try_above( int pos ) {
   if (pos < width) return false;
   if (squares[pos-width] != 0  &&  ! try_above(pos-width)) return false;
   // the slot above is empty  OR  the move above succeeded
   swap( pos, pos-width );
   return true;
}
bool try_below( int pos ) {
   if (pos > width*(height-1)-1) return false;
   if (squares[pos+width] != 0  &&  ! try_below(pos+width)) return false;
   swap( pos, pos+width );
   return true;
}
bool try_left( int pos ) {
   if (pos%width == 0) return false;
   if (squares[pos-1] != 0  &&  ! try_left(pos-1)) return false;
   swap( pos, pos-1 );
   return true;
}
bool try_right( int pos ) {
   if (pos%width == width-1) return false;
   if (squares[pos+1] != 0  &&  ! try_right(pos+1)) return false;
   swap( pos, pos+1 );
   return true;
}
void move( int num ) {
   int i;    ////// find the slot this number is in //////
   for (i=0; i < length; ++i)
      if (squares[i] == num)
         break;
   if (try_above(i)) return;
   if (try_below(i)) return;
   if (try_left(i)) return;
   if (try_right(i)) return;
}