Шахматная доска и шахматный конь

@Raven_13 · Регистрация: 25.09.2019

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

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

C++

#include <iostream>
 
using namespace std;
 
const int SIZE = 6;
 
void show_arr(const int[SIZE][SIZE]);
int max_horse_moves(int arr[SIZE][SIZE], int x, int y, int horse_path);
 
int main()
{
    int arr[SIZE][SIZE]{};
    int x, y;
    cout << "Enter coordinates x & y using space: ";
    cin >> x >> y;
    max_horse_moves(arr, x, y, 0);
    cout << "----------------------------------\n";
    show_arr(arr);
    return 0;
}
int max_horse_moves(int arr[SIZE][SIZE], int i, int j, int horse_path)
{
    arr[i][j] = ++horse_path;
    if (arr[i + 2][j + 1] < arr[SIZE][SIZE] && arr[i + 2][j + 1] == 0) return max_horse_moves(arr, (i + 2), (j + 1), horse_path);
    if (arr[i + 1][j + 2] < arr[SIZE][SIZE] && arr[i + 1][j + 2] == 0) return max_horse_moves(arr, (i + 1), (j + 2), horse_path);
    if (arr[i - 1][j - 2] >= arr[0][0] && arr[i - 1][j - 2] == 0) return max_horse_moves(arr, (i - 1), (j - 2), horse_path);
    if (arr[i - 2][j - 1] >= arr[0][0] && arr[i - 2][j - 1] == 0) return max_horse_moves(arr, (i - 2), (j - 1), horse_path);
    if (arr[i + 1][j - 2] >= arr[0][0] && arr[i + 1][j - 2] < arr[SIZE][SIZE] && arr[i + 1][j - 2] == 0) return max_horse_moves(arr, (i + 1), (j - 2), horse_path);
    if (arr[i - 1][j + 2] >= arr[0][0] && arr[i - 1][j + 2] < arr[SIZE][SIZE] && arr[i - 1][j + 2] == 0) return max_horse_moves(arr, (i - 1), (j + 2), horse_path);
    if (arr[i - 2][j + 1] >= arr[0][0] && arr[i - 2][j + 1] < arr[SIZE][SIZE] && arr[i - 2][j + 1] == 0) return max_horse_moves(arr, (i - 2), (j + 1), horse_path);
    if (arr[i + 2][j - 1] >= arr[0][0] && arr[i + 2][j - 1] < arr[SIZE][SIZE] && arr[i + 2][j - 1] == 0) return max_horse_moves(arr, (i + 2), (j - 1), horse_path);
    return 0;
}
 
void show_arr(const int arr[SIZE][SIZE])
{
    for (int i = 0; i < SIZE; i++)
    {
        for (int j = 0; j < SIZE; j++)
            cout << arr[i][j] << "\t ";
        cout << "\n";
    }   
}

Конь не коректно перемещается по массиву, доходя до края массива, конь перескакивает на его начало или конец, и вообще я хоть в правильном направлении двигаюсь?
Помогите пожалуйста кому не трудно понять что я делаю не так?

@Raven_13 · 28.09.2019, 16:46 **[ТС]**

сам себе отвечу

C++

#include <iostream>
 
using namespace std;
 
const int SIZE = 6;
 
void show_arr(const int[SIZE][SIZE]);
int max_horse_moves(int arr[SIZE][SIZE], int x, int y, int horse_path);
 
