Форумы » Клуб » Радости жизни » Головоломка
[image]

Головоломка

Теги:радости жизни
 
Новый опрос Новый фотосет Новая тема Написать сообщение в тему
1 2 3 4
RU AGRESSOR #17.12.2006 06:50
+
-
edit
 

AGRESSOR

литератор
★★★★★
☠
http://www.ellf.ru/uploads/flash/8queens.swf

Маялся минут 15-20. Собрал-таки. :)
   
US Сергей-4030 #17.12.2006 06:53
+
-
edit
 

Сергей-4030

исключающий третье
★★
AGRESSOR> http://www.ellf.ru/uploads/flash/8queens.swf
AGRESSOR> Маялся минут 15-20. Собрал-таки. :)

Задача о 8 ферзях. Первый курс, предмет: программирование ЭВМ, тема: рекурсивные алгоритмы. :) А вообще, надо сказать, вручную на самом деле тяжко.
   
US Mishka #17.12.2006 07:06
+
-
edit
 

Mishka

модератор
★★★
А Г.С.Цейтин написал её на алголе без единной локальной переменной.
   
BY minchuk #17.12.2006 08:17
+
-
edit
 

minchuk

координатор
★★☆
Ну я бы не сказал, что — тяжело, но... Минут 7-10, "исключая варианты", вполне. :)
   
US Mishka #17.12.2006 08:56
+
-
edit
 

Mishka

модератор
★★★
А найти все варианты?
   
US Машинист #17.12.2006 09:18
+
-
edit
 

Машинист

старожил
★★
админ. бан
Mishka> А найти все варианты?
ИМХО их только 8, из них 1 оригинальный, остальные - то же, но повёрнутое и/или отражённое.
   
US Сергей-4030 #18.12.2006 06:38
+
-
edit
 

Сергей-4030

исключающий третье
★★
Mishka>> А найти все варианты?
Машинист> ИМХО их только 8, из них 1 оригинальный, остальные - то же, но повёрнутое и/или отражённое.

По-моему, нет. Во первых - я только что освежил в памяти, написал программку. Решений, если не искать повороты/отражения - 92. Если искать (я малость усложнил программку, чтоб искала) - то тогда находится 12, вроде как все они существенно различны. Кто хочет проверить: вот текст программы (без комментариев, но это неважно - надо только запустить):

