Thanks to Julio Marchi for this space in MSX All
  

Games Course



8-Puzzle


  Portugues

  A puzzle game where you must place in order 8 blocks on a 3x3 board, by moving the blocks to the hole.
  This game is a variation of N-Puzzle game, where we can also find the 15-Puzzle, 24-Puzzle etc.


1. Game Construction
  The game will be programmed in C and it also compatible with PCs. Thus, it can be easly ported to Pascal.


  Game board

  The game board can be built using a 3x3 matrix or an array of 9 positions. Both solutions will be presented.

3x3 Matrix Array of 9 
int board[3][3], HX, HY, moves;

int board[9], pos, moves;

  For the 3x3 matrix, we must store the X and Y hole coordinates in HX and HY, respectively. For the array, we only store the hole position in pos. The variable moves counts the number of moves performed by the player to solve the game.
  Once C arrays and matrixes ranges from 0 to N-1, the hole coordinates or position will also range from 0 to N-1. Nevertheless, the block labels ranges from 1 to 8. So, we must pay attention to this issue.
  The initial board configuration cannot came up from a random sequence numbers, once it may result on a game without solution. According to that, the solution to get a valid initial sequence will be the same used in the real game: from an ordered sequence, do N moves to shuffle them.


  Shuffle

  First of all, a function will place the numbers in order, reserving the value 0 for the hole.

3x3 Matrix Array of 9 
void end_board()
{
  int x,y,val=1;

  for (y=0; y<3; y++)
  {
    for (x=0; x<3; x++)
      board[x][y] = val++;
  }

  board[2][2] = 0;
  HX=2;
  HY=2;
}

void end_board()
{
  int p,val=1;

  for (p=0; plt&;9; p++)
    board[p] = val++;

  board[8] = 0;
  pos=8;
}

  Then, it is necessary to perform N successive moves to shuffle the numbers. Thus, before we must take a look how to swap blocks.


  Possible moves

  The possible moves analysis are always performed based on the hole position.
  For the 3x3 matrix, the analysis is done at executing time. From a proposed shift dx and dy to the hole position HX e HX, we check if:
  • The resulting coordinates HX+dx and HY+dy lie on the board's limits;
  • The sum dx + dy is NOT equal 0 (hole do not move); and
  • The sum dx + dy is NOT greater than 1 (move in diagonal).
  Obs: -1 < dx < 1 e -1 < dy < 1

  For the array of 9, we will store all possible moves for each hole position in an array. The swapping is done directly between the current hole position and one of the possible positions.
  The next figure shows the possible moves (green) for each hole position (red).

 

  Now we have:

Array of 9 
char possible_moves[9][4] = {"24  ","135 ","26  ","157 ",
                             "2468","359 ","48  ","579 ",
                             "68  "};
int total_moves[9] = {2,3,2,3,4,3,2,3,2};

  Once standard C do not return the length of a string, we store the total amount of moves on a new array called total_moves.

  The swapping codes are:

3x3 Matrix Array of 9 
int swap_pos(int x, int y)
{
  int temp;

  if ((x==HX) && (y==HY))
    return 0;

  if ((x>2) || (x<0) || (y>2) || (y<0))
    return 0; 

  if (abs(HX-x)+abs(HY-y) > 1)
    return 0;

  temp = board[HX][HY];
  board[HX][HY] = board[x][y];
  board[x][y] = temp;

  HX=x;
  HY=y;

  return 1;
}

int get_pm_value(int i)
{
  return (int) possible_moves[pos][i] - 49;
}

int valid_move(int p)
{
  int i, pp;

  for (i=0; i<4; i++)
  {
    pp = get_pm_value(i);
    if (pp == p)
      return 1;
  }

  return 0;
}

int swap_pos(int p)
{
  int temp;

  if ((p>8) || (p<0))
    return 0; 

  if (!valid_move(p))
    return 0;

  temp = board[pos];
  board[pos] = board[p];
  board[p] = temp;

  pos=p;

  return 1;
}

  On the array of 9, the possible move value comes from the character (ASCII code) conversion to integer value in the function get_pm_value. In order to adapt the position value to the C arrays and matrix indexes, this function also converts the position to the ranging from 0 to N-1. Example of this process in Basic: 
Q = "2"
P = ASC(Q) - 48
PRINT P
 2

P = P-1
PRINT P
 1
  For both cases the parameters passed to the functions are the new hole position.
  After swapping, the hole position is updated.


  Shuffle code

  After we see how to swap blocks, me are ready to shuffle.

