Introduction:The eight queens puzzle is the problem of placing eight chess queens on an 8Ś8 chessboard so that no two queens attack each other. Thus, a solution requires that no two queens share the same row, column, or diagonal.

The eight queens puzzle is an example of the more general n-queens problem of placing n queens on an nŚn chessboard, where solutions exist for all natural numbers n with the exception of 2 and 3.

The Challenge:To create a program that will return a solution to the n-queens puzzle for arbitrary 'n'. The program should take a single argument 'n' and return a list of 2D coordinates describing the positions of the queens on the nxn chessboard such that no two queens attack each other. For consistency of solutions in this thread, the first square can have coordinates (1, 1).

Examples:Note that these examples illustrate one possible solution, of which there may be many unique solutions.

`_$ (nQueens 4)`

((4 3) (3 1) (2 4) (1 2))

`_$ (nQueens 8)`

((8 4) (7 2) (6 7) (5 3) (4 6) (3 8) (2 5) (1 1))