Обсуждение:Задача о восьми ферзях

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

Поленились товарищи и не описали алгоритм, скажем с использованием С/С++.

Во-первых, пожалуйста, подписывайтесь в обсуждениях.
Во-вторых — Вы тоже поленились. Правьте смело! --dm обсужд. 07:24, 27 апреля 2010 (UTC)[ответить]
Пожалуйста на Си:
 # include <stdio.h>
# include <math.h>
main()
{ int a,b,c,d,e,f,g,h,i,q ;
   int m0,m1,m2,m3,m4,m5,m6,m7,m8;
 i=0;
  a=0;
 m0: b=0;
  ++a;
 if(a==9)
     goto m8;
 m1:c=0;
       ++b;
  if(b==9)     
     goto m0 ;
  if(b==a)
     goto m1;
  if (fabs(b-a)==1)
     goto m1;
 m2:d=0;
 ++c;
  if (c==9)
     goto m1;
  if (c==a || c==b)
     goto m2;
  if(fabs(c-b)==1 || fabs(c-a)==2)
     goto m2;
m3:e=0;
++d;
  if (d==9)
     goto m2;
  if (d==a || d==b || d==c)
    goto m3;
  if (fabs(d-a)==3 || fabs(d-b)==2 || fabs(d-c)==1)
   goto m3;
m4:f=0;
 ++e;
  if (e==9)
   goto m3;
  if (e==a || e==b || e==c || e==d)
   goto m4;
  if (fabs(e-d)==1 || fabs(e-c)== 2 || fabs (e-b)==3 || fabs(e-a)==4)
  goto m4;
m5:g=0;
 ++f;
  if (f==9)
   goto m4;
  if (f==a || f==b || f==c || f==d || f==e)
    goto m5;
if (fabs(f-e)==1 || fabs(f-d)==2 || fabs(f-c)==3 || fabs(f-b)==4 || fabs(f-a)==5)
    goto m5;
m6:h=0;
++g;
   if (g==9)
   goto m5;
 if (g==a || g==b || g==c || g==d || g==e || g==f)
   goto m6;
 if (fabs(g-f)==1 || fabs(g-e)==2 || fabs(g-d)==3 || fabs(g-c)==4 || fabs(g-b)==5 )
   goto m6;
 if (fabs(g-a)==6)
 goto m6;
m7:++h;
 if (h==9)
  goto m6;
 if (h==a || h==b || h==c || h==d || h==e || h==f || h==g)
  goto m7;
 if (fabs(h-g)==1 || fabs(h-f)==2 || fabs(h-e)==3 || fabs(h-d)==4 || fabs(h-c)==5)
   goto m7;
  if (fabs(h-b)==6 || fabs(h-a)==7)
   goto m7;
    ++i;
 printf(" %d",i);
 printf(":");
      printf("%d%d%d%d%d%d%d%d",a,b,c,d,e,f,g,h);
      printf(";");
      goto m7;
     m8:   q= getchar();
 }

Правда пятёрку за такую программу не поставят-ведь в ней goto.
alex62.148.136.45 16:25, 4 января 2011 (UTC)[ответить]

         Но это только демонстрация метода перебора с возвратом.

Этот алгоритм можно записать компактно и обобщить на любое n. 

Результат записывается в файл,который создаётся в той же папке,

где находится данная программа(FileEditor). Чтобы его увидеть, нужно выбрать All files(“.”). 


# include <stdio.h>
# include <math.h>
 
  main()
     
     { int k,n,j;
    int m1,m2,m3,m4;
    long i; 
    char filename [15];
    printf(" Input filename with .dat");
    scanf("%s",filename);
    FILE*fp;
       fp =fopen(filename,"w");
    printf("n=");   
    scanf("%d",&n);
         int y[n+1];
    k=0;
    j=0;
    i=0;
  m1:k=k+1;
  y[k]=0;
   if(k==n+1)
   goto m2;
       m3:  y[k]=y[k]+1;
      if(y[1]==n+1)
    goto m4;
    if (y[k]==n+1){
     y[k]=0;
     k=k-1;
     goto m3;}
        for(j=1;j<k;++j){
        if(y[j]==y[k] || fabs(y[k]-y[j])==k-j)
    goto m3;}
    goto m1;
     m2:i=i+1;
    
     fprintf(fp,"%d",i);
    fprintf(fp,":");
    for(j=1;j<n+1;++j){
    fprintf(fp,"%d",y[j]);
     fprintf(fp," ");}
     fprintf(fp,"\n ");
                       
    k=k-1;
    goto m3;
   
     m4: fclose(fp);
         
    }

86.110.166.46 05:45, 18 июня 2011 (UTC) Alex[ответить]

Сопредельная задача

[править код]

Есть N² ферзей N различных цветов, по N ферзей каждого цвета. Сколькими способами можно расставить все эти ферзи на шахматной доске NxN таким образом, что ферзи одного цвета друг друга не бьют?

