# 8 Queens Problem

> The [**eight queens puzzle**](https://en.wikipedia.org/wiki/Eight_queens_puzzle) is the problem of placing eight [chess](https://en.wikipedia.org/wiki/Chess) [queens](https://en.wikipedia.org/wiki/Queen_\(chess\)) on an 8×8 [chessboard](https://en.wikipedia.org/wiki/Chessboard) so that no two queens threaten each other; thus, a solution requires that no two queens share the same row, column, or diagonal. 

<div align="center"><img src="https://2502734374-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MdM8iXEiSa6vIC3EFqT%2F-MeUVxL5N8mgIGuvp69d%2F-MeV6JYg5SkDNZFmRRE8%2F8%20Queens%20Problem%20Solutions.png?alt=media&#x26;token=9b9de929-4c95-4162-8d6a-abcca679a496" alt="Eight Queens Puzzle Solutions at Depth 1, 2 and 3"></div>

The above images represent the distribution of solutions for the eight queens puzzle. The original images can be viewed in the [gallery](https://b-faze.github.io/faze/Eight-Queens-Problem.html).

## Pipeline Summary

#### Data Pipeline

```csharp
ReversePipelineBuilder.Create()
    .SaveTree(EightQueensProblemExhaustiveDataPipeline.Id, treeDataProvider)
    .Map(resultsMapper)
    .LimitDepth(3)
    .GameTree(new SquareTreeAdapter(BoardSize))
    .Build(() => new PiecesBoardState(new PiecesBoardStateConfig(BoardSize, new QueenPiece(), onlySafeMoves: true)));
```

#### Render Pipeline

```csharp
ReversePipelineBuilder.Create()
    .GallerySave(galleryService, galleryMetaData)
    .Render(new SquareTreeRenderer(rendererConfig))
    .Paint(painter)
    .LoadTree(EightQueensProblemExhaustiveDataPipeline.Id, treeDataProvider);
```

## Pipeline Breakdown

### Game

The game rules are handled by the `PiecesBoardState` type using the following configuration:

| Property      | Value      | Description                                                          |
| ------------- | ---------- | -------------------------------------------------------------------- |
| Dimension     | 8          | Size of the board                                                    |
| Piece         | QueenPiece | Defines how the piece moves on the board                             |
| OnlySafeMoves | true       | Game state will only return moves that do not attack existing queens |

### Results Tree Mapper

Next the results mapper (`EightQueensProblemSolutionTreeMapper`) will take the game tree and transform it into a tree containing the results we can use generate the visualisation. In this case we are given a game tree 3 moves deep and then collect our results using the `EightQueensProblemSolutionAggregate` type.

```csharp
private static Tree<EightQueensProblemSolutionAggregate> MapTreeAgg(Tree<IGameState<GridMove, SingleScoreResult?>> tree)
{
    if (tree == null)
        return null;


    if (tree.IsLeaf())
    {
        var resultAgg = AggregateResults(tree.Value);
        return new Tree<EightQueensProblemSolutionAggregate>(resultAgg);
    }

    var children = tree.Children.Select(x => MapTreeAgg(x)).ToList();

    var treeValue = new EightQueensProblemSolutionAggregate();    
    foreach (var childValue in children.Where(x => x != null).Select(x => x.Value))
    {
        treeValue.Add(childValue);
    }

    return new Tree<EightQueensProblemSolutionAggregate>(treeValue, children);
}
```

### Tree Painter

We then have a tree painter (`EightQueensProblemPainter`) which maps the results tree into a colour tree.&#x20;

```csharp
private Tree<Color> Paint(Tree<EightQueensProblemSolutionAggregate> tree, TreeMapInfo info, uint maxSiblingWins)
{
    if (tree == null)
    {
        return info.Parent.ChildIndex == info.ChildIndex 
            ? null 
            : new Tree<Color>(Color.Black);
    }

    var value = maxSiblingWins > 0 
        ? (double)tree.Value.Wins / maxSiblingWins 
        : 0;
        
    var color = value > 0 
        ? colorInterpolator.GetColor(value) 
        : Color.Black;

    if (tree.IsLeaf())
        return new Tree<Color>(color);

    var maxChildrenWins = tree.Children.Where(c => c != null).Select(x => x.Value.Wins).Max();
    var children = tree.Children.Select((c, i) => Paint(c, info.Child(i), maxChildrenWins));

    return new Tree<Color>(color, children);
}
```

The `EightQueensProblemPainter` normalises the number of wins of a tree node against the maximum value of its siblings.&#x20;

E.g. if we have 3 child nodes: \[100, 10, 50], the max sibling value is 100 so the normalised result will be \[100/100, 10/100, 50/100] or \[1, 0.1, 0.5]

The [GoldInterpolator](https://b-hub.gitbook.io/faze/v2.0.0/rendering/color-interpolators#gold) then takes this normalised value and converts it to a colour.

All unavailable moves will be coloured black, with the exception of moves that are the same as the previous. The relevant code segment is here:

```csharp
    if (tree == null)
    {
        return info.Parent.ChildIndex == info.ChildIndex 
            ? null 
            : new Tree<Color>(Color.Black);
    }
```

Returning a null node will be ignored by the renderer.  This means the null nodes will be coloured according to the parent's results which acts like a summary at each depth:

![Summary nodes](https://2502734374-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MdM8iXEiSa6vIC3EFqT%2F-MeUVxL5N8mgIGuvp69d%2F-MeVIopi8o8X2y9-Ngvi%2F8%20Queens%20Problem%20Solutions%20depth%202%20circled.png?alt=media\&token=394611ac-44de-45d1-b563-0c18cc7f36b0)

### Tree Renderer

The `SquareTreeRenderer` fits very nicely with this type of problem as it is played on a 8x8 board.

| Property | Value      |
| -------- | ---------- |
| MaxDepth | 1, 2 and 3 |