All the knight moves in all the right places Challenge

Find all possible moves for a knight on an empty chessboard.

Specifications


The first argument is a path to a file.
The file contains multiple lines.
Each line is a test case representing the position of the knight in CN form.


C is a letter from “a” to “h” and denotes a column.
N is a number from 1 to 8 and denotes a row.

For each test case, print all positions for the next move of the knight ordered alphabetically.


&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;

Sample Input


  g2
  a1
  d6
  e5
  b1


Sample Output


  e1 e3 f4 h4
  b3 c2
  b5 b7 c4 c8 e4 e8 f5 f7
  c4 c6 d3 d7 f3 f7 g4 g6
  a3 c3 d2


Source

My Solution

#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;

#define LINE_LENGTH 5
#define BOARD_LENGTH 8
#define MOVE_BUFFER 24

int rows[] = {1, 2, 3, 4, 5, 6, 7, 8};
char cols[] = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'};
char moves[MOVE_BUFFER];
int move_iter = 0;

char num_convert(int *n) {
    for (int i = 0; i &lt; BOARD_LENGTH; i++) {
        if (*n == rows[i]) {
            return cols[i];
        }
    }
}

int alpha_convert(char *c) {
    for (int i = 0; i &lt; BOARD_LENGTH; i++) {
        if (*c == cols[i]) {
            return rows[i];
        }
    }
}

void add_moves(int c, int n1, int n2) {
    if (c &gt;= 1 &amp;&amp; c &lt;= 8) {
        if (n1 &gt;= 1) {
            moves[move_iter++] = num_convert(&amp;c);
            moves[move_iter++] = n1 + '0';
            moves[move_iter++] = ' ';
        }
        if (n2 &lt;= 8) {
            moves[move_iter++] = num_convert(&amp;c);
            moves[move_iter++] = n2 + '0';
            moves[move_iter++] = ' ';
        }
    }
}

char* valid_moves(char position[]) {
    int C = alpha_convert(&amp;position[0]);
    int N = atoi(&amp;position[1]);

    add_moves(C - 2, N - 1, N + 1);
    add_moves(C - 1, N - 2, N + 2);
    add_moves(C + 1, N - 2, N + 2);
    add_moves(C + 2, N - 1, N + 1);

    moves[move_iter - 1] = '\0';
    move_iter = 0;
    return moves;
 }

int main(int argc, char *args[]) {
    if (argc &lt; 2) {
        fprintf(stderr, "File path not provided. Exiting...\n");
        return 1;
    }

    if (argc &gt; 2) {
        puts("Excessive arguments, only the first will be considered.");
    }

    FILE *file = fopen(args[1], "r");
    if (file == NULL) {
        perror("Error");
        return 1;
    }

    char position[LINE_LENGTH];
    while (fgets(position, LINE_LENGTH, file)) {
        puts(valid_moves(position));
    }

    fclose(file);
}
Joshua: What's the difference?

Computers sometimes have a hard time to differentiate between things that are apples and oranges to us, some examples are:


if this is a game or if this is real
thermonuclear war and a game of chess
char and int


You have two functions converting from char to int and back:

char num_convert(int *n) {
    for (int i = 0; i &lt; BOARD_LENGTH; i++) {
        if (*n == rows[i]) {
            return cols[i];
        }
    }
}

int alpha_convert(char *c) {
    for (int i = 0; i &lt; BOARD_LENGTH; i++) {
        if (*c == cols[i]) {
            return rows[i];
        }
    }
}


This is not necessary in C, because char and int are kind of the same thing. You can do regular calculations with characters just like you do with integers. Once in character, stay in character.

So when it comes to playing the game of converting between both types, I'd have to say the only winning move is not to play.

the mysterious void add_moves()

I have no idea what this function does.

void add_moves(int c, int n1, int n2) {
    if (c &gt;= 1 &amp;&amp; c &lt;= 8) {
        if (n1 &gt;= 1) {
            moves[move_iter++] = num_convert(&amp;c);
            moves[move_iter++] = n1 + '0';
            moves[move_iter++] = ' ';
        }
        if (n2 &lt;= 8) {
            moves[move_iter++] = num_convert(&amp;c);
            moves[move_iter++] = n2 + '0';
            moves[move_iter++] = ' ';
        }
    }
}


Why are there two n but only a single c? What do those values represent?
They are apparently boundary checked, too. Then there's this code block that's pretty much duplicated for both n, which is bad.

        if (n1 &gt;= 1) {
            moves[move_iter++] = num_convert(&amp;c);
            moves[move_iter++] = n1 + '0';
            moves[move_iter++] = ' ';
        }


After all, something is somehow added to moves, which justifies the name add_moves(). But it's not immediately clear to me what's going on in that function and I feel like too much is going on.

a hint in char* valid_moves()

This function takes away a bit of the mystery from what add_moves() is doing. As it calls it with different possible moves of the knight.

add_moves(C - 2, N - 1, N + 1);
add_moves(C - 1, N - 2, N + 2);
add_moves(C + 1, N - 2, N + 2);
add_moves(C + 2, N - 1, N + 1);


