Задача о мирных ферзях

Так как верный результат мной сейчас не получен, в коллекцию задач на шахматной доске заметка пока не пойдёт, а суть проблемы состоит вот в чём:

Мирно сосуществующие армии ферзей.

Найти максимальное натуральное число m такое, что m белых и m чёрных ферзей могут сосуществовать на шахматной доске n x n, не атакуя фигур противоположного цвета.

Теоретическим решениями должна соответствовать последовательность A250000, но показанная ниже программка не находит расстановки максимально допустимого количества ферзей для некоторых размерностей доски (8, а также от 10 и выше).

Кто найдёт решение проблемы - тому конфетка, может, начинать поиск нужно иначе. Программка тестировалась в консоли Visual Studio 2019.

#include <iostream>
#include <vector>
using namespace std;

enum class Piece { empty, black, white };
typedef pair <int, int> position;

bool isAttacking (const position &queen, const position &pos) {
 return queen.first == pos.first || queen.second == pos.second || 
        abs(queen.first - pos.first) == abs(queen.second - pos.second);
}

bool place (const int m, const int n, vector<position>& pBlackQueens, vector<position>& pWhiteQueens) {
 if (m == 0) return true;
 bool placingBlack = true;
 for (int i = 0; i < n; i++) {
  for (int j = 0; j < n; j++) {
   auto pos = make_pair(i, j);
   for (auto queen : pBlackQueens) {
    if (queen == pos || !placingBlack && isAttacking(queen, pos)) goto next_step;
   }
   for (auto queen : pWhiteQueens) {
    if (queen == pos || placingBlack && isAttacking(queen, pos)) goto next_step;
   }
   if (placingBlack) {
    pBlackQueens.push_back(pos);
    placingBlack = false;
   }
   else {
    pWhiteQueens.push_back(pos);
    if (place(m - 1, n, pBlackQueens, pWhiteQueens)) {
     return true;
    }
    pBlackQueens.pop_back();
    pWhiteQueens.pop_back();
    placingBlack = true;
   }
   next_step: ; //т.к. выходим из вложенного цикла
  }
 }
 if (!placingBlack) pBlackQueens.pop_back();
 return false;
}

void printBoard (int n, const vector<position> &blackQueens, const vector<position> &whiteQueens) {
 vector <Piece> board (n * n);
 fill (board.begin(), board.end(), Piece::empty);
 for (auto& queen : blackQueens) board[queen.first * n + queen.second] = Piece::black;
 for (auto& queen : whiteQueens) board[queen.first * n + queen.second] = Piece::white;
 for (size_t i = 0; i < board.size(); ++i) {
  if (i != 0 && i % n == 0) cout << endl;
  switch (board[i]) {
  case Piece::black:
   cout << "B ";
  break;
  case Piece::white:
   cout << "W ";
  break;
  case Piece::empty:
  default:
   int j = i / n;
   int k = i - j * n;
   if (j % 2 == k % 2) {
    cout << "x ";
   }
   else {
    cout << "* ";
   }
   break;
  }
 }
 cout << endl << endl;
}

int main() {
 vector <position> nms = { //какие доски проверить: размерность, количество ферзей
   {1,0}, {2,0}, {3,1}, {4,2}, {5,4}, {6,5}, {7,7},
   {8,9}, {9, 12}, {10,14}, {11,17}, {12,21}
 };
 for (auto nm : nms) {
  cout << nm.second << " black and " << nm.second << " white queens on a " << nm.first << " x " << nm.first << " board:\n";
  vector<position> blackQueens, whiteQueens;
  if (place(nm.second, nm.first, blackQueens, whiteQueens)) {
   printBoard(nm.first, blackQueens, whiteQueens);
  }
  else {
   cout << "No solution found" << endl << endl;
  }
 }
 cin.get();
 return 0;
}

19.01.2020, 14:41 [1436 просмотров]