Kata

Generalizing the N-Queens problem

The N-queens problem is a chess puzzle where one should place on a n x n chessboard n queens in such a way no queen can attack another one.
For more information, you can have a look on wikipedia : https://en.wikipedia.org/wiki/Eight_queens_puzzle

We would like to generalize this problem, and count the number of distinct ways of placing a given selection of chess pieces taken amongst King, Queen, Bishop, Rook and Knight on a rectangular m x n chessboard.
No piece should be able to attack another one.

For example, one can place in 8 different ways 1 King, 1 Rook, 1 Bishop and 2 Knights on a 4 x 3 chessboard :

A solution could be the following (K=King, N=Knight, B=Bishop):

    1   2   3   4 
1 | N |   |   | B |
2 |   | R |   |   |
3 | N |   |   | K |

There is 7 more solutions for that setting.
Hint: you can take symetrical solutions along the X and Y axis.

You are asked to complete the following function :

-- Dimensions of the chessboard (width,height)
type Dim = (Int,Int)
data Piece = Knight | Rook | Bishop | King | Queen deriving(Eq,Ord,Show)

-- Count the number of distinct chessboard settings containing all the provided pieces
-- where no piece can attack another one.
solve :: Dim -> [Piece] -> Int

Please note :

• The list of pieces and the chessboard size of the tests will allow you to implement a naive brute-force algorithm
  
• We are counting only DISTINCT solutions.
  For instance a King at position (1,1) on the chessboard is identical to another King at position (1,1) - even if the list of pieces you are given contains 2 Kings.
  
• Black and White colors don't matter for this problem, like for the N-Queens problem.
  
• Your program should be able to run the N-Queens for low dimensions, even with a naive algorithm. You can use wikipedia for help and create some unit tests.
  

If you need a reminder of the chess moves, you can find information here :
King : https://en.wikipedia.org/wiki/King_(chess)
Queen : https://en.wikipedia.org/wiki/Queen_(chess)
Rook : https://en.wikipedia.org/wiki/Rook_(chess)
Bishop : https://en.wikipedia.org/wiki/Bishop_(chess)
Knight : https://en.wikipedia.org/wiki/Knight_(chess)