Matlab Tutorials | Examples
Knight’s Tour (Advance)
One of the interesting puzzles for chess buffs is the Knight’s Tour problem, which is attributed to the famous mathematician Euler. The question is this: Can the chess piece called the knight move around an empty chessboard and land in each of the 64 squares once and only once?
The knight, symbolized by a horse figure in chess, makes L-shaped moves: It goes two places horizontally or vertically, and one place in a direction perpendicular to the initial one. Thus, from a square in the middle of an empty chessboard, a knight can make eight different moves. However, at the sides of the board, or even more at the corners, the alternative moves a knight can make are much more limited (see the black and white knights in the picture).
Write a MATLAB program that will do the following:
a) Create an 8×8 matrix for keeping track of the visited and non-visited squares of a chess board. Unvisited squares should have a value of zero.
b) Randomly initialize the knight into one of the squares on the board.
c) If there are unvisited square(s) the knight can move to, randomly choose one of those, and move the knight to the chosen square. Add the address of this square into an array for later printing. Keep repeating (c).
d) When there are no unvisited squares the knight can move to, check the number of squares that were visited. If the count is greater than or equal to 60, print all the moves of the knight (the list of squares in their visit order) into a file named KnightsTour.txt. The list for the sequence of moves should be printed on a single line. The line should contain the iteration number and the number of squares that were visited.
e) Unless all 64 squares are visited, repeat the program from (a).
This program may take many hours and many thousands of iterations. Note that due to the random nature of iterations, there is no predefined single output.
letter = ['a','b','c','d','e','f','g','h']; %% Letter of the chess table
knightmove = [2,1,-1,-2,-2,-1,1,2;1,2,2,1,-1,-2,-2,-1];%% Knight moves
moves = 0;
iteration = 0;
[fout,err]= fopen('KnightsTour.txt','w');%% Open File
while moves<64 %% Ending condition
moves = 1;
table = zeros(8,8); %% Create empty table
x = randi(8); %% Create random position
y = randi(8);
table(y,x) = 1; %% Fill the table 1 on position
iterationtable = [x;y]; %% moves array
movecheck = true; %% flag for possible moving situation
movecheck = false;
newmove = ;
X2=x + knightmove(1,i);
Y2=y + knightmove(2,i);
if (X2>0 && Y2>0 && X2<=8 && Y2<=8 && table(Y2,X2) == 0) %% check knight can move or not
newmove = [newmove [X2;Y2]];
movecheck = true;
%End Select move
%%Update table given move
new = size(newmove);
updatetable = new(2);
selectmove = randi(updatetable);
table(newmove(2,selectmove),newmove(1,selectmove)) = 1; %% update table
y = newmove(2,selectmove); %% update knight position
x = newmove(1,selectmove);
iterationtable = [iterationtable [newmove(1,selectmove);newmove(2,selectmove)]]; %% add the moves table nw move
moves = moves + 1;
iteration = iteration + 1;
if moves >= 60 %% printing condition
fprintf(fout,'Iteration # %g (%g moves):',iteration,moves);
fprintf('Iteration # %g (%g moves):',iteration,moves);