Восемь ферзей

В этой статье поговорим об известной логической головоломке под названием "восемь ферзей". Суть задачи заключается в том, что нужно суметь расставить на шахматной доске (8 х 8) восемь ферзей так, чтобы они не находились под боем друг друга (напомню, что ферзь (королева) бьет по прямой и по диагонали). Скажу, что вариантов расстановки есть несколько, но найти их вручную не всегда легко, особенно тяжело поставить последнего ферзя. Один из вариантов расстановок ферзей смотрим ниже на рисунке 1

Рисунок 1

Для того, чтобы решить задачу о восьми ферзях, мы напишем программу на языке программирования С++, которая и будет расставлять ферзей. Предлагаю следовать такой тактике:

1. Шахматную доску представить в виде двумерного массива, размером 8 х 8.

2. Для каждой ячейки массива задать число, которое будет говорить, сколько с данной клетки ферзь может побить других клеток. Смотрим рисунок 2

Рисунок 2

Как видите, если поставить ферзя на позицию x = 2, y = 1, то под боем будет находиться 23 клетки. Такую процедуру нужно будет проделать для каждой клетки шахматной доски (двумерного массива). В итоге получим вот такую картину, показанную ниже на рисунке 3

Рисунок 3

3. После того, как приоритеты расставлены, нужно выбрать клетку с минимальным приоритетом (ту, с которой меньше бьется других клеток доски) и поставить на нее ферзя. Думаю, что тут понятно...т.к., если ставить ферзей на те клетки, с которых можно побить большее количество других клеток, то до расстановки восьми ферзей мы точно не дойдем. Продолжаем рассуждать...если клеток с минимальным приоритетом нашлось несколько (а в самом начале расстановки будет именно так), то выбирать подходящую будем случайным образом. Как это логически обоснованно организовать? Для этого мы должны сначала найти минимальный приоритет (допустим, 21 - именно оно будет самым маленьким в первой итерации - см. рисунок 3), затем сосчитать число клеток с этим приоритетом (в нашем случае с 21 этих одинаковых клеток будет аж 28), далее сгенерировать случайное число в интервале от 1 до числа одинаковых клеток (их 28) и, исходя из полученного при генерации числа, поставить ферзя на нужное место. Ту клетку, куда мы ставим ферзя, будем как-то помечать, допустим, присваивая ей значение 100. Можно брать абсолютно любое значение, только вот подбирайте так, чтобы оно не определялось как минимальное при определении приоритетов.

4. После постановки ферзя, нужно удалить побитые им клетки, пометив их каким-либо числом. Допустим, я буду помечать эти клетки для удобства числом 99.

Небольшое пояснение. Когда основной алгоритм расстановки ферзей отработает и у нас останутся на шахматной доске (двумерном массиве, эмулирующим шахматную доску) лишь ячейки с числами 100 (это ферзи) и 99 - побитые клетки, то мы выведем полученный результат на экран с условием, что если нам встречается число 100 - то рисовать ферзя (либо в консоли - снежинку, решетку и т.д.), в ином случае делать клетку просто пустой (либо в консоли для наглядности можно их помечать дефисом, точками и т.д.).

5. Далее опять все повторяется с пункта 2 по 4, пока не расставим всех ферзей, которых должно быть восемь. Тут есть еще один момент: с первой попытки, даже используя так называемый "умный" подход к реализации задачи, приведенный выше алгоритм может не расставить всех восемь ферзей. Но тут есть выход из этого положения. После расстановки мы будем проверять: получилось ли поставить всех ферзей. Если нет, то повторяем расстановку заново.

На следующем четвертом рисунке я привожу в действие описанный выше алгоритм для наглядности. Он может выдавать различные варианты расстановок, но для этого вы должны перезагрузить вашу веб-страницу (кнопка "обновить" в браузере, либо F5) и тогда результат поменяется. К сожаления, web-технологию Ajax я пока что еще не знаю, поэтому для получения новой картинки нужно перезагружать страницу.

Рисунок 4

Вот вид программы (пока что привожу лишь ее основную часть - функцию main() ), реализующей алгоритм

const int SIZE = 8;

