Chess in C (Part 5) - Potential moves of a bishop: up-left, cardinal, pope

On a chess board, the bishop can move diagonally forward or back by any number of squares. I've never seen a bishop in person, but I can say with a high degree of certainty that they don't move diagonally in real life. But just to be on the safe side, if I ever meet a bishop in real life I'm going to stand directly infront of them so they don't bump into me. Wikipedia has a technically correct but literally impenetrable explanation of how bishops move on chess boards, but I believe I've bested the Wikipedia community with my diagram.

Potential moves of the bishop,
aka "the diagonal piece"

Given a square on a chess board, how do we draw the potential moves of a bishop? In the diagram above, the bishop is in position (3,4). There are four possible directions the bishop can move in.

• Up-left: (0,1) (1,2) (2,3)
• Up-right: (0,7) (1,6) (2,5)
• Down-left: (4,3) (5,2) (6,1) (7,0)
• Down-right: (4,5) (5,6) (6,7)

Each direction radiates outward from the bishop like rays from the sun. To make this easy, work on each diagonal separately.

Radiating up-left.

Mission: write an algorithm that returns the upper-left diagonal.

The bishop is at (3,4). We need an algorithm that returns us the positions (0,1) (1,2) (2,3). If the bishop wanted to move up-left one square from (3,4), it would be in (2,3). If it wanted to move up-left two squares, it would be in (1,2). If it moved up-left three squares, it would be in (0,1). It seems simple enough to generate the list of potential moves: you start from the bishop, then work backwards from there. 

Now let's implement it. Remember the code used to iterate through each square on the board from part one of the blog post? I'll post it here.

	/* Zero out the board */
	for (i = 0; i <= 7; i++) {
	for (j = 0; j <= 7; j++) {
	/* Zero out the square */
	board[i][j] = 0;
	}
	}

view raw chessInCPart1-iterateThroughAndZeroOutBoard.c hosted with ❤ by GitHub

The code iterates uses two for loops to iterate through each square on the board. The code starts at board position (0,0) and iterates to the end of the row (0,7). It repeats this until it reaches position (7,7). We used this code to clear the board (overwrite each array element with a zero) and also to draw the board. Here's an illustration of how that code works.

The catch is that you can't use this code to work out where the bishop's potential moves are. Imagine the bishop is at (3,4). When the iteration code reaches (3,4), it will be too late already: you'll have passed some of the squares which are potential bishop moves. The iteration code is only useful if you're trying to work out the potential down-right bishop moves. To work out the potential up-left diagonal bishop moves, you need to work backwards.

In the first post of this blog series, I put some code in the original program to iterate through the two-dimensional board array backwards, just for fun. Here's the code to iterate through the board backwards.

	/* Iterate backward through board */
	for (i = 7; i >= 0; i--) {
	for (j = 7; j >= 0; j--) {
	/* Zero out the square */
	board[i][j] = 0;
	}
	}

view raw chessInCPart5-iterateThroughBoardBackwards.c hosted with ❤ by GitHub

Here's our logic. It's incorrect, but let's run with it for now.

1. Start at the last square and iterate through the board backwards.
2. For each square, check if there's a bishop in the lower-right square.
1. If there is, mark this square as a potential move.
3. Repeat until you reach (0,0).
4. All potential diagonal up-left moves have been marked.

Let's model this theory before we code it. If you need to, put your finger on position (7,7) on the diagram and ask yourself the question: for this square, is there a bishop in the lower-right square?

This algorithm correctly identifies (2,3) as a potential move, but not (1,2) or (0,1) which are also potential moves. Close, but no cigar. We can modify our algorithm to mark some squares with breadcrumbs. A breadcrumb is a marker for a potential move. Why do we need breadcrumbs? Well, it's obvious that (2,3) is a potential move and our algorithm works for this. But this check doesn't work for (1,2). What we can do at (2,3) is drop a breadcrumb: a marker that can be checked for when we get to (1,2). We can modify the algorithm to drop and detect breadcrumbs as follows:

1. Start at the last square and iterate through the board backwards.
2. For each square, check if there's a bishop OR breadcrumb in the lower-right square
1. If there is, this square is a potential move. Mark this square with a breadcrumb.
3. Repeat until you reach (0,0).

Let's model this theory. Again, put your finger on the square and ask the question, is there a bishop or breadcrumb in the lower-right square?

Hey, this works! Time to pop the champagne? Well, no. There's still another flaw in this code. When you're at position (7,7), you're asking the question, is there a bishop or breadcrumb in the lower-right square? In this instance, the lower-right square is (8,8), which doesn't exist. The memory allocated outside of the array could be anything. If you check for position (8,8), you'll get undefined behaviour: when you run your program, board[8][8] could be equal to 0. The next time you run, it could be equal to 5. Or 9. Or 42. I've described why this happens in part two. Basically, you don't know what information is stored outside of the array. All you need to know is that you must not check array locations that don't exist. This will require one final change to the algorithm.

