Задача расстановки ферзей на шахматной доске (N-Queens)

Размещено на http://www.allbest.ru/

Задача расстановки ферзей на шахматной доске (N-Queens)

Хорошо известной задачей в учебниках по элементарному программированию, структурам данных и алгоритмам, является задача о расстановке на шахматной доске восьми ферзей таким образом, чтобы ни один из них не находился под боем какого-либо другого из ферзей. То, что эта задача имеет решение, было продемонстрировано Карлом Фридрихом Гауссом и Францем Науком в 1850 году. На самом деле, имеется 92 различных способа расставить указанным образом ферзей на обычной шахматной доске.

Вычисление количества решений и всех их перечисление для данной задачи является одной из базовых проблем компьютерного программирования. Задача о 8 ферзях естественным образом обобщается до задачи об N ферзях, когда задается число N - размер шахматной доски, и требуется найти все способы расстановки N ферзей на этой доске, чтобы они попарно не атаковали друг друга.

Для решения этой задачи предлагались различные методы - некоторые из них можно найти в известной книге Н. Вирта “Алгоритмы + Структуры Данных = Программы”. Далее будут рассмотрены теоретические основы и реализация эффективного алгоритма решения задачи N ферзей (N-Queens), эффективность которого достигается

1) во-первых, представлением текущих расстановок ферзей на шахматной доске в виде битовых векторов и, соответственно, использованием только битовых операций,

2) во-вторых, распараллеливанием алгоритма, использующего битовые векторы.

Типичные методы решения.

Далее, при объяснении методов решения, будет использоваться пример с 8 ферзями (т.е., доской 8 x 8).

Прямая проверка. Предположим, что ферзь находится на i-ой горизонтали (строке) и на j-ой вертикали (столбце), т.е., на клетке (i,j). Тогда, клетки, которые находятся под боем данного ферзя, включают в себя: все клетки i-ой строки и все клетки j-го столбца, а также все клетки (k,l), где k -l = i - j, или k + l = i + j. Последние две группы клеток располагаются на двух диагоналях, которые находятся под боем ферзя, расположенного в клетке (i,j). шахматный ферзь алгоритм программирование

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

Эта процедура может быть представлена алгоритмически в виде последовательности проверок, при которых вначале делается попытка выставить ферзя в первой строке, затем второго ферзя - во второй строке, и т.д. Если для очередного ферзя в i-ой строке безопасная позиция отсутствует, то необходима процедура бектрекинга.

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

В усовершенствованном методе используются три массива column, left и right для хранения информации о текущей конфигурации ферзей, которые состоят из 8, 15 и 15 элементов соответственно (так как 15 = 8 + ( 8 - 1 ) при N = 8 ). Пусть column[i] равно 1, если имеется ферзь в i-ом столбце доски, и 0 - в противном случае. Если ферзь находится в позиции (i,j), то left [ i + j ] и right [ 7 - j + i ] будут равны 1, в противном случае - 0 (как обычно, мы предполагаем, что нумерация элементов массива начинается с 0).

