VPF::Задача о 8 ферзях - Форум программистов

Kuvaldis

Дата 26.7.2006, 13:36 (ссылка)

(нет голосов)

Загрузка ...

механик-вредитель

Профиль
Группа: Участник Клуба
Сообщений: 1189
Регистрация: 16.6.2006
Где: Минск

Репутация: 1
Всего: 61

Небезызвесная задача о расстановке 8 ферзей на шахтатной доске так, чтобы они не били друг друга.
Всего существует 92 решения. Но основных из них 12. Остальные получаются из них при помощи симметрии (центральной, осевой и т.д.) Нигде в нете не удалось найти решение данной задачи для этих 12 расстановок. у меня есть очевидное решение: идет генерация ВСЕХ 92 решений и последующая проверка на симметрию с сохраненными предыдущими решениями.

Вопрос: можно ли этот процесс каким либо образом оптимизировать. буду рад в том числе и математическому обоснованию.

Заранее спасибо.

--------------------

Помни - когда ты спишь, враг не дремлет
Спи чаще и дольше, изматывай врага бессоницей

nostromo

Дата 26.7.2006, 14:53 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 194
Регистрация: 23.3.2006

Репутация: 5
Всего: 10

На мой взгляд, в данном конкретном случае оптимизировать совершенно незачем --- число проверок равно C(92, 2)=4186 --- т.е. совсем небольшое.
Однако поиск решений можно оптимизировать, если вести перебор с оглядкой на симметрию. Например, выдвинув предположения:
- количество ферзей в нижней половине доски не меньше четырех;
- количество ферзей в левой половине доски не меньше четырех.

Замечу, что эти предположения сделаны лишь с учетом того, что нас интересуют решения с точностью до симметрий и не учитывают никакой специфики задачи (вместо ферзей можно, например, расставлять королей).

--------------------

На пыльных тропинках далеких планет останутся наши следы.

Fin

Дата 26.7.2006, 15:42 (ссылка)

(нет голосов)

Загрузка ...

Дракон->Спать();

Профиль
Группа: Участник
Сообщений: 687
Регистрация: 4.1.2006

Репутация: 1
Всего: 10

Kuvaldis, Я как то делал программу на нахождение всех комбинаций. Вроде она давала 96 решений. Но в принципе можно покапаться в архиве и уточнить точное значение. Кстати, как ты вышел на цифру 12? Вроде 92 не делется на 12 нацело. Хотя по логике должно.

--------------------

Пролетал мимо.

Akina

Дата 26.7.2006, 17:34 (ссылка)

(нет голосов)

Загрузка ...

Советчик

Профиль
Группа: Модератор
Сообщений: 20581
Регистрация: 8.4.2004
Где: Зеленоград

Репутация: 20
Всего: 454

Цитата(nostromo @ 26.7.2006, 15:53

)

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

Вообще-то более чем очевидно - ибо на каждой вертикали (горизонтали) может быть только 1 ферзь...

--------------------

О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума.

nostromo

Дата 26.7.2006, 17:38 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 194
Регистрация: 23.3.2006

Репутация: 5
Всего: 10

Цитата

Вроде 92 не делется на 12 нацело. Хотя по логике должно.

Не должно.
Например, число способов раскраски каждой стороны квадрата в один из двух цветов равно 16. А с учетом вращений --- 6.
Это определяется теоремой <забыл кого> и связано с порядком подгрупп допустимых преобразований.

Добавлено @ 17:43

Цитата

Вообще-то более чем очевидно - ибо на каждой вертикали (горизонтали) может быть только 1 ферзь...

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

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

--------------------

На пыльных тропинках далеких планет останутся наши следы.

Kuvaldis

Дата 26.7.2006, 19:14 (ссылка)

(нет голосов)

Загрузка ...

механик-вредитель

Профиль
Группа: Участник Клуба
Сообщений: 1189
Регистрация: 16.6.2006
Где: Минск

Репутация: 1
Всего: 61

Цитата

Вот код программы. Она герерирует не все 92 а только 74 варианта. Т.е. оптимизация к сожалению не хорошая.

int Queen_Virt(int n) - классическая функция из книги Вирта "Алгоритмы и структуры данных"

int Queen_Virt_optim(int n) - "оптимизированная"

Код


//---------------------------------------------------------------------------
#include <iostream>
#include <conio.h>
using namespace std;
//---------------------------------------------------------------------------
#pragma hdrstop
#pragma argsused
//---------------------------------------------------------------------------
const int  CELL_X_SIZE = 3;
const int  CELL_Y_SIZE = 4;
const int  SIZE = 8;
const int  DIAG = SIZE * SIZE - 1;
const char SYM = '\2';
const int  NEW_COL = 12;
const int  OLD_COL = 15;
//---------------------------------------------------------------------------
int chess_field[SIZE][SIZE] = {0};
int a[SIZE] = {0};    // ãîðèçîíòàëü

