nqueenpartial.cpp

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

class Queens
{
  public:
    Queens(int size);
    bool Solve();                   // return true if solvable
    void Print(ostream& out) const; // print the last board
  private:
    // helper functions
    bool NoQueensAttackingAt(int r, int c) const;
    bool SolveAtCol(int col);

    tmatrix<bool> myBoard;          // the board
};

bool Queens::NoQueensAttackingAt(int r, int c) const
// post: return true if row clear and diagonals crossing at
//       (row,col) clear

bool Queens::Solve()
// post: return true if n queens can be placed
{
    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;  // N queens placed
    for(k=0; k < rows; k++)
    {   if (NoQueensAttackingAt(k,col))  // can place here?
        {   myBoard[k][col] = true;      // try it
            if (SolveAtCol(col+1))       // recurse
            {    return true;
            }
            myBoard[k][col] = false;     // backtrack
        }
    }
    return false;
}

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;
}