Функции.Перебор с возвратом

/////////////////////////////////////////////////////////////////////////////////////////
//Найти расстановку пяти ферзей на шахматной доске, при которой каждое поле 
//будет находиться под ударом одного из них.
/////////////////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <complex>
#include <iostream>
#include <iterator>
#include <set>
#include <vector>
/////////////////////////////////////////////////////////////////////////////////////////
class  T_cell
{    
public:
    //-----------------------------------------------------------------------------------
    typedef int                             T_coord;
    //-----------------------------------------------------------------------------------
private:
    //-----------------------------------------------------------------------------------
    typedef std::pair<T_coord, T_coord>     T_cells_coords;
    //-----------------------------------------------------------------------------------
    T_cells_coords                          coords_;      
    //-----------------------------------------------------------------------------------
public:
    static const T_coord    EMPTY_COORD     = 0;
    static const T_coord    MIN_COORD       = 1;
    static const T_coord    MAX_COORD       = 8;
    //-----------------------------------------------------------------------------------
    T_cell
        (
            T_coord     i   =   EMPTY_COORD,
            T_coord     j   =   EMPTY_COORD
        )
        :
        coords_(i, j)
    {}
    //-----------------------------------------------------------------------------------
    T_coord  horiz()                const
    {
        return  coords_.first;
    }
    //-----------------------------------------------------------------------------------    
    T_coord  vert()                 const
    {
        return  coords_.second;
    }
    //-----------------------------------------------------------------------------------
    bool  operator< (T_cell  cell)  const
    {
        return  coords_ < cell.coords_;
    }
    //-----------------------------------------------------------------------------------
    void  print_cell_and_tab()      const
    {
        std::cout   <<  std::complex<T_coord>
                            (
                                coords_.first,
                                coords_.second
                            )
 
                    <<  '\t';
    }
    //-----------------------------------------------------------------------------------
    T_cell  vert_reflection()       const
    {
        return  T_cell
                    (
                        horiz(),
                        MAX_COORD + 1 - vert()
                    );
    }
    //-----------------------------------------------------------------------------------
    T_cell  transp()                const
    {
        return  T_cell
                    (
                        vert    (),
                        horiz   ()
                    );
    }
    //-----------------------------------------------------------------------------------
    T_cell  cell_rotate()           const
    {     
        return  vert_reflection().transp();
    }
    //-----------------------------------------------------------------------------------
};
/////////////////////////////////////////////////////////////////////////////////////////
typedef std::set< T_cell    >   T_cells;
typedef std::set< T_cells   >   T_positions;
/////////////////////////////////////////////////////////////////////////////////////////
T_cells&  operator-= 
    (
        T_cells&        L,
        const T_cells&  R
    )
{
    T_cells  res;
 
    std::set_difference
        (
            L.begin (),
            L.end   (),
            R.begin (),
            R.end   (),
            std::inserter
                (
                    res,
                    res.begin()
                )
        );
 
    L.swap( res );
    return  L;
}
/////////////////////////////////////////////////////////////////////////////////////////
class  T_queen
{
    T_cell      point_;
    T_cells     attacked_cells_;
    //-----------------------------------------------------------------------------------
public:
    //-----------------------------------------------------------------------------------
    T_queen
        (
            T_cell          cell,
            const T_cells&  board,
            T_cells&        free_cells
        )
        :
        point_      ( cell ),
 
