Обход конем шахматной доски python

Путь коня по всем клеткам шахматной доски N×M

Требуется, начиная с некоторой исходной позиции, обойти конем все клетки шахматной доски N×M, посетив каждую клетку ровно один раз.
Путь коня вывести в виде матрицы с номерами ходов, на которых конь посещает соответствующую клетку. Считать, что клетка, на которой конь стоит изначально, посещается на нулевом ходу.
Если невозможно обойти конем все клетки заданной доски, вывести «Нет решения.» (без кавычек).

В первой строке вводится пара чисел N и M через пробел (1 Во второй строке вводится исходная позиция коня в шахматной нотации.

Выведите искомый путь коня.

Вывод:
24 17 2 11 22
7 12 23 16 3
18 1 6 21 10
13 8 19 4 15
0 5 14 9 20

Пример 2:

Ввод:
2 2
A1

Вывод:
Нет решения.

Ограничения:

Время: 1 с
Память: 64 Мб

Добавлено через 5 часов 12 минут
Эту задачу одолел:

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

#Правило Варнсдорфа #При обходе доски конь следует #на то поле, с которого можно #пойти на минимальное число #ещё не пройденных полей. #Если таких полей несколько, то #требуется перебор с возвратом. n, m = map(int, input().split()) pos = input() x0 = n - int(pos[1]) y0 = ord(pos[0]) - ord('A') #Суммарное количество клеток доски. cells_total = n * m #Инициализация доски. board = [[-1] * m for _ in range(n)] visited = [[False] * m for _ in range(n)] #Список допустимых ходов коня. moves = [(1, 2), (-1, -2), (2, 1), (-2, -1), (-1, 2), (1, -2), (-2, 1), (2, -1)] #Функция проверки координат #на соответствие границам доски. def check_bounds(x, y): return -1  x  n and -1  y  m #Функция проверки состояния клетки #(посещена клетка или еще нет). def is_visited(x, y): return visited[x][y] #Функция, возвращающая список #непосещённых клеток доски, #на которые конь может пойти #с данной позиции. def get_move_list(x, y): available_moves = [] for dx, dy in moves: xnew, ynew = x + dx, y + dy if check_bounds(xnew, ynew): if not is_visited(xnew, ynew): available_moves.append((xnew, ynew)) return available_moves #Рекурсивная функция решения #задачи о пути коня по доске. #Возвращает True, если путь #найден, и False иначе. def tour(x, y, move_number): #Отмечаем текущую клетку #как посещенную. visited[x][y] = True #Если отмечаемый номер соответствует #суммарному количеству клеток доски, #то возвращаем True (нашли решение). answer = False if move_number == cells_total - 1: board[x][y] = move_number; answer = True else: move_list = get_move_list(x, y) if len(move_list) != 0: #Получение количества полей, #которые доступных с полей #из текущего списка. neighbors = [ \ (len(get_move_list(xnew, ynew)), (xnew, ynew)) \ for xnew, ynew in move_list] #Определение минимального #количества полей, доступных #с клеток из списка. neighbors_min = min([pair[0] for pair in neighbors]) #Отбор тех полей из списка, #с которых можно пойти на #минимальное число ещё не #пройденных полей. canditates = [pair[1] for pair in neighbors \ if pair[0] == neighbors_min] #Рекурсивно вызываем функцию #для каждого из полей-кандидатов, #пока не решим задачу или не #переберем всех кандидатов. for xnew, ynew in canditates: if tour(xnew, ynew, move_number + 1): board[x][y] = move_number; answer = True break visited[x][y] = False return answer if tour(x0, y0, 0): for row in board: print(*row) else: print("Нет решения.")

Остались две нерешенные (на текущий момент) проблемы:

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

Движение коня по всем 64 клеткам шахматной доски так, чтобы он появился на каждом поле по одному разу
Помогите с решениям. А то моих знаний С++ не достаточно Условие задачи: Шахматный конь: Написать.

Пройти конем по всем клеткам шахматной доски
Всем доброго времени суток! Есть задача по которой нужно реализовать прохождения шахмотной фигуры.

Составить программу обхода шахматным конем шахматной доски по всем клеткам
Составить программу обхода шахматным конем шахматной доски по всем клеткам, не побывав на каждой.

Теория графов (ходом коня пройти по всем ячейкам шахматной доски)
можно ли ходом коня пройти по всем ячейкам шахматной доски (8х8)? если можно напишите алгоритм.

Источник

Python алгоритмы

Блог про алгоритмы и все что с ними связано. Основной инструмент реализации — Python.

Дай 10 !)

