VPF::[C++] Расстановка 12 коней - Форум программистов

TuttiFrutti

Дата 17.11.2006, 20:48 (ссылка)

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

Загрузка ...

Новичок

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

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

Ребята,уважаемые кодеры,не могу решить зада4у,кто 4ем может помогите!!!
...Зада4а:Написать программу, 4тобы пк расставил 12 коней на шахматной доске так,чтобы все клетки были под ударом.(клетки,занятые конями не с4итать)
Вот,4то я нарешал.Использовал функцию слу4айных 4исел,для определения координат каждогог из 12 коней,но как вы сами понимаете, вероятность того ,4то совпадет нужная расстановка о4ень мала,тем более random функция повторяет присвояемые зна4ения.Help....help....help!!!
Мой код:

Код


void main()
{
    int Chess[8][8];
    int m = 0;
    bool ok = false;
    for ( int i = 0;i<8; i++)
    {
        for(int j = 0;j<8;j++)
        {
            Chess[i][j] = 0;
            cout<< Chess[i][j];
        };
        cout<<endl;
    };


    while (!ok) // пока правильно не расставим
    {
        for (int i=0, j = 0,k =0; k<12;k++)
        {
            i=rand()%7;
            j=rand()%7;
            if    (Chess[i][j] == 2) // если клетка уже двойка то как прошлого коня
                k--;
            else
                Chess[i][j] = 2;
            if(Chess[i-2][j-1]!=2)
            {
                Chess[i-2][j-1]=1;
            };
            if(Chess[i-2][j+1]!=2)
            {
                Chess[i-2][j+1]=1;
            };
            if(Chess[i+2][j-1]!=2)
            {
                Chess[i+2][j-1]=1;
            };
            if(Chess[i+2][j+1]!=2)
            {
                Chess[i+2][j+1]=1;
            };
            if(Chess[i-1][j-2]!=2)
            {
                Chess[i-1][j-2]=1;
            };
            if(Chess[i-1][j+2]!=2)
            {
                Chess[i-1][j+2]=1;
            };
            if(Chess[i+1][j-2]!=2)
            {
                Chess[i+1][j-2]=1;
            };
            if(Chess[i+1][j+2]!=2)
            {
                Chess[i+1][j+2]=1;
            };
        };
        for(int i=0; i<8; i++)
        {
            for(int j=0; j<8; j++)
            {
                m += Chess[i][j];
            };
        };
        cout<<endl;
        if (m==76) // если сумма клеток 76 (12 двоек остальные единицы) то выводим
        {
            cout<<endl;
            for(int i=0; i<8; i++)
            {
                for(int j=0; j<8; j++)
                {
                    cout<<Chess[i][j]<<" " ;
                };
                cout<<endl;
            };    
            ok = !ok; // говорим что удалось, больше цикл не будет крутиться
        }
        else
        {
            for ( int i = 0;i<8; i++) // если сумма не равна обнуляем всё
            {
                for(int j = 0;j<8;j++)
                {
                    Chess[i][j] = 0;
                    cout<< Chess[i][j];
                };
                cout<<endl;
            };
            m = 0;
        };
    };
};

maxim1000

Дата 17.11.2006, 21:49 (ссылка)

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

Загрузка ...

Эксперт

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

Репутация: 24
Всего: 110

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

полный перебор будет порядка 64^12, но можно сделать несколько шагов по оптимизации:
1. отдельно решать задачу для белых клеток и для чёрных, т.к. они независимы, это приведет к 2*(32^6), что уже неплохо
2. прекращать просмотр ветки, если количество оставшихся безопасных клеток меньше, чем количество коней*8 (т.к. конь не может бить больше 8 клеток) - на сколько это ускорит не знаю, возможно, стоит делать это отсечение более "интеллектуально"

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

qqq

Dov

Дата 17.11.2006, 22:20 (ссылка)

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

Загрузка ...

аСинизатор

Профиль
Группа: Завсегдатай
Сообщений: 1721
Регистрация: 10.5.2003
Где: Эрец-Исраэль

Репутация: 50
Всего: 88

TuttiFrutti, пойди в алгоритмы, там эта задача точно есть. Я лично мучился, переводил с паскаля, абсолютно им не владея, на С++. smile

Ладно, вот я уже сам нашёл.12 коней

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

Тут вечности запах томительный,
И свежие фрукты дешевые,
А климат у нас – изумительный,
И только соседи – #уевые.
Игорь Губерман.

TuttiFrutti

Дата 18.11.2006, 12:42 (ссылка)

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

Загрузка ...

Новичок

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

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

maxim1000, вам спасибо за содействие..попробую сам написать, у4тя советы!
Dov, спасибо!!!...все работает!...я спасен!

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