This is not very intuitive. Why do I only see 4 lines here? The knight can do 8 moves in general. Now it is clear why add_moves() takes two n values as parameters, but only one c.

This distribution of logic doesn't appear to be plausible. It's like some part of the movement is calculated in one place while the other happens later. If the concerns of the functions were more clearly separated, it would be easier to understand them.



I gave it a try myself. Here's how I did it:

Position type

This is all about positions, so let's create a type for that.

typedef struct 
{
    signed char column;
    int row;
}
Position;


We're not in oop land, but we still group data together if it belongs together. This helps a lot when passing it around.


  disclaimer: I often see type names like position_t and I absolutely hate that, which is why I'm not using it. Your naming convention may vary.


relative knight moves as positions

Is 5 meters an absolute position or a difference between two positions? It can very well be both! In the same idea, let's create an array of Position that represent the relative movements a knight can perform.

Position allKnightMovesInAlphabeticalOrder[] = 
{
    {-2, -1}, 
    {-2, +1}, 
    {-1, -2}, 
    {-1, +2}, 
    {+1, -2}, 
    {+1, +2}, 
    {+2, -1}, 
    {+2, +1} 
};

#define numberOfKnightMoves 8


As you can see, -2 is a perfectly fine signed char value. 1

If you are uncomfortable reusing the Position type which from its name might suggest to be an absolute position, you can always typedef it to a Move type, which makes the intention more clear.

position check

A handy helper function could solve the sub-problem of whether a certain position is on the board or not.

bool positionIsInChessboard(Position *position)
{
    return 
        position-&gt;column &gt;= 'a' &amp;&amp;
        position-&gt;column &lt;= 'h' &amp;&amp;
        position-&gt;row &gt;= 1 &amp;&amp;
        position-&gt;row &lt;= 8;
}


You need to #include &lt;stdbool.h&gt; for bool. If you don't want that, you should be able to use _Bool as a return type.

making a move

Another helper function that simply adds two positions together.

void addTwoPositions(Position *a, Position *b, Position *result)
{
    result-&gt;column = a-&gt;column + b-&gt;column;
    result-&gt;row = a-&gt;row + b-&gt;row;
}


Again, as a Position might represent a relative movement, this starts to make sense I hope. If not, recall how a 2D vector in math might represent a fixed point or the difference between two points. This is the same idea.

putting it all together

#include &lt;stdio.h&gt;
#include &lt;stdbool.h&gt;

typedef struct 
{
    signed char column;
    int row;
}
Position;

Position allKnightMovesInAlphabeticalOrder[] = 
{
    {-2, -1}, 
    {-2, +1}, 
    {-1, -2}, 
    {-1, +2}, 
    {+1, -2}, 
    {+1, +2}, 
    {+2, -1}, 
    {+2, +1} 
};

#define numberOfKnightMoves 8

bool positionIsInChessboard(Position *position)
{
    return 
        position-&gt;column &gt;= 'a' &amp;&amp;
        position-&gt;column &lt;= 'h' &amp;&amp;
        position-&gt;row &gt;= 1 &amp;&amp;
        position-&gt;row &lt;= 8;
}

void addTwoPositions(Position *a, Position *b, Position *result)
{
    result-&gt;column = a-&gt;column + b-&gt;column;
    result-&gt;row = a-&gt;row + b-&gt;row;
}

int main ()
{
    Position testPositions[] = 
    {
        {'g', 2},
        {'a', 1},
        {'d', 6},
        {'e', 5},
        {'b', 1}
    };

    int numberOfTestPositions = sizeof(testPositions)/sizeof(Position);

    Position result;

    for(int testPositionIndex = 0; testPositionIndex &lt; numberOfTestPositions; testPositionIndex++)
    {
        printf("%c%d:\t", testPositions[testPositionIndex].column, testPositions[testPositionIndex].row);

        for(int moveIndex = 0; moveIndex &lt; numberOfKnightMoves; moveIndex++)
        {
            addTwoPositions(&amp;testPositions[testPositionIndex], &amp;allKnightMovesInAlphabeticalOrder[moveIndex], &amp;result);

            if(positionIsInChessboard(&amp;result))
            {
                printf("%c%d ", result.column, result.row);
            }
        }

        printf("\r\n");
    }
}


I hard coded the test positions into main() for brevity. the basic idea for every test case is to iterate over all the possible knight moves, perform them via addTwoPositions() and then check the validity of the result with positionIsInChessboard().

I do not build up a buffer as you do in your code simply because that isn't necessary.

Here's what I get as a result in terminal:

$ ./chess 
g2: e1 e3 f4 h4 
a1: b3 c2 
d6: b5 b7 c4 c8 e4 e8 f5 f7 
e5: c4 c6 d3 d7 f3 f7 g4 g6 
b1: a3 c3 d2 




1 thanks @Daniel Jour for pointing out that plain char has an unspecified signedness, which may vary across platforms and compilers.

For me, I get the same output for any of the three versions char, signed char or unsigned char. It's still good practice to use signed char as it makes it more obvious that a Position might be a relative position.