перебор конём шахматной доски

тут не перебор, а backtracking.

Известная задача. Читай про backtracking, там легко.

https://en.wikipedia.org/wiki/Backtracking

Спасибо.

Ты серьезно? В книге этого Столярова ничего нет про поиск с возвратом (backtracking, как тут уже написал товарищ)? На фиг тогда эта книга. Советую перестать читать это муру. И взять любой нормальный учебник по программированию, например.

Например например?

Как задача сформулирована? От какой клетки до какой нужно перебрать конём шахматное поле?

https://ru.wikipedia.org/wiki/Задача_о_ходе_коня

От 0, 0 к 0, 0. Доска в 8 ячеек.

Я понял, кажется должно быть всего 8! возможных перебров, а у меня просто баг. Может полное поле неправильно ловлю.

Я понял о чём вы. Вы думаете что я не додумался запоминать ходы?

От 0,0 к 0,0 на доске 8x8? Берёте из интернетов любой готовый замкнутый маршрут коня, циклически переставляете так, чтобы 0,0 была в начале и распечатываете.

И переборы не нужны. Только поиск максимум длины 64 в готовом циклическом маршруте.

Спасибо, здравствуйте.

Под перебором имеется ввиду наступлением конём на каждое поля (то есть все поля на доске) один и только один раз.

Под перебором имеется ввиду наступлением конём на каждое поле (то есть все поля на доске) один и только один раз.

Погуглите «benchmarks обход конем».

Владимир

По гамильтонову циклу пройдётесь от a1 до a1. По определению побываете на каждой клетке (кроме a1) по одному разу

Оказывается что для пяти, шести и семи полей работает за доли секунды. Но дальше… тотальный пештидор.

Может кто рассксзать — на восьми-ячейной доске нужно 40000 итераций для полного обхода или всёже (64!)? Я вытерпел 11 триллионов итераций — ничего не родилось.

Откуда ты взял этот бред про факториал? И откуда вообще вопрос про «сколько итераций»? Если ты сам писал программу то должен знать сколько итераций ей нужно. Невозможно написать алгоритм (если он только не рандомный) и при этом не знать сколько циклов он сделает. Ты наверно скачал с инета готовое решение и хочешь чтобы тут тебе объяснили где в нём баг?

Да. Сколько раз вы сможете написать точку в каждой ячейке доски 8x8? 64 раза? Скажем что рисование точки — это итерация.

Хорошо, а сколько раз конь сможет обскакать всю доску таким образом, дабы путь ячеек не повторялся и конь проскакал всю именную область?

Например: 0->11->5->22 (предположим что доска в одномерном массиве) не равна 0->11->28->22

Вы понимаете. Сколько таких имён есть у доски 8x8? Я могу вывести закономерность с доски 6x6 и 5x5, но я уже своим указом приказал завершить задачу.

Думаю Вам не хватает любви, советую прочесть парочку историй Ошейник-тян, пообщаться с понифагом, а также почитать книгу «rust prigramming language book» последнего издания.

there are approximately 4×10^51 possible move sequences on an 8 × 8 board

On an 8 × 8 board, there are exactly 26,534,728,821,064 directed closed tours

https://en.wikipedia.org/wiki/Knight%27s_tour#Finding_tours_with_computers

Перечисление всех решений затянется. Одно решение из триллионов можно найти прекалком. Не такая уж нерешаемая головоломка.

Насколько я помню - эту задачку проходят в теме «Рекурсия».

А самое большое удивление было в ней от того, что один и тот же алгоритм скомпилированный Symantec C++ 7.5 для 16-бит DOS исполнялся 1 секунду, а Visual Studio C++ 6.0 для 32-бит WinConsole - 8 секунд на одной и той же машине. (Нашёл тут свои записульки)

А условие полностью можно? Нужно найти один (первый встретившийся, на этом выход) закрытй маршрут коня? Т.е. из 0,0 в 0,0.

Имеется еще один интересный вопрос - «С любой ли клетки можно обойти все клетки без повторения?».

PS: Наверное задача интересная, но для чего на нее тратить время мне не понятно.

Владимир

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

И какая возможна геометрия доски? Только 8x8, только квадратная, только прямоугольная?

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

ИМХО, не очевидно.

Владимир

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

Странно, что ты решал задачу быстро для поля из 7 клеток. Я тут тоже накостылил решение, 6 нормально решает, с семью не стал ждать.

#include <iostream>
#include <iterator>
#include <vector>
#include <array>
#include <unordered_set>

using namespace std;

