About
This is a really quick and classic programming problem called "8 Queens". The goal is to put 8 queens on a chess board so that they don't attack each other.
Note that there is more than one way how to do it (even more - for 8 by 8 board there are 92 ways how to do it).
Actually this mini-project is done as a #shorts and it took much less than 5 minutes.
First time I faced this problem around 2000 when I was preparing for one of programming competitions. I was taking part in USACO (USA Computing Olympiad) in one of junior divisions and failed this quite simple problem.
Let's take a look how it can be done.
Link to Wikipedia: https://en.wikipedia.org/wiki/Eight_queens_puzzle
Live coding
Here is a live coding session that shows how it can be done.
Duration: 0:59 (coding - 0:53)
Disclaimer: never use this code in production. It was created for fun.
Breakdown
Let's break down the solution and comment on some complex or interesting things.
The solution is based on recursive algorithm with the following ideas:
- Each row can contain one and only one queen - that's pretty obvious as the queen also attacks the row therefore no other queen can be on the same row. Similarly we can easily see that 8 queens should occupy all 8 rows - therefore each row will have exactly one queen
- We will go from top to bottom and try to put queen on each column of the row
- When trying to put a queen we need to check if this cell is under attack or not. Instead of checking if the cell is under attack by other queens, we can check if the queen we are going to place attacks some other already placed queen or not - we can do it as attacks are simetrical: if queen A attacks queen B this also means that queen B attacks queen A
- We need to check only 3 directions for attack:
- vertical - all rows above
- diagonal - to the top left
- diagonal - to the top right
Let's look at the example (assume that we are processing row 4 now - so only first 4 rows are shown):Q Q Q Q
This idea is called Backtracking and it is a very powerful technique to solve combinatorial problems.
And now let's go through important points of the video.
0:00 - defining the program structure. n will be the size of the board (and you can adjust it to see the solutions for different board sizes), board will be the current position (0 means empty cell and 1 means that this cell is occupied by a queen). Also let's count number of solutions - for this we'll use numSols variable (remember that for 8 by 8 there should be 92 solutions).
solve function will be the one where all the magic will happen. It accepts one parameter - row number (represented by y)
In main function we'll output total number of solutions as well.
0:14 - checking if we have found a solution. If we reached the last row and went one beyond it (y == n) then it means that all previous rows have valid position - and it is a solution. Output it to console and increase number of solutions.
0:22 - trying to put a queen on y-th row into i-th column. Before putting it we need to check if the cell is under attach - for this we are using underAttack function that we'll implement a bit later. The function has 3 parameters - x and y for coordinates of the cell, and last parameter is dx - direction for x coordinate change.
If the cell is not under attack, then try to put a queen there (board[y][x] = 1) and switch to the next row by calling solve recursively. After recursive call we need to backtrack and mark the cell as empty (board[y][x] = 0)
0:37 - implement underAttack function. The idea is to go up by vertical axis by one and by dx by horizontal axis on every step.
Here we need to be careful with board borders - we should be betwen 0 and n-1 by x axis.
And this concludes the implementation.
0:53 - we can run our program for the first time using go run . and see the results. As we see we got exactly 92 unique solutions. We can check any of them and make sure that it works.
As you see the problem is quite simple and it took us less than a minute to implement it.
Resources
Sources: https://github.com/5minute/examples/tree/main/8queens
See live results:https://play.golang.org/p/WL6_6YYST0s
