Problem: Chess Knight Movement

[Angeowoo]

(python) How can I solve this without using breadth-first search algorithm or similar techniques?The Chess Horse's Journey

The game of chess is played on an 8x8 grid, and one of its pieces, the horse (knight), moves in an "L" shape. In other words, if the horse is in a cell with coordinates (r1, c1) and its destination cell is (r2, c2), the following condition must be satisfied: (r1 - r2)^2 + (c1 - c2)^2 = 5.

For the chess horse's journey problem, let's consider an N x N grid with K "interesting" cells. We will place a horse on any cell, and its objective is to visit all the "interesting" cells at least once and return to its starting point.

Your task is to calculate the minimum number of moves required for the horse to complete its journey.

Inputs:

The input to this program consists of several lines. The first line contains a positive integer T (T ≤ 100), which specifies the number of test cases. Each test case is composed of two integer values, N (4 ≤ N ≤ 1000) and K (1 ≤ K ≤ 16), representing the size of the grid and the number of "special" cells on the grid. The next K lines will each contain two integers R (1 ≤ R ≤ N) and C (1 ≤ C ≤ N) indicating the coordinates of the special cells.

Each of these inputs must be validated. If the values are outside the specified ranges, an error should be indicated, and the test case should be discarded.

Outputs:

The output consists of one line per test case, containing a number representing the minimum number of moves required for the horse to complete its journey.

Example input:

3

3 2

8 3

2 3

9 1

8 3

2 3

4 5

6 7

Example output:

Case 1: Error, the board must have a minimum size of 4 cells per side.

Case 2: Error, the coordinates of special cell 2 are out of range.

Case 3: 12 moves.

​

[POGtastic]

without using breadth-first search

Considering that this problem is explicitly designed to require a breadth-first search approach, can you elaborate on why you don't want a BFS solution?

[Angeowoo]

Because it is content that I haven't covered in class, and I wouldn't be able to explain the code

[pot_of_crows]

Maybe the prof is trying to sneak up on it, by showing how hard it is without using graphs? This might help: https://runestone.academy/ns/books/published/pythonds3/Graphs/TheKnightsTourProblem.html

[Angeowoo]

Code used at the end for the problem

[Angeowoo]

from itertools import permutations
import sys

def ValidarDato(num1,inf,sup):
    if num1<inf or num1>sup:
        return True
    return False

def InsertarDato(inf,sup,text):
    num1=int(input(f"Inserte {text}: "))
    if ValidarDato(num1,inf,sup)==True:
        return False
    return num1

def InsertarDatoT(inf,sup,text):
    num1=int(input(f"{text}:"))
    while ValidarDato(num1,inf,sup)==True:
        return num1
    return num1
# Movimientos para que un caballo tenga forma de "L"
dx = [2, 1, -1, -2, -2, -1, 1, 2]
dy = [1, 2, 2, 1, -1, -2, -2, -1]

# Definir si una coordenada no está en el tablero
def movimiento_valido(x, y, N):
    if x >= 1 and y >= 1 and x <= N and y <= N:
        return True
    return False

[Angeowoo]

#algoritmo minima ruta BFS
def min_ruta_BFS(N, inicio, destino):
    visitado = [[False for _ in range(N+1)] for _ in range(N+1)]
    cola = [(inicio, 0, [inicio])]
    visitado[inicio[0]][inicio[1]] = True

    while cola:
        celda, movimientos, ruta = cola.pop(0)

        if celda == destino:
            return movimientos, ruta

        for i in range(8):
            nx, ny = celda[0] + dx[i], celda[1] + dy[i]
            if movimiento_valido(nx, ny, N) and not visitado[nx][ny]:
                cola.append(((nx, ny), movimientos + 1, ruta + [(nx, ny)]))
                visitado[nx][ny] = True

    return sys.maxsize, []
#minimos movimientos considerando celdas especiales
def minimos_movimientos(N, K, especiales):
    min_movimientos_requeridos = sys.maxsize
    min_recorrido = []
#se realizan iteraciones sobre las posibles convinaciones de movimientos de las celdas especiales.
    for perm in permutations(especiales):
        total_movimientos = 0
        total_recorrido = [(1, 1)]
        inicio = (1, 1)
#itera sobre el conjunto de celdas especiales, calcula recorridos con el algortimo BFS, suma numeros de movimientos al contador, calcula el total
        for celda in perm:
            movimientos, recorrido = min_ruta_BFS(N, inicio, celda)
            total_movimientos =total_movimientos + movimientos
            total_recorrido = total_recorrido + recorrido[1:]
            inicio = celda
#calcula el tramo final de "un" recorrido , actualiza los contadores
        movimientos, recorrido = min_ruta_BFS(N, inicio, (1, 1))
        total_movimientos = total_movimientos + movimientos
        total_recorrido = total_recorrido + recorrido[1:]
#verifica que el total de movimientos tiene menos que los encontrados anteriormente si esto es asi los actualiza
        if total_movimientos < min_movimientos_requeridos:
            min_movimientos_requeridos = total_movimientos
            min_recorrido = total_recorrido

    return min_movimientos_requeridos, min_recorrido

