#include <stdio.h>
#include <stdlib.h>

//int init_matrix[] = {0, 1, 2, 3, 4, 5, 6, 7, 8};

struct State
{
  State()
  {
    i = 1;
    j = 1;

    matrix[0] = 4;
    matrix[1] = 1;
    matrix[2] = 2;

    matrix[3] = 7;
    matrix[4] = 0;
    matrix[5] = 3;

    matrix[6] = 8;
    matrix[7] = 5;
    matrix[8] = 6;
  }

  int i, j;
  int matrix[9];
};

enum Move
{
  LEFT,
  RIGHT,
  UP,
  DOWN
};

const int MAX_DEPTH = 8;
int solution[1024];

void print_state(State &state)
{
    printf("%d,%d\n", state.i, state.j);
    printf("%d %d %d\n", state.matrix[0], state.matrix[1], state.matrix[2]);
    printf("%d %d %d\n", state.matrix[3], state.matrix[4], state.matrix[5]);
    printf("%d %d %d\n", state.matrix[6], state.matrix[7], state.matrix[8]);
}


bool goal_state(State &state)
{
    return (state.matrix[0] == 1 &&
            state.matrix[1] == 2 &&
	    state.matrix[2] == 3 &&
	    state.matrix[3] == 4 &&
	    state.matrix[4] == 5 &&
	    state.matrix[5] == 6 &&
	    state.matrix[6] == 7 &&
	    state.matrix[7] == 8 &&
	    state.matrix[8] == 0);
}


void make_move(State &state, Move move)
{
  switch(move)
  {
    case LEFT:
    {
      if (state.j < 2)
      {
        state.matrix[state.i * 3 + state.j] = state.matrix[state.i * 3 + state.j + 1];
        state.matrix[state.i * 3 + state.j + 1] = 0;
        ++state.j;
      }
      break;
    }
    case RIGHT:
    {
      if (state.j > 0)
      {
        state.matrix[state.i * 3 + state.j] = state.matrix[state.i * 3 + state.j - 1];
        state.matrix[state.i * 3 + state.j - 1] = 0;
        --state.j;
      }
      break;
    }
    case UP:
    {
      if (state.i < 2)
      {
        state.matrix[state.i * 3 + state.j] = state.matrix[(state.i + 1) * 3 + state.j];
        state.matrix[(state.i + 1) * 3 + state.j] = 0;
        ++state.i;
      }
      break;
    }
    case DOWN:
    {
      if (state.i > 0)
      {
        state.matrix[state.i * 3 + state.j] = state.matrix[(state.i - 1) * 3 + state.j];
        state.matrix[(state.i - 1) * 3 + state.j] = 0;
        --state.i;
      }

      break;
    }
    default:
    {
    }
  }
}


void print_solution(int depth)
{
    for (int i = 0; i < depth; ++i)
    {
        switch((Move)solution[i])
	{
	    case LEFT:
	    {
		printf("Left\n");
		break;
	    }
	    case RIGHT:
	    {
		printf("Right\n");
		break;
	    }
	    case UP:
	    {
		printf("Up\n");
		break;
	    }
	    case DOWN:
	    {
		printf("Down\n");
		break;
	    }
	    default:
	    {
		break;
	    }
	}
    }
}


int solve_recursive(State &state, int depth, int max_depth)
{
//    print_state(state);

    if (goal_state(state))
    {
        printf("Happy !\n");
        print_state(state);
	print_solution(depth);
        return 0;
    }
    if (depth > max_depth)
    {
       return -1;
    }
    for (int move = LEFT; move <= DOWN; ++move)
    {
       State next_state = state;
       make_move(next_state, (Move)move);
       solution[depth] = move;
       if (solve_recursive(next_state, depth + 1, max_depth) == 0)
       {
	   return 0;
       }
    }
    return -1;
}


int iterative_deepening(State &state)
{
    int max_depth = 1;

    while (true)
    {
	printf("Trying depth = %d ...\n", max_depth);
	if (solve_recursive(state, 0, max_depth) == 0)
	{
	    return 0;
	}
	++max_depth;
    }
    return -1;
}


int main(int argc, char **argv)
{
    printf("Puzzle solver\n");

    State initial_state;
//    print_state(initial_state);

//    make_move(initial_state, LEFT);
//    print_state(initial_state);

//    make_move(initial_state, LEFT);
//    print_state(initial_state);

//    make_move(initial_state, RIGHT);
//    print_state(initial_state);

//    make_move(initial_state, UP);
//    print_state(initial_state);

//    make_move(initial_state, DOWN);
//    print_state(initial_state);

    printf("Solving...\n");
//    solve_recursive(initial_state, 0, 8);
    iterative_deepening(initial_state);

    return 0;
}