Мастера DELPHI (документация, исходники, скачать)

Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG

« предыдущая ветвь | форум | следующая ветвь »

Ход конём [D6, WinXP]

Страницы: 1 2 3 >
Ezhik © (2004-10-12 01:31:00)
Уважаемые мастера, я в отчаянии. Пишу широкоизвестную прогу "Ход конём"(есть поле 10*10, и надо начиная с любой клетки порйти все 100 ходов побывав в каждой из них единажды). Алгоритм я понимаю и все казалось бы прозрачно (рекурсия), но что-то не то.:( Уже 2-а дня сижу за отладкой, надпись на клавише ф7 уже стерлась :). Через ф7, я наблюдаю, что все идеально, вродеб-то. Умоляю, посмотрите что в этом алгоритме не так... Спасибо за внимание

var
Hodu: array of array of byte; //сюда пишем сделаные ходы
Masiv: array[1..10,1..10] of Boolean; //Помечаем ечейку занетой
VariantListXXX: array of byte; //
VariantListYYY: array of byte; //списки возможных ходов
Variantu: array[1..100,1..2] of byte; //пишем число вариантов ходов и под каким вариантом мы зашли в даный момент
x,y,FreeCount,move_num: integer;

x:=0;
y:=0;

procedure Recors();
var
i,a,b: byte;
begin
CheckHodCount(x,y); //проверяем число возможных ходов
if FreeCount <> 0 then
begin
SetLength(Hodu,move_num+1,2);

Masiv[x,y]:= True;
Hodu[move_num,0]:= x;
Hodu[move_num,1]:= y;

Variantu[move_num+1,1]:= FreeCount;
Inc(move_num);

if move_num >= 100 then begin ShowMessage('100!!!'); draw; exit end;

X:= VariantListXXX[Variantu[move_num,2]]; //первый раз мы берём из списка возможных ходов первый, при неудаче - 2-й, и т.д.
Y:= VariantListYYY[Variantu[move_num,2]];

// Form1.Caption:= Inttostr(move_num);
Recors;
end
else
begin
// ShowMessage('000');
repeat
a:= Variantu[move_num,1];
b:= Variantu[move_num,2];
Masiv[(Hodu[move_num-1,0]),(Hodu[move_num-1,1])]:= False;
if a <= b+1 then
begin
Variantu[move_num,1]:=0;
Variantu[move_num,2]:=0;
end;
inc(move_num,-1);
until a > b+1;

x:= Hodu[move_num,0];
y:= Hodu[move_num,1];
Variantu[move_num+1,2]:= Variantu[move_num+1,2] + 1;
Recors
end;
end;

CheckHodCount(x,y); - это порцедура мне возврашает число вариантов ходовю

Defunct (2004-10-13 18:31:00) [1]
> 2Defunct пари? чтож вы боитесь? вы же уверены в сложности задачи и ее нерешаемости!!!

Был уверен, уже нет ;)

Sha (2004-10-13 13:26:00) [2]
Опять 27-ой уехал:
27 24 1 50 41 22 43 48 39 20 2 51 26 23 66 49 40 21 44 47 25 28 67 0 57 42 65 46 19 38 52 3 56 89 68 87 58 77 64 45 29 84 53 86 99 90 69 62 37 18 4 55 98 91 88 61 76 59 78 63 83 30 85 54 97 80 95 70 17 36 8 5 92 81 94 75 60 79 14 71 31 82 7 10 33 96 73 12 35 16 6 9 32 93 74 11 34 15 72 13

Sha (2004-10-13 13:24:00) [3]
> lehich © (13.10.04 12:34) [41]
> у меня он замыкается в самом центре, а до него минимум по 3-4 замкнутых круга ВНЕШНИХ

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

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