code java
  1. package samples;
  2.  
  3. import java.io.PrintStream;
  4. import java.util.ArrayList;
  5.  
  6. public class EightQueens {
  7.         static final int SIZE=8;
  8.         int currentSolution[] = new int[SIZE];
  9.  
  10.         ArrayList<int[]> solutions = new ArrayList<int[]>();
  11.  
  12.         private boolean horz[] = new boolean[SIZE];
  13.  
  14.         private boolean verts[] = new boolean[SIZE];
  15.  
  16.         private boolean diags[] = new boolean[2*SIZE-1];
  17.  
  18.         private boolean diags2[] = new boolean[2*SIZE-1];
  19.  
  20.         PrintStream out;
  21.  
  22.         boolean doQueen(int x, int y) {
  23.                 if (!(horz[x] || verts[y] || diags[y - x + (SIZE-1)] || diags2[y + x])) {
  24.                         horz[x] = true;
  25.                         verts[y] = true;
  26.                         diags[y - x + (SIZE-1)] = true;
  27.                         diags2[y + x] = true;
  28.                         return true;
  29.                 }
  30.                 return false;
  31.         }
  32.  
  33.         boolean equalsTo(int anotherSolution[]) {
  34.                 for(int i=0;i<currentSolution.length;i++) {
  35.                         if(currentSolution[i]!=anotherSolution[i])
  36.                                 return false;
  37.                 }
  38.                 return true;
  39.         }
  40.  
  41.         int [] rotate(int board[]) {
  42.                 int newboard[]=new int[SIZE];
  43.                 for(int i=0;i<SIZE;i++) {
  44.                         newboard[SIZE-board[i]-1]=i;
  45.                 }
  46.                 return newboard;
  47.         }
  48.  
  49.         int [] mirrorHoriz(int board[]) {
  50.                 int newboard[]=new int[SIZE];
  51.                 for(int i=0;i<SIZE;i++) {
  52.                         newboard[i]=SIZE-board[i]-1;
  53.                 }
  54.                 return newboard;
  55.         }      
  56.  
  57.         int [] mirrorVert(int board[]) {
  58.                 int newboard[]=new int[SIZE];
  59.                 for(int i=0;i<SIZE;i++) {
  60.                         newboard[SIZE-i-1]=board[i];
  61.                 }
  62.                 return newboard;
  63.         }      
  64.  
  65.         int [] mirrorCenter(int board[]) {
  66.                 int newboard[]=new int[SIZE];
  67.                 for(int i=0;i<SIZE;i++) {
  68.                         newboard[SIZE-i-1]=SIZE-board[i]-1;
  69.                 }
  70.                 return newboard;
  71.         }      
  72.        
  73.        
  74.         void undoQueen(int x, int y) {
  75.                 horz[x] = false;
  76.                 verts[y] = false;
  77.                 diags[y - x + (SIZE-1)] = false;
  78.                 diags2[y + x] = false;
  79.         }
  80.  
  81.         boolean tryMirror(int res[]) {
  82.                 int temp[]=mirrorVert(res);
  83.                 if(equalsTo(temp))
  84.                         return true;
  85.                 temp=mirrorHoriz(temp);
  86.                 if(equalsTo(temp))
  87.                         return true;
  88.                 temp=mirrorVert(temp);
  89.                 if(equalsTo(temp))
  90.                         return true;
  91.                 if(equalsTo(mirrorCenter(res)))
  92.                         return true;
  93.                 return false;
  94.         }
  95.        
  96.         boolean alreadyHave() {
  97.                 for(int [] res:solutions) {
  98.                         if(equalsTo(res))
  99.                                 return true;
  100.                         if(tryMirror(res))
  101.                                 return true;
  102.                         int rotate[]=rotate(res);
  103.                         if(equalsTo(rotate))
  104.                                 return true;
  105.                         if(tryMirror(rotate))
  106.                                 return true;
  107.                         if(equalsTo(rotate=rotate(rotate)))
  108.                                 return true;
  109.                         if(tryMirror(rotate))
  110.                                 return true;
  111.                         if(equalsTo(rotate=rotate(rotate)))
  112.                                 return true;
  113.                         if(tryMirror(rotate))
  114.                                 return true;
  115.                 }
  116.                 return false;
  117.         }
  118.        
  119.         void arrange(int y) {
  120.                 if (y == SIZE) {
  121.                         if(! alreadyHave())
  122.                                 solutions.add(currentSolution.clone());
  123.                 } else {
  124.                         for (int x = 0; x < SIZE; x++) {
  125.                                 if (doQueen(x, y)) {
  126.                                         currentSolution[y] = x;
  127.                                         arrange(y + 1);
  128.                                         undoQueen(x, y);
  129.                                 }
  130.                         }
  131.                 }
  132.         }
  133.  
  134.         void printLine(int numspaces) {
  135.                 for (int i = 0; i < numspaces; i++)
  136.                         out.print("  ");
  137.                 out.println("FF");
  138.         }
  139.  
  140.         public void printSolution(int solution[]) {
  141.                 out.print("  ");
  142.                 for (int i = 0; i < SIZE; i++)
  143.                         out.print("--");
  144.                 out.println();
  145.                 for (int i = 0; i < solution.length; i++) {
  146.                         out.print("" + (SIZE - i) + " ");
  147.                         printLine(solution[i]);
  148.                 }
  149.                 out.print("  ");
  150.                 int ch='A';
  151.                 for(int i=0;i<SIZE;i++) {
  152.                         out.print(" ");
  153.                         out.print((char)(ch+i));
  154.                 }
  155.                 out.println();
  156.                 out.print("  ");
  157.                 for (int i = 0; i < SIZE; i++)
  158.                         out.print("--");
  159.                 out.println();
  160.         }
  161.        
  162.         public void print() {
  163.                 int count = 1;
  164.                 out.println("Found:" + solutions.size() + " solutions.\n");
  165.                 for (int res[] : solutions) {
  166.                         out.println("\nSolution " + (count++));
  167.                         printSolution(res);
  168.                 }
  169.         }
  170.  
  171.         public EightQueens(PrintStream str) {
  172.                 out = str;
  173.                 out.print("Searching for solutions...");
  174.                 arrange(0);
  175.                 out.println("done!");
  176.         }
  177.  
  178.         public static void main(String args[]) {
  179.                 (new EightQueens(System.out)).print();
  180.         }
  181. }


А вот тут: найденные решения. Посмотрите, может я чего пропустил и есть какие-то производные друг от друга решения.

