// 1) print the board
// 2) print the board with loops
// 3) add an array to maintain a mapping of location and value
// 4) add cin, search, update
// 5) draw_board(), move(), swap()
// 6) mix up the numbers
// 7) recursive move of entire row/column

#include <iostream>
#include <string>
#include <sstream>
#include <iomanip>
using std::cout;
using std::cin;
using std::string;
using std::setw;

#if 0

// 1) print the board

int main() {
   cout << " 1  2  3  4\n";
   cout << " 5  6  7  8\n";
   cout << " 9 10 11 12\n";
   cout << "13 14 15 16\n";
}

//  1  2  3  4
//  5  6  7  8
//  9 10 11 12
// 13 14 15 16



// 2) print the board with loops

int main() {
   int number = 1;
   for (int i=0; i < 4; i = i + 1) {
      for (int j=0; j < 4; j = j + 1) {
         cout << setw(3) << number;
         number = number + 1;
      }
      cout << '\n';
}  }


int main() {
   for (int i=0; i < 4; i = i + 1) {
      for (int j=0; j < 4; j = j + 1)
         cout << setw(3) << i * 4 + j + 1;
      cout << '\n';
}  }


int main() {
   for (int i=1; i <= 16; i = i + 1) {
      cout << setw(3) << i;
      if (i % 4 == 0)
         cout << '\n';
}  }



// 3) add an array to maintain a mapping of location and value

int main() {
   int numbers[] = { 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16 };
   for (int i=0; i < 16; i = i + 1) {
      cout << setw(3) << numbers[i];
      if ((i+1) % 4 == 0)
         cout << '\n';
}  }



// 4) add cin, search, update

int main() {
   int numbers[] = { 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16 };
   int number;
   while (true) {
      cout << '\n';
      for (int i=0; i < 16; i = i + 1) {
         if (numbers[i] == 0)
            cout << "   ";
         else
            cout << setw(3) << numbers[i];
         if ((i+1) % 4 == 0)
            cout << '\n';
      }
      cout << "\nNumber: ";
      cin >> number;
      for (int i=0; i < 16; i = i + 1)
         if (numbers[i] == number) {
            numbers[i] = 0;
            break;
}  }     }

  1  2  3  4
  5  6  7  8
  9 10 11 12
 13 14 15 16

Number: 2

  1     3  4
  5  6  7  8
  9 10 11 12
 13 14 15 16

Number: 13

  1     3  4
  5  6  7  8
  9 10 11 12
    14 15 16

Number: 11

  1     3  4
  5  6  7  8
  9 10    12
    14 15 16



// 5) draw_board(), move(), swap()

void draw_board( int numbers[] ) {
   cout << '\n';
   for (int i=0; i < 16; i = i + 1) {
      if (numbers[i] == 0)
         cout << "   ";
      else
         cout << setw(3) << numbers[i];
      if ((i+1) % 4 == 0)
         cout << '\n';
   }
   cout << "\nNumber: ";
}

void swap( int numbers[], int position_one, int position_two ) {
   int temp              = numbers[position_one];
   numbers[position_one] = numbers[position_two];
   numbers[position_two] = temp;
}

void move( int numbers[], int number ) {
   int i;
   for (i=0; i < 16; i = i + 1)
      if (numbers[i] == number)
         break;
   if (i == 16)
      return;
   // if i is not on the top row AND the space is above
   if      (i / 4 > 0  &&  numbers[i-4] == 0)
      swap( numbers, i, i-4 );
   // if i is not on the bottom row AND the space is below
   else if (i / 4 < 3  &&  numbers[i+4] == 0)
      swap( numbers, i, i+4 );
   // if i is not in the left column AND the space is to the left
   else if (i % 4 > 0  &&  numbers[i-1] == 0)
      swap( numbers, i, i-1 );
   // if i is not in the right column AND the space is to the right
   else if (i % 4 < 3  &&  numbers[i+1] == 0)
      swap( numbers, i, i+1 );
}

int main() {
   int numbers[] = { 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,0 };
   int number;
   while (true) {
      draw_board( numbers );
      cin >> number;
      move( numbers, number );
}  }

  1  2  3  4
  5  6  7  8
  9 10 11 12
 13 14 15

Number: 15

  1  2  3  4
  5  6  7  8
  9 10 11 12
 13 14    15

Number: 11

  1  2  3  4
  5  6  7  8
  9 10    12
 13 14 11 15