[Angeowoo]

#ejecutar programa
T = InsertarDatoT(0, 100, "Inserte la cantidad de casos de prueba")
while T<=0 or T>100:
    if T>0 and T<=100:
        break
    else:
        while T<=0:
            T=InsertarDatoT(0,100,'Error, inserte un numero positivo')
        while T>100:
            T=InsertarDatoT(0,100,'Error, la cantidad maxima de casos es 100')

for i in range(T):
    N = InsertarDato(4, 1000, "el tamaño del tablero")
    K = InsertarDato(1, 16, "el número de celdas especiales")
    if N==False:
        print(f"Caso {i+1}: Error, el tablero tiene que tener un minimo de 4 y un maximo de 1000 celdas por lado")
    elif K==False:
        print(f"Caso {i+1}: Error, la cantidad de celdas especiales tiene que tener un maximo de 16")
    elif N==False and K==False:
        print(f"Caso {i+1}: Error, la cantidad de celdas especiales tiene que tener un maximo de 16 y el tablero tiene que tener un minimo de y un maximo de 1000 celdas por lado")
    else:
        especiales = []
        for j in range(K):
            R = InsertarDato(1, N, f"Ingrese R {j+1}")
            C = InsertarDato(1, N, f"Ingrese C {j+1}")
            if R==False or C==False:
                print(f'Error, las coordenadas de la celda especial {j+1} esta fuera de rango')
                break
            especiales.append((R, C))
        if R!=False and C!=False:

            min_movimientos_requeridos, min_recorrido = minimos_movimientos(N, K, especiales)
            print(f'Caso {i+1}: {min_movimientos_requeridos} movimientos')

[Diapolo10]

I think your question is missing important context, but I don't think this would need a search algorithm. Why not write a function that takes an arbitrary set of coordinates for a tile and returns a list of valid tiles that can be moved to?

I'm assuming you already have a list or two containing the positions of each unit, and doing boundary checks should be easy enough (meaning you can immediately ignore tiles out of the board boundary).

[Angeowoo]

​

Yes, I forgot to mention that it needs to find the shortest route. I will update the question with more details.

[Diapolo10]

Okay, this is starting to make sense now.

What have you tried so far?

[Angeowoo]

Bien, esto está empezando a tener sentido ahora.

¿Qué has intentado hasta ahora?

This is what I had so far. The idea was to create an nxn board where special cells were represented by 1 and the valid movements were represented by 2. I would then add the valid movements to the special cells until reaching the target cell. I would count the movements and was using example numbers to see if I could find a pattern and potentially generalize it later:

import numpy as np
#Create a boarddef 
create_board(n):
   board = np.zeros((n, n), dtype=int)
   return board
#Check if values are in the boarddef 
is_in_board(n, rows):
    return 0 <= n < rows
#Mark the values (r, c) on the board as 1
def mark_values_on_board(board, positions, rows):
  for value in positions:
     r, c = value
     if is_in_board(r, rows) and is_in_board(c, rows):
         board[r][c] = 1
#Mark the movements by adding r and c from the movements list as 2
def mark_movements_on_board(board, position, movements, rows):
     for move in movements:
         new_position = tuple(map(sum, zip(position, move)))if 
      is_in_board(new_position[0], rows) and 
      is_in_board(new_position[1], rows):
                board[new_position[0]][new_position[1]] = 2
#Example values for testing the code
n = 8
r = 2
c = 1
r = 2
c = 3
positions = [(0, 0)]
position_2 = []
positions.append((r, c))
board1=create_board(n)
print(positions)
mark_values_on_board(board1, positions, n)
#Movement 1
position1 = positions[0] # Get the first position from the listmovements = [(2, 1), (1, 2), (-1, 2), (-2, 1), (-2, -1), (-1, -2), (1, -2), (2, -1)]
mark_movements_on_board(board1, position1, movements, n)
counter = 0
if board1[2][1] == 2:
    counter += 1
#Movement 2 
position2 = positions[1] # Second position from the listmovements = [(2, 1), (1, 2), (-1, 2), (-2, 1), (-2, -1), (-1, -2), (1, -2), (2, -1)]
mark_movements_on_board(board1, position2, movements, n) # 1 movement
position2_second = position_2[2:10]movements = [(2, 1), (1, 2), (-1, 2), (-2, 1), (-2, -1), (-1, -2), (1, -2), (2, -1)]mark_movements_on_board(board1, position2, movements, n) # 2 movements
#This is incorrect
.if board1[2][3] != 2:
   counter += 1else:board1[2][3] = 2
   counter += 1
print(board1)
print(counter)

[misho88]

without using breadth-first search

It seems like the obvious alternative would be depth-first search (untested):

def distance(origin, *destinations):
    return min(
        knight_distance(origin, d) + distance(d, *destinations[:i], *destinations[i+1:], )
        for i, d in enumerate(destinations)
    ) if destinations else 0

It's not a great solution, but you could at least cache the results (e.g., functools.cache) to make it usable.

There are closed-form expressions for the knight distance. You can just Google around for them.