Шахматы. Каждый ферзь бьет ровного одного ферзя

/*
Описание:
Промежуточные данные:
    1. int x[8] - координаты расположения ферзей. Номер вертикали определяется
        индексом элемента массива, номер горизонтали - его значением;
        Например, выражение x[3] = 5 означает, что на пересечении 4-й вертикали и
        6-й горизонтали расположен ферзь (массивы в C++ индексируются с нуля!).
    2. bool a[8] - массив признаков безопасности горизонталей шахматной доски
        (true - горизонталь безопасна, false - горизонталь находится под ударом
        одного или нескольких ферзей);
    3. bool b[15] - массив признаков безопасности диагоналей "справа сверху влево
        вниз" шахматной доски(true - диагональ безопасна, false - диагональ
        находится под ударом). Номер такой диагонали равен сумме координат занятой
        ферзём клетки;
    4. bool c[15] - массив признаков безопасности диагоналей "слева снизу вправо
        вверх" шахматной доски(true - диагональ безопасна, false - диагональ
        находится под ударом). Номер такой диагонали равен разности координат
        занятой ферзём клетки плюс 7
    5. int st_sol_numb - начальный номер решения для вывода на экран.*/
#include <stdio.h>
#include <clocale>
#include <conio.h>
#define _CRT_SECURE_NO_DEPRECATE 0
#define _CRT_SECURE_NO_WARNINGS 0
int  x[8];
bool l[8],a[8], b[15], c[15];
 
//функция печати расположения ферзей на доске
void PrintChessBoard();
//функция установки ферзя
void TryInstallQueen(int i);
 
int main(){
    setlocale(LC_ALL, "Russian");
    for (int i = 0; i < 8; i++){
        a[i] = true;
        l[i] = true;
    }
    for (int i = 0; i < 15; i++){
        b[i] = true;
        c[i] = true;
    }
 
    TryInstallQueen(0);
 
    return 0;
}
 
/*ФУНКЦИЯ ПЕЧАТИ РАСПОЛОЖЕНИЯ ФЕРЗЕЙ НА ШАХМАТНОЙ ДОСКЕ
Входные данные: отсутствуют.
Возвращаемое значение: отсутствует
Локальные переменные:
    1. int i - счётчик горизонталей;
    2. int j - счётчик вертикалей;
    3. static int solution_numb - счётчик числа напечатанных решений. 
        Статическая переменная, сохраняющая своё значение после выхода из функции;*/
void PrintChessBoard(){
    static int solution_numb = 1;
 
    printf("\n РЕШЕНИЕ №%d\n", solution_numb++);
    for (int i = 0; i < 8; i++){
        if (i == 0)
            printf("   A B C D E F G H ");
        printf("\n  -----------------\n%d |", i + 1);
 
        for (int j = 0; j < 8; j++)
            if (i == x[j])
                printf("Q|");
            else
                printf(" |");
 
        if (i == 7)
            printf("\n  -----------------\n\n");
    }//for i
    return;
}
 
 
/*ФУНКЦИЯ УСТАНОВКИ ФЕРЗЯ
Входные данные: 
1. int i номер вертикали, в которую необходимо установить ферзя
Возвращаемое значение: отсутствует
Локальные переменные:*/
void TryInstallQueen(int i)
{   {int m=i+1;
        l[i] = true;
    for (int j1 = 0; (j1 < 8); j1++){
    for (int j2 = 2; (j2 < 8); j2++){
        if ((a[j1] && b[i + j1] && c[i - j1 + 7]) & (a[j2] && b[i + j2] && c[i - j2 + 7])){
            x[i] = j1;
            a[j1] = false;
            b[i+ j1] = false;
            c[i - j1 + 7] = false;
            x[i] = j2;
            b[i+ j2] = false;
            c[i - j2 + 7] = false;
            l[i] = false;
 
 
            if (i < 7)
                TryInstallQueen(i+1);
            else
                PrintChessBoard();
 
            a[j1] = true;
            b[i + j1] = true;
            c[i - j1 + 7] = true;
            b[i + j2] = true;
            c[i - j2 + 7] = true;
            /*if  (((a[j1] && b[i + j1] && c[i - j1 + 7]) == (a[j1] && b[m + j1] && c[m - j1 + 7])) || 
            ((a[j1] && b[i + j1] && c[i - j1 + 7]) == (a[j1] && b[m + j1] && c[m - j1 + 7]))) {
 
                l[i] = false;
            }*/
        }//if (a[j] && b[i + j] && c[i - j + 7]){
    }//for j
} 
 
}
    return;
    getch();
}