int b[DIAG] = {0};    // 45 äèàãîíàëü
int c[DIAG] = {0};    // 135 äèàãîíàëü
//---------------------------------------------------------------------------
void Init(void);
void DrawBoard();
void DrawCell(int color);
int Queen_Virt(int n);
int Queen_Virt_optim(int n);
//---------------------------------------------------------------------------
int main(int argc, char* argv[])
{
    int  count;

    count = Queen_Virt_optim(SIZE); 
   // count = Queen_Virt(SIZE);
    printf("\nTOTAL: %d combinations\n", count);
    getch();
    return 0;
}
//---------------------------------------------------------------------------
int Queen_Virt_optim(int n)
{
    static int count = 0;
    static int d1 = 0;      // для подсчета под главной диагональю
    static int d2 = 0;     // для подсчета под побочной диагональю
    int i = SIZE - n;

    for (int j = 0; j < SIZE; j++)
    {
       if ((a[j] == 0) &&  (b[i + j] == 0) && (c[j - i + 2] == 0))
       {
          a[j] = 1;
          b[i + j] = 1;
          c[j - i + 2] = 1;
          chess_field[i][j] = 1;
          
          if(i > j)
             d1++;
          if(j > (SIZE - i - 1))
            d2++;

          if(n  > 1)
             Queen_Virt_optim(n - 1);
          else
          {
             if((d1 >= 4) && (d2 >= 4))
             {
                DrawBoard();
                printf("\n%d combination\n", ++count);
               // getch();
                clrscr();
                d1 = d2 = 0;
             }   
          }
          a[j] = 0;
          b[i + j] = 0;
          c[j - i + 2] = 0;
          chess_field[i][j] = 0;
       }
    }

    return count;
}

//---------------------------------------------------------------------------
int Queen_Virt(int n)
{
    static int count = 0;
    int i = SIZE - n;

    for (int j = 0; j < SIZE; j++)
    {
       if ((a[j] == 0) &&  (b[i + j] == 0) && (c[j - i + 2] == 0))
       {
          a[j] = 1;
          b[i + j] = 1;
          c[j - i + 2] = 1;
          chess_field[i][j] = 1;
          if(n  > 1)
             Queen_Virt(n - 1);
          else
          {
             DrawBoard();
             printf("\n%d combination\n", ++count);
       //      getch();
             clrscr();
          }
          a[j] = 0;
          b[i + j] = 0;
          c[j - i + 2] = 0;
          chess_field[i][j] = 0;
       }
    }

    return count;
}
//---------------------------------------------------------------------------
void Init(void)
{
    clrscr();
    gotoxy(1, 1);
    for(int i = 0; i < SIZE; i++)
        for (int j = 0; j < SIZE; j++)
           chess_field[i][j] = 0;    
    return;
}
//---------------------------------------------------------------------------
void DrawBoard()
{
    int x = wherex();
    int y = wherey();
    int color;

    for (int i = 0; i < SIZE; i++)
    {
        for (int j = 0; j < SIZE; j++)
        {
           color = ( chess_field[i][j] ? NEW_COL : OLD_COL );
           DrawCell(color);
           x += 3 + CELL_X_SIZE;  // 1 - for gap
           gotoxy(x, y);
        }
        x = 1;
        y += 1 + CELL_Y_SIZE;  // 1 - for gap
        gotoxy(x, y);
    }

    return;
}
//---------------------------------------------------------------------------
void DrawCell(int color)
{
    int x = wherex();
    int y = wherey();

    textcolor(color);
    for (int i = 0; i < CELL_X_SIZE; i++)
    {
       for (int j = 0; j < CELL_Y_SIZE; j++)
          cprintf("%c", SYM);
       gotoxy(x, ++y);
    }

    return;
}
//---------------------------------------------------------------------------

Я тут еще подумал о следующем.
Если я не ошибаюсь, то любое размещение ОДНОЗНАЧНО определяется положением первого поставленного ферзя. Если его ставить в 1/8 часть доски: между главной диагональю до середины и вертикальной осью симметрии, то как раз и будут эти 12 вариантов. Но... кардинально меняется алгоритм. Извилин не хватает его реализовать.

--------------------

Помни - когда ты спишь, враг не дремлет
Спи чаще и дольше, изматывай врага бессоницей

Akina

Дата 26.7.2006, 20:01 (ссылка)

(нет голосов)

Загрузка ...

Советчик

Профиль
Группа: Модератор
Сообщений: 20581
Регистрация: 8.4.2004
Где: Зеленоград

Репутация: 20
Всего: 454

