Задача о восьми ферзях

Постановка задачи. Как на шахматной доске расположить восемь ферзей таким образом, чтобы никакие два из них не «били» друг друга.

Ответ: 92 расстановки.

Решение.

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

Рис. 4. Шахматная доска

Можно заметить, что два ферзя, которые находятся в клетках с координатами и , будут «бить» друг друга, если выполняется хотя бы одно из следующих равенств:

1. , то есть ферзи находятся на одной вертикали;

2. , то есть ферзи находятся на одной горизонтали;

3. , то есть ферзи находятся на одной диагонали, идущей снизу вверх слева направо (для данной нумерации клеток);

4. , то есть ферзи находятся на одной диагонали, идущей сверху вниз слева направо (для данной нумерации клеток).

Рассмотрим реализацию решения данной задачи с использованием параллельного программирования на языке С++.

Для начала рассмотрим решение этой задачи с использованием только одного потока. Ниже приведен листинг программы.

#include <stdio.h>

#include <windows.h>

#define S 8

int a[S];

int N = 0;

void print()

{

for(int i = 0; i< S; i++) printf("%d",a[i]);

printf("\n");

N++;

}

int test(int p)

{

for(int i = 0; i < p; i++)

{

if(a[i] == a[p]) return 0;

if(a[i]-a[p] == p-i || a[p]-a[i] == p-i) return 0;

}

return 1;

}

void f(int p)

{

if(p == S)

{

print();

}

else

{

for(int i = 0; i < S; i++)

{

a[p] = i;

if(test(p)) f(p+1);

}

}

}

int main(void)

{

LARGE_INTEGER time_start, time_finish;

QueryPerformanceCounter(&time_start);

f(0);

QueryPerformanceCounter(&time_finish);

printf("S = %d\nVsego: %d\nThreads: sinlge\nTime:\n%lu\t%lu\t%lu\n%lu\t%lu\t%lu\n",S,N,

(long)time_finish.HighPart,(long)time_finish.LowPart, (long)time_finish.QuadPart,(long)time_start.HighPart,

(long)time_start.LowPart,(long)time_start.QuadPart);

fgetc(stdin);

return 0;

}

Как видно из листинга, размер шахматной доски в общем случае не фиксирован и может изменяться константой S. Затем создается массив , в который будут записыватся значения координаты по вертикали. Например, значениям массива {7, 3, 0, 2, 5, 1, 6, 4} будет соответствовать следующее расположение ферзей на шахматной доске:

Рис. 5. Вариант размещения 8 ферзей на шахматной доске

Также объявляется переменная N для подсчета количества найденных расстановок ферзей на шахматной доске. В программе используются 3 функции: int main (void) – основная функция, в которой измеряется время нахождения всех перестановок и вызывается функция void f (int p) в которой последовательно заполняется массив a [ S ]. При каждом новом внесении значения в массив вызывается функция int test (int p), проверяющая возможность постановки нового ферзя. Если удается заполнить все элементы массива (то есть S раз функция test вернет 1), то текущая перестановка считается успешной и вызывается функия void print (), которая выводит её на консоль и увеличивает счетчик найденных перестановок на единицу.

Для каждого нового ферзя фунция int test (int p) проверяет не стоят ли ферзи на одной гоизонтали:

for(int i = 0; i < p; i++)

{

if(a[i] == a[p]) return 0;

}

Расстановка ферзей на одной вертикали невозможна в силу задания структуры массива a [ S ].

Затем проверяется не стоят ли ферзи на одной диагонали:

for(int i = 0; i < p; i++)

{

if(a[i]-a[p] == p-i || a[p]-a[i] == p-i) return 0;

}

Рассмотим конкретный пример работы функции int test (int p). Пусть значения первых двух элементов массива а равны соответственно их координаты на шахматной доске – (8, 1), (4, 2). При постановке третьего ферзя функция void f (int p) последовательно ставит его на горизонтали третьей вертикали снизу вверх. Тогда фунция test работает с массивом . В цикле значение сравнивается с предыдущими значениями массива. Как уже изложено выше равенство будет означать, что два ферзя «бьют» друг друга, так как стоят на одной горизонтали. Для проверки диагоналей используется диагональ квадрата, построенного в относительных координатах. Это означает, проверку равенства , где g изменяется от 0 до 2.

