The Queens Problem

Before I started hacking on cabal, I wanted to look at a simpler version of the problem.

I decided to write the interactive part for the queens problem.

If you care to see the code, you can find it at https://github.com/mr-/hsQueens 

The queens problem consists of a chess board of size n and m queens. The challenge is to place the queens on the board so that no queen is endangered.

In the program I decided to represent a queen by its position:

type Piece = (Int, Int)

and the board is a list of pieces:

type Board = [Piece]

From this I (lazily) built a tree, where each node is a board. It has as root the empty board, on the first level are all the boards with one piece, on the second are all the boards with two pieces, and so on.

Then I prune the tree, removing all the boards that are inconsistent in the sense that queens are unsafe.
Afterwards comes a (rather stupid) heuristics phase, which sorts the choices by the number of their children. Even though it is so simple, it managed to reduce computation time by quite a bit.

Now, to solve the problem for m queens, you just have to DFS the tree till you find a board that has at least m queens.

Walking the tree is done using Data.Tree.Zipper, which works using trees from Data.Tree.

I have implemented the following commands:

go n       --   takes the n'th choice (Choices are given as n: Piece)

auto n    --   tries to find a board with n queens, given the current choices

up          --   goes up in the tree, i.e. reverts the last choice

          top         --   goes all the way to the root

These commands can be joined using ",". so "go 0, up" would do nothing.

Wrapping it into an UI using haskeline, it looks like that:

  martin@office:~$ hsQueens 4

  ....
  ....
  ....
  ....


  0:(2,2) 1:(2,3) 2:(3,2) 3:(3,3) 4:(1,1) 5:(1,2) 6:(1,3) 7:(1,4) 
  8:(2,1) 9:(2,4) 10:(3,1) 11:(3,4) 12:(4,1) 13:(4,2) 14:(4,3) 
  15:(4,4) 
  17:08:43> go 0
  ....
  .♛..
  ....
  ....


  0:(1,4) 1:(3,4) 2:(4,1) 3:(4,3) 
  17:08:46> go 1
  ....
  .♛..
  ....
  ..♛.


  0:(4,1) 
  17:08:47> up
  ....
  .♛..
  ....
  ....


  0:(1,4) 1:(3,4) 2:(4,1) 3:(4,3) 
  17:08:51> auto 4
  Nothing found
  17:08:54> auto 3
  ....
  .♛..
  ...♛
  ♛...

That's it. The next post will be about cabal-install's tree and its zipper.