Given a N*N board with the Knight placed on the first block of an empty board. Moving according to the rules of chess knight must visit each square exactly once. Print the order of each cell in which they are visited. Starting point is determined by 0 on the question table. The formula should be dynamic enough to adjust and work when the starting position is changed.
📌 Challenge Details and Links
Challenge Number: 170
Challenge Difficulty: ⭐⭐⭐⭐⭐⭐
📥Download Sample File
📥Link to the solutions on LinkedIn
Solving the challenge of The Knight’S Tour! with Excel
Excel solution 1 for The Knight’S Tour!, proposed by Julian Poeltl:
=LET(N,8,SC,"0|101",REDUCE(SC,SEQUENCE(N^2-1),LAMBDA(A,B,LET(M,TEXTAFTER(FILTER(A,--MAP(A,LAMBDA(A,TEXTBEFORE(A,"|")))=B-1),"|"),UNIQUE(B&"|"&DROP(REDUCE(0,M,LAMBDA(C,D,VSTACK(C,LET(LM,TEXTAFTER(D,",",-1,,,D),TEXTBEFORE(LM,",",-1,,,D)&","&TOCOL(LET(R,LM+VSTACK(201,199,102,98,-98,-102,-199,-201),T,TRUNC(R/100),M,MOD(R,100),IF((M>0)*(M<=N)*(T<=N)*(T>0)*NOT(ISNUMBER(SEARCH("*"&R&",",D))),R,X)),3))))),1))))))Solving the challenge of The Knight’S Tour! with Python
Python solution 1 for The Knight’S Tour!, proposed by Konrad Gryczan, PhD:
def knights_tour(N, start_pos):
board = [[-1] * N for _ in range(N)]
moves = [(-2, -1), (-1, -2), (1, -2), (2, -1), (2, 1), (1, 2), (-1, 2), (-2, 1)]
def pos_to_indices(pos):
return N - int(pos[1:]), ord(pos[0].lower()) - ord('a')
def is_valid(x, y):
return 0 <= x < N and 0 <= y < N and board[x][y] == -1
def count_onward_moves(x, y):
return sum(is_valid(x + dx, y + dy) for dx, dy in moves)
def solve(x, y, step):
board[x][y] = step
if step == N * N - 1:
return True
possible_moves = sorted(((count_onward_moves(x + dx, y + dy), x + dx, y + dy) for dx, dy in moves if is_valid(x + dx, y + dy)), key=lambda x: x[0])
for _, nx, ny in possible_moves:
if solve(nx, ny, step + 1):
return True
board[x][y] = -1
return False
start_row, start_col = pos_to_indices(start_pos)
if not solve(start_row, start_col, 0):
print("No solution exists for the given board and starting position.")
return
for row in board:
print(' '.join(f"{cell:2}" for cell in row))
if __name__ == "__main__":
knights_tour(8, 'a8')Python solution 2 for The Knight'S Tour!, proposed by Abdallah Ally:
import pandas as pd
def is_valid_move(x, y, board, N):
return 0 <= x < N and 0 <= y < N and board[x][y] == -1
def solve_knights_tour(N, start_x=0, start_y=0):
board = [[-1 for _ in range(N)] for _ in range(N)]
moves_x = [2, 1, -1, -2, -2, -1, 1, 2]
moves_y = [1, 2, 2, 1, -1, -2, -2, -1]
board[start_x][start_y] = 0
def solve(x, y, step_count):
if step_count == N * N:
return True
for i in range(8):
next_x, next_y = x + moves_x[i], y + moves_y[i]
if is_valid_move(next_x, next_y, board, N):
board[next_x][next_y] = step_count
if solve(next_x, next_y, step_count + 1):
return True
board[next_x][next_y] = -1 # Backtrack
return False
if not solve(start_x, start_y, 1):
print("No solution exists for the given starting position.")
else:
return pd.DataFrame(data=board)
# Display the final results
solve_knights_tour(8)Python solution 3 for The Knight'S Tour!, proposed by Anmar Kamil:
def knight_tour(board, x, y, move_count):
if move_count == N * N:
return True
for dx, dy in MOVES:
nx, ny = x + dx, y + dy
if 0 <= nx < N and 0 <= ny < N and board[nx][ny] == -1:
board[nx][ny] = move_count
if knight_tour(board, nx, ny, move_count + 1):
return True
board[nx][ny] = -1 # Backtrack
return False
def solve_knight_tour():
board = [[-1] * N for _ in range(N)]
board[0][0] = 0
if knight_tour(board, 0, 0, 1):
for row in board:
print(" ".join(f"{cell:2}" for cell in row))
else:
print("No solution exists!")
solve_knight_tour()
Solving the challenge of The Knight'S Tour! with Python in Excel
Python in Excel solution 1 for The Knight'S Tour!, proposed by Alejandro Campos:
def solve_knight_tour(N, x, y):
board, moves = [[-1]*N for _ in range(N)], [(2, 1), (1, 2), (-1, 2), (-2, 1), (-2, -1), (-1, -2), (1, -2), (2, -1)]
board[x][y] = 0
def solve(x, y, move_i):
if move_i == N*N: return True
for dx, dy in moves:
nx, ny = x+dx, y+dy
if 0 <= nx < N and 0 <= ny < N and board[nx][ny] == -1:
board[nx][ny] = move_i
if solve(nx, ny, move_i+1): return True
board[nx][ny] = -1
return False
return pd.DataFrame(board) if solve(x, y, 1) else None
N, start_x, start_y = 8, 0, 0
solution_df = solve_knight_tour(N, start_x, start_y)