Как же реализовать рассмотренный алгоритм? Самый простой и самый трудоемкий по времени исполнения — это метод прямого перебора. Первым ходом поставим ферзя на какую-нибудь клетку, затратив на это единицу времени. Затем в следующем ходе просматриваем 64 возможных вариантов постановки очередного ферзя. Для каждого варианта (i,j), i — номер горизонтали, j — номер вертикали, необходимо проверить по 8 клеток i-й горизонтали и j-й вертикали, от 1 до 8 клеток для каждой диагонали, проходящей через клетку (i,j).
Таким образом, число переборов оказывается непомерно великим.Учтем то обстоятельство, что на каждой горизонтали может быть установлен только один ферзь. Поэтому первый ферзь установим на первой горизонтали, второй — на второй и т.д. Тогда для каждого /-го хода останется всего лишь восемь вариантов постановки ферзя, а проверяться будут клетки только на j-й вертикали и двух диагоналях. Несмотря на это, число проверок остается большим.
Если теперь принять во внимание то, что не только на каждой горизонтали, но на каждой вертикали и каждой диагонали может находиться только один ферзь, число проверок можно существенно сократить. Для этого необходимо иметь информацию о состоянии («занято» — «свободно») 8 вертикалей, 15 восходящих (слева снизу — направо вверх) и 15 нисходящих (слева сверху — направо вниз) диагоналей. С этой целью используем три одномерных массива: а[8] — состояние вертикалей, Ь[\5] —¦ состояние восходящих диагоналей, с[\5] — состояние нисходящих диагоналей. Тогда для каждого варианта (i,j) необходимы только три проверки. Встает вопрос: Как для варианта (i,j) выбирать для проверки элементы массивов а,Ь,с? Последовательный номер элемента а совпадает с номером варианта у. Обратим внимание на то, что для каждой восходящей диагонали сумма (i +J) постоянна: (1 + 1) = 2; (2 + 1) = = (1 + 1) = (1 + 2) = 3 и т.д. (8 + 8) = 16, эти суммы меняются от 2 до 16 (2,3,4,...,15,16), а для каждой нисходящей диагонали постоянна разность (i -j): (8 - 1) = 7; (7 - 1) = (8 - 2) = 6; ...;(1 - 8) = - 7, они меняются от 7 до - 7 (7,6,..., - 6, - 7). Это позволяет для каждого варианта (i,j) однозначно вычислять индексы соответствующих массивов с учетом границ изменения индексов.
Возможны два условия задачи расстановки ферзей: найти одну или все возможные расстановки. Всего имеются 92 различные расстановки, но только 12 из них являются независимыми, остальные можно получить поворотами и зеркальными отражениями доски.
-Алгоритм решения задачи
Словесный (содержательный) алгоритм решения задачи:
Начало
1. Выполнить пункты 2-8; (v1)
2. Если не достигли пределов доски, то выполняем пункт 3,иначе пункт 9; (z1)
3. Если сумма каждого элемента i-ой фигуры пентамино и каждого поля доски, начиная с исходной позиции j, не больше единицы, то пункт 4, иначе пункт 2; (z2)
4. Присваиваем соответствующим элементам доски значение i (т.е. устанавливаем фигуру пентамино на доску); (v2)
5. Если i<12, то пункт 6, иначе 7; (z3)
6. Увеличиваем i на единицу и переход к пункту 2; (v3)
7. Вывод на экран одного решения; (v4)
8. Обнуляем значения i-ой фигуры на доске; (v5)
9. Если j<n, то пункт 1; (z4)
Конец
Словесный алгоритм даёт краткое описание программной реализации решения задачи, и предназначен с общей схемой алгоритма. В частности в нём не рассматривается процесс представления формы каждой фигуры в памяти ЭВМ, так как этот вопрос описывается далее. Также существует неточность по поводу количества циклов, так ка в программе их значительно больше, по причине работы с трёхмерными массивами. Однако для удобства и наглядности, я полагаю, этим можно пренебречь.
-Обоснование выбора структур данных
Прежде чем приступить к разработке алгоритма и созданию программы, нам необходимо иметь представление о способе представления данных в ЭВМ. Поэтому первым вопросом, при разработке программ, является выбор структур данных. В своей программе мне пришлось применить последовательно две структуры для представления в памяти фигур пентамино. Изначально каждая фигура была описана как строка массива geometry. Количество столбцов в этом массиве-25. Именно столько необходимо для представления двумерного массива 5х5. А количество строк соответственно равно 12, так как мы знаем, что всего фигурок двенадцать.
Возможно, возникнет вопрос: «Почему для представления каждой фигуры нужно 25 чисел?» Действительно, это довольно много, но если для каждой фигуры создать отдельный массив со своей “собственной” размерностью, то в памяти необходимо хранить этот массив размерностей для каждой фигуры пентамино и обращаться к ним исключительно по индексам массива. А это помимо того, что неудобно в процессе отладки, к тому же достаточно громоздко и ничуть не экономит память. Вследствие этого, я предпочла иметь константный массив geometry[12][25].
Однако, как уже было сказано, такое представление данных имеется только на начальном этапе работы программы. Если при выполнении рекурсии, в обращение к подпрограмме, в качестве фактических параметров выступает массив, размерностью 12х25, то это чрезвычайно снижает эффективность программы, экономию памяти, а также быстродействие. Несмотря на то, что современная вычислительная система справится даже с наихудшим программным вариантом алгоритма, этот факт стоит учитывать. По этой причине, мне пришлось перевести массив geometry в структуры типа массив записей. Каждая запись массива имеет два поля: массив shape(5x5), в котором представлена форма каждой фигуры и переменная located. Она служит чем-то вроде метки на каждую фигуру, предоставляющей информацию о том стоит ли фигура на доске или нет. С такой структурой данных работать гораздо удобнее так как при рекурсивном вызове процедуры, мы передаём всего лишь текущий элемент массива записей, то есть одну запись.
Опять-таки, вновь возникает вопрос: «Почему нельзя было представить фигуры пентамино в таком виде, не затрачивая лишней памяти на массив geometry?» Это возможно лишь в том случае, если данные вводят с устройства ввода, но это слишком утомительно, так как их объём достаточно велик. Также можно было считывать с файла, но эти способы идентичны по объёму занимаемой памяти. Описывать же каждое поле каждой записи в виде константы не позволяют средства языков программирования, как TurboPascal, так и VisualC++.
Говоря о выборе языка программирования, то это вопрос, возникающий сразу после разработки алгоритма. При выборе языка, я руководствовалась выбранным представлением данных, свойствами алгоритма и особенностями задачи. Мой выбор пал на язык С++ в среде MicrosoftVisualC++, так как по моим представлениям именно в ней содержится наиболее гибкие средства для обработки различных данных, сколь угодно большого объёма. Описание подпрограмм, написанных на этом языке, даны ниже и содержит три подпрограммы, используемые в программе:
1. Подпрограмма из массива geometry формирует структуру типа массив записей, используемую далее в главной подпрограмме placing:
void forming();
2. Подпрограмма непосредственно реализует метод проб и ошибок с использованием метода backtracking. Осуществляет рекурсивное покрытие прямоугольной области nxm фигурами пентамино и при нахождении каждого решения обращается к функции print:
void placing(int i);
3. Подпрограмма осуществляет вывод на экран различных данных, используемых и полученных в программе:
void print();
Вызов функций forming() осуществляется непосредственно из основной функции main(), функция placing(inti) изначально вызывается в функции main, а затем происходит рекурсивный вызов подпрограммы.
-Программа
Далее приводится непосредственно сам текст исходного кода программы, реализующей алгоритм решения задачи Y-пентамино.
#include<iostream.h>
#include<cmath>
#include"pent.h"
void forming(int geo[12][25]);
void placing(int);
void print(int geo[12][25]);
int main()
{ //массив,в котором каждая строка,реализует представление 1 фигуры
int geometry[12][25]={1,1,1,0,0,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,
1,1,0,0,0,1,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,1,0,0,0,1,1,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,1,0,0,1,1,1,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,
1,1,0,0,0,1,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,1,1,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
1,1,0,0,0,0,1,1,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,
1,1,0,0,0,0,1,0,0,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,0,
1,1,0,0,0,0,1,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,
1,0,0,0,0,1,0,0,0,0,1,1,0,0,0,1,0,0,0,0,0,0,0,0,0,
1,1,0,0,0,0,1,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,
0,1,1,1,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
//структура 1 фигуры
//прямоугольная область размещения фигур
//(в дальнейшем поле расстановки) 6х10
//clrscr(); //очистка экрана
cout<<"beginning dates:"<<endl; //вывод начальных данных
getch(); // ожидание нажатия клавишы
//подпрограмма формирования массива фигур,
//из начального массива geometry
forming(geometry);
// int kol=10; int kol2=0;short b=1;
// int g=-33, h=48;
//основная функция, выполняющая всевозможные расстановки фигур
//на поле расстановки
placing(1);
//вывод данных(поле расстановки) на экран
print(geometry);
getch();
// b ? Print(kol,kol2) : Print(kol,pow(kol,2)+g);
// b ? Prrint(kol,kol2) : Prrint(kol,pow(kol,2)-h);
return 0;
}
//подпрограмма формирования массива фигур,
//изначальногомассива geometry
void forming(int geo[12][25])
{ struct pents
{ int shape[5][5];//форма фигуры
char located; //находится на доске/не находится
} image[12]; //массив из 12 фигур
int h;
for(int i=1;i<=12;i++) //кол-во фигур
{ h=1;
for(int j=1;j<=5;j++) //размерность каждой фигуры
for(int k=1;k<=5;k++)
//присвоение массиву форматов каждой фигуры,
//значений из нгчальных данных
{ image[i].shape[j][k]=geo[i][h];
h++;
}
}
for(i=1;i<=12;i++)
//пока ни одна фигура не ледит на поле расстановки,
//поэтомузначение "N"
image[i].located='N';
}
//основная функция, выполняющая всевозможные расстановки фигур
//на поле расстановки
void placing(int i) //i-номер фигуры
{ const static int n=6,m=10;
struct pents
{ int shape[5][5];//формафигуры
char located; //находится на доске/не находится
} image[12]; int field[n][m];
//вспомогательные счётчики и
//признак нахождения подходящего варианта