        attacked_cells_ 
            ( 
                get_attacked_cells  
                    ( 
                        cell,
                        board
                    )
            )
    {
        free_cells -= attacked_cells_;
    }
    //-----------------------------------------------------------------------------------
    T_cell  get_point()         const
    {
        return  point_;
    }
    //-----------------------------------------------------------------------------------
    T_cells  attacked_cells()   const
    {
        return  attacked_cells_;
    }
    //-----------------------------------------------------------------------------------
private:
    //-----------------------------------------------------------------------------------    
    struct  T_cell_is_not_attacked_from
    {
        T_cell  point_;
        //-------------------------------------------------------------------------------
        T_cell_is_not_attacked_from(T_cell  point)
            :
            point_( point )
        {}
        //-------------------------------------------------------------------------------
        bool  operator() (T_cell  cell)
        {
            int     H   =   cell.horiz  ()  -   point_.horiz    ();
            int     V   =   cell.vert   ()  -   point_.vert     ();
 
            return      H * V   !=  0
                    &&  abs(H)  !=  abs(V);
        }
    };   
    //-----------------------------------------------------------------------------------
    static T_cells  get_attacked_cells
        (
            T_cell          point,
            const T_cells&  board
        )
    {
        T_cells  res;
 
        std::remove_copy_if
            (
                board.begin (),
                board.end   (),
                std::inserter
                    (
                        res,
                        res.begin()
                    ),
                T_cell_is_not_attacked_from(point)
            );
        return  res;
    }
    //-----------------------------------------------------------------------------------    
};
/////////////////////////////////////////////////////////////////////////////////////////
typedef std::vector<T_queen>    T_queens;
/////////////////////////////////////////////////////////////////////////////////////////
T_cells  make_board()
{
    T_cells  res;
    for(T_cell::T_coord  i = T_cell::MIN_COORD; i <= T_cell::MAX_COORD; ++i)
    {
        for(T_cell::T_coord  j = T_cell::MIN_COORD; j <= T_cell::MAX_COORD; ++j)
        {
            res.insert
                ( 
                    T_cell(i, j)
                );
        }
    }
    return  res;
}
/////////////////////////////////////////////////////////////////////////////////////////
T_cells  get_position(const T_queens&  queens)
{
    T_cells  res;
 
    std::transform
        (
            queens.begin    (),
            queens.end      (),
            std::inserter
                (
                    res,
                    res.begin()
                ),
                std::mem_fun_ref(&T_queens::value_type::get_point)
        );
 
    return  res;
}
/////////////////////////////////////////////////////////////////////////////////////////
bool  successfully_add_queen_and_recount_free_cells
    (
        T_queens&       queens,
        const T_cells&  board,
        T_cells&        free_cells,
        T_cell          prev_cell
    )
{
    T_cells::const_iterator     queen_cell_it   =   free_cells.upper_bound  ( prev_cell );
    bool                        bool_res        =   queen_cell_it != free_cells.end();
 
    if(bool_res)
    {
        queens.push_back
            ( 
                T_queen
                    ( 
                        *queen_cell_it,
                        board,
                        free_cells
                    ) 
            );    
    }
    return  bool_res;
}
/////////////////////////////////////////////////////////////////////////////////////////
struct  T_subtract_attacked_cells_from
{
    //-----------------------------------------------------------------------------------
    T_cells    board_;
    //-----------------------------------------------------------------------------------
    T_subtract_attacked_cells_from(const T_cells&    board)
        :
        board_( board )
    {}
    //-----------------------------------------------------------------------------------
    void  operator() (const T_queen&  queen)
    {
        board_     -=  queen.attacked_cells();
    }
    //-----------------------------------------------------------------------------------
    operator T_cells()
    {
        return  board_;
    }
};
/////////////////////////////////////////////////////////////////////////////////////////
void  recount_free_cells         
    (
        const T_queens&     queens,
        const T_cells&      board,
        T_cells&            free_cells
    )
{
    free_cells  =   std::for_each
                        (
                            queens.begin                    (),
                            queens.end                      (),
                            T_subtract_attacked_cells_from  ( board )
                        );
}
/////////////////////////////////////////////////////////////////////////////////////////
void  print_position(const T_cells&  position)
{
    std::for_each
        (
            position.begin      (),
            position.end        (),
            std::mem_fun_ref    (&T_cells::value_type::print_cell_and_tab)
        );
 
    std::cout << std::endl;
}
/////////////////////////////////////////////////////////////////////////////////////////
T_cells  get_position_vert_reflection( const T_cells&  position )
{
    T_cells  res;
    std::transform
        (
            position.begin  (),
            position.end    (),
            std::inserter
                (
                    res,
                    res.begin()
                ),
                std::mem_fun_ref(&T_cells::value_type::vert_reflection)
        );
 
    return  res;
}
/////////////////////////////////////////////////////////////////////////////////////////
void  position_rotate( T_cells&  position )
{
    T_cells  res;
 
    std::transform
        (
            position.begin  (),
            position.end    (),
            std::inserter
                (
                    res,
                    res.begin()
                ),
                std::mem_fun_ref(&T_cells::value_type::cell_rotate)
        );
    position.swap(res);
}
/////////////////////////////////////////////////////////////////////////////////////////
T_cells  get_min_position(T_cells  position)
{
    T_positions     res;
    T_cells         position_reflection     =   get_position_vert_reflection( position );
  
    const int       BOARD_SIDES_TOTAL   =   4;
    for(int  i = 0; i < BOARD_SIDES_TOTAL; ++i)
    {
        res.insert      ( position              );
        res.insert      ( position_reflection   );
        position_rotate ( position              );
        position_rotate ( position_reflection   );
    }
    return  *res.begin();
}
/////////////////////////////////////////////////////////////////////////////////////////
void  print_positions_of_queens_attacking_all_board_and_not_attacking_each_other(size_t  queens_total)
{    
    static const T_cells    BOARD               =   make_board();
    T_cells                 free_cells          =   BOARD;
    int                     solutions_counter   =   0;
    T_queens                queens;
    T_positions             min_positions;    
    T_cell                  prev_cell;    
 
    for( bool  forward = true; ; )
    {
        forward     =       queens.size()   <   queens_total
                        &&  successfully_add_queen_and_recount_free_cells
                                (
                                    queens,
                                    BOARD,
                                    free_cells,
                                    prev_cell
                                );
 
        prev_cell   =   queens.empty()
                            ? T_cell                    ()
                            : queens.back().get_point   ();
        
        if( !forward )
        {
            if( queens.empty() )
            {
                break;
            }
            
            queens.pop_back();
 
            recount_free_cells
                ( 
                    queens,
                    BOARD,
                    free_cells
                );
        }
 
        if( 
                free_cells.empty() 
            &&  queens.size()   ==  queens_total
          )
        {
            T_cells  min_position   =   get_min_position
                                            ( 
                                                get_position( queens ) 
                                            );
 
            if( min_positions.insert( min_position ).second )
            {
                std::cout   <<  "#"
                            <<  ++solutions_counter
                            <<  ":"
                            <<  '\t';
 
                print_position( min_position ); 
                std::cout   <<  std::endl;
            }
        }
    }//for
    std::cout   <<  "Всего "
                <<  min_positions.size()
                <<  " расстановок."
                <<  std::endl;
}
/////////////////////////////////////////////////////////////////////////////////////////
int main()
{
    std::locale::global(std::locale(""));
    size_t  queens_total    =   0;
 
    std::cout   <<  "Введите количество ферзей: ";
    std::cin    >>  queens_total;        
 
    std::cout   <<  std::endl
                <<  "Расстановки "
                <<  queens_total 
                <<  " ферзей, угрожающих каждой клетке доски, "
                <<  std::endl
                <<  "но не угрожающих друг другу (с точностью до поворотов и отражений):"
                <<  std::endl
                <<  std::endl;
 
    print_positions_of_queens_attacking_all_board_and_not_attacking_each_other(queens_total);    
}