code text
  1. Searching for solutions...done!
  2. Found:12 solutions.
  3.  
  4.  
  5. Solution 1
  6.   ----------------
  7. 8 FF
  8. 7         FF
  9. 6               FF
  10. 5           FF
  11. 4     FF
  12. 3             FF
  13. 2   FF
  14. 1       FF
  15.    A B C D E F G H
  16.   ----------------
  17.  
  18. Solution 2
  19.   ----------------
  20. 8 FF
  21. 7           FF
  22. 6               FF
  23. 5     FF
  24. 4             FF
  25. 3       FF
  26. 2   FF
  27. 1         FF
  28.    A B C D E F G H
  29.   ----------------
  30.  
  31. Solution 3
  32.   ----------------
  33. 8   FF
  34. 7       FF
  35. 6           FF
  36. 5               FF
  37. 4     FF
  38. 3 FF
  39. 2             FF
  40. 1         FF
  41.    A B C D E F G H
  42.   ----------------
  43.  
  44. Solution 4
  45.   ----------------
  46. 8   FF
  47. 7         FF
  48. 6             FF
  49. 5 FF
  50. 4     FF
  51. 3               FF
  52. 2           FF
  53. 1       FF
  54.    A B C D E F G H
  55.   ----------------
  56.  
  57. Solution 5
  58.   ----------------
  59. 8   FF
  60. 7         FF
  61. 6             FF
  62. 5       FF
  63. 4 FF
  64. 3               FF
  65. 2           FF
  66. 1     FF
  67.    A B C D E F G H
  68.   ----------------
  69.  
  70. Solution 6
  71.   ----------------
  72. 8   FF
  73. 7           FF
  74. 6 FF
  75. 5             FF
  76. 4       FF
  77. 3               FF
  78. 2     FF
  79. 1         FF
  80.    A B C D E F G H
  81.   ----------------
  82.  
  83. Solution 7
  84.   ----------------
  85. 8   FF
  86. 7           FF
  87. 6               FF
  88. 5     FF
  89. 4 FF
  90. 3       FF
  91. 2             FF
  92. 1         FF
  93.    A B C D E F G H
  94.   ----------------
  95.  
  96. Solution 8
  97.   ----------------
  98. 8   FF
  99. 7             FF
  100. 6     FF
  101. 5           FF
  102. 4               FF
  103. 3         FF
  104. 2 FF
  105. 1       FF
  106.    A B C D E F G H
  107.   ----------------
  108.  
  109. Solution 9
  110.   ----------------
  111. 8   FF
  112. 7             FF
  113. 6         FF
  114. 5               FF
  115. 4 FF
  116. 3       FF
  117. 2           FF
  118. 1     FF
  119.    A B C D E F G H
  120.   ----------------
  121.  
  122. Solution 10
  123.   ----------------
  124. 8     FF
  125. 7         FF
  126. 6   FF
  127. 5               FF
  128. 4 FF
  129. 3             FF
  130. 2       FF
  131. 1           FF
  132.    A B C D E F G H
  133.   ----------------
  134.  
  135. Solution 11
  136.   ----------------
  137. 8     FF
  138. 7         FF
  139. 6               FF
  140. 5       FF
  141. 4 FF
  142. 3             FF
  143. 2   FF
  144. 1           FF
  145.    A B C D E F G H
  146.   ----------------
  147.  
  148. Solution 12
  149.   ----------------
  150. 8     FF
  151. 7           FF
  152. 6   FF
  153. 5         FF
  154. 4               FF
  155. 3 FF
  156. 2             FF
  157. 1       FF
  158.    A B C D E F G H
  159.   ----------------
   
Это сообщение редактировалось 18.12.2006 в 07:04
US Сергей-4030 #18.12.2006 06:40
+
-
edit
 

Сергей-4030

исключающий третье
★★
Посмотрите, в частности, solution 3 и solution 8 - по-моему, совершенно ясно, что решения абсолютно разные.
   
US Сергей-4030 #18.12.2006 06:53
+
-
edit
 

Сергей-4030

исключающий третье
★★
Кстати, если интересно, можно с разными размерами доски посмотреть. В частности, минимальный размер доски, на которой есть решение: 4

code text
  1. Searching for solutions...done!
  2. Found:1 solutions.
  3.  
  4.  
  5. Solution 1
  6.   --------
  7. 4   FF
  8. 3       FF
  9. 2 FF
  10. 1     FF
  11.    A B C D
  12.   --------


По мере увеличения доски количество решений как правило увеличивается (не всегда: для доски размером 5 есть два решения, а для доски размером 6 - только одно). Впрочем, для "больших" досок число решений растет очень быстро, для 9 - 46, для 10 - 92 (заметьте - столько же, сколько для восьми без учета вращений/отражений), для 11 - 341, для 12 - 1787. Уже для 12 программа работает достаточно долго (около минуты на моем компьютере), так что дальше я не пробовал. Кому интересно - you're welcome. ;)
   
