A Queen is a piece in chess that can go in a straight line or in a diagonal line. In the diagram below, the Queen is located on row 2 and column 3.

0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | |

0 | ||||||||

1 | ||||||||

2 | ||||||||

3 | ||||||||

4 | ||||||||

5 | ||||||||

6 | ||||||||

7 |

In the diagram below, the squares in yellow indicate the squares where the Queen may move to in a single turn.

0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | |

0 | ||||||||

1 | ||||||||

2 | ||||||||

3 | ||||||||

4 | ||||||||

5 | ||||||||

6 | ||||||||

7 |

The eventual goal is to create a function that will determine the number of ways a Queen can be put in each row such that no Queen can move to any other Queen's spot in one turn.

Here is one example of 8 Queens placed in a standard 8 x 8 chessboard in such a manner:

0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | |

0 | ||||||||

1 | ||||||||

2 | ||||||||

3 | ||||||||

4 | ||||||||

5 | ||||||||

6 | ||||||||

7 |

If it is assumed that an 8 x 8 chessboard is used, then it is known as the "8 Queens" problem. We would like to solve this for chessboards of various sizes, which is known as the "N Queens" problem.

One way to calculate all of the ways to place N Queens is to use brute force.

This would mean trying every combination of "one Queen per row".

However, this is not necessary. For example, look at the diagram below.

0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | |

0 | ||||||||

1 | ||||||||

2 | ||||||||

3 | ||||||||

4 | ||||||||

5 | ||||||||

6 | ||||||||

7 |

If we were to try every combination of "one Queen per row", we would continue to try to put 6 more Queens on the board in many different ways. However, none of those combinations would succeed, because the first two Queens already make the placement invalid.

Thus, we will use a technique called **recursive backtracking**.**Recursive:** every time we go to the next row to try placing another Queen, we make a recursive call.**Backtracking:** if the partial solution cannot be completed to form a valid solution, then we abandon the partial solution and backtrack.

In the diagram below, 2 Queens have been placed. The squares where the two Queens can visit are in yellow- when it comes to placing a third Queen, the yellow squares can be ignored. Thus, on row 2, the recursive backtracking solution would only consider columns 0, 5, 6, and 7.

0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | |

0 | ||||||||

1 | ||||||||

2 | ||||||||

3 | ||||||||

4 | ||||||||

5 | ||||||||

6 | ||||||||

7 |

As a first step, let's write a function called ` that will determine if a Queen can be placed on a chessboard for a given row and column without allowing any other Queen to attack the new Queen. No other queens would share the same row, column, or diagonal as the new Queen.`

After we build this function, we can use it to determine where the next Queen can be placed.

The first parameter is ` and determines the size of the chessboard. A standard chessboard is 8 x 8, so this value would be 8 for a standard chessboard.`

The second parameter is `, which is an array of Queen positions. It is an array of arrays- the first value of the array is the row, and the second value is the column.`

The third parameter is `, which is an array of where the new Queen would be placed. It is an array- the first value is the row, and the second value is the column.`

For example, the diagram below illustrates the following parameters:

`var = 8; = 8`

`var = [[0,5],[2,6],[3,0],[4,3],[5,7],[6,4],[7,2]]; = [[0,5],[2,6],[3,0],[4,3],[5,7],[6,4],[7,2]]`

`var = [1,1]; = [1,1]`

0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | |

0 | ||||||||

1 | ||||||||

2 | ||||||||

3 | ||||||||

4 | ||||||||

5 | ||||||||

6 | ||||||||

7 |

` would return `

`trueTrue`

in this case.

Log In