Check the checkmate. Welcome to another problem to solve! If you like playing chess and : 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. coding 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 : check it out and try solving your daily challenge too! here 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: . The result is just the same; we will consider each point given by the problem as the center of a case on the board 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 v , meaning that on the next white turn it will be taken if he does not move; erify if the king is in check on this very turn : I will not go into verifying for overlapping pieces or wrong starting positions. Positions are initially given by the game 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 . Therefore, since we also know the black king position, we . If it is, during the next white turn the white piece will move there to capture the black king. their next move will be the one capturing the black king just need to check if the black king position is one of the possible next moves of the other pieces The situation looks something like this: In the picture above you can see (… I hope so, sorry for the confusion …) 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. every possible move of each piece 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 which will be our pieces next moves. To do this, we first define a define its coordinates and then x,y class for each piece, 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 , since it’s one of the most popular languages at the moment and arguably the most readable by anyone. Still, y to be able to follow from now on. a pretty neat explanation of this concept. Python ou will need to know what a class is Here’s https://gist.github.com/NicolaM94/ae4e0e850250a6974042b0ac72be7585?embedable=true#file-pawn-py Let’s briefly explain: we first define the class and its coordinates . After that, we define the method to calculate the pawn possible moves from there. The pawn moves are relatively easy, so we simply add them to the variable , after checking that it does not move outside our grid, and return the array. Two things to notice here, specifically for the pawn: class Pawn __init__ x,y possibleMoves moves moves 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 , 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. intentionally skip the normal movement Now we can simply check the pawn’s moves by giving him its coordinates and calling the method, like this: and we should obtain something like . possibleMoves print(Pawn(7,2).possibleMoves()) [(6,3),(8,3)] Also, you can see at the top that , so we can possibly change them to run the algorithm on boards of other dimensions. we defined our grid dimensions as variables 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 . To collect all the possible moves here , which will be returned after all the loops. As before, to check the tower moves we can simply and we should get something like this: . possibleMoves we range all the points on the tower two axes and add each single coordinate to the variable moves print(Tower(5,3).possibleMoves()) [(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 . After declaring the class and the init method, we create two variables: , as before, and , which will be used to keep track of the points we collected while moving along its axes. Now using loop, and checking that we are not moving outside our grid, we and . For example, if we want to move up-left from its starting positions, we will need to decrement the value while incrementing the value. If we want to move down right, we will need to increment the value while decrementing the value and so on. Finally, we simply return once again. we need to collect points on the two diagonal axes starting from its starting position moves currentPos while increase and decrease x y accordingly to where we want to move x y x y moves 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, . 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 as the . the queen has the same moves of the bishop and the tower combined possibleMoves union array of moves resulting from bishop’s and tower’s possible moves Notice that while calling the classes and instances in the function their parameters and are given as , so they are actually the queens coordinates. Bishop Tower possibleMoves x y self.x, self.y 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, . 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. we don’t really need to implement his move-set 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 as a couple of coordinates. Then for each piece we create an instance of its class we just built and call the method to calculate its full set of moves. : if they are, we print out that the king is checked by that particular piece. The result here is something like this: blackKing possibleMoves Once we have it, we check if the blackKing coordinates are present in those move-sets 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 or it actually is check mate? For this purpose, we need to calculate the king’s set of moves. if the king has still some chances to survive 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 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, and return only the . possibleMoves we check what moves are illegal (move outside the board) validMoves So now, to check if the king has still a chance to survive, To do this we simply loop over the king moves and the other moves. we need to check if any of his possible moves is not in another piece set of 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 , we must consider the time to initialize that instance. instance of a class Pieces like the do not have any loop inside them and do not depend on any variable dimension, so we can consider them O(1); pawn or the knight The 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 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: tower no matter where its placed on the board, its moves are limited Unluckily, we can’t say the same for the , 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). bishop The needs the set of moves of the tower and the bishop combined. Since , 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. queen while evaluating time complexity we must focus on the worst scenario At last, the has an hard coded set of moves, but also a . 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. king validation process involved which uses a for loop At this point, we use . 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. a for loop for each piece to verify and print out the check status of the black king Finally, , 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. we use a double (inner) for loop to verify the check mate 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.

Too Long; Didn't Read

Making security fun one episode at a time

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

Too Long; Didn't Read

Nicola Moro

About Author

TOPICS

Languages

THIS ARTICLE WAS FEATURED IN...

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

Too Long; Didn't Read

Nicola Moro

About Author

TOPICS

Languages

THIS ARTICLE WAS FEATURED IN...

RELATED STORIES