VPF::Обход любой доски шахматным конем

Диана

Дата 8.8.2005, 19:41 (ссылка)

(голосов: 0)

Загрузка ...

Unregistered

Программисты!
Помогите решить задачу( практика в универе)!

Написать программу, которая осуществляет обход любой доски MxN шахматным конем.

Я знаю языки С, С++, Pascal, а вот методы не практиковала. Надо, чтобы прога работала быстро и была красиво оформлена. Читала, что можно попробовать алгоритм поиска кратчайшего пути на графе, но о графах я не знаю ничего+ Преподаватель любит Visual C, который мы не изучали...
Вопрос в том, стоит ли мучать теорию графов и Visual C? На каком языке лучше писать, чтобы и красиво было(это ценится), и работало нормально?

Может, кто-то писал эту прогу и может поделиться кодом, если, конечно, не жаль...

Спасибо огромное!

Диана

Akina

Дата 8.8.2005, 20:52 (ссылка)

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

Загрузка ...

Советчик

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

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

Цитата

стоит ли мучать теорию графов

да

Цитата

и Visual C

не обязательно

Цитата

На каком языке лучше писать, чтобы и красиво было(это ценится), и работало нормально?

абсолютно все равно (не, только без фанатизма, Клиппер есссно отпадает).

Цитата

можно попробовать алгоритм поиска кратчайшего пути на графе

При чем тут кратчайший путь? у тебя же обход графа...

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

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

Guest

Дата 8.8.2005, 21:25 (ссылка)

(голосов: 0)

Загрузка ...

Unregistered

Спасибо, но про графы я только понаслышке знаю, поэтому ошиблась...

Не выходит прога у меня. smile

Даже простой вариант без интерфейса =>зависает комп... smile

Pakshin A. S.

Дата 8.8.2005, 21:42 (ссылка)

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

Загрузка ...

Эксперт

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

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

Рекурсивно идем по доске конем, перебирая возможные ходы... Впринцеве достаточно бытро пройдем до тупика... А каковы критерии завершения похода коня? smile

Akina

Дата 8.8.2005, 21:51 (ссылка)

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

Загрузка ...

Советчик

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

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

Цитата(Pakshin @ 8.8.2005, 22:42)

каковы критерии завершения похода коня?

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

Цитата(Pakshin @ 8.8.2005, 22:42)

Рекурсивно идем по доске конем, перебирая возможные ходы...

Глубина рекурсии = кол-ву полей, ширина = 8... не думаю что это будет быстро, особенно на больших досках... впрочем на больших досках как раз это скорее оптимум, несмотря на длину...

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

Pakshin A. S.

Дата 8.8.2005, 21:58 (ссылка)

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

Загрузка ...

Эксперт

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

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

Повеселиться что ли с рекурсией на досуге... smile

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

S.A.P.

Дата 8.8.2005, 22:02 (ссылка)

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

Загрузка ...

Эксперт

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

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

Где то видел теорию, там говориться, что надо ставить коня на поле, от куда можно сделать наименьшее количество ходов.

Амортизатор

Дата 8.8.2005, 22:04 (ссылка)

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

Загрузка ...

Опытный

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

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

ИМХО, если пользоваться грубым перебором, займет много времени. Нельзя ли разработать алгоритм, позволяющий отбрасывать на каждом шаге опр кол-во ходов?

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

Поехали!

Диана

Дата 8.8.2005, 23:02 (ссылка)

(голосов: 0)

Загрузка ...

Unregistered

Нужно обойти конем любое поле с заданной позиции.
Попасть в каждую клетку по одному разу. Не более.

Цитата

Это правило Варнсдорфа. Но работает (читала) на досках с 5х5 до 76х76 и когда ходить с углового поля.
Не подходит сюда.

Рекурсия отпадает- в тупик-то конь не зайдет, но долго очень думать будет, а если доска 100х200 - будет совсем весело. Тормоз.

Рекурсия-неплохо для обычной шахматной доски (типа олимпиадная задача для школьников).Тогда проблем нет. А то, что у меня... +интерфейс красивый... Переподаватель любит...

Akina

Дата 9.8.2005, 08:14 (ссылка)

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

Загрузка ...

Советчик

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

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

Цитата(Perchilla @ 8.8.2005, 23:02)

Это всего лишь эвристика. Которая, кстати, даже на поле 8*8 может загнать в тупик. Используется только для определения порядка перебора ходов в рекурсивном поиске (если стоИт задача найти хотя бы один путь, а не все возможные).