constexpr int path_cnt = 1;
using pos_t = long;
constexpr pos_t miss = 100;
#define EXTR_X(pair) ((pair)>>32 & 0xffff)
#define EXTR_Y(pair) ((pair) & 0xffff)
#define SET_X(x, pair) ((pair) |= static_cast<pos_t>(x)<<32)
#define SET_Y(y, pair) ((pair) |= y)

template <int size>
array<pos_t, 8> get_steps(pos_t cur_pos) {
#define CHECK(val) ((val)>=size || (val)<0 ? miss : (val))
	array<pos_t, 8> steps {};
	pos_t x = EXTR_X(cur_pos);
	pos_t y = EXTR_Y(cur_pos);
	SET_X(CHECK(x-1), steps[0]);
	SET_X(CHECK(x-1), steps[1]);
	SET_X(CHECK(x+1), steps[2]);
	SET_X(CHECK(x+1), steps[3]);
	SET_X(CHECK(x-2), steps[4]);
	SET_X(CHECK(x-2), steps[5]);
	SET_X(CHECK(x+2), steps[6]);
	SET_X(CHECK(x+2), steps[7]);
	SET_Y(CHECK(y+2), steps[0]);
	SET_Y(CHECK(y-2), steps[1]);
	SET_Y(CHECK(y+2), steps[2]);
	SET_Y(CHECK(y-2), steps[3]);
	SET_Y(CHECK(y+1), steps[4]);
	SET_Y(CHECK(y-1), steps[5]);
	SET_Y(CHECK(y+1), steps[6]);
	SET_Y(CHECK(y-1), steps[7]);
#undef CHECK
	return steps;
}

template <int size>
void step_inter(vector<vector<pos_t>> &data, unordered_multiset<pos_t> &used) {
	array<pos_t, 8> steps = get_steps<size>(data.back().back());
	for (pos_t next : steps) {
		if (data.size() > path_cnt)
			return;
		pos_t x = EXTR_X(next);
		pos_t y = EXTR_Y(next);
		if (x == miss  ||  y == miss)
			continue;
		if (x == 0  &&  y == 0) {
			if (data.back().size() != size*size)
				continue;
			data.push_back(data.back());
			data.back().reserve(size*size);
			data[data.size()-2].push_back(next);
			break;
		}
		if ( used.contains(next) )
			continue;
		data.back().push_back(next);
		used.insert(next);
		step_inter<size>(data, used);
		data.back().pop_back();
		used.erase(next);
	}
}

template <int size>
void step(vector<vector<pos_t>> &data) {
	unordered_multiset<pos_t> used;
	step_inter<size>(data, used);
}


int main() {
	constexpr unsigned field_size = 7;
	vector<vector<pos_t>> paths{ {0} };
	paths.back().reserve(field_size*field_size);
	step<field_size>(paths);
	paths.pop_back();

	for (auto &path : paths) {
		cout << "--------path--------\n";
		for (auto cell : path)
			cout << EXTR_X(cell) << "  " << EXTR_Y(cell) << endl;
	}

	return 0;
}

$ g++ -std=c++20 -O2 1.cc

field_size - задает размер поля.
path_cnt - количество закрытых путей, которые необходимо найти.
Для поля из 6 клеток:

--------path--------
0  0
1  2
0  4
2  5
1  3
0  5
2  4
3  2
2  0
0  1
2  2
4  1
5  3
4  5
3  3
5  4
3  5
1  4
0  2
1  0
3  1
5  0
4  2
3  4
5  5
4  3
5  1
3  0
1  1
0  3
1  5
2  3
4  4
5  2
4  0
2  1
0  0

Тебе рано заниматься этой задачей. Пройди для начала предыдущие (указанную книгу не видел, но думаю там они есть), только не готовыми ответами с инета, а самостоятельно. А ещё это твоё сообщение местами похоже на гуглоперевод с английского - подучи навыки русской речи заодно.

А какую вы задачу решаете?

Для старта коня в левом верхнем углу (0,0) для поля 8х8 - она у меня и сейчас решается за секунду, проверил.

|  1 | 38 | 55 | 34 |  3 | 36 | 19 | 22 |
-----------------------------------------
| 54 | 47 |  2 | 37 | 20 | 23 |  4 | 17 |
-----------------------------------------
| 39 | 56 | 33 | 46 | 35 | 18 | 21 | 10 |
-----------------------------------------
| 48 | 53 | 40 | 57 | 24 | 11 | 16 |  5 |
-----------------------------------------
| 59 | 32 | 45 | 52 | 41 | 26 |  9 | 12 |
-----------------------------------------
| 44 | 49 | 58 | 25 | 62 | 15 |  6 | 27 |
-----------------------------------------
| 31 | 60 | 51 | 42 | 29 |  8 | 13 | 64 |
-----------------------------------------
| 50 | 43 | 30 | 61 | 14 | 63 | 28 |  7 |
-----------------------------------------
Start time: 1617444766 : Sat Apr  3 17:12:46 2021
End time: 1617444767  : Sat Apr  3 17:12:47 2021
Total seconds: 1