четверг, 25 апреля 2013 г.

Задача о путешествии шахматного коня

Задача о ходе коня — задача о нахождении маршрута шахматного коня, проходящего через все поля доски по одному разу.

Эта задача известна по крайней мере с XVIII века. Леонард Эйлер посвятил ей большую работу «Решение одного любопытного вопроса, который, кажется, не подчиняется никакому исследованию» (датируется 26 апреля 1757 года).

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

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

Итак, каждый ход мы будем характеризовать 3-мя числами: его порядковым номером i и парой координат x, y. История ходов будет храниться в матрице списков, в соответствующей ячейке записываем порядковый номер хода. Соответственно, если в ячейке 0, значит туда мы еще не ходили.

Важно определиться с вычислением новой координаты. Можно заметить, что у коня есть 8 позиций-кандидатов (u, v) куда может прыгнуть конь.
Будем получать новые координаты прибавляя соответствующие смещения, хранящиеся в 2х списках dx, dy и отслеживать допустимость хода (находимся в пределах доски).

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

Очень советую читать именно алгоритм, тем более Питон в этом сильно помогает. Это даст куда больше толку. чем множество лишних слов!)

#Задача о коняшке def knightsTour(x0, y0, done, size=5): #создаем шахматную доску в виде 2го списка h = [[0 for j in xrange(size)] for i in xrange(size)] #начальная координата(1го хода) h[x0][y0] = 1 #Возможные ходы dx = [2, 1, -1, -2, -2, -1, 1, 2] dy = [1, 2, 2, 1, -1, -2, -2, -1] def CanBeDone(u, v, i): h[u][v] = i done = tryNextMove(u, v, i) if not done: h[u][v] = 0 return done def tryNextMove(x,y, i): #eos - показывает все ли варианты возможных 8ми ходов мы рассмотрели #done - показывает удачна ли данная ветка решения #k - порядковый номер рассмотренной попытки из 8 допустимых env = def next(): x = env['u'] y = env['v'] while env['k'] < 8: env['k'] +=1; if env['k'] < 8: env['u'] = x + dx[env['k']] env['v'] = y + dy[env['k']] if (env['u'] >= 0 and env['u']=0 and env['v']
Источник
Обход доски шахматным конем
Помогите исправить код 
В задаче необходимо обойти поле, например 8*8, ходом шахматного коня 
Я написал программу, но все поле не заполняется.
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
 
n=int(input('Размер Поля: ')) n=n+4 a=[[0 for j in range (n)] for i in range (n)] for i in range(2): for j in range(n): a[i][j]=1 a[j][i]=1 a[n-i-1][j]=1 a[j][n-i-1]=1 i,j=map(int,input('Введите координаты: ').split()) i+=2 j+=2 si=[ -2, -1, 1, 2, 2, 1, -1, -2 ] sj=[ 1, 2, 2, 1, -1, -2, -2, -1 ] m=1 t=True while t: a[i][j]=m for g in range(8): if a[i+si[g]][j+sj[g]]==0: i+=si[g] j+=sj[g] m+=1 break else: t=False for i in a: for j in i: print('%4d'%j, end='') print()
 
Написать программу обхода шахматной доски конем, начиная с данной клетки
2.Написать программу обхода шахматной доски конем, начиная с данной клетки. На каждой клетке конь.
 
Обход доски шахматным конем
решал задачу "Тур конем". : На шахматной доске размером n*n на поле с координатами x0,y0 находится.
 
Обход доски шахматным конем
Buillder 6 никак не получается вывести на экран массив, помогите пожалуйта, уже не знаю что делать
 
Написать программу, реализующую обход доски шахматным конём
Конь находится в клетке (x1,y1).Нужно вывести любой его путь из (x1,y1) в (x2,y2).Если это.
 
 
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
 
n = 8 a = [[-1] * n for _ in range(n)] move = [(-2, 1), (-1, 2), (1, 2), (2, 1), (2, -1), (1, -2), (-1, -2), (-2, -1)] def foo(i, j, pos): if pos == n * n: return True for mi, mj in move: i_new = i + mi j_new = j + mj if 0  i_new  n and 0  j_new  n and a[i_new][j_new] == -1: a[i_new][j_new] = pos if foo(i_new, j_new, pos + 1): return True a[i_new][j_new] = -1 return False x = 0 y = 0 a[x][y] = 0 if foo(x, y, 1): for row in a: print(*row)
 
