Форум программистов, компьютерный форум, киберфорум
Наши страницы
Lazarus
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.67/3: Рейтинг темы: голосов - 3, средняя оценка - 4.67
Ovenvan
1 / 1 / 3
Регистрация: 27.12.2014
Сообщений: 68
1

Обход доски конём

06.06.2015, 22:16. Просмотров 621. Ответов 8
Метки нет (Все метки)

Добрый день. Возникла задача обойти доску конём. Есть код, который запускается, но не то, чтобы правильно работает. Проставляется первый ход и всё, остальные поля оставляет заполненными нулями. Помогите, пожалуйста, разобраться.
Delphi
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
unit Unit1;
 
{$mode objfpc}{$H+}
 
interface
 
uses
  Classes, SysUtils, FileUtil, Forms, Controls, Graphics, Dialogs, Grids,
  StdCtrls;
 
const
  n = 8;
  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);
 
type
 
  { TForm1 }
 
  TForm1 = class(TForm)
    Button1: TButton;
    Edit1: TEdit;
    Edit2: TEdit;
    Label1: TLabel;
    Label2: TLabel;
    Label3: TLabel;
    Label4: TLabel;
    StringGrid1: TStringGrid;
    procedure Button1Click(Sender: TObject);
  private
    { private declarations }
  public
    { public declarations }
  end;
 
var
  Form1: TForm1;
  Board : array [1..n, 1..n] of integer; {номеру хода, когда посещена клетка или 0, если конь еще не заходил}
  Okey : boolean; {обход удался}
  x0, y0: integer;
 
implementation
 
{$R *.lfm}
 
{ TForm1 }
 
procedure Clear; {очистка доски}
var
  i, j: integer;
begin
  for i:= 1 to n do
    for j:= 1 to n do
      Board[i,j]:= 0;
end;
 
procedure Draw; {отрисовка доски}
var
  i, j: integer;
begin
  for i:= 1 to n do
    for j:= 1 to n do
       form1.StringGrid1.Cells[i-1,j-1]:= inttostr(Board[i,j]);
  Form1.Refresh;
end;
 
function SetBeginXY: boolean; {начальные координаты}
begin
    x0:= strtoint(form1.Edit1.Text);
    y0:= strtoint(form1.Edit2.Text);
    Board[x0,y0]:= 1;
  end;
 
procedure Trying(step, x, y: integer; var OK: boolean); {OK успешность хода, step текущий номер хода}
var
  xnext, ynext: integer;
  k: integer; {возможный ход}
  OK1: boolean;
begin
  k:= 0;
  repeat
    inc(k);
    OK1:= false; {пока не найден подходящий ход}
    xnext:= x + dx[k];
    ynext:= y + dy[k];
    if ((1 <= xnext) and (xnext <= n) and (1 <= ynext) and (ynext <= n) and (Board[xnext,ynext] = 0)) then
      begin
        Board[xnext,ynext]:= step; {свободная клетка}
        if step < n*n then
          begin
            Trying(step + 1, xnext, ynext, OK1);
            if (not OK1) then Board [xnext,ynext]:= 0; {неудачный ход не получился следующий}
          end;
      end
    else OK1:=TRUE; {последний ход}
  until OK1 or (k = 8);
  OK:= OK1;
end;
 
procedure TForm1.Button1Click(Sender: TObject);
begin
  form1.StringGrid1.RowCount:= n;
  form1.StringGrid1.ColCount:= n;
  Clear;
  Draw;
  if (SetBeginXY) then Trying(2,x0,y0,Okey);
  Draw;
end;
 
end.
0
Лучшие ответы (1)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
06.06.2015, 22:16
Ответы с готовыми решениями:

Определить: являются ли эти два поля шахматной доски полями одного цвета?
Помогите: координаты любого поля шахматной доски могут быть заданы парой...

обход графа
Дан ориентированный граф, ацикличный, нет таких пар вершин соединенных парой...

Обход каталога, поиск определенных txt-файлов, конвертация их в csv
Здравствуйте, ребят я сделал цыкл, которий делает обход каталогов sp.txt, ...

Обход доски конём
Добрый день. Не могли бы Вы помочь с задачей об обходе конём шахматной доски...

Обход конём шахматной доски
Приветствую всех форумчан! Нужно решить задачу: обойти конём шахматное поле...

