Chess is a game played on an 8 8 board. Assuming there are no other pieces that block its path, and without going off the edge of the board, the queen is a piece that is allowed to move any number of spaces in one of eight different directions. These directions correspond to moving along its current row, column, or in a diagonal direction. The 8 queens puzzle involves placing 8 queens on a chessboard such that no queen can attack another queen. That is, no queen can reach another queen in a single move. Generalizing, the n queens puzzle involves placing n queens on an n n chessboard such that no queen can attack another queen. Given a placement of n queens on an n n chessboard, design an O(n) algorithm to determine whether or not the placement is a solution to the n queens puzzle.