Рассмотрим более подробно функцию f:

void f(int p)

{

if(p == S)

{

print();

}

else

{

for(int i = 0; i < S; i++)

{

a[p] = i;

if(test(p)) f(p+1);

}

}

}

Смысл её работы заключается в следующем. Сначала на первую вертикаль доски выставляется один ферзь (будем считать, что заполение ведется снизу вверх слева направо). Относительно него будут ставиться ферзи на другие вертикали с B до H – рис. 6.

Рис. 6. Размещение первого ферзя

Затем предпринимается попытка поставить второго ферзя на вертикаль B, так чтобы ферзи не мешали друг другу. Сначала ферзь ставится на первую горизонталь, но вызов функции test показывает, то это невозможно. Тогда он передвигается на вторую горизонталь. Здесь также оказывается, что ферзи мешают друг другу. Ферзь передвигается на третью горизонталь. Функция test показывает, что данное положение фигур допустимо. Таким образом функия test позволяет избежать проверки всех возможных расстановок фигур, исключая целые блоки, как показано на рис. 7.

Рис. 7. Попытка размещения второго ферзя

Рис. 8. Первая удачная попытка размещения второго ферзя

Аналогичным образом, с помощью функии test ведется расстановка всех последующих ферзей. Когда ферзь оказывается в позиции, в которой можно выставить следующего (рис. 8), постановка осуществляется на первую диагональ.

Теперь рассмотрим выставление последней фигуры. Когда ферзь «дойдет» до последней горизонтали, он уберется с доски, а седьмой передвинется на горизонталь выше. Затем восьмой ферзь выставляется, начиная с первой горизонтали. Когда и седьмой, и восьмой ферзь оказываются на последней горизонтали, они убираются с доски, а шестой ферзь передвигается на горизонталь выше и седьмой ферзь начинает выставлятся сначала. Таким образом осуществляется проверка возможных размещений в «блоках» правее рассматриваемой вертикали для каждого из восьми ферзей данной вертикали, и тем самым реализуется принцип рекурсии.

Программа перебирает варианты расстановки 8 ферзей на шахматную доску и функцией int test (int p) выбирает 92 расстановки, в которых ферзи не «бьют» друг друга, что соответствует общеизвестному решению этой задачи.

Измерение времени нахождения всех перестановок осуществляется с помощью функции QueryPerformanceCounter() — «тай­мер вы­со­ко­го раз­ре­ше­ния». Он вве­дён фир­мой Microsoft, что­бы раз и на­все­гда по­ста­вить точ­ку в про­бле­мах из­ме­ре­ния вре­ме­ни. Ча­сто­та это­го тай­ме­ра (1 МГц и вы­ше) не ме­ня­ет­ся во вре­мя ра­бо­ты си­сте­мы. Ча­сто­ту мож­но узнать с по­мо­щью функ­ции Query­Per­for­mance­Fre­quen­cy(). Для каж­дой си­сте­мы Windows са­ма опре­де­ля­ет, с по­мо­щью ка­ких устройств реа­ли­зо­вать этот тай­мер.

Теперь рассмотрим решение задачи о 8 ферзях с использованием потоков.

Изначально функция main инициализирует семафор и буфер задач, который является критической областью. Затем создаются и по очереди запускаются 2 потока. Для их обозначения создается массив индексов потоков:

for(int i = 0; i < M; i++) id[i] = i;

Потоки создаются следующим образом:

for(int i = 0; i < M; i++)

Processes[i] = CreateThread(NULL,0,Run,&id[i],0,NULL);

Запись CreateThread(NULL,0,Run,&i,0,NULL) оказалась бы неверна, поскольку несмотря на то, что значение переменной i в цикле меняется, её адрес остается неизменным. В массиве же у каждого элемента свой адрес, который передается как параметр при создании нового потока.

