5 minutes of code - 8 Queens! (2024)

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
    Note that it does not make sense to check horizontal (as there will be one queen per row as shown before) and directions to the bottom (as there are no queens yet).
    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

5 minutes of code - 8 Queens! (2024)

FAQs

What is the 8 queens problem in Ada? ›

The 8 queens problem aims to place 8 queens on a chessboard so that no two queens attack each other. Backtracking is an algorithm that builds candidate solutions incrementally and abandons partial solutions ("backtracks") that cannot be completed.

How many possible solutions exist for an 8 queen problem? ›

The eight queens puzzle is the problem of placing eight chess queens on an 8×8 chessboard so that no two queens threaten each other; thus, a solution requires that no two queens share the same row, column, or diagonal. There are 92 solutions.

What is the time complexity of the 8 queens problem? ›

Space and Time Complexity

In the worst case, the algorithm tries to place a queen in each of the N rows in the first column, then in each of the remaining N-1 rows in the second column, and so on. This leads to a time complexity of O(N * (N-1) * (N-2) * … * 1) = O(N!) .

Is the 8 Queens problem solvable? ›

There are 92 solutions. The problem was first posed in the mid-19th century. In the modern era, it is often used as an example problem for various computer programming techniques."

How many moves does it take to solve an 8-puzzle? ›

Any solvable 8-slider puzzle can be solved with at most 31 moves; any solvable 15-slider puzzle can be solved with at most 80 moves.

What is the best algorithm for the 8 queens problem? ›

There's plenty of solutions to this problem, but there's one particular algorithm which is my favorite: Min-Conflicts. Min-conflicts will randomly choose a queen, and move it to a place on the board where there are less conflicting queens than there are now.

What is the prize for the 8 queens problem? ›

The underlying problem is one of the most major unsolved problems in computer science and mathematics. Known as P versus NP, it is one of the seven Millennium Prize Problems which carry the million dollar reward for their first correct solution.

What is the backtracking strategy for the 8 queens problem? ›

If the algorithm reaches the 8th column and all queens are placed in a safe position, it prints the board and returns true. If the algorithm is unable to place a queen in a safe position in a certain column, it backtracks to the previous column and tries a different row.

Can you place 8 queens on a chessboard? ›

There are nearly 4.5 billion ways in which it's possible to place eight queens on a chessboard (4 426 165 368 to be precise), but only 92 of these possibilities satisfy the requirement that no two queens can threaten each other.

What is the brute force solution to the 8 queens problem? ›

The simplest solution to the 8-Queens puzzle is to use a brute-force search algorithm, which considers all 648 = 281,474,976,710,656 possible blind placements of eight queens, and then removing all placements that place two queens, either on the same space, or in mutually attacking positions.

Which searching mechanism is associated with the 8 queen problem? ›

8 - queen's problem:

It is the backtracking approach. In backtracking approach, all the possible configurations are checked and check whether result is obtained or not. A queen can only be attacked if it is in the same row or column or diagonal of another queen.

What are the implicit constraints for 8 queens problem? ›

No two queens on the same column

This constraint is implicit in the definition of queens . Since no two elements of queens can have the same index, no two queens can be in the same column.

Which technique is commonly used to solve the N-queens problem? ›

The backtracking algorithm is used to solve the N queen problem, in which the board is recursively filled with queens, one at a time, and backtracked if no valid solution is found. At each step, the algorithm checks to see if the newly placed queen conflicts with any previously placed queens, and if so, it backtracks.

What is the initial state of the 8 queens problem? ›

The initial state is given by the empty chess board. Placing a queen on the board represents an action in the search problem. A goal state is a configuration where none of the queens attacks any of the others. Note that every goal state is reached after exactly 8 actions.

How to put 8 queens on a chessboard without threatening each other? ›

Placing queens on a chessboard using the knight's move to separate them can be quite a good strategy for playing eight queens. If you remove the black knights from Figure 1a and replace the four white knights with four queens, then no two queens are threatening each other (Figure 1b).

How many solutions are there for 8 queens on 8 * 8 board 91 93 92 90? ›

Explanation: For 8*8 chess board with 8 queens there are total of 92 solutions for the puzzle.

How to solve n queen problem? ›

When we place a queen in a column, we check for clashes with already placed queens. In the current column, if we find a row for which there is no clash, we mark this row and column as part of the solution. If we do not find such a row due to clashes, then we backtrack and return false.

What are the possible combinations of the 8-puzzle? ›

For our 8-Puzzle problem the number of possible arrangements (Permutations) is 9! which is equal to 362880. But theres a twist in these permutations. Only Half of the permutations i.e., 181440 is actually solvable.

Top Articles
Latest Posts
Article information

Author: Gregorio Kreiger

Last Updated:

Views: 6084

Rating: 4.7 / 5 (77 voted)

Reviews: 84% of readers found this page helpful

Author information

Name: Gregorio Kreiger

Birthday: 1994-12-18

Address: 89212 Tracey Ramp, Sunside, MT 08453-0951

Phone: +9014805370218

Job: Customer Designer

Hobby: Mountain biking, Orienteering, Hiking, Sewing, Backpacking, Mushroom hunting, Backpacking

Introduction: My name is Gregorio Kreiger, I am a tender, brainy, enthusiastic, combative, agreeable, gentle, gentle person who loves writing and wants to share my knowledge and understanding with you.