Например, маршрут [27] - замкнутый:
27 24 1 50 41 22 43 48 39 20 2 51 26 23 66 49 40 21 44 47 25 28 67 0 57 42 65 46 19 38 52 3 56 89 68 87 58 77 64 45 29 84 53 86 99 90 69 62 37 18 4 55 98 91 88 61 76 59 78 63 83 30 85 54 97 80 95 70 17 36 8 5 92 81 94 75 60 79 14 71 31 82 7 10 33 96 73 12 35 16 6 9 32 93 74 11 34 15 72 13
Для того чтобы замостить поле 1000*1000 маршрутом [27] достаточно в нем разомкнуть некоторые из переходов: 10-11,30-31,40-41,71-72.
Для связи с соседями по горизонтали можно образовать переходы: 30-71,31-72.
Для связи с соседями по вертикали можно образовать переходы: 10-41,11-40.
Соседние паркетины соединим змейкой:
0 1 2 3 4 5 6 7 8 9 19 18 17 16 15 14 13 12 11 10 20 21 22 23 24 25 26 27 28 29 39 38 37 36 35 34 33 32 31 30 40 41 42 43 44 45 46 47 48 49 59 58 57 56 55 54 53 52 51 50 60 61 62 63 64 65 66 67 68 69 79 78 77 76 75 74 73 72 71 70 80 81 82 83 84 85 86 87 88 89 99 98 97 96 95 94 93 92 91 90
Мы снова получаем замкнутый маршрут.

lehich (2004-10-13 12:34:00) [4]
у меня он замыкается в самом центре, а до него минимум по 3-4 замкнутых круга ВНЕШНИХ

Sha (2004-10-13 11:25:00) [5]
> lehich © (13.10.04 11:00) [39]
> в моем решении 10х10 сотая цифра почти в самом центре
> оказывается, следовательно 1000*1000 не разбить по десяткам...

Как правило, для разбиения достаточно иметь замкнутый маршрут.
Если у тебя такой, то дело в шляпе.

lehich (2004-10-13 11:00:00) [6]
2Sha употею, яж не про компьютерный алгоритм говорю а про то что на бумаге это сделаю, тем более что в моем решении 10х10 сотая цифра почти в самом центре оказывается, следовательно 1000*1000 не разбить по десяткам...

Sha (2004-10-13 09:35:00) [7]
> Ezhik (13.10.04 02:53) [35]
> делаю поле 10*10 и все - бесконечная рекурсия,

Правило Варнсдорфа нашел?

> lehich © (13.10.04 09:23) [36]
> 2Defunct пари? чтож вы боитесь? вы же уверены в сложности задачи и ее нерешаемости!!!

Давай пари со мной для доски 1000*1000 - кто быстрее?

Sha (2004-10-13 09:29:00) [8]
> Defunct © (13.10.04 02:21) [33]
> просьба обновить анкету ;>

Обновил

> только в 5x5 не находит краевых решений (когда точкой старта выбирается угол).

Вот тебе решение 5*5 с началом(концом) в центре и концом(началом) в углу
24 9 4 15 18 3 14 17 10 5 8 23 0 19 16 13 2 21 6 11 22 7 12 1 20

lehich (2004-10-13 09:23:00) [9]
2Defunct пари? чтож вы боитесь? вы же уверены в сложности задачи и ее нерешаемости!!!

Ezhik (2004-10-13 02:53:00) [10]
Уважаемые мастера , задачу я решил, но действительно только для поля 8*8, в этом же коде делаю поле 10*10и все - бесконечная рекурсия, или может ответ и возможен, но нада долго ждать(я ждал около 5 мин, в то время как 8*8 нашло за 1 сек...).
Для поля 8*8 все легче чемк казалось:

procedure Recors; var i,nx,ny: integer; begin Xodu[Nom,0]:= x; Xodu[Nom,1]:= y; pole[x,y]:= 1; inc(Nom); for i:= 0 to 7 do begin if Nom >= 100 then begin if flag = 0 then draw; exit; end; nx:= x + NextX[i]; ny:= y + NextY[i]; if (nx < 0) or (nx > 9) or (ny < 0) or (ny > 9) then continue; if pole[nx,ny] = 1 then continue; x:= nx; y:= ny; Recors; end; pole[Xodu[Nom-1,0],Xodu[Nom-1,1]]:= 0; x:= Xodu[nom-2,0]; y:= Xodu[nom-2,1]; Inc(Nom,-1); end;

Так что всем огромное спасибо за расмотрение вопорса