Каждый поток описывается функцией Run, в которой реализована логика обращения к буферу задач buffer через семафор hBufferFull для получения новой задачи. В этой функции Run выполняется проверка наличия задания в буфере. При отсутствии задания происходит ожидание поступления новых заданий. Затем идет обращение к семафору (вход в критическую секцию), получение задание, копирование его в собственный буфер (рабочую область), выход из критической секции, непосредственное решение полученной задачи. Чтобы все потоки не были заблокированы в ожидании новых заданий в конце работы (когда все задания выполнены), вводится переменная Finish.

Для генерации задач используется функция f. Задачей является рекуррентная расстановка ферзей в блоки, находящиеся справа от рассматриваемой вертикали p, с целью перебора всех возможных ситуаций и нахождения решения задачи о 8 ферзях для текущей расстановки p ферзей. Её логика аналогична логике функции f для одного потока, с той лишь разницей, что если в буфере задач есть свободное место, то задача передается в него. Если места нет, то происходит переход не следующую итерацию рекуррентного алгоритма.

Логика функции test (проверки «удовлетворяет ли новый поставленный ферзь условию задачи?»: пересечений по горизонтали и диагоналям) рассмотрена в задаче о 8 ферзях для одного потока.

При нахождении расстановки 8 ферзей «не бьющих» друг друга вызывается функция print, которая приостанавливает работу потока для получения его id и вывода на консоль полученной расстановки ферзей.

Программная реализация на языке С++.

Подключив стандартные библиотеки,

#include <stdio.h>

#include <windows.h>

#include <tchar.h>

создадим 4 константы:

- определяющую размер игрового поля и, соответственно, количество ферзей (изменяя данную константу можно получить решение задачи и для другого размера, например, при s = 12, 12 ферзей расположатся на поле размером 12 x 12);

#define S 8

- определяющую число потоков, создаваемых для решения данной задачи;

#define M 2

- определяющую количество милисекунд для входа в критическую область;

#define TIME 2