US Сергей-4030 #18.12.2006 07:30
+
-
edit
 

Сергей-4030

исключающий третье
★★
Кстати, заметьте - этакие "прямоугольные" решения очень популярны. ;) Причем только для "четных" досок! Интересно...

code text
  1. 4:
  2.   --------
  3. 4   FF
  4. 3       FF
  5. 2 FF
  6. 1     FF
  7.    A B C D
  8.   --------


code text
  1. 6:
  2.   ------------
  3. 6   FF
  4. 5       FF
  5. 4           FF
  6. 3 FF
  7. 2     FF
  8. 1         FF
  9.    A B C D E F
  10.   ------------


code text
  1. 8:
  2.   ----------------
  3. 8     FF
  4. 7         FF
  5. 6   FF
  6. 5               FF
  7. 4 FF
  8. 3             FF
  9. 2       FF
  10. 1           FF
  11.    A B C D E F G H
  12.   ----------------


code text
  1. 10:
  2.   --------------------
  3. 10  FF
  4. 9       FF
  5. 8           FF
  6. 7               FF
  7. 6                   FF
  8. 5 FF
  9. 4     FF
  10. 3         FF
  11. 2             FF
  12. 1                 FF
  13.    A B C D E F G H I J
  14.   --------------------


Впрочем, для "нечетных" досок в той же степени характерны "прямоугольные подобласти", как здесь:

code text
  1. 9:
  2.   ------------------
  3. 9 FF
  4. 8       FF
  5. 7           FF
  6. 6     FF
  7. 5                 FF
  8. 4   FF
  9. 3               FF
  10. 2         FF
  11. 1             FF
  12.    A B C D E F G H I
  13.   ------------------
   
US Сергей-4030 #18.12.2006 17:29
+
-
edit
 

Сергей-4030

исключающий третье
★★
Интересно, что в "прямоугольных" решениях обе главные диагонали - свободны. Что, кстати, и позволяет из решения размерности 8 элементарно сделать решение размерности 9.

Прикольно, что, по видимому, решение размерности 10 вручную найти легче, чем решение размерности 8.
   
18.12.2006 18:19, minchuk: +1: За интересный и подробный анализ.
RU AGRESSOR #18.12.2006 17:51
+
-
edit
 

AGRESSOR

литератор
★★★★★
☠
92 решения?! Обалдеть! Я подозревал, что программно эту головоломку можно несколькими вариантами решить, но чтоб столько... А насколько реально самому такое кол-во решений найти?
   
US Сергей-4030 #18.12.2006 18:23
+
-
edit
 

Сергей-4030

исключающий третье
★★
AGRESSOR> 92 решения?! Обалдеть! Я подозревал, что программно эту головоломку можно несколькими вариантами решить, но чтоб столько... А насколько реально самому такое кол-во решений найти?

Да все решения вполне реально найти, конечно. :) Только долго. Конкретно: программа 15720 раз ставила ферзей на разные позиции. 2496 раз программа добиралась до последней линии, при этом 2404 раза из этих попыток она не могла поставить последнего ферзя. Надо думать, при некоторой тренировке можно ставить / оценивать за 1 секунду, плюс записывать получившиеся решения - ну, скажем, 30 секунд. Итого, 15720 + 30*92 секунд. То есть, чуть больше пяти часов - при должной тренировке.

ЗЫ А вот оценивать отражения/повороты, боюсь, будет дольше. ;)
   
US Mishka #19.12.2006 02:26
+
-
edit
 

Mishka

модератор
★★★
Агги, тебе подсказка. Пока только для 8 на 8 (но можно обобщить) — возьми полоску 8 на 2 и расположи на ней всеми возможными способами (почему 2 — думаю, очевидно — одно мало, а 3 не расположить) — должно получиться не более 64 :F — тоже понятно почему. На самом деле, значительно меньше. Потом состыковывать эти полоски.

А для произвольной доски — там похоже есть некорые свойства связанные с делением на 4.
   
US Сергей-4030 #06.02.2008 22:55
+
-
edit
 

Сергей-4030

исключающий третье
★★
Продолжение тут!
   
RU GOGI #06.02.2008 23:13
+
-
edit
 

GOGI

старожил
★★★★
админ. бан
На одно решение вручную легко. Если бы еще доска не в проекции была изображена.
   
US Сергей-4030 #06.02.2008 23:44  @GOGI#06.02.2008 23:13
+
-
edit
 

Сергей-4030

исключающий третье
★★
GOGI> На одно решение вручную легко. Если бы еще доска не в проекции была изображена.

Попробуй модифицировать условия. ;) Скажем, доска 16x16. ;)

