Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > Центр помощи > [C++] Расстановка 12 коней


Автор: TuttiFrutti 17.11.2006, 20:48
Ребята,уважаемые кодеры,не могу решить зада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
перебором можно
для примера можно посмотреть задачу расстановки ферзей на доске так, чтобы они друг друга не били

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

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

Ладно, вот я уже сам нашёл.http://forum.vingrad.ru/topic-85228/hl/%25D0%25BA%25D0%25BE%25D0%25BD%25D0%25B5%25D0%25B9/20.html

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

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