LINUX.ORG.RU

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

 


1

3

Вот такая задачка есть у Столярова в третьем томе рядом с tcl/tk.

Как и положено, понял суть задачи только после написания первого решения.

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

По всей видимости, переборов нужно 64!, но я круглый электрик-гумантирай. Багов не обнаружил.

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

Как решить такую задачу?

Интересно что поиск для досок на

полейзанимает времени
50.019u
60.559u
70.502u

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

Перемещено leave из general

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

anonymous ()
Ответ на: комментарий от vM

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

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

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

yufhgigibi ()
Ответ на: комментарий от yufhgigibi

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

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

vM ()

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

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

yufhgigibi ()
Ответ на: комментарий от yufhgigibi

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

firkax ()
Ответ на: комментарий от firkax

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

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

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

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

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

yufhgigibi ()

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

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

anonymous ()

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

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

Владимир

anonymous ()
Ответ на: комментарий от vM

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

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

Владимир

anonymous ()

Странно, что ты решал задачу быстро для поля из 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
pavlick ★★ ()
Последнее исправление: pavlick (всего исправлений: 1)
Ответ на: комментарий от yufhgigibi

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

firkax ()
Ответ на: комментарий от pavlick

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

Для старта коня в левом верхнем углу (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
anonymous ()

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

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

anonymous ()
Ответ на: комментарий от pavlick

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

yufhgigibi ()
Ответ на: комментарий от yufhgigibi

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

grem ★★★★★ ()
Последнее исправление: grem (всего исправлений: 1)
Ответ на: комментарий от anonymous

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

pavlick ★★ ()
Ответ на: комментарий от anonymous

Умные люди уже 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
А в тех записульках было 1800 секунд. Ну, значит мой нынешний дачный компутер в два раза быстрее тогдашнего рабочего )

anonymous ()
Ответ на: комментарий от pavlick

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

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

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

anonymous ()
Ответ на: комментарий от anonymous

Ясно, вообще я решал много более сложную задачу нежели вы, который искал открытый путь, я же искал закрытый путь т.е. если стартуем в точке 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
pavlick ★★ ()