http://forum.vingrad.ru/index.php?showtopic=75536
http://forum.vingrad.ru/index.php?showtopic=72136

а искать по Инету я даже не пытался - ну просто потому что.

PS. Оптимизация ради оптимизации мне представляется занятием менее чем осмысленным. А цели не видать... разве что вместо

Цитата(Kuvaldis @ 26.7.2006, 14:36

)

очевидное решение: идет генерация ВСЕХ 92 решений и последующая проверка на симметрию с сохраненными предыдущими решениями

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

--------------------

Kuvaldis

Дата 26.7.2006, 21:30 (ссылка)

(нет голосов)

Загрузка ...

механик-вредитель

Профиль
Группа: Участник Клуба
Сообщений: 1189
Регистрация: 16.6.2006
Где: Минск

Репутация: 1
Всего: 61

Цитата

PS. Оптимизация ради оптимизации мне представляется занятием менее чем осмысленным. А цели не видать...

Представим, что у нас доска не 8 х 8, а 200 х 200 , т.е. смысл есть (для чего, в принципе, все и делается)

Цитата

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

Т.е. я нашел вариант, прокрутил все возможные симметрии. Но.. все равно придется дедовским способом генерировать остальные 92 варианта (чтобы ничего не пропустить). Или я не прав? Т.Е. выигрыш маленький

Как найти следующее базовое решение? В этом смысл.

Еще более пристально порылся в нете.

Вот цитата из книги "Шахматы и математика"

Цитата

Известно много способов организовать эффективный поиск расположения восьми мирных ферзей (методы Пермантье, Ла-Ное, Гюнтера, Глэшера, Лакьера и др.). Эти способы описаны в многочисленной литературе по занимательной математике. В наш век ЭВМ задача такого сорта не вызвала бы столь живой интерес. Ведь достаточно составить несложную программу, и уже через несколько минут после ее введения в машину все 92 необходимые позиции будут выданы на печать.

Из каждого решения задачи о ферзях можно получить ряд других при помощи поворотов (вращений) доски на 90, 180 и 270°, а также при ее зеркальном отражении относительно линий, разделяющих доску пополам1. Например, из расстановки, показанной на рис. 34,а, при повороте доски на 90° по часовой стрелке мы получаем расстановку на рис. 34,в, а при отражении доски относительно линии, разделяющей королевский и ферзевый фланги, — на рис. 34,г. При помощи других поворотов и отражений доски можно получить еще пять решений.

Итак, указанные операции с шахматной доской позволяют из одного расположения мирных ферзей получить, вообще говоря, семь новых. Доказано, что в общем случае на доске nґn (при n > 1) для любой расстановки п мирных ферзей возможны три ситуации: 1) при одном отражении доски возникает новая расстановка ферзей, а при поворотах и других отражениях новых решений не получается; 2) новое решение возникает при повороте доски на 90°, а ее отражения дают еще две расстановки; 3) три поворота доски и четыре отражения приводят к семи различным расстановкам (а если считать и исходную, то всего имеем восемь позиций).

В случае 1) исходное решение называется дважды симметрическим, в случае 2) — симметрическим, а в случае 3) — простым. Для обычной доски каждое решение является либо простым, либо симметрическим, а дважды симметрических не существует.

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

методы Пермантье, Ла-Ное, Гюнтера, Глэшера, Лакьера - про них нигде нет.

Добавлено @ 21:39

Цитата

http://forum.vingrad.ru/index.php?showtopic=75536
http://forum.vingrad.ru/index.php?showtopic=72136

C этого я и начал, но там нет ответа на мой вопрос (там решение в лоб)

--------------------

Помни - когда ты спишь, враг не дремлет
Спи чаще и дольше, изматывай врага бессоницей

Fin

Дата 26.7.2006, 23:30 (ссылка)

(нет голосов)

Загрузка ...

Дракон->Спать();

Профиль
Группа: Участник
Сообщений: 687
Регистрация: 4.1.2006

Репутация: 1
Всего: 10

Вот нашел в архивах свое решение этой задачи smile

Она быстренько генерирует все 92 решения. Оказывается я плохо помню, какие результаты были лет пять назад smile

Код


#include <stdio.h>
#include <stdlib.h>

#define MAXPOLE 8

int pole[MAXPOLE];
int count=0;
bool check(int beg)
{
    bool res=true;
    if (beg>=1)
    {
        int i=0;
        while (res &&  (i<beg))
        {
            if (pole[i] == pole[beg]) res=false;
            if (abs(pole[beg]-pole[i]) == abs(beg-i)) res=false;
            i++;
        }
    }
    return res;
}