int main()
{
    int board[SIZE][SIZE];
    int x, y;
    int *ptrX = &x, *ptrY = &y;

    srand(time(NULL));

    //пока не расставим все 8 ферзей
    do
    {
        resetBoard(board);

        //пробуем расставить ферзей
        for(int i = 1; i <= 8; i++)
        {
            updateBoard(board);
            choiseCell(board, ptrX, ptrY);
            board[x][y] = 100;
            deleteCell(board, x, y);
        }
    }
    while(!checkQueens(board));

    printBoard(board);

    return 0;
}

Как видите, в нем реализовано то, что я говорил выше

1) Объявляем двумерный массив board, размерностью 8 х 8 ячеек - это будет наша шахматная доска. Также нам будут нужны переменные для хранения координат точек (x и y) и указатели на них (ptrX и ptrY). Для инициализации массива нулями у нас будет служить функция resetBoard().

2) Матрица объявлена, инициализирована. Теперь смотрим внутрь цикла for, который и будет у нас выполнять расстановку восьми ферзей. Как мы говорили выше в пункте 2, нам нужно задать для каждой ячейки матрицы свой приоритет. Это будет делать функция updateBoard().

3) Приоритеты расставлены. Теперь, как мы говорили в пункте 3, нам нужно выбрать клетку с минимальным приоритетом. Если их будет несколько, то выбор сделать случайным образом. Выполняет это все функция choiseCell(), которая принимает в качестве аргументов матрицу и указатели на координаты x и y. Действуя через указатели, эта функция меняет значения координат x и y в основной программе. Т.к. координаты x и y изменились (во время объявления, как видите, они не были инициированы), то можно к матрице board обращаться по индексу. Задаем для выбранных координат значение 100 (здесь у нас стоит ферзь).

4) После постановки ферзя, помечаем убитые им клетки. Выполняет это функция deleteCell().

Этот процесс повторяется ровно восемь раз, как задано в условиях цикла for. Если, как я писал выше, не получится с первой попытки расставить все восемь ферзей, то процесс расстановки обнуляется с помощью resetBoard() и цикл расстановки начинается заново. Для того, чтобы сообщить нам, расставлены ли все восемь ферзей или нет, служит функция checkQueens(), возвращающая ложь, если не получилось расставить, и истину, если расстановка удалась.

Вот, в принципе и все, что я хотел рассказать по данному алгоритму. Полную реализацию программы привожу ниже.

//Восемь ферзей

//необходимые заголовочные файлы
#include <iostream>
#include <iomanip>
#include <stdlib.h>
#include <time.h>

const int SIZE = 8;

//прототипы функций
void resetBoard(int[][SIZE]);
void updateBoard(int[][SIZE]);
int helpUpdateBoard(int[][SIZE], int, int, bool);
void choiseCell(int[][SIZE], int*, int*);
void deleteCell(int[][SIZE], int, int);
bool checkQueens(int[][SIZE]);
void printBoard(int[][SIZE]);

using namespace std;

int main()
{
    int board[SIZE][SIZE];
    int x, y;
    int *ptrX = &x, *ptrY = &y;

    srand(time(NULL));

    //пока не расставим все 8 ферзей
    do
    {
        resetBoard(board);

        //пробуем расставить ферзей
        for(int i = 1; i <= 8; i++)
        {
            updateBoard(board);
            choiseCell(board, ptrX, ptrY);
            board[x][y] = 100;
            deleteCell(board, x, y);
        }
    }
    while(!checkQueens(board));

    printBoard(board);

    return 0;
}

//проверяем, расставлены ли все ферзи или нет
bool checkQueens(int board[][SIZE])
{
    int counter = 0;

    for(int i = 0; i < SIZE; i++)
        for(int j = 0; j < SIZE; j++)
            if(board[i][j] == 100)
                counter++;

    return (counter == 8 ? true : false);
}

//обнуляем все клетки доски
void resetBoard(int board[][SIZE])
{
    for(int i = 0; i < SIZE; i++)
        for(int j = 0; j < SIZE; j++)
            board[i][j] = 0;
}

//помечаем побитые клетки
void deleteCell(int board[][SIZE], int x, int y)
{
    helpUpdateBoard(board, x, y, true);
}