#include <iostream>
#include <vector>
///////////////////////////////////////////////////////////////////////////////
typedef std::vector<int>   T_vec;
typedef std::vector<T_vec> T_matrix;
///////////////////////////////////////////////////////////////////////////////
using std::cin;
using std::cout;
using std::endl;
///////////////////////////////////////////////////////////////////////////////
T_matrix board;
size_t boardSize;
///////////////////////////////////////////////////////////////////////////////
void printBoard ();
bool tryToSet   (size_t);
void changeBoard(size_t, size_t, int);
///////////////////////////////////////////////////////////////////////////////
int main()
{
    cout << "Enter board size: ";
    cin  >> boardSize;
    board.resize(boardSize, T_vec(boardSize, 0));
    tryToSet(0);
    printBoard();
    return 0;
}
///////////////////////////////////////////////////////////////////////////////
void printBoard()
{
    unsigned char WHITE = 178,
                  BLACK = 176,
                  QUEEN = 5;
    for(size_t i = 0; i < boardSize; i++)
    {
        for(size_t j = 0; j < boardSize; j++)
            if(board[i][j] == -1)
                cout << QUEEN << " ";
            else if((i+j)%2)
                    cout << WHITE << WHITE;
                 else
                    cout << BLACK << BLACK;
        cout << endl;
    }
}
 
bool tryToSet(size_t i) //takes current row
{
    bool result = false;
    for(size_t j = 0; j < boardSize; j++)
    {
        if(board[i][j] == 0)
        {
            changeBoard(i, j, 1);
            if(i == boardSize-1)
                result = true;
            else if (!(result = tryToSet(i+1)))
                changeBoard(i, j, -1);
        }
        if(result)
            break;
    }
    return result;
}
 
void changeBoard(size_t row, size_t column, int value) // value: 1 for set, -1 for unset
{
    for(size_t x = 0; x < boardSize; x++)
    {
        board[row][x]    += value;
        board[x][column] += value;
        size_t foo;
        foo = column - row + x;
        if(foo >= 0 && foo < boardSize)
            board[x][foo] += value;
        
        foo = column + row - x;
        if(foo >= 0 && foo < boardSize)
            board[x][foo] += value;
    }
    if(value == 1)
        board[row][column] = -1;
    else
        board[row][column] = 0;
}