Задача «Хід коня»

Міністерство освіти і науки України Полтавський державний педагогічний університет

імені В. Г. Короленка Задача

Хід коня

Підготували студенти групи Ф-52

Татушенко М.В., Прудка І.І., Кириченко І.О.

Полтава — 2009

План

• Вступ
• Умова задачі
• Блок-схема задачі «Хід коня»
• Підпрограма
• Лістинг програми

Вступ

Зовсім не обов’язково бути шахматистом, щоб знати, яка шахматна фігура найдивовижніша. Звісно, це кінь! Не випадково вислів «хід конем» став крилатим. А один із відомих гросмейстерів, С. Тартаковер, вважав, що «вся шахматна партія — це один замаскований хід конем» .

Задача про хід коня відома ще з XVIII століття. Леонард Ейлер присвятив їй велику працю «Розв'язання одного цікавого питання, яке, здається, не підкоряється ніякому дослідженню» (26.04.1757). В листі до Гольдбаха він писав: «Спогади про запропоновану колись мені задачу послугували для мене недавно приводом до деяких витонченостей, в яких звичайний аналіз здавалося б немає ніякого застосування… Я знайшов нарешті ясний спосіб знаходити безліч розв’язків (хоча їх кількість небезкінечна), не роблячи спроб» .

Умова задачі

Задача про хід коня відома ще з XVIII століття. Леонард Ейлер присвятив їй велику працю «Розв'язання одного цікавого питання, яке, здається, не підкоряється ніякому дослідженню» (26.04.1757). В листі до Гольдбаха він писав: «Спогади про запропоновану колись мені задачу послугували для мене недавно приводом до деяких витонченостей, в яких звичайний аналіз здавалося б немає ніякого застосування… Я знайшов нарешті ясний спосіб знаходити безліч розв’язків (хоча їх кількість небезкінечна), не роблячи спроб» .

Тож розглянемо задачу про хід коня.

Здійснимо постановку задачі. Дано дошку n*n, яка містить n² полів. Коня, який ходить згідно шахових правил, поміщують на поле з початковими координатами х₀ та у₀. Потрібно покрити всю дошку ходами коня, тобто обчислити обхід дошки, якщо він існує, з n²-1 ходів, такий, щоб кожне поле відвідується єдиний раз. Очевидно, задачу покриття n² полів можна звести до більш простої: або виконати черговий хід, або встановити, що ніякий хід далі неможливий. Перша спроба виглядатиме так:

Procedure спроба наступного кроку;

Begin ініціація вибірки ходів;

Repeat вибір наступного можливого ходу зі списку чергових ходів;

If він прийнятний then

Begin запис ходу;

If дошка незаповнена then

Begin спроба наступного кроку;

If невдачаthen стирання попереднього кроку

End

End

Until (хід був удалим) && (немає інших можливих ходів)

End.

Блок-схема задачі «Хід коня»

хід коня лістинг алгоритм

Підпрограма

Лістинг програми

Program tyr_konia;

Uses crt'

Const

dx: array [1.8] of integer= (2,1,-1,-2,-2,-1,1,2);

dy; array [1.8] of integer= (1,2,2,1,-1,-2,-2,-1);

var

i, j, n, Nsqr: integer;

q: boolean;

h: array [1.8,1.8] of integer;

procedure Try (i, x, y: integer; var q: boolean);

var k, u, v: integer;

q1: boolean;

begin

k: =0;

repeat

k: =k+1;

q1: =false;

u: =x+dx [k];

v: =y+dy [k];

if (l<=u) and (u<=n) and (l<=v) and (v<=n) and (h [u, v] =0) then

begin

h [u, v]: =i-1;

if i

begin

Try (i+1,u, v, q1);

If not q1 then h [u, v]: =0;

End

Else q1: =true;

End;

Until q1 or (k=8);

q: =q1;

end;

begin

clrscr;

for i: =1 to 8 do

for j: =1 to 8 do

h [i, j]: =0;

write (`n='); readln (n);

write (`i='); readln (i);

write (`j='); readln (j);

Nsqr: =n*n;

h [i, j]: =1;

Try (2, i, j, q);

Writeln (`Po4atkove polo*ennnia kon9: [', i,'; ', j,'] ');

If q then

Begin

h [i, j]: =0;

for i: =1 to n do

begin

for j: =1 to n do write (h [i, j]: 3);

writeln;

end;

end

else

writeln (`path not found');

readln;

end.