amdidio.github.io
Project - The Trapped Knight
In this project, I have written computer code to generate a particular sequence of numbers described in the following YouTube video: The Trapped Knight
The code is implemented in three parts.
Part 1 - Initialize the board
The chess board is stored in a 2d-array of integers. The size of the board is (2n+1)-by-(2n+1). The board is initialized by filling it with the integers described in the video, such that it returns this "spiral pattern" for any given input parameter n.
function initialize_board(n) #n indicates the radius of the board
board = zeros(Int64,2n+1,2n+1)
row = n+1 #row number of board matrix
col = n+1 #column number of board matrix
center = board[row,col] = 1
count = 1
for r = 1:n
current = board[row,col+1] = count + 1 #right once to initialize new radius r
count = current
for k = 1:(2r-1) #up
current = board[row-k,col+1] = count + k
end
count = current
for j = 1:(2r) #left
current = board[row-2r+1,col+1-j] = count +j
end
count = current
for i = 1:(2r) #down
current = board[row-2r+1+i,col+1-2r] = count + i
end
count = current
for h = 1:(2r) #right to complete radius
current = board[row+1,col+1-2r+h] = count + h
end
row += 1 #new starting points will be along the row=col diagonal
col += 1
count = current
end
board
end
For example, the following input:
board = initialize_board(3)
Produces the following output:
7×7 Array{Int64,2}:
37 36 35 34 33 32 31
38 17 16 15 14 13 30
39 18 5 4 3 12 29
40 19 6 1 2 11 28
41 20 7 8 9 10 27
42 21 22 23 24 25 26
43 44 45 46 47 48 49
Part 2 - Simulate the walk
The following functions simulate the movements of a knight on a chessboard, followed by the simulate_walk function, which takes an initialized board as input, and produces a list of numbers as well as the corresponding x- and y-coordinates.
function right_up(i,j,x,y) #move two spaces right, one space up
i = i-1
j = j+2
x = x+2
y = y+1
return (i,j,x,y)
end
function right_down(i,j,x,y) #move two spaces right, one space down
i = i+1
j = j+2
x = x+2
y = y-1
return (i,j,x,y)
end
function left_up(i,j,x,y) #move two spaces left, one space up
i = i-1
j = j-2
x = x-2
y = y+1
return (i,j,x,y)
end
function left_down(i,j,x,y) #move two spaces left, one space down
i = i+1
j = j-2
x = x-2
y = y-1
return (i,j,x,y)
end
function up_left(i,j,x,y) #move two spaces up, one space left
i = i-2
j = j-1
x = x-1
y = y+2
return (i,j,x,y)
end
function up_right(i,j,x,y) #move two spaces up, one space right
i = i-2
j = j+1
x = x+1
y = y+2
return (i,j,x,y)
end
function down_left(i,j,x,y) #move two spaces down, one space left
i = i+2
j = j-1
x = x-1
y = y-2
return (i,j,x,y)
end
function down_right(i,j,x,y) #move two spaces down, one space right
i = i+2
j = j+1
x = x+1
y = y-2
return (i,j,x,y)
end
function simulate_walk(board)
n = Int((size(board,1)-1)/2)
available_spaces = ones(Int64,2n+1,2n+1)
i = n+1
j = n+1
available_spaces[i,j] = 0
seq = [1]
x = 0
y = 0
xs = [0]
ys = [0]
move = true
while move == true
valid_options= []
options = [right_up(i,j,x,y),right_down(i,j,x,y),left_up(i,j,x,y),left_down(i,j,x,y),up_left(i,j,x,y),
up_right(i,j,x,y),down_left(i,j,x,y),down_right(i,j,x,y)]
for k = 1:8
if (options[k][1] in 1:(2n+1)) && (options[k][2] in 1:(2n+1)) && (available_spaces[options[k][1], options[k][2]] == 1)
push!(valid_options,options[k])
end
end
if isempty(valid_options) == true
move == false
break
end
valid_options
l = length(valid_options)
values = []
for h = 1:l
push!(values,board[valid_options[h][1], valid_options[h][2]])
end
least_index = findmin(values)
coordinates = valid_options[least_index[2]]
push!(seq, least_index[1])
i = coordinates[1]
j = coordinates[2]
x = coordinates[3]
y = coordinates[4]
push!(xs, x)
push!(ys, y)
available_spaces[i,j] = 0
options = []
end
(xs,ys,seq)
end
For example, the following input:
board = initialize_board(2)
display(board)
seq, xs, ys = simulate_walk(board);
println(\"Sequence = \", seq)
println(\"x-coordinates = \", xs)
println(\"y-coordinates = \", ys)
produces the following output:
5×5 Array{Int64,2}:
17 16 15 14 13
18 5 4 3 12
19 6 1 2 11
20 7 8 9 10
21 22 23 24 25
Sequence = [1, 10, 3, 6, 9, 4, 7, 2, 5, 8, 11, 14]
x-coordinates = [0, 2, 1, -1, 1, 0, -1, 1, -1, 0, 2, 1]
y-coordinates = [0, 1, -1, 0, 1, -1, 1, 0, -1, 1, 0, -2]
Part 3 - Generate the full sequence and plot the path
The code below generates the full sequence (for this case, n=100), outputs the last number, and plots the path by straight lines between all the visited x,y-coordinates.
using PyPlot
board = initialize_board(100)
path = simulate_walk(board)
println("The knight is trapped at number ",path[3][end])
plot(path[1],path[2]) #(xs,ys)
axis("equal")
grid(true)
xlabel("x-coordinates")
ylabel("y-coordinates")
title("Path of the Trapped Knight");