Цитата

Нельзя ли разработать алгоритм, позволяющий отбрасывать на каждом шаге опр кол-во ходов?

Нет, только конечные отсечения. Или частные случаи.

Цитата

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

В тупик - запросто. А слегка ускорить алгоритм можно проверкой количества возможных ходов с каждого из непройденных полей.

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

Snowy

Дата 9.8.2005, 08:57 (ссылка)

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

Загрузка ...

Эксперт

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

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

На algolib.narod.ru есть готовый исходняк на паскале.
Добавлено @ 09:01
Вот прямой линк на исходняк

AntonSaburov

Дата 9.8.2005, 11:04 (ссылка)

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

Загрузка ...

Штурман

Профиль
Группа: Модератор
Сообщений: 5658
Регистрация: 2.7.2002
Где: Санкт-Петербург

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

Цитата(Akina @ 9.8.2005, 08:14)

Эта эвристика работает на полях от 5х5 до 70х70 - я сам студентам такое даю.

Вот программа - у нас работает.

Код


#include <stdio.h>

#define M 10

int numberOfSteps(int x, int y, int A[M][M]);
void printArray(int A[M][M]);

int offset[8][2];

int main()
{
    int A[M][M];
    int steps[8];
    int x=0, y=0, count=1, idx=0;

    offset[0][0]= 2; offset[0][1]= 1; 
    offset[1][0]= 2; offset[1][1]=-1; 
    offset[2][0]= 1; offset[2][1]= 2;
    offset[3][0]= 1; offset[3][1]=-2; 
    offset[4][0]=-1; offset[4][1]= 2; 
    offset[5][0]=-1; offset[5][1]=-2;
    offset[6][0]=-2; offset[6][1]= 1; 
    offset[7][0]=-2; offset[7][1]=-1;

    for(int i=0;i<M;i++) {
        for(int j=0;j<M;j++) {
            A[i][j]=0;    
        }
    }

    A[x][y]=count;
    
    do {
        for(int k=0; k<8; k++) {
            steps[k]=numberOfSteps(x+offset[k][0], y+offset[k][1], A);
        }

        for(int k=0; k<8; k++) {
            if(steps[k]>0) {
                idx = k;
                break;
            }
            if(k==7) {
                for(int i=0; i<8; i++) {
                    if(steps[i]==0) {
                        A[x+offset[i][0]][y+offset[i][1]]=++count;
                    }
                }
                printArray(A);
                return 0;    
            }
        }

        for(int k=0; k<8; k++) {
            if(steps[k]<steps[idx] && steps[k]>0) {
                idx = k;
            }
        }
        
        x += offset[idx][0]; 
        y += offset[idx][1]; 
        A[x][y]=++count;
        
    } while(true);

    return 0;
}

int numberOfSteps(int x, int y, int A[M][M])
{
    if((x<0 || x>=M || y<0 || y>=M || A[x][y]!=0)) {
        return -1;
    }

    int count=0;
    for(int k=0; k<8; k++) {
        int xn=x+offset[k][0];
        int yn=y+offset[k][1];
        if(xn>=0 && xn<M && yn>=0 && yn<M && A[xn][yn]==0) {
            count++;
        }
    }
    
    return count;
}

void printArray(int A[M][M])
{
    for(int i=0;i<M;i++) {
        for(int j=0;j<M;j++) {
            printf("%4d",A[i][j]);
        }
        printf("\n");
    }    
}

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

Мои проекты для Винграда

S.A.P.

Дата 9.8.2005, 11:27 (ссылка)

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

Загрузка ...

Эксперт

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

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

Так, а если еще попробовать скомбинировать данный вариант с рекурсией, скажем если где - то встречаются несколько равносильных ходов, то перебирать все?

Диана

Дата 9.8.2005, 11:56 (ссылка)

(голосов: 0)

Загрузка ...

Unregistered

Спасибо!

Попробую запустить.

Akina

Дата 9.8.2005, 12:39 (ссылка)

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

Загрузка ...

Советчик

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

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

Цитата(AntonSaburov @ 9.8.2005, 12:04)

Эта эвристика работает на полях от 5х5 до 70х70 - я сам студентам такое даю.

Повторяю. На доске 8*8 существует (и не одно) полностью удовлетворяющее этим условиям прохождение, при котором конь попадает в тупик. Абсолютно достоверно. Обсуждалось в "Наука и жизнь" годах в 70-х, с анализом и конкретным примером тупика.

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

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