| Форумы
ЧАТ |
Орешник |
|
| Форумы -» | Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG |
|
| ||
|
|
Новости |
Поиск |
FAQ |
Статьи |
Книги |
Новости VCL
| | Форумы ЧАТ |
Орешник |
|
| |||
| |||
| |||
« предыдущая ветвь | форум | следующая ветвь »
Ход конём [D6, WinXP]
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); - это порцедура мне возврашает число вариантов ходовю
Sha (2004-10-12 22:39:00) [21]Defunct © (12.10.04 22:37) [23]
Имеет
Defunct (2004-10-12 22:37:00) [22]> Sha
Просто скажи, 10x10 имеет решение или нет?
У меня получается, что нет. Может быть я заблуждаюсь.
Sha (2004-10-12 22:20:00) [23]> Defunct © (12.10.04 21:11) [20]
> вопрос ведь не в размере доски, а в кратности.
> 8x8, 12x12, 16x16 и т.п. покрываются.
> Как бы мы ни резали 10x10, получаются поля которые невозможно покрыть.
Выбираются несколько фиксированных типоразмеров досок (не обязательно квадрадных, даже большинство не квадратных).
Затем для них отыскиваются решения кольцевого обхода.
Затем доказывается, что прямоугольные доски произвольного размера, большего m*n, можно разрезать на доски фиксированных типоразмеров с сохранением решения. Затем для ВСЕХ досок меньшего размера, для которых решение есть, отыскивается решение при помоши известных или оригинальных алгоритмов.
Все.
Ezhik (2004-10-12 21:41:00) [24]Точно утверждать не буду, но я видел эту игру уже написаную, тока там надо самому заполнять эти поля. Так вот там было поле именно 10*10. И в таблице рекордов были люди заполнившие все поле. Значит же можно какнибуть такое поле заполнить.
Defunct (2004-10-12 21:11:00) [25]> Sha
вопрос ведь не в размере доски, а в кратности.
8x8, 12x12, 16x16 и т.п. покрываются.
Как бы мы ни резали 10x10, получаются поля которые невозможно покрыть.
Sha (2004-10-12 21:07:00) [26]Defunct © (12.10.04 21:01) [18]
Надо уметь разрезать :)
У меня есть решение для досок сколь угодно большого размера.
В свое время писал для DelphiChallenge. Был такой сайт. Умер.
Defunct (2004-10-12 21:01:00) [27]Sha © (12.10.04 18:29) [17]
Задача не решается.
Поле 5x5 покрыть нельзя, соотв нельзя покрыть 4x5x5
Sha (2004-10-12 18:29:00) [28]Defunct © (12.10.04 17:43) [16]
Задача несложная.
Для малых досок - перебор, для больших - по частям.
Defunct (2004-10-12 17:43:00) [29]lehich © (12.10.04 17:39) [15]
вы что издеваетесь? или совсем не представляете сложности задачи?
lehich (2004-10-12 17:39:00) [30]2Defunct вручную решали! вручную! может пари на что-нибудь что я в течении 3-4 дней вручную решу задачу (на бумажке) по ходу конем на поле 10х10 клеток? и оно будет ВСЁ заполнено? и пришлю отсканированный рисунок
Defunct (2004-10-12 17:36:00) [31]Defunct © (12.10.04 17:22) [13]
> (пересмотреть 2^103 вариантов)
ошибся 2^300 вариантов.
Defunct (2004-10-12 17:22:00) [32]lehich © (12.10.04 09:09) [12]
приведите ваше решение.
лет 10-15 назад не было машин способных "на уроке решить такую задачу (пересмотреть 2^103 вариантов)".
lehich (2004-10-12 09:09:00) [33]2Defunct как это для 10х10 не решается? еще 15 лет назад сидя на уроках от нечего делать рисовали такие поля и заполняли их целиком
wnew (2004-10-12 05:59:00) [34]Да, а я и не догадывался ввести поле больше, чем 8X8, сейчас попробовал - комп. уже пять минут перебирает по решению [6]. Хотя с полем 8X8 справляется мгновенно:) Пошёл курить:)
Defunct (2004-10-12 05:27:00) [35]wnew © (12.10.04 05:19) [9]
сорри, засиделся я уже не различаю ники, пора идти спать..
> Я эту задачу решал 10 лет назад, когда на курсах по C++ учился
для шахматного поля задача решается, а для 10x10 не знаю, [2] показывает - что нет.
wnew (2004-10-12 05:19:00) [36]Defunct © (12.10.04 5:16) [8]
Да нет, это не мне она интересна, вопрос же не я задавал:) Я эту задачу решал 10 лет назад, когда на курсах по C++ учился :)
Defunct (2004-10-12 05:16:00) [37][5]
Не каждое поле можно обскакать, например, поля 2x2, 3x3, 4x4 обойти нельзя, неисключено что и 10x10 тоже.
[4]
Задача интересна для вас, поэтому и решать ее вам. Все что мог я и так уже сделал (на этом чисто академический интерес с моей стороны заканчивается, соответственно больше мне предложить нечего, по ссылкам лазить - увы нет желания). Простой рекурсивный обход [2] требует времени.
wnew (2004-10-12 04:56:00) [38]А здесь решение для второй, тоже на Си:
#include
//#include
int xsize=0,ysize=0,*feld=0;
int springer(int x, int y)
{
static int pos=1;
if((feld[y*xsize+x]==1)&&(pos==((xsize-4)*(ysize-4)+1)))
return(1);
if(feld[y*xsize+x]) return(0);
feld[y*xsize+x]=pos;
pos++;
if(!springer(x+1,y-2))
if(!springer(x+2,y-1))
if(!springer(x+2,y+1))
if(!springer(x+1,y+2))
if(!springer(x-1,y+2))
if(!springer(x-2,y+1))
if(!springer(x-2,y-1))
if(!springer(x-1,y-2))
{
feld[y*xsize+x]=0;
pos--;
return(0);
}
return(1);
}
void main(void)
{
int x,y,z,xstart,ystart;
cout > xsize;
cout > ysize;
xsize+=4;
ysize+=4;
if(feld=new(int[xsize*ysize]))
{
for(x=0;x
wnew (2004-10-12 04:55:00) [39]Здесь решение для первой задачи на Си:
#include <iostream.h>
//#include <stdlib.h>
int xsize=0,ysize=0,*feld=0;
int springer(int x, int y, int pos)
{
if(feld[y*xsize+x]) return(0);
feld[y*xsize+x]=pos;
if(pos!=((xsize-4)*(ysize-4)))
if(!springer(x+1,y-2,pos+1))
if(!springer(x+2,y-1,pos+1))
if(!springer(x+2,y+1,pos+1))
if(!springer(x+1,y+2,pos+1))
if(!springer(x-1,y+2,pos+1))
if(!springer(x-2,y+1,pos+1))
if(!springer(x-2,y-1,pos+1))
if(!springer(x-1,y-2,pos+1))
{
feld[y*xsize+x]=0;
return(0);
}
return(1);
}
void main(void)
{
int x,y,z,xstart,ystart;
cout << "Breite des Feldes :";
cin >> xsize;
cout << "Hцhe des Feldes :";
cin >> ysize;
xsize+=4;
ysize+=4;
if(feld=new(int[xsize*ysize]))
{
for(x=0;x<xsize;x++)
for(y=0;y<ysize;y++)
feld[y*xsize+x]=0;
for(x=0;x<xsize;x++)
{
feld[x]=-1;
feld[xsize+x]=-1;
feld[((ysize-1)*xsize)+x]=-1;
feld[((ysize-2)*xsize)+x]=-1;
}
for(y=0;y<ysize;y++)
{
feld[xsize*y]=-1;
feld[xsize*y+1]=-1;
feld[xsize*y+x-1]=-1;
feld[xsize*y+x-2]=-1;
}
do
{
cout << "X-Position des Springers ( 1-" << xsize-4 << ") :";
cin >>xstart;
} while((xstart<1)||(xstart>(xsize-4)));
do
{
cout << "Y-Position des Springers ( 1-" << ysize-4 << ") :";
cin >> ystart;
} while((ystart<1)||(ystart>(ysize-4)));
cout << "\nBerechne Loesung fuer Feldgroesse (" << xsize-4 << "," << ysize-4 << ") ";
cout << "und Startposition (" << xstart << "," << ystart << "...\n\n";
if(!springer(xstart+1,ystart+1,1))
cout << "Es gibt keine Lцsung!!\n\n";
else
{
for(z=1;z<=(ysize-4)*(xsize-4);z++)
for(y=2;y<ysize-2;y++)
for(x=2;x<xsize-2;x++)
if(feld[y*xsize+x]==z)
cout << "(" << x-1 << "," << y-1 << ")\n";
}
delete(feld);
}
}
wnew (2004-10-12 04:53:00) [40]Есть две таких задачи: по условию первой - конь должен стартовать из угла и побывать в каждой клетке один раз, а по условию второй - конь должен стартовать из угла, побывать в каждой клетке один раз и вернуться на клетку с которой стартовал.
| |
Страницы: 