Number: 10

  1  2  3  4
  5  6  7  8
  9    10 12
 13 14 11 15



// 6) mix up the numbers

void draw_board( int numbers[] ) {
   cout << '\n';
   for (int i=0; i < 16; i = i + 1) {
      if (numbers[i] == 0)
         cout << "   ";
      else
         cout << setw(3) << numbers[i];
      if ((i+1) % 4 == 0)
         cout << '\n';
   }
   cout << "\nNumber: ";
}

void swap( int numbers[], int position_one, int position_two ) {
   int temp              = numbers[position_one];
   numbers[position_one] = numbers[position_two];
   numbers[position_two] = temp;
}

void move( int numbers[], int number ) {
   int i;
   for (i=0; i < 16; i = i + 1)
      if (numbers[i] == number)
         break;
   if (i == 16)                                // look for space:
      return;
   if      (i / 4 > 0  &&  numbers[i-4] == 0)  //    above
      swap( numbers, i, i-4 );
   else if (i / 4 < 3  &&  numbers[i+4] == 0)  //    below
      swap( numbers, i, i+4 );
   else if (i % 4 > 0  &&  numbers[i-1] == 0)  //    to the left
      swap( numbers, i, i-1 );
   else if (i % 4 < 3  &&  numbers[i+1] == 0)  //    to the right
      swap( numbers, i, i+1 );
}

int main() {
   int numbers[] = { 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,0 };
   srand( time( 0 ) );
   for (int i=0; i < 600; i = i + 1)
      move( numbers, rand() % 15 + 1 );

   int number;
   while (true) {
      draw_board( numbers );
      cin >> number;
      move( numbers, number );
}  }

     6  4 14
  2  1  7  8
  9  3 13 12
 11  5 10 15

Number: 6

  6     4 14
  2  1  7  8
  9  3 13 12
 11  5 10 15

Number: 1

  6  1  4 14
  2     7  8
  9  3 13 12
 11  5 10 15

Number: 2

  6  1  4 14
     2  7  8
  9  3 13 12
 11  5 10 15



// 7) recursive move of entire row/column

void draw_board( int numbers[] ) {
   cout << '\n';
   for (int i=0; i < 16; i = i + 1) {
      if (numbers[i] == 0)
         cout << "   ";
      else
         cout << setw(3) << numbers[i];
      if ((i+1) % 4 == 0)
         cout << '\n';
   }
   cout << "\nNumber: ";
}

void swap( int numbers[], int position_one, int position_two ) {
   int temp              = numbers[position_one];
   numbers[position_one] = numbers[position_two];
   numbers[position_two] = temp;
}

bool try_above( int numbers[], int pos ) {
   if (pos / 4 == 0) return false;
   if (numbers[pos-4] != 0  &&  ! try_above(numbers, pos-4)) return false;
   // the slot above is empty  OR  the move above succeeded
   swap( numbers, pos, pos-4 );
   return true;
}
bool try_below( int numbers[], int pos ) {
   if (pos / 4 == 3) return false;
   if (numbers[pos+4] != 0  &&  ! try_below(numbers, pos+4)) return false;
   swap( numbers, pos, pos+4 );
   return true;
}
bool try_left( int numbers[], int pos ) {
   if (pos % 4 == 0) return false;
   if (numbers[pos-1] != 0  &&  ! try_left(numbers, pos-1)) return false;
   swap( numbers, pos, pos-1 );
   return true;
}
bool try_right( int numbers[], int pos ) {
   if (pos % 4 == 3) return false;
   if (numbers[pos+1] != 0  &&  ! try_right(numbers, pos+1)) return false;
   swap( numbers, pos, pos+1 );
   return true;
}

void move( int numbers[], int number ) {
   int i;
   for (i=0; i < 16; i = i + 1)
      if (numbers[i] == number)
         break;
   if (i == 16) return;
   if (try_above( numbers, i )) return;
   if (try_below( numbers, i )) return;
   if (try_left(  numbers, i )) return;
   try_right( numbers, i );
}

int main() {
   int numbers[] = { 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,0 };
   srand( time( 0 ) );
   for (int i=0; i < 600; i = i + 1)
      move( numbers, rand() % 15 + 1 );

   int number;
   while (true) {
      draw_board( numbers );
      cin >> number;
      move( numbers, number );
}  }

#endif