как сказал классик: 
Давай мне деньги неси, давай мне деньги неси
 
в интернете куча же решений этой задачи.
 
Обойти шахматным конем все клетки доски
Составить программу рбхода шахматным конем шахматной доски, побывав на каждом пое по одному разу.
 
 
 Составить программу обхода шахматным конем шахматной доски по всем клеткам
Составить программу обхода шахматным конем шахматной доски по всем клеткам, не побывав на каждой.
 
Обход шахматным конем произвольных, симметричных досок размерностью > 4х4
На досуге написал консольную программу для обхода конем досок больших чем 4х4. Алгоритм стратегии.
 
 
 Обойти шахматным конем все клетки шахматной доски, побывав на каждой клетке по одному разу
Здравствуйте, помогите пожалуйста Рекурсия, нужно обойти шахматным конем все клетки шахматной.
 
Обход доски конем
Дана шахматная доска размером 8х8 и шахматный конь. Программа должна запросить у пользователя.
 
Обход доски конём
Добрый день. Не могли бы Вы помочь с задачей об обходе конём шахматной доски размером n*n? Что-то.
 
Источник
 
Выведите все возможные ходы коня на шахматной доске
 
Для заданной шахматной доски выведите все последовательности ходов коня на шахматной доске так, чтобы конь посещал каждую клетку только один раз.
 
Например, для стандарта 8 × 8 шахматные доски, ниже один из таких туров. Мы начали обход с крайнего левого верхнего угла доски (отмеченного цифрой 1), а следующее число представляет последовательные ходы коня.
 
1 50 45 62 31 18 9 64 
46 61 32 49 10 63 30 17 
51 2 47 44 33 28 19 8 
60 35 42 27 48 11 16 29 
41 52 3 34 43 24 7 20 
36 59 38 55 26 21 12 15 
53 40 57 4 23 14 25 6 
58 37 54 39 56 5 22 13
 
Рекомендуем прочитать:
 
Конь должен искать путь от начальной позиции до тех пор, пока он не посетит каждую клетку или не исчерпает все возможности. Мы можем легко добиться этого с помощью Backtracking. Мы начинаем с данной исходной клетки на шахматной доске и рекурсивно исследуем все восемь возможных путей, чтобы проверить, ведут ли они к решению или нет. Если текущий путь не достигает пункта назначения или не изучил все возможные пути от текущего квадрата, вернитесь назад. Чтобы убедиться, что путь прост и не содержит циклов, отслеживайте квадраты, участвующие в текущем пути на шахматной доске, и перед исследованием любого квадрата игнорируйте квадрат, если он уже покрыт текущим путем.
 
Мы знаем, что конь может двигаться в 8 возможных направлениях с данного поля, как показано на следующем рисунке:
 
 
Мы можем найти все возможные места, куда рыцарь может двигаться из заданного места, используя массив, в котором хранится относительное положение движения рыцаря из любого места. Например,
 
If the current location is (x, y), we can move to position (x + row[k], y + col[k]) for 0 <= k <=7 using the following arrays:
 
 
row[] = [ 2, 1, -1, -2, -2, -1, 1, 2, 2 ] 
col[] = [ 1, 2, 2, 1, -1, -2, -2, -1, 1 ] 
So, from a position (x, y) in the chessboard, the valid moves are:
 
(x + 2, y + 1) 
(x + 1, y + 2) 
(x – 1, y + 2) 
(x – 2, y + 1) 
(x – 2, y – 1) 
(x – 1, y – 2) 
(x + 1, y – 2) 
(x + 2, y – 1)
 
Важная заметка: Пожалуйста, избегайте изменения последовательности вышеуказанных массивов. Порядок, в котором будет двигаться конь, круговой и будет оптимальным. Используя приведенный выше порядок, мы попадем на вакантную позицию за несколько ходов. Кроме того, всегда лучше начинать откат с любого угла шахматной доски. Если мы начнем где-то с середины, конь может пойти в 8 разных направлениях. Если мы начнем с угла, то конь сможет пройти оттуда только в две точки. Поскольку алгоритм является экспоненциальным, оптимизированный ввод в него может иметь огромное значение.
 
Ниже приведена программа на C++, Java и Python, которая демонстрирует это:
 
Источник
 
Читайте также:  Вывести тип значения java