# Marco Dorantes' WebLog

"Computer science is no more about computers than astronomy is about telescopes" -Edsger W. Dijkstra

# Reflecting in action: programming other algorithms

### Reflecting in action: programming other algorithms

As part of the same preparation I really enjoyed to program a classic:

Which are the 92 solutions to the 8 queen problem?

First, the usage intentions and conditions of satisfaction:

```    [TestMethod]
public void validSolutions()
{
List<ChessBoard> boards = ChessBoard.AllQueens();
foreach (ChessBoard b in boards)
{
IList all=b.Pieces;
Assert.IsTrue(all.Count == 8);
for (int k = 0; k < 8; k++)
{
IList l = b.Rank[k];
Assert.IsTrue(l.Count == 1);
}
foreach (char c in "abcdefgh")
{
IList l = b.File[c];
Assert.IsTrue(l.Count == 1);
}
}
}
[TestMethod]
public void allSolutions()
{
List<ChessBoard> boards = ChessBoard.AllQueens();
Assert.AreEqual(92, boards.Count);
}
```
The AllQueens method:
```    public static List<ChessBoard> AllQueens()
{
ResultKeeper keeper = new ResultKeeper();
ChessBoard board = new ChessBoard();
board.OnNewSolution += new ChessBoard.OnNewSolutionHandler(keeper.OnNewSolution);
board.GetQueens();
return keeper.Results;
}
```
And the ancillary ResultKeeper class:
```  class ResultKeeper
{
List<ChessBoard> results;
public ResultKeeper()
{
results = new List<ChessBoard>();
}
public void OnNewSolution(int count, ChessBoard board)
{
}
public List<ChessBoard> Results
{
get
{
return results;
}
}
}
```
And finally, the ChessBoard class:
```  public class ChessBoard
{
private char[,] board;
private int hit_count;

public ChessBoard()
{
board  = new char[8, 8];
reset();
}
private ChessBoard(char[,] b)
{
board = b;
}

public delegate void OnNewSolutionHandler(int count,ChessBoard board);
public event OnNewSolutionHandler OnNewSolution;

public IList Pieces
{
get
{
ArrayList result = new ArrayList();
for (int k = 0; k < 8; ++k)
for(int j=0;j<8;++j)
if (board[k,j] == 'X')
return result;
}
}
public FileLine File { get { return new FileLine(board); } }
public RankLine Rank { get { return new RankLine(board); } }
public char[,] InternalState
{
get { return board; }
}

public static List<ChessBoard> AllQueens()
{
ResultKeeper keeper = new ResultKeeper();
ChessBoard b = new ChessBoard();
b.OnNewSolution += new ChessBoard.OnNewSolutionHandler(keeper.OnNewSolution);
b.GetQueens();
return keeper.Results;
}

public void GetQueens()
{
find_safe_positions();
}

void reset()
{
for (int k = 0; k < 8; ++k)
for (int j = 0; j < 8; ++j)
board[k, j] = '-';
}

private void find_safe_positions()
{
int rank = 0;
find_safe_position(rank);
}

private bool find_safe_position(int rank)
{
for (int file = 0; file < 8; ++file)
{
if (is_safe(rank, file))
{
board[rank, file] = 'X';
if (rank == 7)
{
NewSolutionFound();
board[rank, file] = '-';
continue;
}
if (find_safe_position(rank + 1))
return true;
else
board[rank, file] = '-';
}
}
return false;
}

bool is_safe(int rank, int file)
{
bool safe = empty_rank(rank) && empty_file(file) && empty_cross(rank, file);
return safe;
}
bool empty_rank(int rank)
{
for (int k = 0; k < 8; ++k)
if (board[rank, k] == 'X')
return false;
return true;
}
bool empty_file(int file)
{
for (int k = 0; k < 8; ++k)
if (board[k, file] == 'X')
return false;
return true;
}
bool empty_cross(int rank, int file)
{
for (int k = rank, j = file; k >= 0 && j >= 0; --k, --j)
if (board[k, j] == 'X')
return false;
for (int k = rank, j = file; k < 8 && j < 8; ++k, ++j)
if (board[k, j] == 'X')
return false;
for (int k = rank, j = file; k < 8 && j >= 0; ++k, --j)
if (board[k, j] == 'X')
return false;
for (int k = rank, j = file; k >= 0 && j < 8; --k, ++j)
if (board[k, j] == 'X')
return false;
return true;
}

void NewSolutionFound()
{
ChessBoard b = new ChessBoard(board.Clone() as char[,]);
++hit_count;
if (OnNewSolution != null)
OnNewSolution(hit_count, b);
}

public class FileLine
{
private char[,] board;
internal FileLine(char[,] b) { board = b; }
public IList this[char c]
{
get
{
ArrayList result = new ArrayList();
int j = (int)c - 97;
for (int k = 0; k < 8; ++k)
if (board[k, j] == 'X')
return result;
}
}
}

public class RankLine
{
private char[,] board;
internal RankLine(char[,] b) { board = b; }
public IList this[int n]
{
get
{
ArrayList result = new ArrayList();
for (int k = 0; k < 8; ++k)
if (board[n, k] == 'X')