Просьба проверить с любой ли клетки можно произвести обход.

Владимир

у меня такое в качестве лабораторки в универе когда-то было :)

Но при этом поиск для 8 и 9 может длиться десятки минут. Наверное, какой-то баг, но я его не вижу.

Исходник покажите.

Немного обманул. Я ищу первый незамкнутый маршрут. В книге сказанно про замкнутый. Задача как таковая не даётся читателю, Столяров рассказывает про визуализацию этой задачи студентами с помощью интерпитатора tcl/tk. Я захотел повторить. Вот тут моё решение: [rocketgit] (https://rocketgit.com/user/panaceya/ChessHorse/source/tree/).

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

Спасибо. Ваши сообщения напоминают мне о отечестве. :3

У вас какой-то хак, одних закрытых маршрутов около 26 трлн (встречал инфу, не считал сам), а вместе с закрытыми вообще тьма. Я никак не читерил. У вас какой-нибудь алгоритм, наверное.

Задача закрыта, мне надоело тратить в неё время, лучше пописать ерунду на LOR.

Посмотрите исходники других программистов https://github.com/search?q=ChessHorse

Владимир

Умные люди уже 400 лет как всё проверили: https://ru.wikipedia.org/wiki/Задача_о_ходе_коня

--------------

Вот, для старта в (0,1)

| 36 | 45 |  2 | 47 | 34 | 29 |  4 | 13 |
-----------------------------------------
|  1 | 48 | 35 | 28 |  3 | 14 | 31 | 16 |
-----------------------------------------
| 44 | 37 | 46 | 33 | 30 | 17 | 12 |  5 |
-----------------------------------------
| 49 | 58 | 27 | 42 | 51 | 32 | 15 | 10 |
-----------------------------------------
| 38 | 43 | 50 | 59 | 18 | 11 |  6 | 21 |
-----------------------------------------
| 57 | 26 | 55 | 52 | 41 | 20 |  9 | 62 |
-----------------------------------------
| 54 | 39 | 24 | 19 | 60 | 63 | 22 |  7 |
-----------------------------------------
| 25 | 56 | 53 | 40 | 23 |  8 | 61 | 64 |
-----------------------------------------
Start time: 1617445164 : Sat Apr  3 17:19:24 2021
End time: 1617446101  : Sat Apr  3 17:35:01 2021
Total seconds: 937

Исходники?

Да пожалуйста: https://pastebin.com/94cinnYR

Это оригинальные, «тогдашние». Сейчас только на скорую руку поменял весь DOS-овский вывод в консоль на обычный, чтоб запустилось на дачном ArchLinux.

Ей-богу, эта задачка была в режиме «дети, смотрите как здорово и удобно использовать рекурсию». Никакого другого педагогического смысла в ней не было.

Молодец!

А теперь просьба проверить алгоритм если конь будет ходить так

| | | | 2 | | | | |

| 1 | | | | | | | |

Владимир

Молодец!

А теперь просьба проверить алгоритм если конь будет ходить так

|    |    |    |  2 |    |    |    |    |
-----------------------------------------
|  1 |    |    |    |    |    |    |    |

Владимир

Тогда он на белую клетку никогда не попадёт.

Тогда он на белую клетку никогда не попадёт.

Точно!
На sql.ru больше года шло обсуждение задачи о расстановке восьми ферзей.

Владимир

Сам подумай. Если существует маршрут обхода доски, значит любая клетка в нем должна быть. Маршруты существуют, значит можно с любой клетки.

Ясно, вообще я решал много более сложную задачу нежели вы, который искал открытый путь, я же искал закрытый путь т.е. если стартуем в точке 0:0, то последний ход должен быть в неё же. Посмотрите внимательно на координаты начала и конца (выхлоп для доски 6х6), они совпадают:

$ ./a.out
--------path--------x:y
0:0 1:2 0:4 2:5 1:3 0:5 2:4 3:2 2:0 0:1 2:2 4:1 5:3 4:5 3:3 5:4 3:5 1:4 0:2 1:0 3:1 5:0 4:2 3:4 5:5 4:3 5:1 3:0 1:1 0:3 1:5 2:3 4:4 5:2 4:0 2:1 0:0

Что касется открытого пути как у вас для поля из 8 клеток, то и его моя поделка решает, правда дольше - за секунд 50, но я не занимался оптимизацией поиска совсем, мне это и не сильно интересно. Зато я умею искать не первый попавшийся путь, а найти несколько решений )) (поле 8 клеток):