Что известно об этой задаче? Я знаю только то, что для нечётных простых N есть как минимум N-3 решений (без учёта N! перестановок цветов). -Тальмон Сильвер-62.219.167.60 21:26, 28 января 2011 (UTC)[ответить] 

  Действительно,для доски 7*7 имеем 4-е группы позиций,
 заполняющих всю доску.Для доски 11*11 их восемь.Для до-
 сок 8*8,9*9 и 10*10 таких групп не обнаружено.

 Для доски 7*7 имеем 40 позиций для 7-и ферзей не атакую-
 щих друг друга. 
 Вот группы позиций ,заполняющих всю доску.
                                
1  3  5  7  2  4  6 
2  4  6  1  3  5  7 
3  5  7  2  4  6  1 
4  6  1  3  5  7  2 
5  7  2  4  6  1  3 
6  1  3  5  7  2  4 
7  2  4  6  1  3  5 
                                   
1  4  7  3  6  2  5 
2  5  1  4  7  3  6 
3  6  2  5  1  4  7 
4  7  3  6  2  5  1 
5  1  4  7  3  6  2 
6  2  5  1  4  7  3 
7  3  6  2  5  1  4 
                                   
1  5  2  6  3  7  4 
2  6  3  7  4  1  5 
3  7  4  1  5  2  6 
4  1  5  2  6  3  7 
5  2  6  3  7  4  1 
6  3  7  4  1  5  2 
7  4  1  5  2  6  3 
                                   
1  6  4  2  7  5  3 
2  7  5  3  1  6  4 
3  1  6  4  2  7  5 
4  2  7  5  3  1  6 
5  3  1  6  4  2  7 
6  4  2  7  5  3  1 
7  5  3  1  6  4  2 

Для доски 11*11 имеется 2680 позиций
11 -и ферзей не бьющих друг друга.
Вот 8-мь групп этих позиций,заполняющих всю доску.                                   
1 
1  3  5  7  9  11  2  4  6  8  10 
2  4  6  8  10  1  3  5  7  9  11 
3  5  7  9  11  2  4  6  8  10  1 
4  6  8  10  1  3  5  7  9  11  2 
5  7  9  11  2  4  6  8  10  1  3 
6  8  10  1  3  5  7  9  11  2  4 
7  9  11  2  4  6  8  10  1  3  5 
8  10  1  3  5  7  9  11  2  4  6 
9  11  2  4  6  8  10  1  3  5  7 
10  1  3  5  7  9  11  2  4  6  8 
11  2  4  6  8  10  1  3  5  7  9 
                                   
2 
1  4  7  10  2  5  8  11  3  6  9 
2  5  8  11  3  6  9  1  4  7  10 
3  6  9  1  4  7  10  2  5  8  11 
4  7  10  2  5  8  11  3  6  9  1 
5  8  11  3  6  9  1  4  7  10  2 
6  9  1  4  7  10  2  5  8  11  3 
7  10  2  5  8  11  3  6  9  1  4 
8  11  3  6  9  1  4  7  10  2  5 
9  1  4  7  10  2  5  8  11  3  6 
10  2  5  8  11  3  6  9  1  4  7 
11  3  6  9  1  4  7  10  2  5  8 
                                   
3 
1  5  9  2  6  10  3  7  11  4  8 
2  6  10  3  7  11  4  8  1  5  9 
3  7  11  4  8  1  5  9  2  6  10 
4  8  1  5  9  2  6  10  3  7  11 
5  9  2  6  10  3  7  11  4  8  1 
6  10  3  7  11  4  8  1  5  9  2 
7  11  4  8  1  5  9  2  6  10  3 
8  1  5  9  2  6  10  3  7  11  4 
9  2  6  10  3  7  11  4  8  1  5 
10  3  7  11  4  8  1  5  9  2  6 
11  4  8  1  5  9  2  6  10  3  7 
                                   
4 
1  6  11  5  10  4  9  3  8  2  7 
2  7  1  6  11  5  10  4  9  3  8 
3  8  2  7  1  6  11  5  10  4  9 
4  9  3  8  2  7  1  6  11  5  10 
5  10  4  9  3  8  2  7  1  6  11 
6  11  5  10  4  9  3  8  2  7  1 
7  1  6  11  5  10  4  9  3  8  2 
8  2  7  1  6  11  5  10  4  9  3 
9  3  8  2  7  1  6  11  5  10  4 
10  4  9  3  8  2  7  1  6  11  5 
11  5  10  4  9  3  8  2  7  1  6 
                                   
5 
1  7  2  8  3  9  4  10  5  11  6 
2  8  3  9  4  10  5  11  6  1  7 
3  9  4  10  5  11  6  1  7  2  8 
4  10  5  11  6  1  7  2  8  3  9 
5  11  6  1  7  2  8  3  9  4  10 
6  1  7  2  8  3  9  4  10  5  11 
7  2  8  3  9  4  10  5  11  6  1 
8  3  9  4  10  5  11  6  1  7  2 
9  4  10  5  11  6  1  7  2  8  3 
10  5  11  6  1  7  2  8  3  9  4 
11  6  1  7  2  8  3  9  4  10  5 
                                   
