Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Центр помощи > [Java] 5 ферзей

Автор: Merhaba 28.9.2011, 10:36

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

Автор: Silent 29.9.2011, 13:15

А что тут думать-то? тут писать надо  Держи (правда на C#, но у тебя же есть опыт перевода C#->Java ;-) ): Код /*  * Задача:  * Расставить на шахматной доске NхN M ферзей, чтобы они:  * 1) не били друг друга  * 2) держали все клетки под боем  *   * перебор организовать рекурсивно  */ using System; using System.Collections.Generic; using System.Text; namespace Merhaba_FiveQueen {     public class myPoint     {         public int x, y;         public myPoint(int x, int y)         {             this.x = x;             this.y = y;         }     }     class Program     {         const int N = 8;    //размерность доски         const int M = 5;    //количество ферзей         static bool[] d1 = new bool[2*N];    //главная диагональ         static bool[] d2 = new bool[2*N];         static bool[] g = new bool[N];         static bool[] v = new bool[N];         static Stack<myPoint> s = new Stack<myPoint>();         static int count = 0;         //return true если все клетки под боем         static bool allFill()         {             bool res = true;             bool [,] f = new bool[N,N];             for (int i = 0; i < N; i++)             {                 if (!g[i])                      for (int j = 0; j < N; j++)                          f[i, j] = true;                 if (!v[i])                      for (int j = 0; j < N; j++)                          f[j, i] = true;             }             //d1             for (int i = 0; i < N; i++)             {                 int x = i,                     y = 0;                 if (!d1[N-i])                     for (int j = 0; j < N-i; j++)                          f[x++, y++] = true;                 x = 0;                 y = i;                 if (!d1[N+i])                     for (int j = 0; j < N - i; j++)                          f[x++, y++] = true;             }             //d2             for (int i = 0; i < N; i++)             {                 int x = 0,                     y = N-1-i;                 if (!d2[y])                     for (int j = 0; j <= N-1 - i; j++)                          f[x++, y--] = true;                 x = i;                 y = N-1;                 if (!d2[i+N-1])                      for (int j = 0; j <= N-1 - i; j++)                          f[x++, y--] = true;             }             for (int i = 0; i < N; i++)                 for (int j = 0; j < N; j++)                     res &= f[i, j];             return res;         }         //вывод ответа в шахматной нотации         static void output()         {              myPoint[] tmp = new myPoint[s.Count];             s.CopyTo(tmp, 0);             Console.Write("{0}  ", count);             for (int i = s.Count - 1; i >= 0 ; i--)                 Console.Write("{0} {1}  ", (char)(N-1 - i + 97), tmp[i].y+1);             Console.WriteLine();         }         //основная процедура поиска         static void search(int x, int y, int level)         {             if (level == M)             {                 if (allFill())                  {                     count++;                     output();                 }             }             else                 if (x < N)                 {                     while (x < N)                     {                         if (g[x] && v[y] && d1[N - x + y] && d2[x + y])                         {                             s.Push(new myPoint(x, y));                             g[x] = false;                             v[y] = false;                             d1[N - x + y] = false;                             d2[x + y] = false;                             search(x + 1, 0, level + 1);                             s.Pop();                             g[x] = true;                             v[y] = true;                             d1[N - x + y] = true;                             d2[x + y] = true;                         }                         x += (++y / N);                         y %= N;                     }                 }         }         static void Main(string[] args)         {             Console.SetOut(new System.IO.StreamWriter("output.txt"));             int x = 0, y = 0;             for (int i = 0; i < N; i++)             {                 v[i] = true;                 g[i] = true;             }             for (int i = 0; i < 2*N; i++)             {                 d1[i] = true;                 d2[i] = true;             }             search(0, 0, 0);             Console.Out.Close();         }     } } Количество вариантов - 728, что, кстати, совпадает с http://sources.codenet.ru/download/3886/5_%D4%E5%F0%E7%E5%E9%20%EF%E5%F0%E5%E1%EE%F0.html программами.

Автор: Merhaba 30.9.2011, 05:13

Silent,  а каким алгоритмом нужно руководствоваться при написании кода к данному заданию: "Найдите такую расстановку пяти ферзей на шахматной доске, при которой каждое поле будет находиться под ударом одного из них." ?

Автор: Silent 30.9.2011, 07:16

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

Автор: Merhaba 1.10.2011, 06:13

Silent,  А каким требованиям должна удовлетворять постановка ферзя, чтобы выполнялось условие задачи? ("каждое поле будет находиться под ударом одного из них")     как можно переписать код, с использованием методов, которые ставят и убирают ферзя : Код void putQueen(int h, int v){         positionOnVertical[v] = h;         onHorizontal[h] = false;         RUtoLD[v+h] = false;         LUtoRD[(v-h) + (deskSize-1)] = false;      }      void removeQueen(int h, int v){         positionOnVertical[v] = 0;         onHorizontal[h] = true;         RUtoLD[v+h] = true;         LUtoRD[(v-h) + (deskSize-1)] = true;     }   ?

Автор: Silent 1.10.2011, 14:53

Формулировка "каждое поле будет находиться под ударом одного из них" подразумевает, что на конечной расстановке ферзей любая клетка поля будет биться только лишь одним ферзем. Сходу я не могу придумать, как изменить алгоритм чтобы ферзя можно было поставить только по этому условию, однако, как подсказывает здравый смысл, нафиг особо такое не надо - в любом случае эта оптимизация будет подмножеством вышереализованного мной алгоритма (ибо нужно чтобы ферзи друг дружку не били): для конечной расстановки просто проверять этот факт. А это просто-напросто немного модифицировать процедуру AllFill() - поменять тип массива f на int, и вместо f[i,j] = true инкрементить f[i,j]++. Если в итоге будут единички (а в позициях ферзей 4) - значит гут, расстановка нам подходит.

Автор: Merhaba 25.12.2011, 16:52

Silent,  скажите Пожалуйста, за что отвечает переменная level? Добавлено через 3 минуты и 36 секунд Silent,  Перепишите Пожалуйста вот этот кусочек кода на Ява:   Код static void output()         {              myPoint[] tmp = new myPoint[s.Count];             s.CopyTo(tmp, 0);             Console.Write("{0}  ", count);             for (int i = s.Count - 1; i >= 0 ; i--)                 Console.Write("{0} {1}  ", (char)(N-1 - i + 97), tmp[i].y+1);             Console.WriteLine();         }

Автор: Mirkes 10.1.2012, 13:42

Цитата(Silent @  1.10.2011,  14:53 ) Формулировка "каждое поле будет находиться под ударом одного из них" подразумевает, что на конечной расстановке ферзей любая клетка поля будет биться только лишь одним ферзем. Ошибка. Эта фраза означает всего лишь, что каждое поле будет биться ХОТЯ БЫ ОДНИМ ферзем. Нельзя поставить на шахматную доску даже двух ферзей так, чтобы ни одно поле не пробивалось двумя ферзями. (опыт шахматиста). В принципе можно организоват перебор просто ставя или снимая ферзя, но это будет совсем полный перебор. Для этого достаточно создать доску типа int[8][8]. Обнулить.  Далее запускаем процедуру поиска с уровнем 0 (нет поставленных ферзей) В процедуре поиска    Проверяем уровень. Если он =5, то проверяем наличие нулевых клеток. Если их нет, то это решение, его можно выводить.    Если уровень 5 и есть нулевые клетки - возврат.    перебираем все клетки по x и y от 1 до 8.       Если клетка нулевая ставим ферзя и вызываем следующую процедуру поиска с уровнем на 1 больше. Снимаем ферзя.     По окончании цикла - возврат Процедура поставить ферзя. По горизонтали, вертикали и обеим диагоналям от позиции ферзя в каждую клетку добавляем по 1. В позицию ферзя добавляем 100. (не обязательно 100, но точно больше 4). Процедура снять ферзя - тоже что поставить, но вместо увеличения - вычитаем.

Автор: Mirkes 13.1.2012, 17:05

Пожалуйста, но я не понимаю, в чем был затык у вас Код package fer; public class Ferz {     private int field[][] = new int[8][8];     static final String not = "abcdefgh";     public static void main(String[] arg) {         new Ferz().run();     }     public boolean full() {         for (int i = 0; i < 8; i++)             for (int j = 0; j < 8; j++)                 if (field[i][j] == 0)                     return false;         return true;     }     public void putFerz(int x, int y) {         for (int i = 0; i < 7; i++) {             // Процедура поставить ферзя. По горизонтали, вертикали             field[i][y]++;             field[x][i]++;             // и обеим диагоналям от позиции ферзя в каждую клетку добавляем по 1. В позицию ферзя добавляем 100. (не обязательно 100, но точно больше 4).             if (x - i >= 0) {                 if (y - i >= 0)                     field[x - i][y - i]++;                 if (y + i < 8)                     field[x - i][y + i]++;             }             if (x + i < 8) {                 if (y - i >= 0)                     field[x + i][y - i]++;                 if (y + i < 8)                     field[x + i][y + i]++;             }         }         field[x][y]+=100;     }     public void removeFerz(int x, int y) {         for (int i = 0; i < 7; i++) {             // Процедура снять ферзя. По горизонтали, вертикали             field[i][y]--;             field[x][i]--;             // и обеим диагоналям от позиции ферзя в каждую клетку добавляем по 1. В позицию ферзя добавляем 100. (не обязательно 100, но точно больше 4).             if (x - i >= 0) {                 if (y - i >= 0)                     field[x - i][y - i]--;                 if (y + i < 8)                     field[x - i][y + i]--;             }             if (x + i < 8) {                 if (y - i >= 0)                     field[x + i][y - i]--;                 if (y + i < 8)                     field[x + i][y + i]--;             }         }         field[x][y]-=100;     }     public void find(int level) {         // В процедуре поиска         if (level == 5) {             // Проверяем уровень. Если он =5, то проверяем наличие нулевых клеток. Если их нет, то это решение, его можно выводить.             if (full()) {                 //его можно выводить                 for (int i = 0; i < 8; i++)                     for (int j = 0; j < 8; j++)                         if (field[i][j] > 100) {                             System.out.print(""+not.charAt(i) + (j + 1) + " ");                         }                 System.out.println();             }             // Если уровень 5 и есть нулевые клетки - возврат.             return;         }         //перебираем все клетки по x и y от 1 до 8.         for (int i = 0; i < 8; i++)             for (int j = 0; j < 8; j++)                 if (field[i][j] == 0) {                     //   Если клетка нулевая ставим ферзя и вызываем следующую процедуру поиска с уровнем на 1 больше. Снимаем ферзя.                     putFerz(i, j);                     find(level + 1);                     removeFerz(i, j);                 }         //По окончании цикла - возврат     }     public void run() {         // Clear field         // Для этого достаточно создать доску типа int[8][8]. Обнулить.         for (int i = 0; i < 8; i++)             for (int j = 0; j < 8; j++)                 field[i][j] = 0;         // Далее запускаем процедуру поиска с уровнем 0 (нет поставленных ферзей)         find(0);     } }

Автор: Merhaba 13.1.2012, 21:18

Mirkes,  Спасибо Вам большое за помощь!!! как можно переделать код, чтобы тут был метод, который будет распечатывать расстановки (ферзь обозначается "*", клетка ".")?  Как организовать подсчёт расстановок?

Автор: Mirkes 14.1.2012, 12:36

Код               //его можно выводить                               for (int i = 0; i < 8; i++)                     for (int j = 0; j < 8; j++)                         if (field[i][j] > 100) {                             System.out.print(""+not.charAt(i) + (j + 1) + " ");                         }                 System.out.println();             } нужно заменить на фрагмент распечатки поля. Например такой Код               //его можно выводить                               for (int i = 0; i < 8; i++){                     for (int j = 0; j < 8; j++)                         if (field[i][j] > 100) {                             System.out.print("*");                         else                             System.out.print(".");                         }                    System.out.println(); // переход к новой строке доски                 }                 System.out.println();  // зарделитель досок             } Насчет подсчета найденных ситуаций все несколько хуже - при проверке программы я обнаружил, что каждая позиция находится пять раз. Так что и доски будут распечатываться по пять раз. Есть такой вариант выхода из положения: запоминать найденные позиции и прежде чем печатать проверять не печатали ли ее раньше.

Автор: Merhaba 14.1.2012, 12:55

Mirkes,  Код //   Если клетка нулевая ставим ферзя и вызываем следующую процедуру поиска с уровнем на 1 больше. Снимаем ферзя.                     putFerz(i, j);                     find(level + 1);                     removeFerz(i, j); Для какой цели нам требуется снимать ферзя?

Автор: Mirkes 16.1.2012, 17:46

Постановка ферзя порит поле, снятие ферзя приводит поле к исходному состоянию.

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)