void print(int beg)
{
    printf("----------- %02d ------------\n",count);
    printf("    A  B  C  D  E  F  G  H \n");
    for(int y=0; y<beg; y++)
    {
        printf("%d  ",y+1);
        for(int x=0; x<MAXPOLE; x++)
        {
            if (x== pole[y]) printf(" F ");
                else printf(" * ");
        }
        printf("\n");
    }
    printf("---------------------------\n");
}

int main()
{
    int beg=0;
    pole[beg]=-1;
    while (beg>=0)
    {
        pole[beg]++;
        if (pole[beg] == MAXPOLE)  beg--;
        else
        {
            if (check(beg))
            {
                beg++;
                if (beg==MAXPOLE) 
                {
                    count++;
                    print(MAXPOLE);
                    beg--;
                }
                else pole[beg]=-1;
            }
        }
        
        
    }    
    //printf("%d \n", count);    
    return 0;
}

--------------------

Пролетал мимо.

Fin

Дата 26.7.2006, 23:46 (ссылка)

(нет голосов)

Загрузка ...

Дракон->Спать();

Профиль
Группа: Участник
Сообщений: 687
Регистрация: 4.1.2006

Репутация: 1
Всего: 10

Я дальше тогда не стал делать оптимизацию, чтобы выкинуть все сеиметричные решения. Но были такие мысли. У меня поле представлено 8 числами от 0 и до 7. В принципе комбинацию можно свести в 24 битовое число. Все комбинации свести в массив чисел. Сделать подпрограмму поворачиваюшую комбинацию на 90 градусов и делаюшую зеркалку. Потом только останется делать перебор всех симетричных комбинаций.
Но это только мысли. Не проверял.

Это сообщение отредактировал(а) Fin - 26.7.2006, 23:58

--------------------

Пролетал мимо.

nostromo

Дата 27.7.2006, 08:47 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 194
Регистрация: 23.3.2006

Репутация: 5
Всего: 10

Цитата

Вот код программы. Она герерирует не все 92 а только 74 варианта. Т.е. оптимизация к сожалению не хорошая.

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

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

--------------------

На пыльных тропинках далеких планет останутся наши следы.

Kuvaldis

Дата 28.7.2006, 02:12 (ссылка)

(нет голосов)

Загрузка ...

механик-вредитель

Профиль
Группа: Участник Клуба
Сообщений: 1189
Регистрация: 16.6.2006
Где: Минск

Репутация: 1
Всего: 61

Ну что, граждане? Достаточно серьезная задачка?
На русском языке я ничего не нашел, но на буржуйском кое-что smile

... быстрый алгоритм без поиска с возвращением на основе градиентной эвристики (мой перевод)
Кого заинтересовало, смотри ссылкуФерзи

--------------------

Помни - когда ты спишь, враг не дремлет
Спи чаще и дольше, изматывай врага бессоницей

nostromo

Дата 28.7.2006, 08:47 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 194
Регистрация: 23.3.2006

Репутация: 5
Всего: 10

Цитата

Ну что, граждане? Достаточно серьезная задачка?

Неплохо было бы, собственно, увидеть постановку задачи.
Непонятно, что Вас интересует:
- алгоритм выделения решений с точностью до симметрии среди всех решений;
- алгоритм поиска всех решений для доски 8х8;
- алгоритм поиска всех решений для досок больших размеров;
- алгоритм поиска некоторых решений для досок очень больших размеров (~500000 ферзей).

--------------------

На пыльных тропинках далеких планет останутся наши следы.

Kuvaldis

Дата 28.7.2006, 12:45 (ссылка)

(нет голосов)

Загрузка ...

механик-вредитель

Профиль
Группа: Участник Клуба
Сообщений: 1189
Регистрация: 16.6.2006
Где: Минск

Репутация: 1
Всего: 61

Цитата

Непонятно, что Вас интересует:
- алгоритм выделения решений с точностью до симметрии среди всех решений;
- алгоритм поиска всех решений для доски 8х8;
- алгоритм поиска всех решений для досок больших размеров;
- алгоритм поиска некоторых решений для досок очень больших размеров (~500000 ферзей).

Хотелось найти алгоритм выделения симметричных решений для генерации всех остальных, так как для больших досок поиск всех решений при помощи backtracking не является эффективным. Но, оказывается (см. ссылку) все решения можно найти более быстро. А тогда симметричные выделяются простым, обычным отбором.

--------------------

Помни - когда ты спишь, враг не дремлет
Спи чаще и дольше, изматывай врага бессоницей

nostromo

Дата 28.7.2006, 12:52 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 194
Регистрация: 23.3.2006

Репутация: 5
Всего: 10

Цитата

Но, оказывается (см. ссылку) все решения можно найти более быстро.

И где там написано, что они находят все решения?

--------------------

На пыльных тропинках далеких планет останутся наши следы.

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Алгоритмы \| Следующая тема »