- вспомогательную константу, отвечающую за вывод информации о состояниии процессов (если объявление данной константы закомментировано, то код, отвечающий за этот вывод, заключенный между директивами препроцессора #ifdef и #endif, выполняться не будет, так как он вообще не будет компилироваться).

#define _DEBUG_

Далее объявим и определим структуру sField

typedef struct{

int field[S];

int p;

} sField;

int id[M];

sField buffer[M];

int buf_size;

sField work[M];

HANDLE hMutex,

hBufferFull,

hMutexOut;

HANDLE Processes[M];

int Finish = 0;

int N = 0; // количество найденных комбинаций

Функция вывода на консоль одного полученного частного решения задачи и id потока, закончившего выполение этого задания:

void print(int *a)

{

WaitForSingleObject(hMutexOut,INFINITE); // входим к критическую секцию

#ifdef _DEBUG_

printf("Id%d: ",GetCurrentThreadId());

for(int i = 0; i< S; i++) printf("%d",a[i]);

printf("\n");

#endif

N++;

ReleaseSemaphore(hMutexOut,1,NULL);

}

Функция проверки возможности постановки нового ферзя p относительно уже расставленных (p – 1) ферзей:

int test(int p,int *a)

{

for(int i = 0; i < p; i++)

{

if(a[i] == a[p]) return 0;

if(a[i]-a[p] == p-i || a[p]-a[i] == p-i) return 0;

}

return 1;

}

Функция генерации новой задачи и помещения её в буфер задач, реализующая рекурентный алгоритм:

void f(int p, int *a)

{

int contin;

if(p == S) print(a);

else

{

for(int i = 0; i < S; i++)

{

a[p] = i;

if(test(p,a))

{

contin = 1;

if(p<2)

if(WaitForSingleObject(hMutex,0)==WAIT_OBJECT_0)

{// если не нужно долго ждать входа в критическую секцию

if(buf_size < M)// и если есть место в буфере, отдаем задание кому-нибудь

{

for(int i = 0; i < S; i++)

buffer[buf_size].field[i] = a[i];

buffer[buf_size].p = p+1;

buf_size++;

ReleaseSemaphore(hBufferFull,1,NULL);

#ifdef _DEBUG_

printf("Id %d out: %d, %d%d%d%d%d%d%d%d the [%d]-th buf\n",GetCurrentThreadId(),p+1,a[0],a[1],a[2],a[3],a[4],a[5],a[6],a[7],buf_size-1);

#endif

contin = 0;

}

ReleaseSemaphore(hMutex,1,NULL);

}

if(contin) f(p+1,a);

}

}

}

if(p==0) Finish = 1;

}

Функция, описывающая работу потока:

DWORD WINAPI Run(LPVOID lpParam)

{

int pnum = *((int*)lpParam); // номер процесса

while(Finish == 0 || buf_size > 0)

{

if(WaitForSingleObject(hBufferFull,TIME)==WAIT_OBJECT_0)

{

// дожидаемся появления в буфере (нового) задания

WaitForSingleObject(hMutex,INFINITE); // входим в критическую секцию

// копируем задание из буфера в свою рабочую область

buf_size--;

for(int i=0; i<S; i++)

{

work[pnum].field[i] = buffer[buf_size].field[i];

}

work[pnum].p = buffer[buf_size].p;

#ifdef _DEBUG_

printf("Id %d get %d, %d%d%d%d%d%d%d%d the [%d]-th buf\n", GetCurrentThreadId(),work[pnum].p,work[pnum].field[0],work[pnum].field[1],work[pnum].field[2],work[pnum].field[3], work[pnum].field[4],work[pnum].field[5],work[pnum].field[6],work[pnum].field[7],buf_size);

#endif

ReleaseSemaphore(hMutex,1,NULL);// выходим из критической секции

// запускаем решение задачи с этого места

f(work[pnum].p, work[pnum].field);

}

}

return 0;

}

int main()

{

LARGE_INTEGER time_start, time_finish;

QueryPerformanceCounter(&time_start);

hMutex = CreateSemaphore(NULL, 1, 1,NULL);

hMutexOut = CreateSemaphore(NULL, 1, 1,NULL);

hBufferFull = CreateSemaphore(NULL, 0, M, NULL);

buffer[0].p = 0;

buf_size = 1;

for(int i = 0; i < M; i++) id[i] = i;

ReleaseSemaphore(hBufferFull,1,NULL);

for(int i = 0; i < M; i++)

Processes[i] = CreateThread(NULL,0,Run,&id[i],0,NULL);

WaitForMultipleObjects(M,Processes,TRUE,INFINITE);

QueryPerformanceCounter(&time_finish);

printf("S = %d\nVsego: %d\nThreads: %d\nTime:\n%lu\t%lu\t%lu\n%lu\t%lu\t%lu\n",S,N,M, (long)time_finish.HighPart,(long)time_finish.LowPart,(long)time_finish.QuadPart, (long)time_start.HighPart,(long)time_start.LowPart,(long)time_start.QuadPart);

fgetc(stdin);

return 0;

}

Алгоритм решения задачи о 8 ферзях с несколькими потоками приводит к тому же результату, что и алгоритм с одним потоком.

ПРИЛОЖЕНИЕ 1

Функция CreateThread создает поток, который выполняется в пределах виртуального адресного пространства вызывающего процесса. Чтобы создать поток, который запускается в виртуальном адресном пространстве другого процесса, используется функция CreateRemoteThread.

Синтаксис

HANDLE CreateThread( LPSECURITY_ATTRIBUTES lpThreadAttributes, // дескриптор защиты SIZE_T dwStackSize, // начальный размер стека LPTHREAD_START_ROUTINE lpStartAddress, // функция потока LPVOID lpParameter, // параметр потока DWORD dwCreationFlags, // опции создания LPDWORD lpThreadId // идентификатор потока );

Параметры

Дата добавления: 2015-11-28