Daily Coding Problem: Use Your Coding Skills to Check the Checkmate

Check the checkmate. Welcome to another problem to solve! If you like playing chess and coding: this one’s for you! Today, we will help the king to survive another day on the battlefield, and also write quite a lot of code.

So without further ado, let’s see our problem. Before starting though, as always, two disclaimers:

These problems are provided by the wonderful newsletter Daily Coding Problem, which you can subscribe to here: check it out and try solving your daily challenge too!
I’m not an expert programmer, just a guy who likes to share his attempts (and failures). If you have a better idea or solution you are more than welcome to share it: I’d love to see you tackle it!

The problem

Today’s problem was initially asked by Oracle.

You are presented with an 8 by 8 matrix representing the positions of pieces on a chess board. The only pieces on the board are the black king and various white pieces. Given this matrix, determine whether the king is in check.

For details on how each piece moves, see here.

For example, given the following matrix:

...K....
........
.B......
......P.
.......R
..N.....
........
.....Q..

You should return True, since the bishop is attacking the king diagonally.

The problem is quite clear, so we won’t elaborate more about it. We just need some starting specifications though:

We are on a graph, not on a board: we will consider each point given by the problem as the center of a case on the board. The result is just the same;
The white king has gone on vacation with other 7 pawns: king and pawns are the most boring of all the pieces and removing them is not going to change our solution that much;
We need to verify if the king is in check on this very turn, meaning that on the next white turn it will be taken if he does not move;
Positions are initially given by the game: I will not go into verifying for overlapping pieces or wrong starting positions.

The solution

First of all, a quick recap of pieces and move-sets:

Given the starting position of each piece and his move-set, we can “easily” calculate every possible next move of every piece.

And since they are all interested in capturing the king as quick as possible, we can assume that their next move will be the one capturing the black king. Therefore, since we also know the black king position, we just need to check if the black king position is one of the possible next moves of the other pieces. If it is, during the next white turn the white piece will move there to capture the black king.

The situation looks something like this:
In the picture above you can see (… I hope so, sorry for the confusion …) every possible move of each piece on the white side, colored with different colors, and the black king above waiting to be captured. So for example the bishop, starting in (2,7), can move to (1,6), (1,8), (3,8), (3,6), (4,5), (5,4) and so on.

I just randomly decided the starting positions of these pieces since this does not affect the final result.

Since we are on a 8x8 graph (to be clear, any other dimensions will work the same way) and we have the starting coordinates of each piece, we can build series of coordinates x,y which will be our pieces next moves. To do this, we first define a class for each piece, define its coordinates and then define the rules to calculate every possible move from there.

The pieces — The Pawn

Let’s start simple with the Pawn. By the way, I’m building this in Python, since it’s one of the most popular languages at the moment and arguably the most readable by anyone. Still, you will need to know what a class is to be able to follow from now on. Here’s a pretty neat explanation of this concept.

https://gist.github.com/NicolaM94/ae4e0e850250a6974042b0ac72be7585?embedable=true#file-pawn-py

Let’s briefly explain: we first define the class Pawn class and __init__ its coordinates x,y . After that, we define the possibleMoves method to calculate the pawn possible moves from there. The pawn moves are relatively easy, so we simply add them to the variable moves , after checking that it does not move outside our grid, and return the moves array. Two things to notice here, specifically for the pawn:

We consider the white pawn to move from bottom to top, like if we are the white player moving our pawn ahead towards our opponent. This does not really change anything, it’s just keeping things in order.
We intentionally skip the normal movement, since we are interested in capturing the black king: since the pawn can only capture diagonally and we don’t care about moving the pieces in other directions, we can skip its normal movement.

Now we can simply check the pawn’s moves by giving him its coordinates and calling the possibleMoves method, like this: print(Pawn(7,2).possibleMoves()) and we should obtain something like [(6,3),(8,3)] .