6 
1  8  4  11  7  3  10  6  2  9  5 
2  9  5  1  8  4  11  7  3  10  6 
3  10  6  2  9  5  1  8  4  11  7 
4  11  7  3  10  6  2  9  5  1  8 
5  1  8  4  11  7  3  10  6  2  9 
6  2  9  5  1  8  4  11  7  3  10 
7  3  10  6  2  9  5  1  8  4  11 
8  4  11  7  3  10  6  2  9  5  1 
9  5  1  8  4  11  7  3  10  6  2 
10  6  2  9  5  1  8  4  11  7  3 
11  7  3  10  6  2  9  5  1  8  4 
                                   
7 
1  9  6  3  11  8  5  2  10  7  4 
2  10  7  4  1  9  6  3  11  8  5 
3  11  8  5  2  10  7  4  1  9  6 
4  1  9  6  3  11  8  5  2  10  7 
5  2  10  7  4  1  9  6  3  11  8 
6  3  11  8  5  2  10  7  4  1  9 
7  4  1  9  6  3  11  8  5  2  10 
8  5  2  10  7  4  1  9  6  3  11 
9  6  3  11  8  5  2  10  7  4  1 
10  7  4  1  9  6  3  11  8  5  2 
11  8  5  2  10  7  4  1  9  6  3 
                                   
8 
1  10  8  6  4  2  11  9  7  5  3 
2  11  9  7  5  3  1  10  8  6  4 
3  1  10  8  6  4  2  11  9  7  5 
4  2  11  9  7  5  3  1  10  8  6 
5  3  1  10  8  6  4  2  11  9  7 
6  4  2  11  9  7  5  3  1  10  8 
7  5  3  1  10  8  6  4  2  11  9 
8  6  4  2  11  9  7  5  3  1  10 
9  7  5  3  1  10  8  6  4  2  11 
10  8  6  4  2  11  9  7  5  3  1 
11  9  7  5  3  1  10  8  6  4  2 
                                   
В принципе ещё можно найти такие группы
для доски 13*13,но для дальнейших расчётов время
будет слишком большим.
Интересно,что и диагонали (в первой и последней группах только одна)
представляют собой позиции из предыдущей и последующей групп.

Задача о максимальном числе комбинаций из 8 ферзей

[править код]

Я считаю, что максимальное число комбинаций из 8 ферзей- 196. Домин Яков Анастасия30399 (обс.) 13:07, 20 мая 2017 (UTC)[ответить]

Задача о максимальном числе комбинаций из 8 ферзей

[править код]

По вопросам о моем решении звонить на 84992005196 Анастасия30399 (обс.) 13:16, 20 мая 2017 (UTC)[ответить]

Класс задачи

[править код]

Любопытно, установлено ли, какая это задача? NP? NP-полная? NP-трудная?
217.107.126.124 16:12, 2 сентября 2017 (UTC)MichaelMM[ответить]

Частичное решение задачи для NxN

[править код]

Идея в том, что для досок, размерности которых есть число из ряда

2, 3, 8, 9, 14, 15, 20, 21, 26, 27, 32, 33, 38, 39, 44, 45, 50, 51, 56, 57, 62, 63, 68, 69, 74, 75, 80, 81, 86, 87, 92, 93, 98, 99, 104, 105, 110, 111, 116, 117, 122, 123, 128, 129, 134, 135, 140, 141, 146, 147, 152, 153, 158, 159, 164, 165, 170, 171, 176, 177, 182, 183 (http://oeis.org/A047243)

не возможно построение решения алгоритмом "Ступеньки". Алгоритм "Ступеньки" представляет из себя числовой ряд, который начинается из всех четных чисел и продолжается нечетными по возрастанию (2 4 6 8 10 1 3 5 7 9 для доски 10х10). Данное утверждение справедливо для всех досок, размер которых не вход в числовую последовательность A047243. Для проверки входит ли n в числовую последовательность A047243, необходимо разделить n на 6 и если остаток от деления равен 2 или 3, то однозначно нет решения для данной доски алгоритмом "Ступеньки". Ниже дан псевдокод.

if ((n mod 6) !== 2) AND ((n mod 6) !== 3) then 

    call horse_step_algo()

Пример: n = 2017 (2017x2017)

n mod 6 -> 2017 mod 6 = 1 - решение есть, 2 4 6 8 10 ..... 2016 1 3 5 7 9 ..... 2017

пс: Уточнение по поводу записи решения - 2 4 6 8 10 1 3 5 7 9 само число есть номер столбца, позиция числа в решении есть номер строки, 2 - второй столбец первая строка, 4 - 4 столбец вторая строка. 

Amanda Sproule (обс.) 21:25, 10 декабря 2017 (UTC)[ответить]

Неточность в количестве возможных комбинаций

[править код]

"и затем проверяя атаки по диагоналям, можно сократить число возможных расположений всего до 40 320 (то есть 8!)" - 8! является числом возможных комбинаций ДО проверки диагоналей а не после

Источник — https://ru.wikipedia.org/w/index.php?title=Обсуждение:Задача_о_восьми_ферзях&oldid=109466395