//ищем подходящую клетку для постановки ферзя
void choiseCell(int board[][SIZE], int *ptrX, int *ptrY)
{
    int counter = 0, rnd;
    int min = board[0][0];

    //находим значение минимального приоритета
    for(int i = 0; i < SIZE; i++)
        for(int j = 0; j < SIZE; j++)
            if(board[i][j] < min)
                min = board[i][j];

    //узнаем сколько в матрице есть клеток в одинак.приоритетом
    for(int i = 0; i < SIZE; i++)
        for(int j = 0; j < SIZE; j++)
            if(board[i][j] == min)
                counter++;

    //генерируем случайное число
    rnd = 1 + rand() % counter;
    counter = 0;

    //выбираем одну клетку из одинаковых случайным образом
    //и запоминаем ее координаты
    for(int i = 0; i < SIZE; i++)
        for(int j = 0; j < SIZE; j++)
            if(board[i][j] == min)
                if(++counter == rnd)
                    *ptrX = i, *ptrY = j;
}

//обновляем приоритеты клеток шахматной доски
void updateBoard(int board[][SIZE])
{
    for(int i = 0; i < SIZE; i++)
        for(int j = 0; j < SIZE; j++)
            if(board[i][j] != 100 && board[i][j] != 99)
                board[i][j] = helpUpdateBoard(board, i, j, false);
}

//вспомогательная ф-ция: делаем проходы по всем направлениям
//для вычисления приоритетов клеток
int helpUpdateBoard(int board[][SIZE], int x ,int y, bool label)
{
    int counter = 0, xTemp = x, yTemp = y;

    //по диагонали вправо вниз
    while(xTemp < (SIZE - 1) && yTemp < (SIZE - 1))
    {
        xTemp++;
        yTemp++;

        if(label)
            board[xTemp][yTemp] = 99;

        //если клетка не занята ферзем и не побита
        if(board[xTemp][yTemp] != 100 && board[xTemp][yTemp] != 99)
            counter++;
    }

    xTemp = x, yTemp = y;
    //по диагонали влево вверх
    while(xTemp > 0 && yTemp > 0)
    {
        xTemp--;
        yTemp--;

        if(label)
            board[xTemp][yTemp] = 99;

        if(board[xTemp][yTemp] != 100 && board[xTemp][yTemp] != 99)
            counter++;
    }

    xTemp = x, yTemp = y;
    //по диагонали вправо вверх
    while(xTemp < (SIZE - 1) && yTemp > 0)
    {
        xTemp++;
        yTemp--;

        if(label)
            board[xTemp][yTemp] = 99;

        if(board[xTemp][yTemp] != 100 && board[xTemp][yTemp] != 99)
            counter++;
    }

    xTemp = x, yTemp = y;
    //по диагонали влево вниз
    while(xTemp > 0 && yTemp < (SIZE - 1))
    {
        xTemp--;
        yTemp++;

        if(label)
            board[xTemp][yTemp] = 99;

        if(board[xTemp][yTemp] != 100 && board[xTemp][yTemp] != 99)
            counter++;
    }

    xTemp = x, yTemp = y;
    //вверх
    while(yTemp > 0)
    {
        yTemp--;

        if(label)
            board[xTemp][yTemp] = 99;

        if(board[xTemp][yTemp] != 100 && board[xTemp][yTemp] != 99)
            counter++;
    }

    xTemp = x, yTemp = y;
    //вниз
    while(yTemp < (SIZE - 1))
    {
        yTemp++;

        if(label)
            board[xTemp][yTemp] = 99;

        if(board[xTemp][yTemp] != 100 && board[xTemp][yTemp] != 99)
            counter++;
    }

    xTemp = x, yTemp = y;
    //вправо
    while(xTemp < (SIZE - 1))
    {
        xTemp++;

        if(label)
            board[xTemp][yTemp] = 99;

        if(board[xTemp][yTemp] != 100 && board[xTemp][yTemp] != 99)
            counter++;
    }

    xTemp = x, yTemp = y;
    //влево
    while(xTemp > 0)
    {
        xTemp--;

        if(label)
            board[xTemp][yTemp] = 99;

        if(board[xTemp][yTemp] != 100 && board[xTemp][yTemp] != 99)
            counter++;
    }

    return counter;
}

//печать результатов
void printBoard(int board[][SIZE])
{
    for(int i = 0; i < SIZE; i++)
    {
        cout << endl;

        for(int j = 0; j < SIZE; j++)
            cout << setw(4) << (board[i][j] == 100 ? '#' : '.');

        cout << endl;
    }
}

Результат работы программы

Программа

P.S. Также на сайте вы можете найти иную реализацию алгоритма "Восемь ферзей", реализованную программистом Алексеем и выложенную на форуме, за что ему большое спасибо.