Расставить на шахматной доске 8х8, 8 ферзей так, чтобы ни один их них не мог быть атакован другим

Question

Есть задача с расстановкой на шахматной доске 8х8, 8 ферзей так, чтобы ни один из них не мог быть атакован другим. Решить нужно простой проверкой элементов доски по горизонтали, вертикали и диагоналям соответственно текущей позиции вставки на доске. 0 на доске соответствуют пустой позиции, 1-установленному ферзю.

Есть код:

#include <iostream>
using namespace std;

bool SVert(int arr[8][8], int i, int j)
{
    bool inf = true;
    for (int i = 0; i < 8; i++)
    {
        if (arr[j][i] == 1)
        {
            inf = false;
            return inf;
        }

    }
    return inf;
}

bool SHor(int arr[8][8], int i, int j)
{

    bool inf = true;
    for (int j = 0; j < 8; j++)
    {
        if (arr[i][j] == 1)
        {
            inf = false;
            return inf;
        }
    }
    return inf;
}

bool SDiag(int arr[8][8], int i, int j)
{
    bool d1 = true, d2 = true, inf = true;

    return inf;
}

void Nulification(int arr[8][8])
{
    for (int i = 0; i < 8; i++)
        for (int j = 0; j < 8; j++)
            arr[i][j] = 0;
}

void Show(int arr[8][8])
{
    for (int i = 0; i < 8; i++) 
    {
        for (int j = 0; j < 8; j++)
            cout << arr[i][j]<<" ";
        cout << endl;
    }
    cout << endl;
}

void Ferzification(int arr[8][8])
{
    int counter = 0;
    while (counter < 8)
    {
        for(int i=0;i<8;i++)
            for(int j=0; j<8; j++)
                if (SVert(arr,i,j) && (SHor(arr, i, j)) && (SDiag(arr, i, j)))
                {
                    arr[i][j] = 1;
                    counter++;
                }
    }
    cout << "Ferzificated board: " << endl;
    Show(arr);
}

int main()
{
    cout << "Our Board: " << endl;
    int arr[8][8];
    Nulification(arr);
    Show(arr);
    Ferzification(arr);
    return 0;
}

Нужно дописать функцию проверки на 2 горизонтали, которая вернет True, если на обеих горизонталях, относительно позиции вставки нет ферзя, но что-то совсем мысли в голову не идут, хотя дело элементарно.

Answer 1

А можно, я предложу способ проще? Итак, очевидно, что два ферзя на одной вертикали стоять не могут. Поэтому напишем рекурсивную функцию vert(i) установки ферзя в i-й вертикали. Которая просто поочередно проверяет все клетки, и если можно - ставит ферзя и рекурсивно вызывает vert(i+1). Если добрались до 8-й вертикали (несуществующей) - ура, все расставлено. Если где-то нельзя - идет возврат 0, и на предыдущей вертикали новая попытка.

int board[8][8]; // Доска; 1 - ферзь

int chk(int c, int r)  // Проверка, что можно ставить в клетку [r][c] 
{                      // проверка - только слева!
    for(int i = 0; i < c; ++i)
    {
        // Проверка горизонтали
        if(board[i][r]) return 0;
        // Проверка диагонали
        if (r-c+i>=0) if (board[i][r-c+i]) return 0;
        if (r+c-i< 8) if (board[i][r+c-i]) return 0;
    }
    return 1;
}

// Сама рекурсивная функция
int vert(int i) // Установка i-й вертикали
{
    if (i == 8) return 1;  // Ура, расставили
    for(int j = 0; j < 8; ++j)  // Ищем место по ввертикали
        if (chk(i,j))           // Если можно - 
        {
            board[i][j] = 1;    // ставим
            if (vert(i+1)) return 1; // получилось!
            board[i][j] = 0;    // не получилось - убираем ферзя
        }
    return 0;
}

int main(int argc, char * argv[])
{
    vert(0);
    // ... и сам вывод ...
    for(int i = 0; i< 8; ++i)
    {
        for(int j = 0; j< 8; ++j)
            cout << (board[i][j] ? '#' : '.');
        cout << endl;
    }
}

А вот как это работает - https://ideone.com/b5hwIW

БЛОГ НА HUSL

Расставить на шахматной доске 8х8, 8 ферзей так, чтобы ни один их них не мог быть атакован другим

Ответы (1 шт):