The Knight's Tour (C)

From LiteratePrograms

Other implementations: C | Haskell

Implementation

This is a simple tree search.

<<kt.c>>=
includes
main
misc
tour

<<tour>>=
int
KnightsTour (int **board, int xCoor, int yCoor, int xSize, int ySize,
	     int moveNum)
{
  if (!MoveIsValid (board, xCoor, yCoor, xSize, ySize, moveNum))
    {
      return FALSE;
    }
  board[xCoor][yCoor] = moveNum;
  if ((xSize * ySize) == moveNum)
    {
      return TRUE;
    }
  printf("KT: %u, %u (%u)\n", yCoor, xCoor, moveNum); 
  if (!KnightsTour
      (board, (xCoor + 1), (yCoor + 2), xSize, ySize, (moveNum + 1)))
    if (!KnightsTour
	(board, (xCoor - 2), (yCoor + 1), xSize, ySize, (moveNum + 1)))
      if (!KnightsTour
	  (board, (xCoor - 2), (yCoor - 1), xSize, ySize, (moveNum + 1)))
	if (!KnightsTour
	    (board, (xCoor - 1), (yCoor + 2), xSize, ySize, (moveNum + 1)))
	  if (!KnightsTour
	      (board, (xCoor - 1), (yCoor - 2), xSize, ySize, (moveNum + 1)))
	    if (!KnightsTour
		(board, (xCoor + 2), (yCoor + 1), xSize, ySize,
		 (moveNum + 1)))
	      if (!KnightsTour
		  (board, (xCoor + 2), (yCoor - 1), xSize, ySize,
		   (moveNum + 1)))
		if (!KnightsTour
		    (board, (xCoor + 1), (yCoor - 2), xSize, ySize,
		     (moveNum + 1))) {
		  board[xCoor][yCoor] = xSize * ySize;
		  return FALSE;
  }
  moveNum = 0;
  return TRUE;
}

<<main>>=
int
main(int argc, char *argv[])
{
  int xSize, ySize, xCoor, yCoor;
  int **board;
  int a, i;
  xSize = ySize = 5;
  xCoor = yCoor = 3;
  printf("X: %u; Y: %u\n", xSize, ySize);
  printf("X Coor: %u; Y Coor: %u\n", xCoor, yCoor);
// Convert to zero-based coordinates (as opposed to one-based).
  xCoor--;
  yCoor--;
  printf("---------------------------------------------------\n\n");
  board = calloc(xSize, sizeof(int *));
printf("%p\n", board);
  int **temp = board;
  for (i = 0; i < xSize; i++)
    {
      board[i] = calloc(ySize, sizeof(int));
printf("%d %p\n", i, board[i]);
    }
  InitializeBoard (board, xSize, ySize);
  DisplayBoard (board, xSize, ySize);
  printf("---------------------------------------------------\n\n");
  printf("Executing Knight's Tour...\n");
  if (KnightsTour (board, xCoor, yCoor, xSize, ySize, 1))
    {
      printf("Solution found:\n\n");
    }
  else
    {
      printf("No solution found.\n\n");
    }
  DisplayBoard (board, xSize, ySize);
  temp = board;
  for (i = 0; i < xSize; i++)
    {
      free(*temp);
      (temp)++;
    }
  free(board);
  return 0;
}

<<misc>>=
void
InitializeBoard (int **board, int xSize, int ySize)
{
  int x, y;
printf("----\n");
  for (x = 0; x < xSize; x++)
    {
      for (y = 0; y < ySize; y++)
	{
printf("%3d", board[x][y]);
	  board[x][y] = 0;
	}
printf("\n");
    }
}
void
DisplayBoard (int **board, int xSize, int ySize)
{
  int x, y;
  for (x = 0; x < xSize; x++)
    {
      for (y = 0; y < ySize; y++)
	{
	  printf("%3d", board[x][y]);
	}
      printf("\n");
    }
}
int
MoveIsValid (int **board, int xCoor, int yCoor, int xSize, int ySize, int moveNum)
{
  if ((xCoor < 0) || (xCoor >= xSize))
    {
      return FALSE;
    }
  if ((yCoor < 0) || (yCoor >= ySize))
    {
      return FALSE;
    }
  if (board[xCoor][yCoor] && board[xCoor][yCoor] < moveNum)
    {
      return FALSE;
    }
  return TRUE;
}

<<includes>>=
#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
void InitializeBoard (int **board, int xSize, int ySize);
void DisplayBoard (int **board, int xSize, int ySize);
int KnightsTour (int **board, int xCoor, int yCoor, int xSize, int ySize,
		  int moveNum);

Download code