int main()
{
    int arr[SIZE][SIZE]{};
    int x, y;
    cout << "Enter coordinates x & y using space: ";
    cin >> x >> y;
    max_horse_moves(arr, x, y, 0);
    cout << "----------------------------------\n";
    show_arr(arr);
    return 0;
}
int max_horse_moves(int arr[SIZE][SIZE], int i, int j, int horse_path)
{
    arr[i][j] = ++horse_path;
    if (j + 1 < SIZE && i + 2 < SIZE && arr[i + 2][j + 1] == 0) 
        return max_horse_moves(arr, (i + 2), (j + 1), horse_path);
    if (j + 2 < SIZE && i + 1 < SIZE && arr[i + 1][j + 2] == 0)
        return max_horse_moves(arr, (i + 1), (j + 2), horse_path);
    if (j - 2 >= 0 && i - 1 >= 0 && arr[i - 1][j - 2] == 0)
        return max_horse_moves(arr, (i - 1), (j - 2), horse_path);
    if (j - 1 >= 0 && i - 2 >= 0 && arr[i - 2][j - 1] == 0)
        return max_horse_moves(arr, (i - 2), (j - 1), horse_path);
    if (j - 2 >= 0 && i + 1 < SIZE && arr[i + 1][j - 2] == 0) 
        return max_horse_moves(arr, (i + 1), (j - 2), horse_path);
    if (i - 1 >= 0 && j + 2 < SIZE && arr[i - 1][j + 2] == 0) 
        return max_horse_moves(arr, (i - 1), (j + 2), horse_path);
    if (i - 2 >= 0 && j + 1 < SIZE && arr[i - 2][j + 1] == 0) 
        return max_horse_moves(arr, (i - 2), (j + 1), horse_path);
    if (j - 1 >= 0 && i + 2 < SIZE && arr[i + 2][j - 1] == 0) 
        return max_horse_moves(arr, (i + 2), (j - 1), horse_path);
    return 0;
}
 
void show_arr(const int arr[SIZE][SIZE])
{
    for (int i = 0; i < SIZE; i++)
    {
        for (int j = 0; j < SIZE; j++)
            cout << arr[i][j] << "\t ";
        cout << "\n";
    }   
}

задание не выполнено, но хотя бы не перескакивает уже)

@~~Pvt~~ · 28.09.2019, 18:12

Raven_13, что и при const int SIZE = 6; коник не все обскакал?

@Raven_13 · 28.09.2019, 19:10 **[ТС]**

Тут дело не в размере, вот 8 на 8, он просто так сказать мат)) себе ставит. А мне вроде как надо сделать чтобы он выбирал путь так чтобы все поле обойти, если я верно задание конечно понял

C++

0        0       0       0       0       0       0       0
0        1       16      0       0       0       0       0
0        18      0       0       15      0       0       0
20       0       2       17      0       0       14      0
27       0       19      0       0       12      0       0
6        21      24      3       10      0       0       13
23       26      5       8       0       0       11      0
0        7       22      25      4       9       0       0

@~~Pvt~~ · 28.09.2019, 19:18

скорее пат, на то и рекурсия, уходя чистить надо после себя, а у 25 есть и другие варианты хода

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

Тут дело не в размере,

очень даже в нем

@Raven_13 · 28.09.2019, 19:44 **[ТС]**

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

скорее пат, на то и рекурсия, уходя чистить надо после себя, а у 25 есть и другие варианты хода

очень даже в нем

Pvt,

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

уходя чистить надо после себя,

Извините, не совсем понял этот момент, что имеется ввиду?
и последний ход 27 и там нету других ходов, или я и тут вас не понял?

@~~Pvt~~ · 28.09.2019, 19:51

27->26->25->другой ход, в данном случае рекурсия - это перебор ходов

@Raven_13 · 28.09.2019, 20:14 **[ТС]**

Ааа, ну да, точно, спасибо. Осталось понять почему...

@politoto · 29.09.2019, 08:15

В такой постановке задача решается без перебора в три строчки.
До того, как писать код, нужно найти с помощью карандаша и бумаги, в уме или в интернете

какое-нибудь одно циклическое частное решение этой головоломки.
http://chessvdk.ru/forum/index.php?topic=1459.0
http://chessvdk.ru/forum/index... 2589;image

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

Что-то вроде этого

C++

squares cycle{
 // ... ... ...
};
 
squares
hamilton_knight( square start)
{
     auto result{ cycle };
     std::rotate ( std::begin( result ), 
               std::find ( std::begin(result), std::end(result), start ),
               std::end(result) 
     );    
     return result; 
 
}

Рекурсию можно использовать пару раз вместо циклов, если просят.

@~~Pvt~~ · 30.09.2019, 08:57

Raven_13, так что решение найдено?
как и в шахматах начало координат внизу слева:

@Raven_13 · 01.10.2019, 14:55 **[ТС]**

К сожалению нет, но крайне благодарен за помощь. Пока что отложил данную задачку в сторону, ибо и с другими нужно разобраться.