3x3 Matrix Array of 9 
void shuffle_board()
{
  int x,y,r,rounds=50;
  int flag;

  srand(time(NULL));

  for (r=1; r<=rounds; r++)
  {
    flag=0;
    while (flag!=1)
    {
      flag = 1;
      x=rand()%3 - 1;
      y=rand()%3 - 1;

      flag = swap_pos(HX+x,HY+y);
    }
  }
}

void shuffle_board()
{
  int i,p,r,rounds=50;

  srand(time(NULL));

  for (r=1; r<=rounds; r++)
  {
    i = rand()%total_moves[pos];
    p = get_pm_value(i);
    swap_pos(p);
  }
}

  For the 3x3 matrix, it picks up randomly values for dx and dy and only goes on if the move is valid. Otherwise, it tries another values until they are valid.
  The solution for the Array of 9 more intelligent, once it is possible to pick up directly one of a valid move stored on possible_moves array.


  Initialization and board print

  The following codes complete the first step. A function is responsible for the board initialization and another one for printing the board.

3x3 Matrix Array of 9 
void print_board()
{
  int x,y;

  for (y=0; y<3; y++)
  {
    for (x=0; x<3; x++)
    {
      if (board[x][y] == 0)
        printf("  ");
      else
        printf("%d ",board[x][y]);
    }
    printf("\n");
  }
}

void start_board()
{
  end_board();
  shuffle_board();
}

void print_board()
{
  int p;

  for (p=0; p<9; p++)
  {
    if (board[p] == 0)
      printf("  ");
    else
      printf("%d ",board[p]);

    if ((p+1) % 3 == 0)
      printf("\n");
  }
}

void start_board()
{
  end_board();
  shuffle_board();
}


2. Player Control
  This is a single player game. So, the program must read the block label from the keyboard the player whishes to move. For that:
  • The block label must range from 1 to 8; and
  • The move must be valid.
3x3 Matrix e Array of 9 
void player_turn()
{
  int num, flag=0;

  while (flag!=1)
  {
    flag=1;
    printf("Choose a number to move: ");
    scanf("%d",&num);

    if ((num < 1) || (num > 8))
    {
      flag=0;
      printf("The number must range from 1 to 8!\n");
    }

    if (move_square(num)!=1)
    {
      flag=0;
      printf("The number %d cannot be moved!\n",num);
     }
  }
}


  Converting from block label to real board position

  The user selects the block label (number) and not its coordinates. According to that, we must locate the block position on the board.

3x3 Matrix Array of 9 
void get_num_coords(int num, int *xx, int *yy)
{
  int x,y;

  for (y=0; y<3; y++)
  {
    for (x=0; x<3; x++)
    {
      if (board[x][y] == num)
      {
        *xx=x;
        *yy=y;
      }
    }
  }
}

void get_num_pos(int num, int *pp)
{
  int p;

  for (p=0; p<9; p++)
  {
    if (board[p] == num)
      *pp=p;
  }
}


  Swapping

  After locating the referred block, it performs a swapping.

3x3 Matrix Array of 9 
int move_square(int num)
{
  int x,y;

  get_num_coords(num, &x, &y);

  if (swap_pos(x,y)!=1)
    return 0;

  return 1;
}

int move_square(int num)
{
  int p;

  get_num_pos(num, &p);

  if (swap_pos(p)!=1)
    return 0;

  return 1;
}

  If the move is invalid, the function notifies returning 0.


  Checking for game solution

  The checking for game solution routine is quite simple, once all we have to do is to verify if the numbers are ordered in the board.

3x3 Matrix Array of 9 
int check_win()
{
  int x,y,num=1;

  for (y=0; y<3; y++)
  {
    for (x=0; x<3; x++)
    {
      if (board[x][y] != (num++ % 9))
        return 0;
    }
  }

  return 1;
}

int check_win()
{
  int p,num=1;

  for (p=0; p<9; p++)
  {
    if (board[p] != (num++ % 9))
      return 0;
  }

  return 1;
}

  Obs: when the variable num is equal 9, it must be considered as 0 in order to compare with the hole code.


  Game control

  The following routine controls the game in both cases.

3x3 Matrix e Array of 9 
void game()
{
  moves=0;
  start_board();
  print_board();

  while (check_win()!=1)
  {
    player_turn();
    moves++;
    print_board();
  }

  printf("Game finished in %d moves.\n",moves);
}

main()
{
  game();
}


3. Download
  The complete version of both solutions can be found here.

  8puzzle_en.zip - Game in C

  Program in C: Marcelo Silveira

  Game adapted from [1].


  References:

  [1]- Inteligência Artificial em Basic, M. James, Editora Campus, 1985.
Marcelo Silveira
Systems and Computing Engineer
Expert in Image Processing and Artificial Intelligence
© MarMSX 1999-2025