1. Start at the last square and iterate through the board backwards.
2. For each square, check if the lower-right square is within the board
1. If it is, check if there's a bishop OR breadcrumb in the lower-right square
1. If there is, this square is a potential move. Mark this square with a breadcrumb.
3. Repeat until you reach (0,0).

Let's code it! I'll also put the code containing #define lines that contain the cell to piece mapping. This is so you know that an array element with value 5 is a bishop, and value 50 is a breadcrumb for a bishop.

	#define EMPTY 0
	#define KING 1
	#define QUEEN 2
	#define ROOK 3
	#define KNIGHT 4
	#define BISHOP 5
	#define PAWN 6
	#define BREADCRUMB 9
	#define POTENTIAL_MOVE_KING 10
	#define POTENTIAL_MOVE_QUEEN 20
	#define POTENTIAL_MOVE_ROOK 30
	#define POTENTIAL_MOVE_KNIGHT 40
	#define POTENTIAL_MOVE_BISHOP 50
	#define POTENTIAL_MOVE_PAWN 60

view raw chessInCPart5-macros.c hosted with ❤ by GitHub

Here's an implementation of the algorithm.

	/* Calculate possible up-left diagonal destinations
	* This requires the loop to iterate backwards as we are
	* checking cells BEFORE the bishop */
	for (i=7; i>=0; i--) {
	for (j=7; j>=0; j--){
	/* If 1) the cell to right is inbounds of the array and
	* 2) the cell isn't not on the final row */
	if ((j+1 != 8) && (i != 7)) {
	/* ...AND the above-right cell has a bishop OR a breadcrumb ... */
	if (board[i+1][j+1] == BISHOP || board[i+1][j+1] == POTENTIAL_MOVE_BISHOP) {
	/* ...then leave a breadcrumb (50) */
	board[i][j] = POTENTIAL_MOVE_BISHOP;
	}
	}
	}
	}

view raw chessInCPart5-upLeft.c hosted with ❤ by GitHub

Line 1 and 2 contain the for loops that perform the iteration. Because we are iterating backwards, the conditions of the for loop are slightly different.

• Instead of i being equal to 0, i starts at 7 (the end).
• Instead of i iterating until 7, i iterates while it is larger than or equal to 0.
• Instead of incrementing, i decrements.