Defunct (2004-10-13 02:37:00) [11]
Народ раз уж зашел вопрос о переборе, может кто подскажет, решается ли такое:

??? ? ? \|/ | / [2] [3]-?? | / / [1]-[4]-[6] \ \ [5]-? | \ ? ?
есть точки (на рисунке это 1-6 и ?) всего точек 17 каждая точка может быть связана с четырмя любыми другими точками. Можно ли так связать все эти точки, чтобы из любой точки в любую другую максимальный путь был не больше 2.

Defunct (2004-10-13 02:21:00) [12]
> Sha

просьба обновить анкету ;>

> wnew © (13.10.04 01:44) [32]

да, уже вижу. только в 5x5 не находит краевых решений (когда точкой старта выбирается угол).

wnew (2004-10-13 01:44:00) [13]
Defunct © (12.10.04 21:01) [18]

> Поле 5x5 покрыть нельзя

Начиная с 4X5 все решаются. И код приведёный мной в [6] прекрасно это делает. Разумеется, начиная с 8X9 песня затягивается. Но 8X8 находит за пару секунд.

Sha (2004-10-13 01:17:00) [14]
Ezhik (12.10.04 23:42) [30]

Прога исследовательская, там 90% кода тебе не потребуется.
В твоем случае поможет поиск в сети по слову Варнсдорф

Ezhik (2004-10-12 23:42:00) [15]
>>Sha © (12.10.04 23:04) [27]
>>Это выход из программы перебора. Она позволяет отыскивать решения для досок размером примерно до 500*500 и даже чуть выше.

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

Defunct (2004-10-12 23:28:00) [16]
> Sha, DDA

Thnx,

procedure TForm3.Button1Click(Sender: TObject);
Var P:TPoint;
S: Integer;
begin
P.X := 2;
P.Y := 0;
S := 0;
Move(P, d_ld, S);
end;

С наглядным примером [26, 27] - перебор [2] нашел решение. Но у автора была оговорка:

> и надо начиная с любой клетки пройти все 100 ходов побывав в каждой из них единажды

IMHO одно отсюда можно точно вынести, высказывание неверно:
> Алгоритм я понимаю и все казалось бы прозрачно (рекурсия)

Простой рекурсией тут не обойтись.

DDA (2004-10-12 23:14:00) [17]
ну вот всё и решилось

Sha (2004-10-12 23:04:00) [18]
Так лучше.
27 24 1 50 41 22 43 48 39 20 2 51 26 23 66 49 40 21 44 47 25 28 67 0 57 42 65 46 19 38 52 3 56 89 68 87 58 77 64 45 29 84 53 86 99 90 69 62 37 18 4 55 98 91 88 61 76 59 78 63 83 30 85 54 97 80 95 70 17 36 8 5 92 81 94 75 60 79 14 71 31 82 7 10 33 96 73 12 35 16 6 9 32 93 74 11 34 15 72 13

Это выход из программы перебора. Она позволяет отыскивать решения для досок размером примерно до 500*500 и даже чуть выше.

Кроме того, доску 10*10 можно склеить из двух 5*10.

Sha (2004-10-12 22:59:00) [19]
27 24 1 50 41 22 43 48 39 20 2 51 26 23 66 49 40 21 44 47 25 28 67 0 57 42 65 46 19 38 52 3 56 89 68 87 58 77 64 45 29 84 53 86 99 90 69 62 37 18 4 55 98 91 88 61 76 59 78 63 83 30 85 54 97 80 95 70 17 36 8 5 92 81 94 75 60 79 14 71 31 82 7 10 33 96 73 12 35 16 6 9 32 93 74 11 34 15 72 13

DDA (2004-10-12 22:50:00) [20]

> Defunct © (12.10.04 22:37) [23]

на поле 10x10 решение есть,также как и на 9x9 8x8 7x7 6x6 5x5 6x5 7x5
всё это у меня на листочке который составил в шкеле га уроках

Нужен отсканеный рисунок? с этими полями

Страницы: 1 2 3 >

Наверх

	« предыдущая ветвь \| форум \| следующая ветвь »