code text
  1.   --------------------------------
  2. 16 FF
  3. 15     FF
  4. 14         FF
  5. 13   FF
  6. 12                         FF
  7. 11                 FF
  8. 10                           FF
  9. 09                       FF
  10. 08                             FF
  11. 07           FF
  12. 06                               FF
  13. 05             FF
  14. 04       FF
  15. 03                     FF
  16. 02               FF
  17. 01                   FF
  18.    A B C D E F G H I J K L M N O P
  19.   --------------------------------
   
RU GOGI #06.02.2008 23:54
+
-
edit
 

GOGI

старожил
★★★★
админ. бан
Думаешь, не найду? :-) Тока вы мне на флеше сначала такую же доску нарисуйте :-)
   
US Сергей-4030 #07.02.2008 17:48  @GOGI#06.02.2008 23:54
+
-
edit
 

Сергей-4030

исключающий третье
★★
GOGI> Думаешь, не найду? :-) Тока вы мне на флеше сначала такую же доску нарисуйте :-)

Честно говоря, думаю, не найдешь. :) Это, вроде как, NP-полная задача, поэтому придется решать перебором. А перебор тут будет дооооолгий!
   
RU GOGI #07.02.2008 17:58
+
-
edit
 

GOGI

старожил
★★★★
админ. бан
А что такое NP-полная? :-)
А у человека еще и неалгоритмизируемые методы поиска решения есть :-)
   
RU Владимир Малюх #07.02.2008 18:15  @Сергей-4030#17.12.2006 06:53
+
-
edit
 

Владимир Малюх

аксакал
★★☆
AGRESSOR>> http://www.ellf.ru/uploads/flash/8queens.swf
AGRESSOR>> Маялся минут 15-20. Собрал-таки. :)
Сергей-4030> Задача о 8 ферзях. Первый курс, предмет: программирование ЭВМ, тема: рекурсивные алгоритмы. :)

9-й класс - комбинаторика :)
   
RU Владимир Малюх #07.02.2008 18:17  @AGRESSOR#18.12.2006 17:51
+
-
edit
 

Владимир Малюх

аксакал
★★☆
AGRESSOR> 92 решения?! Обалдеть! Я подозревал, что программно эту головоломку можно несколькими вариантами решить, но чтоб столько... А насколько реально самому такое кол-во решений найти?

При знании соответсвующей теории - джае доказать, что это именно ВСЕ решения - обычный вопрос на экзамене. Даже не на засыпку...
   
US Сергей-4030 #07.02.2008 18:22  @GOGI#07.02.2008 17:58
+
-
edit
 

Сергей-4030

исключающий третье
★★
GOGI> А что такое NP-полная? :-)
GOGI> А у человека еще и неалгоритмизируемые методы поиска решения есть :-)

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

PS Строго говоря, какая-то вероятность решения в первый, допустим, час, конечно, есть. Но не очень большая.
   
US Сергей-4030 #07.02.2008 18:24  @Владимир Малюх#07.02.2008 18:17
+
-
edit
 

Сергей-4030

исключающий третье
★★
AGRESSOR>> 92 решения?! Обалдеть! Я подозревал, что программно эту головоломку можно несколькими вариантами решить, но чтоб столько... А насколько реально самому такое кол-во решений найти?
В.М.> При знании соответсвующей теории - джае доказать, что это именно ВСЕ решения - обычный вопрос на экзамене. Даже не на засыпку...

Боюсь, в данном случае, вы неправы. ;) Комбинаторика-комбинаторикой, а сколько из "комбинаторных" решений валидны - тут комбинаторика не поможет. А еще ведь вращения/отражения...
   
RU Владимир Малюх #07.02.2008 18:30
+
-
edit
 

Владимир Малюх

аксакал
★★☆
Эээ, конечно, за 25 лет возни с сопроматами и прочими ТММ и САПР я мог и подзабыть, на задача про ферзи у нас в школе явно была и впрограмме и в экзамене на первой сессии. Я даже помню, кому из одноклассников она попалась в билете... Он, везунчик, ничго больше и не знал :) Может ферзей было не 8, да вроде нет - классика же..
   
Это сообщение редактировалось 07.02.2008 в 18:47
1 2 3 4

в начало страницы | новое
Форумы » Клуб » Радости жизни » Головоломка
Copyright © Balancer 1997..2021
Создано 17.12.2006
Связь с владельцами и администрацией сайта: anonisimov@gmail.com, rwasp1957@yandex.ru и admin@balancer.ru.
 
Поиск
Настройки
Твиттер сайта
Статистика
Рейтинг@Mail.ru