Найти последовательность ходов коня, чтобы попасть на целевую клетку

@ololo2412 · Регистрация: 15.02.2011

Студворк — интернет-сервис помощи студентам

Задача: шахматная доска, дана начальная клетка на доске(откуда) и дана целевая клетка(куда попасть). Дана фигура конь,стоит на начальной клетке. Найти последовательность ходов, чтобы попасть на целевую клетку.

Комментарий модератора

"ох уж этот конь" - неподходящий заголовок для темы

@Catstail · 24.11.2012, 22:18

Вот не самое рациональное решение... Но ищет:

Lisp
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
(setq *sca*   '((1 2) (1 -2) (-1 2) (-1 -2) (2 1) (2 -1) (-2 1) (-2 -1)))
(setq *chk*   nil)
(setq *stack* nil)
 
(defun next-step-list (cell)
     (let ((col (car cell))
           (row (cadr cell))
           (res nil)
           (cc  0)
           (rr  0))
      (dolist (n *sca* res)
           (setq cc (car n))
           (setq rr (cadr n))
           (when (AND (<= (+ col cc) 8) (<= (+ row rr) 8)
                      (> (+ col cc) 0) (> (+ row rr) 0))
                 (setq res (cons (list (+ col cc) (+ row rr)) res))
           )
      )))           
                   
                   
(defun dfs (end)
    (when (null *stack*) 'EOG)
    (let ((lst (next-step-list (car *stack*))))
        (dolist (icell lst t)
            (unless (member icell *chk*)
                    (printline icell)
                    (when (AND (= (car icell) (car end)) (= (cadr icell) (cadr end)))
                          (stop*))
                    (setq *stack* (cons icell *stack*))
                    (setq *chk* (cons icell *chk*))
                    (dfs end)))
        (setq *stack* (cdr *stack*))))            
                    
(defun task (start end)
   (setq *stack* (list start))
   (setq *chk* (list start))
   (dfs end))
 
;; Проверка
 
(task '(1 1) '(5 3))
(3 2)
(1 3)
(3 4)
(1 5)
(3 6)
(1 7)
(3 8)
(5 7)
(7 6)
(5 5)
(7 4)
(5 3)

@ololo2412 · 25.11.2012, 11:20 **[ТС]**

спасибо. подскажите а какой алгоритм брали за основу? (поиск в глубину, ширину, с возвратом или жадный)?

Добавлено через 3 минуты
и еще вопросик. почему программа начинается не с функции? первые три строчки что означают?

@Catstail · 25.11.2012, 14:14

Отвечаю:

1) алгоритм - модификация поиска в глубину (dfs)
2) в начале программы заводятся глобальные переменные (setq на верхнем уровне)

@ololo2412 · 25.11.2012, 15:10 **[ТС]**

простите, а Вы могли бы мне вкратце рассказать принцип работы этой программы. я что-то не очень понимаю.

@Catstail · 25.11.2012, 21:05

Пробую:

Lisp
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
;; *sca* - это список полей, которые можно "достать" ходом коня
 
