데이터 구조 - 8 황후 문제 귀속 코드 실현

#ifndef QUEENS_H
#define QUEENS_H

const int max_board = 30;

class Queens
{
    public:
        Queens(int size);

        bool unguarded(int col)const;
        void insert(int col);
        void remove(int col);
        bool is_solved()const;
        void print()const;
        int board_size;

    protected:

    private:
        int count;
        bool col_free[max_board];   //         
        bool upward_free[2*max_board-1];    //                  
        bool downward_free[2*max_board-1];  //                  
        int queen_in_row[max_board];   //      queen   
        static int success;
};

#endif // QUEENS_H

#include "Queens.h"
#include 

using namespace std;

int Queens::success = 1;

Queens::Queens(int size)
/*Post:      Queens    .
*/
{
    board_size = size;
    count = 0;
    int i;
    for(i = 0; i < board_size; i++)col_free[i] = true;
    for(i = 0; i < (board_size*2-1); i++)upward_free[i] = true;
    for(i = 0; i < (board_size*2-1); i++)downward_free[i] = true;
    for(i = 0; i < board_size; i++)queen_in_row[i] = -1;
}

bool Queens::unguarded(int col)const
/*Post:        (count) col         ,     true    false
*/
{
    return col_free[col] && upward_free[count+col]
           && downward_free[count-col+board_size-1];
}

void Queens::insert(int col)
/*Post:        col     ,            .
*/
{
    queen_in_row[count] = col;  //          count
    col_free[col] = false;
    upward_free[count+col] = false;
    downward_free[count-col+board_size-1] = false;
    count++;
}

void Queens::remove(int col)
/*Post:          col    ,               .
*/
{
    count--;
    queen_in_row[count] = -1;
    col_free[col] = true;
    upward_free[count+col] = true;
    downward_free[count-col+board_size-1] = true;
}

bool Queens::is_solved()const
/*Post:                true,     false.
*/
{
    return count==board_size;
}

void Queens::print()const
/*Post:              .
*/
{
    cout << "case #" << success++ << ":" << endl;
    for(int row = 0; row < board_size; row++)
    {
        for(int col = 0; col < board_size; col++)
        {
            if(queen_in_row[row]==col)
                cout << "*";
            else
                cout << "-";
        }
        cout << endl;
    }
    cout << endl;
}

#include 
#include "Queens.h"

using namespace std;

void solve_from(Queens &configuration)
/*Post:      board_size   ,                         .
  Uses: Queens       .
*/
{
    if(configuration.is_solved())configuration.print();
    else
        for(int col = 0; col < configuration.board_size; col++)
            if(configuration.unguarded(col))
            {
                configuration.insert(col);
                solve_from(configuration);
                configuration.remove(col);
            }
}

int main()
{
    int board_size;
    cin >> board_size;
    if(board_size<0 || board_size>max_board)
        cout << "The number is out of range!" << endl;
    else
    {
        Queens configuration(board_size);
        solve_from(configuration);
    }

    return 0;
}