# N-Queens Problem Backtracking Demo

A visualization and explanation of how a backtracking algorithm searches for a solution to a problem.

**For performance reasons n is bound between 4 and 10.**

*Note: Requires canvas supported browser. Tested on Chrome, Safari, Edge, Firefox.*

# N-queens problem

If I have a chessboard of width and length **n** where **n** is a number.

How can **n** queens be placed so that none of the queens are attacking one another?

Try it yourself here with 8 queens.

## What would the algorithm do without backtracking?

Without backtracking a program would place all n queens before checking if any queens are attacking. This leads to wasteful solutions such as an entire row of queens.

We don’t need a whole row full of queens before we know that the solution failed. Instead we only need 2 queens to be attacking each other to know that the solution is wrong.

## Introducing backtracking

A backtracking algorithm is a way of computing a solution to a problem when constraints are known.

The algorithm places one queen at a time.
If the queen placed is attacking another queen, the queen is removed and we try again in the next position.
This is the *backtracking* step.

If you want to see this in action. Run the animation and look for the queens being taken off the board. This is obvious when solving for 10 queens.