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? Your program should be a function that takes N as a parameter and returns either a solution (a board with the N queens in their appropriate places) or an empty list.
Do this using an NQueens module and a Board.hs module that has all the generic board operations. Your NQueens module will import the Board module. You may use BoardInterface.hs as a starting point for your Board module, and you may use any code from the various Board attempts we looked at earlier, if you find them useful. The main function for the program as a whole should be nQueens N, where N is the size of an N x N board. The function should return a solution if there is one (e.g., the first solution it finds), or an empty list if there is no solution for a board of size N. For example,
nQueens 3 | yields | [] |
nQueens 4 | might yield | [[0,1,0,0],[0,0,0,1],[1,0,0,0],[0,0,1,0]] (one of several possible solutions) |
Using modules such as the board module is a step towards OO, except that you will have to pass the board explicitly to all the board functions rather than send messages (function names & parameters) to the board. Furthermore, a board never changes state.
I have put together a very static, unanimated "animation" of backtracking, which might be useful.