/////////////////////////////////////////////////////////////////////////////////////////
//Расставить на шахматной доске максимальное число ферзей так, чтобы каждый нападал 
//ровно на одного ферзя.
/////////////////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <complex>
#include <conio.h>
#include <functional>
#include <iostream>
#include <vector>
/////////////////////////////////////////////////////////////////////////////////////////
int     const   BOARD_SIZE  =   8;
int     const   MAX_COORD   =   BOARD_SIZE - 1;
/////////////////////////////////////////////////////////////////////////////////////////
class  T_queen
{
    int     x_;
    int     y_;
    int     attack_counter_;
    //-----------------------------------------------------------------------------------
public:
    //-----------------------------------------------------------------------------------
    T_queen
        (
            int     x   =   0,
            int     y   =   0
        )
        :
        x_                  ( x ),
        y_                  ( y ),
        attack_counter_     ()
    {}
    //-----------------------------------------------------------------------------------
    void  print()                               const
    {
        std::cout   <<  std::complex<int>
                            (
                                x_ + 1,
                                y_ + 1
                            );
    }
    //-----------------------------------------------------------------------------------
    void  clear_attack_counter()
    {
        attack_counter_  =   0;
    }
    //-----------------------------------------------------------------------------------
    T_queen  get_queen_with_next_pos()          const
    {
        T_queen     queen( *this );
        queen.inc_pos();
        return  queen;
    }
    //-----------------------------------------------------------------------------------
    bool  is_max_pos()                          const
    {
        return      x_  ==  MAX_COORD
                &&  y_  ==  MAX_COORD;
    }
    //-----------------------------------------------------------------------------------
    void  inc_pos()
    {
        if( x_ < MAX_COORD )
        {
            ++x_;
        }
        else if( y_ < MAX_COORD )
        {
            x_  =   0;
            ++y_;
        }
    }
    //-----------------------------------------------------------------------------------
    void  check_attack( T_queen  &   queen )
    {
        int     X_abs_dist  =   abs( x_ - queen.x_ );
        int     Y_abs_dist  =   abs( y_ - queen.y_ );
 
        bool    is_attack   =           ( X_abs_dist - Y_abs_dist ) 
                                    *   X_abs_dist 
                                    *   Y_abs_dist
                                ==  0;
 
        if( is_attack )
        {
            inc_attack_counter          ();
            queen.inc_attack_counter    ();
        }
    }
    //-----------------------------------------------------------------------------------
    void  inc_attack_counter()
    {
        ++attack_counter_;
    }
    //-----------------------------------------------------------------------------------
    operator int()          const
    {
        return  attack_counter_;
    }
    //-----------------------------------------------------------------------------------
};
/////////////////////////////////////////////////////////////////////////////////////////
typedef std::vector< T_queen    >  T_position;
typedef std::vector< T_position >  T_positions;
/////////////////////////////////////////////////////////////////////////////////////////
void  clear_all_attack_counters( T_position   &   position )
{
    std::for_each
        (
            position.begin(),
            position.end(),
            std::mem_fun_ref( &T_queen::clear_attack_counter )
        );
}
/////////////////////////////////////////////////////////////////////////////////////////
void  count_attacks( T_position   &   position )
{
    for( size_t  i = 0; i < position.size(); ++i )
    {
        for( size_t  j = i + 1; j < position.size(); ++j )
        {
            position[i].check_attack( position[j] );
        }//for
    }//for
}
/////////////////////////////////////////////////////////////////////////////////////////
int  max_attack_counter( T_position  const   &   position )
{
    return  *std::max_element
                (
                    position.begin  (),
                    position.end    ()
                );
}
/////////////////////////////////////////////////////////////////////////////////////////
bool  position_is_bad( T_position   &   position )
{
    clear_all_attack_counters    ( position );
    count_attacks                ( position );
    return  max_attack_counter   ( position )    >   1;
}
/////////////////////////////////////////////////////////////////////////////////////////
int  min_attack_counter( T_position  const   &   position )
{
    return  *std::min_element
                (
                    position.begin  (),
                    position.end    ()
                );
}
/////////////////////////////////////////////////////////////////////////////////////////
bool  position_is_good( T_position  &   position )
{
    clear_all_attack_counters    ( position );
    count_attacks                ( position );
 
    return      min_attack_counter( position )  ==  1
            &&  max_attack_counter( position )  ==  1;
}
/////////////////////////////////////////////////////////////////////////////////////////
void  go_to_next_not_bad_position( T_position  &   position )
{
    if  (
            position.back().is_max_pos()
        )
    {
        position.pop_back();
 
        if  (
                position.empty()
            )
        {
            return;
        }
        else
        {
            position.back().inc_pos();
        }//else
    }
    else
    {
        position.push_back
            (
                position.back().get_queen_with_next_pos()
            );
    }
 
    while   (
                position_is_bad( position )
            )
    {
        if  (
                position.back().is_max_pos()
            )
        {
            go_to_next_not_bad_position( position );
        }
        else
        {
            position.back().inc_pos();
        }
    }//while
}
/////////////////////////////////////////////////////////////////////////////////////////
void  print_queens_position( T_position  const   &   position )
{
    std::for_each
        (
            position.begin      (),
            position.end        (),
            std::mem_fun_ref    ( &T_queen::print )
        );
}
/////////////////////////////////////////////////////////////////////////////////////////
void  find_and_print_good_positions( T_position   &   good_position_with_max_size )
{
    size_t      max_good_position_size   =   0;
 
 
    T_position  position
                    (
                        1,
                        T_queen()
                    );
 
 
    while   (
                !position.empty()
            )
    {
        if  (
                    position_is_good    ( position )
                &&      position.size   ()
                    >=  max_good_position_size
            )
        {
            good_position_with_max_size     =   position;
            max_good_position_size          =   position.size();
            print_queens_position( position );
            std::cout   <<  std::endl;
        }//if
 
        go_to_next_not_bad_position( position );
    }//whle
}
/////////////////////////////////////////////////////////////////////////////////////////
int  main()
{
    std::locale::global(std::locale(""));
    T_position  position;
    find_and_print_good_positions( position );
}