Line 8 does the bounds checking. The if statement performing the bounds checking has two checks: (j+1 != 8) and (i!=7). If j+1 is equal to 8, that means you're in the final column, so don't check further! If i is equal to 7, you're in the bottom row so don't check further! Line 11 checks whether the down-left square has a breadcrumb or a bishop. Line 11 is only executed if the bounds checking in line 8 is successful. And finally, if all these tests have passed, line 13 marks the square as containing a breadcrumb. Here's the code so far. Copy and pasta it into your IDE and hit compile!

	#include <stdio.h>
	#include <stdlib.h>
	#define EMPTY 0
	#define KING 1
	#define QUEEN 2
	#define ROOK 3
	#define KNIGHT 4
	#define BISHOP 5
	#define PAWN 6
	#define BREADCRUMB 9
	#define POTENTIAL_MOVE_KING 10
	#define POTENTIAL_MOVE_QUEEN 20
	#define POTENTIAL_MOVE_ROOK 30
	#define POTENTIAL_MOVE_KNIGHT 40
	#define POTENTIAL_MOVE_BISHOP 50
	#define POTENTIAL_MOVE_PAWN 60
	int main(void) {
	int i = 0; /* Used to count rows when printing board */
	int j = 0; /* Used to count columns when printing board */
	int board[8][8]; /* Represents board */
	int pieceRow = 0; /* Stores the piece row */
	int pieceColumn = 0; /* Stores the piece column */
	int pieceType = 0; /* Stores the piece type - not used yet! */
	int boardValue = 0; /* Temp value used when drawing the board */
	int badAnswer = 0; /* Used to control flow when asking questions */
	char input[256]; /* Contains the user input */
	/* Zero out the board */
	for (i=0; i<=7; i++) {
	for (j=0; j<=7; j++) {
	/* Zero out the square */
	board[i][j] = 0;
	}
	}
	/* Zero out the input array */
	/* Any array is full of garbage when initialized */
	for (i=0; i<=255; i++) {
	input[i] = 0;
	}
	/* Set initial start positions.
	* Keep this here so we can quickly put pieces on the board. */
	/*board[0][0] = ROOK;
	board[0][1] = KNIGHT;
	board[0][2] = BISHOP;
	board[0][3] = QUEEN;
	board[0][4] = KING;
	board[0][5] = BISHOP;
	board[0][6] = KNIGHT;
	board[0][7] = ROOK;
	board[1][0] = PAWN;
	board[1][1] = ROOK;
	board[1][2] = PAWN;
	board[1][3] = PAWN;
	board[1][4] = PAWN;
	board[1][5] = PAWN;
	board[1][6] = ROOK;
	board[1][7] = PAWN;*/
	/* Print and ask for the row number */
	printf("\nRow? (0..7): ");
	/* Get some input */
	if (fgets(input, sizeof(input), stdin)) {
	/* Make sure it's a number! */
	if (input[0] != '\n' && sscanf(input, "%d", &pieceRow)) {
	/* Make sure it's between 0 and 7! */
	if (pieceRow >= 0 && pieceRow <= 7) {
	/* If you got here, congratulations. It's valid input. */
	printf("You've entered %i", pieceRow);
	} else {
	/* It wasn't between 0 and 7! */
	printf("ERROR: Not between 0 and 7");
	badAnswer = 1;
	}
	} else {
	/* It wasn't a number! */
	printf("ERROR: Not a number");
	badAnswer = 1;
	}
	}
	if (!badAnswer) {
	/* Print and ask for the column number */
	printf("\nColumn? (0..7): ");
	/* Get some input */
	if (fgets(input, sizeof(input), stdin)) {
	/* Make sure it's a number! */
	if (input[0] != '\n' && sscanf(input, "%i", &pieceColumn)) {
	/* Make sure it's between 0 and 7! */
	if (pieceColumn >= 0 && pieceColumn <= 7) {
	/* If you got here, congratulations. It's valid input. */
	printf("You've entered %i", pieceColumn);
	} else {
	/* It wasn't between 0 and 7! */
	printf("ERROR: Not between 0 and 7");
	badAnswer = 1;
	}
	} else {
	/* It wasn't a number! */
	printf("ERROR: Not a number");
	badAnswer = 1;
	}
	}
	}
	/* Calculate a bishop move */
	board[pieceRow][pieceColumn] = BISHOP;
	/* Calculate possible up-left diagonal destinations
	* This requires the loop to iterate backwards as we are
	* checking cells BEFORE the bishop */
	for (i=7; i>=0; i--) {
	for (j=7; j>=0; j--){
	/* If 1) the cell to right is inbounds of the array and
	* 2) the cell isn't not on the final row */
	if ((j+1 != 8) && (i != 7)) {
	/* ...AND the above-right cell has a bishop OR a breadcrumb ... */
	if (board[i+1][j+1] == BISHOP || board[i+1][j+1] == POTENTIAL_MOVE_BISHOP) {
	/* ...then leave a breadcrumb (50) */
	board[i][j] = POTENTIAL_MOVE_BISHOP;
	}
	}
	}
	}
	/* Print the board */
	if (!badAnswer) {
	/* New line for the board */
	printf("\n");
	/* For every row */
	for (i=0; i<=7; i++) {
	/* And every column */
	for (j=0; j<=7; j++){
	/* Get the board value */
	boardValue = board[i][j];
	/* And print the contents */
	switch (boardValue) {
	case EMPTY: printf(".");
	break;
	case KING: printf("K");
	break;
	case QUEEN: printf("Q");
	break;
	case ROOK: printf("R");
	break;
	case KNIGHT: printf("N");
	break;
	case BISHOP: printf("B");
	break;
	case PAWN: printf("P");
	break;
	case POTENTIAL_MOVE_KING: printf("+");
	break;
	case POTENTIAL_MOVE_QUEEN: printf("+");
	break;
	case POTENTIAL_MOVE_ROOK: printf("+");
	break;
	case POTENTIAL_MOVE_KNIGHT: printf("+");
	break;
	case POTENTIAL_MOVE_BISHOP: printf("+");
	break;
	case POTENTIAL_MOVE_PAWN: printf("+");
	break;
	case BREADCRUMB: printf("+");
	break;
	}
	}
	/* At the end of each row, make a new line */
	printf("\n");
	}
	} else {
	printf("\nERROR: Incorrect input. Not drawing board.");
	}
	/* Exit the program */
	return EXIT_SUCCESS;
	}

view raw chessInCPart5-complete.c hosted with ❤ by GitHub

Let's see the output.

Bishop in position (0,0).
This is easy.

Bishop in position (4,4).
Yay, it works!

Bishop in position (3,4).
Woo hoo!

Bishop in position (7,7).
It can move right across the board. Great!
No nasty errors from trying to check array elements
that don't exist. 

Bishop in position (4,7).
It works! And no nasty out of bounds errors.

Great! We've written the code that works out the potential upper-left diagonal moves of a bishop. This was the most difficult diagonal move of the bishop to work out: you needed to combine your knowledge of iterating backwards through two-dimensional arrays, bounds checking, and algorithms. It's easy from here on in! In the next post, I'll discuss how to code the other potential moves of the bishop.

Other posts in this series

Chess in C (Part 1)
Chess in C (Part 2) - Insert Pawn Pun Here
Chess in C (Part 3) - Rook, Rooks, Rookies, Wookies, same thing
Chess in C (Part 4) - I'm asking for input
Chess in C (Part 5) - Potential moves of a bishop: up-left, cardinal, pope