Chessboard separation problems are modifications to classic chessboard problems, such as the \( N \) Queens Problem, in which obstacles are placed on the chessboard. This paper focuses on a variation known as the \( N + k \) Queens Problem, in which \( k \) Pawns and \( N + k \) mutually non-attacking Queens are to be placed on an \( N \)-by-\( N \) chessboard. Results are presented from performance studies examining the efficiency of sequential and parallel programs that count the number of solutions to the \( N + k \) Queens Problem using traditional backtracking and dancing links. The use of Stochastic Local Search for determining the existence of solutions is also presented. In addition, preliminary results are given for a similar problem, the \( N + k \) Amazons.