8
Ovenvan
1 / 1 / 3
Регистрация: 27.12.2014
Сообщений: 68
09.06.2015, 18:55  [ТС] 2
Ни у кого нет идей?
0
Kitayets
338 / 292 / 103
Регистрация: 09.09.2011
Сообщений: 1,041
10.06.2015, 16:04 3
не совсем понятно задание. что значит "обход поля конем"? Из Вашего кода понять что требуется сложно. А запустить его невозможно в следствии отсутствия остальных файлов проекта (как минимум файла проекта lpr, файла главной формы lfm)

не могли бы объяснить:

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

вообще это должно быть понятно на уровне логики, что если Вы заинтересованы в получении ответа, то должны предоставить максимум необходимой информации.

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

Добавлено через 3 минуты
вот я ввел в окно поиска "обход конем" и получил кучу ссылок на решения включая готовые проекты. Осталось только просмотреть на соответствие Вашему заданию и посмотреть идеи предложенных решений.
0
Ovenvan
1 / 1 / 3
Регистрация: 27.12.2014
Сообщений: 68
10.06.2015, 16:29  [ТС] 4
Я всё понял. Задание заключается в рекурсивной проверке возможности обойти конём (фигурой с соответствующим ходом) шахматную доску. В каждой клетке должен отображаться номер хода, на котором конь попал в эту клетку (до 64). В Edit'ы записываю первоначальное положение коня (по координатам). На выходе StringGrid с заполненными полями. В этом и проблема: на StringGrid'е только первоначальное положение коня, дальше не отображается.
Файлы проекта в архиве.
0
Вложения
Тип файла: rar Обход доски.rar (2.97 Мб, 5 просмотров)
Kitayets
338 / 292 / 103
Регистрация: 09.09.2011
Сообщений: 1,041
11.06.2015, 09:52 5
Ну самый первый косяк, из-за чего не работает - ошибка в функции function SetBeginXY: boolean;
и среда подсказывает что там что-то не так (см. картинку), что похоже, что функция не возвращает никакого результата.


переделал немного функцию на вот такую:
Delphi
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function SetBeginXY: boolean; {начальные координаты}
begin
  result:= True;
  try
    x0:= strtoint(form1.Edit1.Text);
    y0:= strtoint(form1.Edit2.Text);
    if (x0 < 1) or (x0 > 8) or (y0 < 1) or (y0 > 8) then
      Raise Exception.Create('Wrong range');
  except
    result:= False;
    exit;
  end;
 
  Board[x0,y0]:= 1;
 
end;
теперь показываются несколько следующих шагов, но очевидно что алгоритм в функции Trying запрограммирован не корректно.
0
Миниатюры
Обход доски конём  
Kitayets
338 / 292 / 103
Регистрация: 09.09.2011
Сообщений: 1,041
11.06.2015, 10:41 6
ну и конечно ты написал не полное задание. например не упомянул, что конь должен посетить каждую клетку, причем только 1 раз.
0
Ovenvan
1 / 1 / 3
Регистрация: 27.12.2014
Сообщений: 68
11.06.2015, 11:12  [ТС] 7
Да, так и есть, забыл про это условие. Заметил некоторую особенность: отображение ходов останавливается, как только "конь" доходит до правой границы StringGrid'а.
0
Kitayets
338 / 292 / 103
Регистрация: 09.09.2011
Сообщений: 1,041
11.06.2015, 13:04 8
Лучший ответ Сообщение было отмечено Ovenvan как решение

Решение

Сегодня добрый, подправил твой проект, немного подработал форму на свой вкус... Исправил функцию обхода.

Из-за фиксированного порядка проверки ходов коня - в некоторых случаях перебор вариантов может быть очень долгим.

но при начальных значениях X=8, Y=1 находит ответ очень быстро. Возможно, что статистически быстрее рассчитывать если менять порядок просмотра ходов в случайном порядке.
1
Миниатюры
Обход доски конём  
Вложения
Тип файла: zip обход_доски_изм.zip (3.8 Кб, 7 просмотров)
Ovenvan
1 / 1 / 3
Регистрация: 27.12.2014
Сообщений: 68
12.06.2015, 11:44  [ТС] 9
Спасибо большое за помощь. Разобрался в задаче.
0
12.06.2015, 11:44
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.06.2015, 11:44

Написать программу, реализующую обход доски шахматным конём
Конь находится в клетке (x1,y1).Нужно вывести любой его путь из (x1,y1) в...

Обойти конём все поля шахматной доски
Обойти конём все поля шахматной доски размером (n х n) клеток, побывав на...

Обход конём
Есть доска 8*8 Есть наш конь. Нужно чтобы мы выбрали позицию и конь обошел 64...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
9
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru