Partilhar via

Reflecting in action: programming other algorithms

  • Artigo

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)
    {
      results.Add(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')
              result.Add(board[k,j]);
        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')
              result.Add(board[k, j]);
          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')
              result.Add(board[n, k]);
          return result;
        }
      }
    }
  }

Comments