Implement the N Queens Problem in Haskell. The N Queens problem is: Can you place N queens on an N x N "chess" board, such that no two queens are attacking each other, for any specified value N?
Board Module
Use this incomplete
Board.hs module
containing generic board operations
and Main.hs module
as starting points.
The Board module has been partially implemented using code from the
set of Board development attempts covered in class. It also
contains a few sample test cases for testing Board functions in a
boardAccessFunctionsTestSuite test suite that uses the
TestSuiteSupportModule.
Complete
the code for the module and add test cases to thoroughly test all
of its functions.
NQueens Module
Then develop a module called NQueens that imports the Board module
and defines a function called nQueens.
This function takes an integer parameter that specifies the size of the
board; in other words, nQueens N, where
N is the size of an N x N board.
The function should return
either a solution if there is one (a board with the N queens in appropriate places)
or an empty list
if there is no solution for a board of size N.
For example,
Note that the nQueens function should return just a single solution (e.g., the first one it finds), not all possible solutions for the given board size.nQueens 3yields[]
nQueens 4might yield[[0,1,0,0],[0,0,0,1],[1,0,0,0],[0,0,1,0]](one of several possible solutions)
Test the functions in your NQueens module by adding
calls to the nQueens function with different board
dimensions in the Main module.
(Don't change the TestSuiteSupportModule itself.)
Caution: Do not change the names of the NQueens module or the nQueens function. Your code will be tested against an instructor-defined set of test cases, and those are the names used by those tests.
I have put together a very static, unanimated "animation" of backtracking, which might be useful.