Solving LinkedIn Queens Using Haskell

Summary

[Thanks to James Haydon for his suggestions on improving the post and the code quality]On LinkedIn, you can play a variant of the N-Queens problem. A community version of the game (rather, puzzle) can be found here.Recently, we saw it solved using SAT solvers, using SMT Solvers, using APL and MiniZinc. Today, I will try solving it using Haskell, a slightly more conventional language.The PuzzleYou are given a N-colored square-shaped board of size N. You must place N queens on the board such that:Each row, each column, and each color region has exactly one queen.No two queens touch each other diagonally.Note that placing two queens in the same diagonal is acceptable, as long as they are not diagonally adjacent (unlike in Chess).For instance, one can verify that the following is the only solution for the given colored board.Haskell SetupWe will use Data.Array from the array library to represent the problem.type Color = Int type Row = Int type Column = Int type Problem = Array (Row, Column) Color mkProblem :: [[Color]] -> Problem mkProblem colorsList = Array.array ((0, 0), (n - 1, n - 1)) [((i, j), color) | (i, row) <- zip [0 ..] colorsList, (j, color) <- zip [0 ..] row] where n = length colorsList size :: Problem -> Int size problem = n + 1 where ((_, _), (_, n)) = Array.bounds problem problem1 :: Problem problem1 = mkProblem [ [0, 1, 1, 1, 1], [2, 3, 2, 1, 2], [2, 3, 2, 1, 2], [2, 2, 2, 4, 4], [2, 2, 2, 2, 2] ] The problem shown above is encoded as problem1 in the code. I have encoded a few larger examples in this file.Backtracking, Soundness and Completeness[Source Code for Attempt 0]We will tackle the problem using a backtracking approach. This means, we will place a queen on a plausible cell on the board; check if the current configuration can be extended to a full solution; continue if so, and backtrack otherwise, finding a different plausible cell to put the queen on.To aid our discussion, let us introduce some terminology.A partial placement is a set of position...