@_Ivana · 03.10.2019, 11:44

Прикольная задачка

Lisp

(defn vs [[x y] s]
  (for [i [-2 -1 1 2]
        j [-2 -1 1 2]
        :let [x' (+ x i)
              y' (+ y j)]
        :when (and (#{-2 2} (* i j))
                   (<= 1 x' 8)
                   (<= 1 y' 8)
                   (not (contains? s [x' y'])))]
    [x' y']))
 
(defn f [w s]
  (let [p (last w)]
    (if (= 64 (count s))
      w
      (->> (vs p s)
           (sort-by #(->> (conj s p) (vs %) count))
           (map #(f (conj w %) (conj s %)))
           (some identity)))))
 
(defn task [[c d]]
  (let [c-off (dec (int \a))
        d-off (int \0)
        p [(- (int c) c-off) (- (int d) d-off)]
        p->str (fn [[x y]] (str (char (+ x c-off)) y))]
    (->> (f [p] #{p}) (mapv p->str))))
 
(time (task "a1"))
 
=> "Elapsed time: 6.513563 msecs"
["a1" "b3" "a5" "b7" "d8" "f7" "h8" "g6" "f8" "h7" "g5" "h3" "g1" "e2" "c1" "a2" "b4" "a6" "b8" "c6" "a7" "c8" "e7" "g8" "h6" "g4" "h2" "f1" "d2" "b1" "a3" "c2" "e1" "f3" "h4" "g2" "e3" "d1" "b2" "a4" "c3" "b5" "d4" "f5" "d6" "c4" "e5" "d3" "f2" "h1" "g3" "e4" "c5" "d7" "b6" "a8" "c7" "d5" "f4" "e6" "g7" "e8" "f6" "h5"]
 
(time (task "e2"))
 
=> "Elapsed time: 3.768018 msecs"
["e2" "g1" "h3" "f2" "h1" "g3" "f1" "h2" "g4" "h6" "g8" "e7" "c8" "a7" "b5" "a3" "b1" "d2" "b3" "a1" "c2" "e1" "g2" "h4" "f3" "d4" "f5" "e3" "d1" "b2" "a4" "c3" "a2" "c1" "d3" "b4" "a6" "b8" "c6" "a5" "b7" "d8" "f7" "h8" "g6" "e5" "c4" "d6" "e4" "c5" "d7" "b6" "a8" "c7" "d5" "f4" "h5" "f6" "e8" "g7" "e6" "f8" "h7" "g5"]

@politoto · 03.10.2019, 13:46

_Ivana, можно сделать поиск "от сих до сих" ( в этом случае, очевидно, не всегда есть решение ) или замкнутого маршрута?

@_Ivana · 03.10.2019, 13:53

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

Про "от сих до сих" не понял что имеется в виду.

Добавлено через 4 минуты
ЗЫ про не тот раздел - я специально не стал писать на плюсах. Во-первых, это неудобно и вербозно, то, что пишется на Лиспе в 10 строк на Хаскеле пишется в 5 а на С++ в 100. Во-вторых, Лисп сейчас мой основной рабочий язык, и конечно мне и удобнее его использовать - не надо гуглить и вспоминать как сделать тривиальные вещи. Ну и в-третьих, я не хочу потокать халяве и выкладывать ТС готовый кот. Если интересен алгоритм - он и из Лиспового кота вычленяется.

@politoto · 03.10.2019, 14:16

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

Про "от сих до сих" не понял что имеется в виду.

Например, из пункта h1 в пункт b8

@_Ivana · 03.10.2019, 16:07

В постановке из пункта p0 в пункт p1 решается тривиально. Если же добавить условия стартового поста - при этом посетить все клетки, причем только единожды, тогда мой кот будет вести себя как с поиском циклов - для каких-то входных данных будет работать мгновенно, а для каких-то недопустимо медленно. Это другая задача - накладывать дополнительные условия на финальную точку маршрута, и имхо для нее нужен другой алгоритм.

@politoto · 03.10.2019, 16:19

В уме я решаю эту головоломку ( поиск замкнутого маршрута ) склеиванием непересекающихся циклов, покрывающих всю доску.

@~~Pvt~~ Заблокирован
	28.09.2019, 18:12	3
	Raven_13, что и при `const int SIZE = 6;` коник не все обскакал? 0

@~~Pvt~~ Заблокирован
	28.09.2019, 19:18	5
	скорее пат, на то и рекурсия, уходя чистить надо после себя, а у 25 есть и другие варианты хода Сообщение от Raven_13 Тут дело не в размере, очень даже в нем 0

@Raven_13 64 / 2 / 0 Регистрация: 25.09.2019 Сообщений: 6
	28.09.2019, 19:44 [ТС]	6
	Сообщение от Pvt скорее пат, на то и рекурсия, уходя чистить надо после себя, а у 25 есть и другие варианты хода очень даже в нем Pvt, Сообщение от Pvt уходя чистить надо после себя, Извините, не совсем понял этот момент, что имеется ввиду? и последний ход 27 и там нету других ходов, или я и тут вас не понял? 0

@~~Pvt~~ Заблокирован
	28.09.2019, 19:51	7
	27->26->25->другой ход, в данном случае рекурсия - это перебор ходов 1

@Raven_13 64 / 2 / 0 Регистрация: 25.09.2019 Сообщений: 6
	28.09.2019, 20:14 [ТС]	8
	Ааа, ну да, точно, спасибо. Осталось понять почему... 0

@Raven_13 64 / 2 / 0 Регистрация: 25.09.2019 Сообщений: 6
	01.10.2019, 14:55 [ТС]	11
	К сожалению нет, но крайне благодарен за помощь. Пока что отложил данную задачку в сторону, ибо и с другими нужно разобраться. 0

@politoto Модератор 1783 / 881 / 164 Регистрация: 23.07.2018 Сообщений: 3,052 Записей в блоге: 3
	03.10.2019, 13:46	13
	_Ivana, можно сделать поиск "от сих до сих" ( в этом случае, очевидно, не всегда есть решение ) или замкнутого маршрута? 0

@_Ivana 4816 / 2276 / 287 Регистрация: 01.03.2013 Сообщений: 5,944 Записей в блоге: 27
	03.10.2019, 13:53	14
	Замкнутый маршрут ищет с тривиальным добавлением одной строчки в код, но из каких-то точек быстро, а из каких-то не дождался завершения. Но тут вы правы, можно найти любой замкнутый маршрут и циклически его сдвигать. Про "от сих до сих" не понял что имеется в виду. Добавлено через 4 минуты ЗЫ про не тот раздел - я специально не стал писать на плюсах. Во-первых, это неудобно и вербозно, то, что пишется на Лиспе в 10 строк на Хаскеле пишется в 5 а на С++ в 100. Во-вторых, Лисп сейчас мой основной рабочий язык, и конечно мне и удобнее его использовать - не надо гуглить и вспоминать как сделать тривиальные вещи. Ну и в-третьих, я не хочу потокать халяве и выкладывать ТС готовый кот. Если интересен алгоритм - он и из Лиспового кота вычленяется. 0

@politoto Модератор 1783 / 881 / 164 Регистрация: 23.07.2018 Сообщений: 3,052 Записей в блоге: 3
	03.10.2019, 14:16	15
	Сообщение от _Ivana Про "от сих до сих" не понял что имеется в виду. Например, из пункта h1 в пункт b8 0

@_Ivana 4816 / 2276 / 287 Регистрация: 01.03.2013 Сообщений: 5,944 Записей в блоге: 27
	03.10.2019, 16:07	16
	В постановке из пункта p0 в пункт p1 решается тривиально. Если же добавить условия стартового поста - при этом посетить все клетки, причем только единожды, тогда мой кот будет вести себя как с поиском циклов - для каких-то входных данных будет работать мгновенно, а для каких-то недопустимо медленно. Это другая задача - накладывать дополнительные условия на финальную точку маршрута, и имхо для нее нужен другой алгоритм. 0

@politoto Модератор 1783 / 881 / 164 Регистрация: 23.07.2018 Сообщений: 3,052 Записей в блоге: 3
	03.10.2019, 16:19	17
	В уме я решаю эту головоломку ( поиск замкнутого маршрута ) склеиванием непересекающихся циклов, покрывающих всю доску. 0