(setq *sca*   '((1 2) (1 -2) (-1 2) (-1 -2) (2 1) (2 -1) (-2 1) (-2 -1)))
 
;; *chk* - список уже пройденных полей
 
(setq *chk*   nil)
 
;; *stack* - список, использующийся как стек при обходе в глубину
 
(setq *stack* nil)
 
;; функция, которая для заданного поля cell, строит список всех полей, на которые
;; конь может попасть из поля cell. 
 
(defun next-step-list (cell)
     (let ((col (car cell))
           (row (cadr cell))
           (res nil)
           (cc  0)
           (rr  0))
      (dolist (n *sca* res)
           (setq cc (car n))
           (setq rr (cadr n))
           (when (AND (<= (+ col cc) 8) (<= (+ row rr) 8)
                      (> (+ col cc) 0) (> (+ row rr) 0))
                 (setq res (cons (list (+ col cc) (+ row rr)) res))
           )
      )))           
                   
;; Обход в глубину (end - конечное поле; начальное берется из вершины стека)
                   
(defun dfs (end)
    (when (null *stack*) 'EOG)  ;; если стек пуст - конец
    (let ((lst (next-step-list (car *stack*)))) ;; берем вершину стека и строим список всех достуных полей
        (dolist (icell lst t)  ;; цикл по всем доступным полям
            (unless (member icell *chk*) ;; пока очередное поле не отмечено
                    (printline icell) ;; печатаем
                    (when (AND (= (car icell) (car end)) (= (cadr icell) (cadr end))) ;; если достигли нужного поля
                          (stop*)) ;; останов
                    (setq *stack* (cons icell *stack*)) ;; иначе очередное поле помещаем в стек
                    (setq *chk* (cons icell *chk*)) ;; отмечаем его
                    (dfs end))) ;; и рекурсивно вызываем dfs
        (setq *stack* (cdr *stack*))))  ;; после возврата удаляем поле из стека          
                    
;; Решение
 
(defun task (start end)
   (setq *stack* (list start)) ;; заносим стартовое поле в стек
   (setq *chk* (list start))    ;; отмечаем его
   (dfs end)) ;; обход...

@ololo2412 · 26.11.2012, 13:07 **[ТС]**

просто замечательно,спасибо большое!

05.12.2012, 15:13

Catstail, Здравствуйте, пробую ваше решение прохода конем из одной клетки в другую. не получается запустить в моей оболочке (использую newLisp, что первое скачалось). На лиспе до этого не писал. Хочу разобраться в одной задаче. Надо пройти конем по шахматной доске по всем клеткам и вернуться назад, в исходную клетку(А1), несколько раз находится в одной и той же клетке разрешено. Буду благодарен, если подскажите в каком лиспе писался ваш алгоритм. p.s. какое вижу решение: сначала использовать алгоритм прохода по всем клеткам доски без повторений, а потом вернуться назад по вашему коду. Подскажите, буду благодарен

@Catstail · 05.12.2012, 22:31

Сообщение от jikos

newLisp

- newLisp соответствует языку Scheme, а это не совсем Лисп (хотя очень похож). Скачайте LispWorks или Common Lisp. А можете HomeLisp (в котором я программу отлаживал).

@ololo2412 · 08.12.2012, 12:48 **[ТС]**

у меня почему-то не работает, вот что выводит

@Catstail · 08.12.2012, 14:35

А... Вместо (printline ...) в Common Lisp надо писать (print ...) (terpri)

@ololo2412 · 08.12.2012, 14:40 **[ТС]**

теперь работает) а после последовательности ходов пишет
Stack overflow (stack size 36000).
1 (continue) Extend stack by 50%.
2 Extend stack by 300%.
3 (abort) Return to level 2.
4 Return to debug level 2.
5 Extend stack by 50%.
6 Extend stack by 300%.
7 Return to level 1.
8 Return to debug level 1.
9 Extend stack by 50%.
10 Extend stack by 300%.
11 Return to level 0.
12 Return to top loop level 0.

Type :b for backtrace, :c <option number> to proceed, or :? for other options

@Catstail · 08.12.2012, 15:44

Да, тут дело серьезнее... Во-первых, в Common Lisp функция member работает не так, как в HomeLisp. В связи с чем пришлось написать свою:

Lisp
1
2
3
4
(defun member! (item lst)
     (cond ((null lst) nil)
           ((equal (car lst) item) t)
           (t (member! item (cdr lst)))))

Во-вторых, у меня после первого же нахождения конечной клетки программа останавливается вызовом (stop*). Для Common Lisp этот "номер" не проходит. Пришлось немного изменить алгоритм. Теперь программа перечисляет ряд способов достижения целевой клетки. Получилось вот что:

Lisp
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
(setq *sca*   '((1 2) (1 -2) (-1 2) (-1 -2) (2 1) (2 -1) (-2 1) (-2 -1)))
(setq *chk*   nil)
(setq *stack* nil)
(setq *flg* nil)
 
 (defun member! (item lst)
     (cond ((null lst) nil)
           ((equal (car lst) item) t)
           (t (member! item (cdr lst)))))
 
(defun next-step-list (cell)
     (let ((col (car cell))
           (row (cadr cell))
           (res nil)
           (cc  0)
           (rr  0))
      (dolist (n *sca* res)
           (setq cc (car n))
           (setq rr (cadr n))
           (when (AND (<= (+ col cc) 8) (<= (+ row rr) 8)
                      (> (+ col cc) 0) (> (+ row rr) 0))
                 (setq res (cons (list (+ col cc) (+ row rr)) res))
           )
      )))           
                   
                   
(defun dfs (end)
  (when (not *flg*)
    (let ((lst (next-step-list (car *stack*))))
        (dolist (icell lst t)
            (unless (member! icell *chk*)
                    (print icell) (terpri)
                    (if (AND (= (car icell) (car end)) (= (cadr icell) (cadr end)))
                        (progn  (setq *flg* t)(print 'OK) (return 'ok))
                        (progn  (setq *stack* (cons icell *stack*))
                                (setq *chk* (cons icell *chk*))
                                (dfs end)))
                    (setq *stack* (cdr *stack*)))))))
                    
(defun task (start end)
   (setq *chk*   nil)
   (setq *stack* nil)
   (setq *stack* (list start))
   (setq *chk* (list start))
   (setq *flg* nil)
   (dfs end))
   
 (task '(1 1) '(5 3))

Результат:

CL-USER 1 > (load "c:\\dfs.lsp")
; Loading text file c:\dfs.lsp

(3 2)
(1 3)
(3 4)
(1 5)
(3 6)
(1 7)
(3 8)
(5 7)
(7 6)
(5 5)
(7 4)
(5 3)
OK
...

Нужно будет, вероятно, переписать dfs.

@ololo2412 · 08.12.2012, 19:01 **[ТС]**

попозже попробую, отпишусь)

Добавлено через 1 минуту
у меня вот что выводит

Lisp
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
CL-USER 9 >    
 (task '(1 1) '(5 3)) 
 
(3 2) 
 
(1 3) 
 
(3 4) 
 
(1 5) 
 
(3 6) 
 
(1 7) 
 
(3 8) 
 
(5 7) 
 
(7 6) 
 
(5 5) 
 
(7 4) 
 
(5 3) 
 
OK 
(4 3) 
 
(4 7) 
 
(6 3) 
 
(6 7) 
 
(6 4) 
 
(6 8) 
 
(8 4) 
 
(8 8) 
 
(7 8) 
 
(4 5) 
 
(6 5) 
 
(2 6) 
 
(4 6) 
 
(2 5) 
 
(2 4) 
 
(2 8) 
 
(4 4) 
 
(4 8) 
 
(2 3) 
 
(2 7) 
 
(5 3) 
 
OK 
(2 1) 
 
(5 1) 
 
(5 3) 
 
OK 
T

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

@Catstail · 08.12.2012, 22:30

Вот исправленная версия:

Lisp
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
(setq *sca*   '((1 2) (1 -2) (-1 2) (-1 -2) (2 1) (2 -1) (-2 1) (-2 -1)))
(setq *chk*   nil)
(setq *stack* nil)
(setq *flg*     nil) ;; глобальный флаг - признак окончания
 
;; Функция проверяет, входит ли элемент item в список lst (T или Nil)
 
 (defun member! (item lst)
     (cond ((null lst) nil)
           ((equal (car lst) item) t)
           (t (member! item (cdr lst)))))
 
;; Генерация списка ходов
 
(defun next-step-list (cell)
     (let ((col (car cell))
           (row (cadr cell))
           (res nil)
           (cc  0)
           (rr  0))
      (dolist (n *sca* res)
           (setq cc (car n))
           (setq rr (cadr n))
           (when (AND (<= (+ col cc) 8) (<= (+ row rr) 8)
                      (> (+ col cc) 0) (> (+ row rr) 0))
                 (setq res (cons (list (+ col cc) (+ row rr)) res))
           )
      )))           
                   
                   
(defun dfs (end)
    (let ((lst (next-step-list (car *stack*))))
        (dolist (icell lst t)
            (unless (member! icell *chk*)
                    (if *flg* (return 'OK) t) ;; если уже нашли - выход
                    (print icell) (terpri)
                    (if (AND (= (car icell) (car end)) (= (cadr icell) (cadr end)))
                        (progn  (setq *flg* t) (print 'OK) (return 'OK) ) ;; только что нашли - установим флаг
                        (progn  (setq *stack* (cons icell *stack*))
                                (setq *chk* (cons icell *chk*))
                                (dfs end)))
                    (setq *stack* (cdr *stack*))))))
 
;; Решение
                    
(defun task (start end)
   (setq *chk*   nil)
   (setq *stack* nil)
   (setq *stack* (list start))
   (setq *chk* (list start))
   (setq *flg* nil)
   (dfs end)
)

Результат:

(3 2)
(1 3)
(3 4)
(1 5)
(3 6)
(1 7)
(3 8)
(5 7)
(7 6)
(5 5)
(7 4)
(5 3)
OK

10.12.2012, 22:41

Catstail, При попытке пройти из 1 1 в 8 8 алгоритм дает сбой

Ошибка возникает если конь оказывается в ситуации, когда ему некуда пойти, на всех клетках он уже был...
Он начинает прыгать ОЧЕНЬ далеко или например из 7 8 в 8 8

Поделитесь пожалуйста ссылкой на лисп которым Вы пользуетесь

@Catstail · 10.12.2012, 22:43

Спасибо за найденную ошибку. Буду разбираться.
А использую я свой homelisp

Новые блоги и статьи Все статьи Все блоги /
Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Programma_Boinc 23.12.2025 Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Рецензия / Мнение/ Перевод https:/ / **********/ gallery/ thinkpad-x220-tablet-porn-gzoEAjs . . .	PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Как объединить две одинаковые БД Access с разными данными VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .
От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .	Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .

@ololo2412 0 / 0 / 0 Регистрация: 15.02.2011 Сообщений: 24
	25.11.2012, 11:20 [ТС]
	спасибо. подскажите а какой алгоритм брали за основу? (поиск в глубину, ширину, с возвратом или жадный)? Добавлено через 3 минуты и еще вопросик. почему программа начинается не с функции? первые три строчки что означают? 0

@Catstail Супер-модератор 38161 / 21096 / 4306 Регистрация: 12.02.2012 Сообщений: 34,683 Записей в блоге: 14
	25.11.2012, 14:14
	Отвечаю: 1) алгоритм - модификация поиска в глубину (dfs) 2) в начале программы заводятся глобальные переменные (setq на верхнем уровне) 1

@ololo2412 0 / 0 / 0 Регистрация: 15.02.2011 Сообщений: 24
	25.11.2012, 15:10 [ТС]
	простите, а Вы могли бы мне вкратце рассказать принцип работы этой программы. я что-то не очень понимаю. 0

@ololo2412 0 / 0 / 0 Регистрация: 15.02.2011 Сообщений: 24
	26.11.2012, 13:07 [ТС]
	просто замечательно,спасибо большое! 0

jikos
	05.12.2012, 15:13
	Catstail, Здравствуйте, пробую ваше решение прохода конем из одной клетки в другую. не получается запустить в моей оболочке (использую newLisp, что первое скачалось). На лиспе до этого не писал. Хочу разобраться в одной задаче. Надо пройти конем по шахматной доске по всем клеткам и вернуться назад, в исходную клетку(А1), несколько раз находится в одной и той же клетке разрешено. Буду благодарен, если подскажите в каком лиспе писался ваш алгоритм. p.s. какое вижу решение: сначала использовать алгоритм прохода по всем клеткам доски без повторений, а потом вернуться назад по вашему коду. Подскажите, буду благодарен

@ololo2412 0 / 0 / 0 Регистрация: 15.02.2011 Сообщений: 24
	08.12.2012, 12:48 [ТС]
	у меня почему-то не работает, вот что выводит Миниатюры 0

@Catstail Супер-модератор 38161 / 21096 / 4306 Регистрация: 12.02.2012 Сообщений: 34,683 Записей в блоге: 14
	08.12.2012, 14:35
	А... Вместо (printline ...) в Common Lisp надо писать (print ...) (terpri) 0

@ololo2412 0 / 0 / 0 Регистрация: 15.02.2011 Сообщений: 24
	08.12.2012, 14:40 [ТС]
	теперь работает) а после последовательности ходов пишет Stack overflow (stack size 36000). 1 (continue) Extend stack by 50%. 2 Extend stack by 300%. 3 (abort) Return to level 2. 4 Return to debug level 2. 5 Extend stack by 50%. 6 Extend stack by 300%. 7 Return to level 1. 8 Return to debug level 1. 9 Extend stack by 50%. 10 Extend stack by 300%. 11 Return to level 0. 12 Return to top loop level 0. Type :b for backtrace, :c <option number> to proceed, or :? for other options 0

@Catstail Супер-модератор 38161 / 21096 / 4306 Регистрация: 12.02.2012 Сообщений: 34,683 Записей в блоге: 14
	10.12.2012, 22:43
	Спасибо за найденную ошибку. Буду разбираться. А использую я свой homelisp 1