2
\$\begingroup\$

Just trying to get used to writing programs in C so have written this program to find valid Knights Tours on a 8x8 board. I guess my queries are more focused on my use of the language and how I could or should do things better.

A little about the code. It is a C implementation based on something I wrote previously in python. It uses Warnsdoff's heuristic to try to find a knights tour on a 8x8 board. This rule follows that you should choose the square with the least available of successor squares as your next move. This is implemented by a non recursive function that loops until it can find no more successor nodes or the tour has reached the length of completion. Finding the successor nodes is achieved by the NodeSuccessor function which loops through possible moves defined in the array Deltas which is filtered by the already visited squares and the dimensions of the board. The SelectedNode function then pics optimal solution by counting the number of successors for each node then in case of a draw taking into account the distance from the center. Draws after this are dismissed as equally good and the first one to be assigned. In this case I have not incorporated backtracking and though I haven't tested it rigorously previous a previous implementation of similar design found a valid tour from any start position 99% of the time for any MxN board >= 6 where M and N are both even.

But maybe to focus more on my use of the language C. Being used to more high level languages what could I be doing better here. Are my choice of data structures ok? Should I be doing anything different in the case of handling memory? - Here I have just set a fixed size for the VECTOR.nodes and PATH.Path lengths as i concluded that I don't want a path bigger than 64 and the available successor nodes can only go up to 8. I haven't utilised pointers at all, is there any need to in this case? I'm just trying to get a feel for the best practices.

#include <stdio.h>
#include <math.h>

typedef struct { int x; int y; } VECTOR;

typedef struct { VECTOR nodes[8]; int length; } NODE_LIST;

typedef struct {
    VECTOR path[64];
    int pathLength;
    int success;
} PATH;

const VECTOR Deltas[8] = {{-2, 1}, {-2,-1}, {-1,-2}, { 1,-2},  /* possible moves a knight  */
                          { 2,-1}, { 2, 1}, { 1, 2}, {-1, 2}}; /* can make in vector space.*/

PATH KnightsTour(VECTOR start);

VECTOR SelectedNode(NODE_LIST nodelist, PATH tour);

NODE_LIST NodeSuccessors(VECTOR node, PATH path);

int NodeNotInPath(VECTOR node, PATH path);

float EuclideanDistance(VECTOR node);

int main()
{
    VECTOR start = {3,3};
    PATH tour = KnightsTour(start);
    if (tour.success)
    {
        printf("Success!\n");
        for (int i = 0; i < tour.pathLength; i++)
        {
            printf("[%d, %d], ", tour.path[i].x,  tour.path[i].y);
        }
    }
    else
    {
        printf("Failed! \n");
    }
    printf("\n%d \n", tour.pathLength);
}

PATH KnightsTour(VECTOR start)
{
    /* takes start co-ordinates and try's to find a valid
     tour else fails */
    VECTOR node = start;
    PATH tour;
    tour.pathLength = 0;
    tour.success = 0;
    while (!tour.success)
    {
        tour.path[tour.pathLength] = node;
        tour.pathLength++;
        if (tour.pathLength >= 64)
        {
            tour.success = 1; /* found a tour; set exit condition */
            continue;
        }
        NODE_LIST successors = NodeSuccessors(node, tour);
        if (successors.length != 0)
            node = SelectedNode(successors, tour);
        else
            break; /* failed to find a tour no valid successors */
    }
    return tour;
}

VECTOR SelectedNode(NODE_LIST nodelist, PATH tour)
{
    /* Following Warnsdoff's rule this function searches for the 
     node that has the least number of successor nodes then incase of a
     draw tries to tiebreak on distance from the center of the board
     if this tiebreaks also the first added is selected. 
     */
    int bestNode = 8; // max amount of possible successor nodes.
    float currentFurthest = 0;
    VECTOR selectedNode = {-1, -1}; // init incase of fail.
    for (int n = 0; n < nodelist.length; n++)
    {
        int len = NodeSuccessors(nodelist.nodes[n], tour).length;
        if (len <= bestNode)
        {
            if (len == bestNode){
                int eucDist = EuclideanDistance(nodelist.nodes[n]);
                if (eucDist > currentFurthest)
                { 
                    bestNode = len;
                    currentFurthest = eucDist;
                    selectedNode = nodelist.nodes[n];
                }
            }
            else
            {
                bestNode = len;
                selectedNode = nodelist.nodes[n];
            }
        }
    }
    return selectedNode;
}

NODE_LIST NodeSuccessors(VECTOR node, PATH path)
{
    /* Returns available move nodes from the current position. */
    NODE_LIST successors;
    int count = 0;
    for (int i = 0; i < 8; i++)
    {
        VECTOR N = {node.x + Deltas[i].x, node.y + Deltas[i].y};
        if ((N.x <  8) && (N.y <  8) &&
            (N.x >= 0) && (N.y >= 0) && NodeNotInPath(N, path))
        {
            successors.nodes[count] = N;
            count++;
        }
    }
    successors.length = count;
    return successors;
}

int NodeNotInPath(VECTOR node, PATH path)
{
    /* Searches for a node a given path and returns 0 if found else 1 */
    for (int i = 0; i < path.pathLength; i++)
    {
        if ((path.path[i].x == node.x) && (path.path[i].y == node.y))
            return 0;
    }
    return 1;
}

float EuclideanDistance(VECTOR node) 
{
    /* returns approx Euclidean distance^2 from the center of the board
     basically the hypotenuse of a triangle */
    float center = 7.0 / 2;
    return (pow((node.x - center), 2) + pow((node.y - center), 2));
}
\$\endgroup\$
2
\$\begingroup\$
  1. RATHER THAN SHOUT YOUR TYPES NAMES LIKE VECTOR, consider vector or Vector.

  2. Odd to exit the loop with continue and break in KnightsTour(). Suggest break; with {} for both.

  3. Simplify EuclideanDistance() and use int math.

    int center = 7;
    int dx2 = node.x*2 - center;
    int dy2 = node.y*2 - center;
    return dx2*dx2 + dy2*dy2;
    
  4. With functions that return 1 or 0, consider bool instead

    // int NodeNotInPath(VECTOR node, PATH path)
    bool NodeNotInPath(VECTOR node, PATH path) {
      ...
      // return 1;
      return true;
    
  5. Avoid Not in 1/0, true/false function names. Reversion the return value

    // bool NodeNotInPath(VECTOR node, PATH path);
    bool NodeInPath(VECTOR node, PATH path) {
      ...
      return false;
    
  6. Minor: VECTOR is passed around a lot by value. Typically structures are passed by their address. Yet VECTOR is small. Consider making it smaller

    // typedef struct { int x; int y; } VECTOR;
    typedef struct { short x; short y; } VECTOR;
    // or 
    typedef struct { signed char x; signed char y; } VECTOR;
    
  7. PATH is passed around by value. This larger structure should have its address passed. With PATH KnightsTour(VECTOR start), suggest passing in the address of the PATH and return success bool.

    // int NodeNotInPath(VECTOR node, PATH path)
    int NodeNotInPath(VECTOR node, const PATH *path)
      ...  
      // if ((path.path[i].x
      if ((path->path[i].x
    
     // PATH KnightsTour(VECTOR start)
     bool KnightsTour(VECTOR start, PATH *tour)
       // tour.pathLength = 0;
       // tour.success = 0;
       tour->pathLength = 0;
       tour->success = 0;
    
  8. Avoid magic numbers. Instead:

    #define BOARD_N 8
    #define BOARD_NN (BOARD_N * BOARD_N)
    #define DELTA_N 8
    
    typedef struct {
      VECTOR nodes[DELTA_N]
    
    typedef struct {
      VECTOR path[BOARD_NN];
    
    if (tour.pathLength >= BOARD_NN)
    
  9. An arithmetic compare looks more self documenting for variables thar have values like 0,1,2,3,4...

    // if (successors.length != 0)
    if (successors.length > 0)
    
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.