nqueens.cpp

C++&datastructure书籍源码,以前外教提供现在与大家共享

#include <iostream>
using namespace std;

#include "tmatrix.h"
#include "prompt.h"

class Queens
{
  public:
    Queens(int size);
    
    bool Solve();
    
    void Print(ostream& out) const;
  private:
  
    bool NoQueensAttackingAt(int r, int c) const;
    bool SolveAtCol(int col);
    tmatrix<bool> myBoard;
};

bool Queens::NoQueensAttackingAt(int r, int c) const
// pre: column col is clear
// post: return true if row clear and diagonals crossing at
//       (row,col) clear
{
    int k, row,col;
    for(k=0; k < myBoard.numcols(); k++)
    {   if (k != c && myBoard[r][k]) return false;
    }
    row = r-1; col = c-1;
    while (0 <= row && 0 <= col)
    {   if (myBoard[row][col]) return false;
        row--; col--;
    }
    row = r+1; col = c+1;
    while (row < myBoard.numrows() && col < myBoard.numcols())
    {   if (myBoard[row][col]) return false;
        row++; col++;
    }
    row = r-1; col = c+1;
    while (0 <= row && col < myBoard.numcols())
    {   if (myBoard[row][col]) return false;
        row--; col++;
    }
    row = r+1; col = c-1;
    while (row < myBoard.numrows() && 0 <= col)
    {   if (myBoard[row][col]) return false;
        row++; col--;
    }
    return true;
}

Queens::Queens(int size)
  : myBoard(size,size,false)
{ }

bool Queens::Solve()
{
    return SolveAtCol(0);
}

bool Queens::SolveAtCol(int col)
// pre: queens placed at columns 0,1,...,col-1
// post: returns true if queen can be placed in column col
//       if col == size of board, then n queens are placed
{
    int k;
    int rows = myBoard.numrows();
    if (col == rows) return true;
    
    for(k=0; k < rows; k++)
    {   if (NoQueensAttackingAt(k,col))
        {   myBoard[k][col] = true;
            if (SolveAtCol(col+1))
            {    return true;
            }
            myBoard[k][col] = false;
        }
    }
    return false;
}

void Queens::Print(ostream& out) const
{
    int j,k;
    for(j=0; j < myBoard.numrows(); j++)
    {   for(k=0; k < myBoard.numcols(); k++)
        {   out << (myBoard[j][k] ? 'X' : '.');
        }
        out << endl;
    }
}

int main()
{
    int size = PromptRange("size of board: ",2,12);
    
    Queens nq(size);
    
    if (nq.Solve())
    {    nq.Print(cout);
    }
    else
    {   cout << "no solution found" << endl;
    }
    return 0;
}