$ time ./a.out
--------path--------x:y
0:0 1:2 0:4 1:6 2:4 3:6 4:4 3:2 2:0 0:1 1:3 0:5 1:7 2:5 3:7 4:5 3:3 2:1 0:2 1:4 0:6 2:7 1:5 0:7 2:6 3:4 2:2 1:0 3:1 2:3 3:5 4:7 6:6 7:4 6:2 7:0 5:1 4:3 5:5 6:7 4:6 5:4 7:3 6:1 4:0 5:2 6:0 4:1 5:3 7:2 6:4 7:6 5:7 6:5 7:7 5:6 7:5 6:3 7:1 5:0 4:2 3:0 1:1 0:3
--------path--------x:y
0:0 1:2 0:4 1:6 2:4 3:6 4:4 3:2 2:0 0:1 1:3 0:5 1:7 2:5 3:7 4:5 3:3 2:1 0:2 1:4 0:6 2:7 1:5 0:7 2:6 3:4 2:2 1:0 3:1 2:3 3:5 4:7 6:6 7:4 6:2 7:0 5:1 4:3 5:5 6:7 4:6 5:4 7:3 5:2 4:0 6:1 5:3 4:1 6:0 7:2 6:4 7:6 5:7 6:5 7:7 5:6 7:5 6:3 7:1 5:0 4:2 3:0 1:1 0:3
--------path--------x:y
0:0 1:2 0:4 1:6 2:4 3:6 4:4 3:2 2:0 0:1 1:3 0:5 1:7 2:5 3:7 4:5 3:3 2:1 0:2 1:4 0:6 2:7 1:5 0:7 2:6 3:4 2:2 1:0 3:1 2:3 3:5 4:7 6:6 7:4 6:2 7:0 5:1 4:3 5:5 7:6 5:7 6:5 7:7 5:6 6:4 7:2 6:0 4:1 5:3 6:1 4:0 5:2 7:3 5:4 4:6 6:7 7:5 6:3 7:1 5:0 4:2 3:0 1:1 0:3
--------path--------x:y
0:0 1:2 0:4 1:6 2:4 3:6 4:4 3:2 2:0 0:1 1:3 0:5 1:7 2:5 3:7 4:5 3:3 2:1 0:2 1:4 0:6 2:7 1:5 0:7 2:6 3:4 2:2 1:0 3:1 2:3 3:5 4:7 6:6 7:4 6:2 7:0 5:1 4:3 5:5 7:6 5:7 6:5 7:7 5:6 6:4 7:2 5:3 4:1 6:0 5:2 4:0 6:1 7:3 5:4 4:6 6:7 7:5 6:3 7:1 5:0 4:2 3:0 1:1 0:3
--------path--------x:y
0:0 1:2 0:4 1:6 2:4 3:6 4:4 3:2 2:0 0:1 1:3 0:5 1:7 2:5 3:7 4:5 3:3 2:1 0:2 1:4 0:6 2:7 1:5 0:7 2:6 3:4 2:2 1:0 3:1 2:3 3:5 4:7 6:6 7:4 6:2 7:0 5:1 4:3 6:4 7:2 6:0 4:1 5:3 6:1 4:0 5:2 7:3 5:4 4:6 6:7 5:5 7:6 5:7 6:5 7:7 5:6 7:5 6:3 7:1 5:0 4:2 3:0 1:1 0:3
--------path--------x:y
0:0 1:2 0:4 1:6 2:4 3:6 4:4 3:2 2:0 0:1 1:3 0:5 1:7 2:5 3:7 4:5 3:3 2:1 0:2 1:4 0:6 2:7 1:5 0:7 2:6 3:4 2:2 1:0 3:1 2:3 3:5 4:7 6:6 7:4 6:2 7:0 5:1 4:3 6:4 7:2 6:0 4:1 5:3 6:1 4:0 5:2 7:3 5:4 4:6 6:7 7:5 5:6 7:7 6:5 5:7 7:6 5:5 6:3 7:1 5:0 4:2 3:0 1:1 0:3
...
real    0m59.392s
user    0m59.351s
sys     0m0.004s