Имея такие массивы, проверка очередной клетки на возможность размещения в ней очередного ферзя, становится прямой и эффективной. Для проверки позиции (i',j'), нам необходимо только проверить элементы column[i'], left[i'+j'] и right[7-j'+i']. Если все три элемента массивов равны 0, то позиция (i',j') является безопасной для нового ферзя. Для поиска безопасной расстановки или всех возможных таких расстановок, как обычно, используются процедуры последовательного перебора и бектрекинга.

Следующий шаг в повышении эффективности алгоритма состоит в представлении указанных массивов в виде битовых векторов. Однако, здесь имеется трудность, связанная с тем, что операция взятия элемента по индексу не является базовой и эффективно реализуемой для битовых векторов.

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

Метод решения на основе битовых векторов.

Предположим, что b₁ является битовым вектором для первого ряда доски, и j-й бит в b₁ содержит 1, представляющую размещенного в этой позиции ферзя. Тогда, (j-1)-ая позиция во втором ряду атакуется (контролируется) данным ферзем, и соответствующая отметка в битовом векторе может быть получена сдвигом вектора b₁ на один бит влево. Аналогичным образом, (j+1)-ая позиция во втором ряду, которая также контролируется данным ферзем, определяется сдвигом вправо вектора b₁ на один бит. Тогда, все контролируемые позиции во втором ряду представляются следующим битовым вектором (мы используем << и >> как обозначения операций сдвига влево и вправо, символ | обозначает побитовое ИЛИ, 1 используется для обозначения занятой или контролируемой позиции, а 0 - для свободных позиций):

Также легко найти позиции, контролируемые первым ферзем в третьей строке: достаточно сдвинуть вектор b₁ влево или вправо еще на один бит. Т.е.:

b₁ | ( b₁ > да, все контролируемые позиции во втором ряду представляются следующим битовым вектором (мы используем х попытках расставить << 2) | (b₁ >> 2)

В общем случае, позиции, контролируемые первым ферзем в k-ой строке, могут быть определены путем сдвига вектора b₁ на k - 1 битов влево и вправо и выполнением побитовой операции ИЛИ над этими тремя векторами. Ферзь в первой строке контролирует в каждой строке ниже самое большее три позиции. Отметим также, что при сдвиге биты, содержащие 1, могут выходить за пределы векторов, размер которых совпадает с размером доски. Пусть B_i[k] обозначает вектор, представляющий контролируемые позиции в строке k ферзем, находящимся в строке i ( k > i ). Тогда, очевидно, имеем:

B_i[k] = b_i | ( b_i > да, все контролируемые позиции во втором ряду представляются следующим битовым вектором (мы используем х попытках расставить << ( k - i ) ) | (b_i >> ( k - i ) )

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

Однако, существует естественный способ объединить все эти управляющие векторы в три рабочих вектора, которые будут называться left, down и right, соответственно.

Вектор down представляет столбцы, которые на текущий момент контролируются уже выставленными ферзями. Когда новый ферзь ставится на доску, соответствующий бит вектора down принимает значение 1.

Вектор left представляет контролируемые выставленными ферзями позиции влево от них по диагонали. На каждом шаге, при переходе к следующей строке вектор left сдвигается на один бит влево. Когда новый ферзь ставится на доску, в векторе left соответствующий бит должен получить значение 1. Вектор right играет ту же самую роль, что и вектор left, но только для направления вправо по диагонали.

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

B = left | down | right

На каждом шаге, новый ферзь добавляется в некоторую позицию, для которой бит в векторе B равен 0, и все три рабочих вектора модифицируются в соответствующем бите. После этого, происходит переход к следующему шагу, при котором векторы left и right сдвигаются на 1 бит влево и вправо, соответственно. Тем самым, для каждой строки поддерживается инвариант

контролируемые позиции = left | down | right,

который гарантирует корректность процедуры.

Описанный процесс поиска с бектрекингом легко реализовать в виде (последовательной) рекурсивной процедуры на языке C#:

using System;

public class NQueens {

public static int N, MASK, COUNT;

public static void Backtrack(int y, int left, int down, int right)

{

int bitmap, bit;

if (y == N) {

COUNT++;

} else {

bitmap = MASK & ~(left | down | right);

while (bitmap != 0) {

bit = -bitmap & bitmap;

bitmap ^= bit;

Backtrack(y+1, (left | bit)<<1, down | bit, (right | bit)>>1);

}

}

}

public static void Main(String[] args )

{

N = 10; /* <- N */

COUNT = 0; /* result */

MASK = (1 << N) - 1;

Backtrack(0, 0, 0, 0);

Console.WriteLine ("N=” + N + “ -> “ + COUNT);

return;

}

}

Параллельный алгоритм решения задачи N-Queens

Базовая идея параллельного алгоритма проста: для каждой возможной позиции ферзя в 1-ой строке ( а всего таких позиций N для доски размером N x N ) поиск расстановок всех остальных ферзей может проводиться независимо, а потому параллельно на нескольких процессорах. Однако, этот прямой вариант пригоден только когда N = P, где P есть число доступных процессоров.

Однако, прямой вариант легко обобщить путем независимого поиска решений для всех допустимых конфигураций ферзей на первых M ( M ? N ) строках. Очевидно, что число таких конфигураций не превышает N^M, и все они могут быть сгенерированы с помощью процедуры Backtrack, приведенной выше.

Все эти конфигурации оформляются в виде объектов класса Task, которые в качестве своих полей содержат векторы left, down и right, представляющие очередную расстановку ферзей на первых M строках, для которой будет искаться полная расстановка.

Таким образом, отдельные процессоры (Worker'ы), будут брать из некоторой очереди (представляемой каналом sendTask и обработчиком getTask) очередную задачу, решать ее и пересылать ответ главной программе при запросе очередного задания. Worker заканчивает свою работу при считывании из очереди концевого маркера (объекта класса Task со значением -1 для каждого из векторов left, down,right).

Полный текст программы NQueens на языке MC# представлен ниже.

using System;

public class Task {

public int left, down, right;

public Task ( int l, int d, int r ) {

left = l;

down = d;

right = r;

}

}

//**************************************************//

public class NQueens {

public static long totalCount = 0;

public static void Main ( String[] args ) {

int N = System.Convert.ToInt32 ( args [ 0 ] ); // Board size

int M = System.Convert.ToInt32 ( args [ 1 ] ); // Number of fixed queens

int P = System.Convert.ToInt32 ( args [ 2 ] ); // Number of workers

NQueens nqueens = new NQueens();

nqueens.launchWorkers ( N, M, P, nqueens.getTask, nqueens.sendStop, nqueens );

nqueens.generateTasks ( N, M, P, nqueens.sendTask );

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

nqueens.getStop ? ();

Console.Write ( "Task challenge : " + N + " " );

Console.WriteLine ( "Solutions = " + totalCount );

}

//***************************************************************************//

public handler getTask Task(int count ) & channel sendTask ( Task task ) {

totalCount += count;

return ( task );

}

//***************************************************************************//

public handler getStop void() & channel sendStop () {

return;

}

//***************************************************************************//

public async launchWorkers ( int N, int M, int P, handler Task(int) getTask,

channel () sendStop, NQueens nqueens ){

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

nqueens.Worker ( i, N, M, getTask, sendStop );

}

//***************************************************************************//

public void generateTasks ( int N, int M, int P, channel (Task) sendTask ) {

int y = 0;

int left = 0;

int down = 0;

int right = 0;

int MASK = ( 1 << N ) - 1;

MainBacktrack ( y, left, down, right, MASK, M, sendTask );

Task finish_marker = new Task ( -1, -1, -1 );

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

sendTask ! ( finish_marker );

}

//***************************************************************************//

public void MainBacktrack ( int y, int left, int down, int right, int MASK,

int M, channel (Task) sendTask ) {

int bitmap, bit;

if ( y == M )

sendTask ! ( new Task ( left, down, right ) );

else {

bitmap = MASK & ~ ( left | down | right );

while ( bitmap != 0 ) {

bit = -bitmap & bitmap;

bitmap = bitmap ^ bit;

MainBacktrack (y + 1, (left | bit)<<1, down | bit, ( right | bit ) >> 1,

MASK, M, sendTask );

}

}

}

//***************************************************************************//

public async Worker ( int myNumber, int N, int M, handler Task(int) getTask,

channel () sendStop ) {

int MASK = ( 1 << N ) - 1;

int count = 0;

Task task = (Task) getTask ? ( count );

while ( task.left != -1 ) {

WorkerBacktrack ( M, task.left, task.down, task.right, MASK, N, ref count );

task = (Task) getTask ? ( count );

count = 0;

}

sendStop ! ();

}

//***************************************************************************//

public void WorkerBacktrack ( int y, int left, int down, int right, int MASK,

int N, ref int count ) {

int bitmap, bit;

if ( y == N )

count++;

else {

bitmap = MASK & ~ ( left | down | right );

while ( bitmap != 0 ) {

bit = -bitmap & bitmap;

bitmap = bitmap ^ bit;

WorkerBacktrack ( y + 1, (left|bit) << 1, down|bit, (right|bit) >> 1,

MASK, N, ref count );

}

}

}

}

Размещено на Allbest.ru