/////////////////////////////////////////////////////////////////////////////////////////
//Расставить на шахматной доске максимальное число ферзей так, чтобы каждый нападал 
//ровно на одного ферзя.
/////////////////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <complex>
#include <conio.h>
#include <fstream>
#include <functional>
#include <iostream>
#include <iterator>
#include <limits>
#include <set>
#include <utility>
#include <vector>
/////////////////////////////////////////////////////////////////////////////////////////
int     const   BOARD_SIZE  =   8;
int     const   MAX_COORD   =   BOARD_SIZE - 1;
/////////////////////////////////////////////////////////////////////////////////////////
class  T_queen
{
    int     x_;
    int     y_;
    int     attack_counter_;
    //-----------------------------------------------------------------------------------
public:
    //-----------------------------------------------------------------------------------
    T_queen
        ()
        :
        x_                  (),
        y_                  (),
        attack_counter_     ()
    {}
    //-----------------------------------------------------------------------------------
    int  get_attack_counter()                   const
    {
        return  attack_counter_;
    }
    //-----------------------------------------------------------------------------------
    void  print()                               const
    {
        std::cout   <<  std::complex<int>
                            (
                                x_ + 1,
                                y_ + 1
                            );
    }
    //-----------------------------------------------------------------------------------
    void  clear_attack_counter()
    {
        attack_counter_ = 0;
    }
    //-----------------------------------------------------------------------------------
    T_queen  get_queen_with_next_pos()          const
    {
        T_queen     queen( *this );
        queen.inc_pos();
        return  queen;
    }
    //-----------------------------------------------------------------------------------
    bool  is_max_pos()                          const
    {
        return      x_  ==  MAX_COORD
                &&  y_  ==  MAX_COORD;
    }
    //-----------------------------------------------------------------------------------
    void  inc_pos()
    {
        if( x_ < MAX_COORD )
        {
            ++x_;
        }
        else if( y_ < MAX_COORD )
        {
            x_ = 0;
            ++y_;
        }
    }
    //-----------------------------------------------------------------------------------
    void  count_attack( T_queen  &   queen )
    {
        int     X_abs_dist  =   abs( x_ - queen.x_ );
        int     Y_abs_dist  =   abs( y_ - queen.y_ );
 
        bool    is_attack   =           ( X_abs_dist - Y_abs_dist ) 
                                    *   X_abs_dist 
                                    *   Y_abs_dist
                                ==  0;
 
        if( is_attack )
        {
            ++attack_counter_;
            ++queen.attack_counter_;
        }//if
    }
    //-----------------------------------------------------------------------------------
    bool  operator< ( T_queen   const   &   queen )     const
    {
        return      std::make_pair
                        (
                            x_,
                            y_
                        )
 
                <   std::make_pair
                        (
                            queen.x_,
                            queen.y_
                        );
    }
    //-----------------------------------------------------------------------------------
    void  rotate()
    {
        reflect     ();
        transpose   ();
    }
    //-----------------------------------------------------------------------------------
    void  reflect()
    {
        x_  =   MAX_COORD - x_;
    }
    //-----------------------------------------------------------------------------------
private:
    //-----------------------------------------------------------------------------------
    void  transpose()
    {
        std::swap( x_, y_ );
    }
    //-----------------------------------------------------------------------------------
};
/////////////////////////////////////////////////////////////////////////////////////////
typedef std::vector < T_queen   >   T_queens;
typedef std::vector < int       >   T_attack_counters;
/////////////////////////////////////////////////////////////////////////////////////////
class  T_position
{
    //-----------------------------------------------------------------------------------
    T_queens            queens_;
    int                 min_attack_counter_;
    int                 max_attack_counter_;
    T_attack_counters   attack_counters_;
    //-----------------------------------------------------------------------------------
public:
    //-----------------------------------------------------------------------------------
    typedef std::set    < T_position    >   T_positions;
    //-----------------------------------------------------------------------------------
    T_position()
        :
        queens_
            (
                1,
                T_queen()
            )
    {
        clear_all_attack_counters();
    }
    //-----------------------------------------------------------------------------------
    bool  empty()                                           const
    {
        return  queens_.empty();
    }
    //-----------------------------------------------------------------------------------
    bool  is_good()
    {
        count_attack_counters();
 
        return      min_attack_counter_     ==  1
                &&  max_attack_counter_     ==  1;
    }
    //-----------------------------------------------------------------------------------
    bool  is_bad()
    {
        count_attack_counters();
 
        return  max_attack_counter_ > 1;
    }
    //-----------------------------------------------------------------------------------
    size_t  size()                                          const
    {
        return  queens_.size();
    }
    //-----------------------------------------------------------------------------------
    bool  operator< ( T_position    const   &   position )  const
    {
        return  queens_ < position.queens_;
    }
    //-----------------------------------------------------------------------------------
    T_position  get_min_position_inv_for_move()             const
    {
        T_positions     positions_inv_for_move;
        T_position      cur_position(*this);
 
        insert_all_rotated_positions_of_into
            (
                cur_position,
                positions_inv_for_move
            );
 
        reflect_and_sort_position( cur_position );
 
        insert_all_rotated_positions_of_into
            (
                cur_position,
                positions_inv_for_move
            );
 
        return  *positions_inv_for_move.begin();
    }
    //-----------------------------------------------------------------------------------
    void  print()                                           const
    {
        std::for_each
            (
                queens_.begin       (),
                queens_.end         (),
                std::mem_fun_ref    ( &T_queen::print )
            );
    }
    //-----------------------------------------------------------------------------------
    void  go_to_next_not_bad_position()
    {
        if  (
                queens_.back().is_max_pos()
            )
        {
            queens_.pop_back();
 
            if  (
                    queens_.empty()
                )
            {
                return;
            }
            else
            {
                queens_.back().inc_pos();
            }//else
        }
        else
        {
            queens_.push_back
                (
                    queens_.back().get_queen_with_next_pos()
                );
        }
 
        while   (
                    is_bad()
                )
        {
            if  (
                    queens_.back().is_max_pos()
                )
            {
                go_to_next_not_bad_position();
            }
            else
            {
                queens_.back().inc_pos();
            }
        }//while
    }
    //-----------------------------------------------------------------------------------
private:
    //-----------------------------------------------------------------------------------
    static void  insert_all_rotated_positions_of_into
        (
            T_position      &   position,
            T_positions     &   positions
        )
    {
        positions.insert            ( position );
 
        rotate_and_sort_position    ( position );
        positions.insert            ( position );
 
        rotate_and_sort_position    ( position );
        positions.insert            ( position );
 
        rotate_and_sort_position    ( position );
        positions.insert            ( position );
    }
    //-----------------------------------------------------------------------------------
    static void  rotate_and_sort_position( T_position   &   position )
    {
        std::for_each
            (
                position.queens_.begin  (),
                position.queens_.end    (),
                std::mem_fun_ref        ( &T_queen::rotate )
            );
 
        std::sort
            (
                position.queens_.begin  (),
                position.queens_.end    ()
            );
    }
    //-----------------------------------------------------------------------------------
    static void  reflect_and_sort_position( T_position  &   position )
    {
        std::for_each
            (
                position.queens_.begin  (),
                position.queens_.end    (),
                std::mem_fun_ref        ( &T_queen::reflect )
            );
 
        std::sort
            (
                position.queens_.begin  (),
                position.queens_.end    ()
            );
    }
    //-----------------------------------------------------------------------------------
    void  count_attack_counters()
    {
        clear_all_attack_counters           ();
        count_attacks                       ();
        count_min_and_max_attack_counters   ();
    }
    //-----------------------------------------------------------------------------------
    void  clear_all_attack_counters()
    {
        std::for_each
            (
                queens_.begin       (),
                queens_.end         (),
                std::mem_fun_ref    ( &T_queen::clear_attack_counter )
            );
 
        min_attack_counter_ = 0;
        max_attack_counter_ = 0;
        attack_counters_.clear();
    }
    //-----------------------------------------------------------------------------------
    void  count_attacks()
    {
        for( size_t  i = 0; i < queens_.size(); ++i )
        {
            for( size_t  j = i + 1; j < queens_.size(); ++j )
            {
                queens_[i].count_attack( queens_[j] );
            }//for
        }//for
    }
    //-----------------------------------------------------------------------------------
    void  count_min_and_max_attack_counters()
    {
        std::transform
            (
                queens_.begin       (),
                queens_.end         (),
                std::back_inserter  ( attack_counters_ ),
                std::mem_fun_ref    ( &T_queen::get_attack_counter )
            );
        
        min_attack_counter_     =   *std::min_element
                                        (
                                            attack_counters_.begin  (),
                                            attack_counters_.end    ()
                                        );
 
        max_attack_counter_     =   *std::max_element
                                        (
                                            attack_counters_.begin  (),
                                            attack_counters_.end    ()
                                        );
    }
    //-----------------------------------------------------------------------------------
};
/////////////////////////////////////////////////////////////////////////////////////////
void  find_good_positions_inv_for_move( T_position::T_positions   &   positions )
{
    size_t  max_position_size   =   0;
 
    T_position  position;
 
    while   (
                !position.empty()
            )
    {
        if  (
                    position.is_good    ()
                &&  position.size       ()  >=  max_position_size
            )
        {
            if  (
                    position.size() > max_position_size
                )
            {
                max_position_size   =   position.size();
            }
            positions.insert
                (
                    position.get_min_position_inv_for_move()
                );
 
            position.print();
            std::cout   <<  std::endl;
        }
        position.go_to_next_not_bad_position();
    }//whle
}
/////////////////////////////////////////////////////////////////////////////////////////
struct  T_print_ind_size_and_position
{
    //-----------------------------------------------------------------------------------
    int     position_counter_;
    size_t  prev_size_;
    //-----------------------------------------------------------------------------------
    T_print_ind_size_and_position()
        :
        position_counter_   (),
        prev_size_          ()
    {}
    //-----------------------------------------------------------------------------------
    void  operator() ( T_position   const   &   position )
    {
        if( position.size() != prev_size_ )
        {
            position_counter_   =   0;
            prev_size_          =   position.size();
            std::cout   <<  std::endl;
        }
 
        std::cout   <<  "#"
                    <<  ++position_counter_
                    <<  '\t'
                    <<  "size = "
                    <<  prev_size_
                    <<  '\t';
 
        position.print();
        std::cout   <<  std::endl;
    }
    //-----------------------------------------------------------------------------------
};
/////////////////////////////////////////////////////////////////////////////////////////
void  print_positions( T_position::T_positions  const   &   positions )
{
    std::for_each
        (
            positions.begin                 (),
            positions.end                   (),
            T_print_ind_size_and_position   ()
        );
}
/////////////////////////////////////////////////////////////////////////////////////////
int  main()
{
    std::locale::global(std::locale(""));
 
    T_position::T_positions     positions_inv_for_move;
    find_good_positions_inv_for_move( positions_inv_for_move );
 
    std::cout   <<  std::endl
                <<  "Позиции ферзей, каждый из которых атакует только одного "
                <<  std::endl
                <<  "(без поворотов и отражений):"
                <<  std::endl;
 
    print_positions( positions_inv_for_move );
    std::cout   <<  "finish"
                <<  std::endl;
 
    system("pause");
}