The 8 Queen Problem is a puzzle in which 8 queens must be placed on an 8x8 chessboard so that no two queens threaten each other. It is a classic problem in computer science and mathematics. There are 92 solutions to this problem. The eight queens puzzle problem was first posed in the mid-19th century.

Backtracking is a recursive approach for solving any problem where we must search among all the possible solutions following some constraints. More precisely, we can say that it is an improvement over the brute force technique. In this blog, we will learn one popular DSA problem: 8 queens problem using Backtracking.

We will retain the backtracking approach and go through its time optimization. Let's start with the problem statement of solving 8 queens problem using backtracking in the next section.

**Problem Statement**

Given an 8x8 chess board, you must place 8 queens on the board so that no two queens attack each other. Print all possible matrices satisfying the conditions with positions with queens marked with '1' and empty spaces with '0'. You must solve the 8 queens problem using backtracking.

**Note 1:**A queen can move vertically, horizontally and diagonally in any number of steps.**Note 2:**You can also go through the__N-Queen Problem__for the general approach to solving this problem.

**Sample Example**

**Example:** One possible solution to the 8 queens problem using backtracking is shown below. In the first row, the queen is at E8 square, so we have to make sure no queen is in column E and row 8 and also along its diagonals. Similarly, for the second row, the queen is on the B7 square, thus, we have to secure its horizontal, vertical, and diagonal squares. The same pattern is followed for the rest of the queens.

**Output:**

**0 0 0 0 1 0 0 0**

**0 1 0 0 0 0 0 0**

**0 0 0 1 0 0 0 0**

**0 0 0 0 0 0 1 0**

**0 0 1 0 0 0 0 0**

**0 0 0 0 0 0 0 1**

**0 0 0 0 0 1 0 0**

**1 0 0 0 0 0 0 0**

**Bruteforce Approach**

One brute-force approach to solving this problem is as follows:

- Generate all possible permutations of the numbers 1 to 8, representing the columns on the chessboard.
- For each permutation, check if it represents a valid solution by checking that no two queens are in the same row or diagonal.
- If a valid solution is found, print the board layout.

While this approach works for small numbers, it quickly becomes inefficient for larger sizes as the number of permutations to check grows exponentially. More efficient algorithms, such as backtracking or genetic algorithms, can be used to solve the problem in a more optimized way.

Also read, __Permutation of string__