Also, you can see at the top that we defined our grid dimensions as variables, so we can possibly change them to run the algorithm on boards of other dimensions.

Now let’ s move on to the tower.

The tower

https://gist.github.com/NicolaM94/7897939bdd7933cb09d8915b7b8bc0b5?embedable=true#file-tower-py

Again, we init the Tower class with its coordinates and define the function possibleMoves . To collect all the possible moves here we range all the points on the tower two axes and add each single coordinate to the variable moves , which will be returned after all the loops. As before, to check the tower moves we can simply print(Tower(5,3).possibleMoves()) and we should get something like this: [(1,3), (2,3), (3,3), ..., (5,8)] .

The bishop

Now it’s time for the bishop.

https://gist.github.com/NicolaM94/a6ae6f6138b78d550b2f2e27d5c453aa?embedable=true#file-bishop-py

Bishop’s moves are more complex than the tower, so we might explain a bit what’s happening here. Basically we need to collect points on the two diagonal axes starting from its starting position. After declaring the class and the init method, we create two variables: moves , as before, and currentPos , which will be used to keep track of the points we collected while moving along its axes. Now using while loop, and checking that we are not moving outside our grid, we increase and decrease x and y accordingly to where we want to move. For example, if we want to move up-left from its starting positions, we will need to decrement the x value while incrementing the y value. If we want to move down right, we will need to increment the x value while decrementing the y value and so on. Finally, we simply return moves once again.

The queen

Now you could think: if tower moves are complex and bishop are even more, how the heck are we going to code the queen? Actually, the queen moves are the most easy to code, just with the help of a simple trick. Let’s see the queen then.

https://gist.github.com/NicolaM94/22bd55aab7a0976f4656403c3749a6ee?embedable=true#file-queen-py

Alright, what’s happening here? Well, if we think about it, the queen has the same moves of the bishop and the tower combined. She’s more like a tower shaped bishop mecha-bot than a queen. For this reason, coding her moves is really simple. After declaring her class we simply define her possibleMoves as the union array of moves resulting from bishop’s and tower’s possible moves.

Notice that while calling the classes Bishop and Tower instances in the possibleMoves function their parameters x and y are given as self.x, self.y , so they are actually the queens coordinates.

The knight

Now to the knight!

https://gist.github.com/NicolaM94/c19d2c41e4461c66fca54aab239ede9e?embedable=true#file-knight-py

The knight is the most particular to me. His move-set is strange, like “L” shaped, so I did not find a particularly clever or fast way to code it and I ended up hard coding its moves simply calculating each of the 8 possible moves he has from his starting position.

The king

A couple of brief concepts about the king. Since we are not required to move the king, just giving out if he’s checked or not, we don’t really need to implement his move-set. However, we will also see a brief implementation in the end of the article. Also, coding it is not as simple as nerfing down the queen’s move-set, as we will see later. So for now, let’s skip his movements and see the solution.

The solution code

Given that we have the possible positions for each piece, the solution is pretty simple now: we just need to check if the black king coordinates are in the set of moves of one or more of the other pieces. Let’s code it!

https://gist.github.com/NicolaM94/75826a753105c3a3aecae4f6890b631a?embedable=true#file-check-py

We now simply create a variable blackKing as a couple of coordinates. Then for each piece we create an instance of its class we just built and call the method possibleMoves to calculate its full set of moves. Once we have it, we check if the blackKing coordinates are present in those move-sets: if they are, we print out that the king is checked by that particular piece. The result here is something like this:

Pawn moves: [(8, 3), (6, 3)]
Tower moves: [(1, 3), (2, 3), (3, 3), (4, 3), (6, 3), (7, 3), (8, 3), (5, 1), (5, 2), (5, 4), (5, 5), (5, 6), (5, 7), (5, 8)]
Check by the tower!
Bishop moves: [(3, 8), (1, 6), (1, 8), (3, 6), (4, 5), (5, 4), (6, 3), (7, 2), (8, 1)]
Queen moves: [(4, 3), (5, 4), (6, 5), (7, 6), (8, 7), (2, 1), (2, 3), (1, 4), (4, 1), (1, 2), (2, 2), (4, 2), (5, 2), (6, 2), (7, 2), (8, 2), (3, 1), (3, 3), (3, 4), (3, 5), (3, 6), (3, 7), (3, 8)]
Knight moves: [(4, 7), (4, 5), (8, 7), (8, 5), (5, 4), (7, 4), (7, 8), (5, 8)]
Check by the knight!

I used the messy image above as reference, so you could check that the king is actually checked by the tower and the knight.

Check mate

What about if we also want to calculate if the king has still some chances to survive or it actually is check mate? For this purpose, we need to calculate the king’s set of moves.

https://gist.github.com/NicolaM94/cca18293bedb2293bbc621e86236571f?embedable=true#file-king-py

Let’s describe it a bit. First off, we define our class and coordinates as before. After that we create the possibleMoves method and code the possible moves of the king (again, I’m pretty sure that there is a faster way, but there are just 8 possible moves so…). After that, we check what moves are illegal (move outside the board) and return only the validMoves .

So now, to check if the king has still a chance to survive, we need to check if any of his possible moves is not in another piece set of moves. To do this we simply loop over the king moves and the other moves.

https://gist.github.com/NicolaM94/9bdb64c10e2d039905e6353ed37cc101?embedable=true#file-checkmate-py

So there’s still hope for our king to survive! Lucky for him I guess…

Time complexity

As always, a brief look at the time complexity of this solution.

First off, since each piece is an instance of a class, we must consider the time to initialize that instance.

Pieces like the pawn or the knight do not have any loop inside them and do not depend on any variable dimension, so we can consider them O(1);
The tower is a bit tricky: since it contains 4 for loop you could instantly think that its time complexity is O(n), right? Actually, if we think about how the tower moves, we’ll notice that no matter where its placed on the board, its moves are limited to the free board cases on its vertical and horizontal axes. And since the board is a square, we will always have 14 free cases to move our tower on. So its time complexity should actually be O(1), constant to 14 couples of coordinates. Here’s a graphic example:

Unluckily, we can’t say the same for the bishop, which set of moves appears to be a bit more complex. Basically, it has 7, 9, 11 or 13 moves depending on where it is placed on the board. Therefore, the steps needed to calculate his set of moves are based on his position, thus we may consider a t.c. of O(n).

The queen needs the set of moves of the tower and the bishop combined. Since while evaluating time complexity we must focus on the worst scenario, the t.c. of the bishop prevails on the t.c. of the tower. Thus, we must consider a t.c. of O(n) also for the queen.
At last, the king has an hard coded set of moves, but also a validation process involved which uses a for loop. So technically, even if the king’s set of moves is relatively small in any case, we must consider his t.c. as O(n), also depending on his position on the board.

At this point, we use a for loop for each piece to verify and print out the check status of the black king. This gives us no problems where the t.c. is constant (take the tower, for example: we calculate its 14 moves and then loop other 14 times over them at most, so we can consider it also fixed time). Still, we’re going to have troubles where the t.c. is O(n) or above, since we are adding a loop which will also grow while the number of moves grow.

Finally, we use a double (inner) for loop to verify the check mate, which is definitely going to be a t.c. of O(n²), depending on the number of moves of the king and the moves of the other pieces.

That’s it; there’s my solution. I’m well aware that some points are not as most efficient as possible, but while writing I liked the idea of describing the process more than building the perfect solution.

What do you think about this? Give me your opinion about it and let’s discuss your solutions in the comments!

As always, if you liked the article, please leave a clap or two and subscribe, or share it with someone who could be interested in this kind of algorithms, if you can! Thanks for reading until the end, this time more than always given the length of this solution!

As always, thanks for reading.