Matlab Tutorials | Examples
Practice 14:
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.
Solution:
|
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 |
clear clc fclose all; 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 if fout==-1 disp(err); fclose all; return end 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 while movecheck movecheck = false; %Select move newmove = []; for (i=1:8) 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 end %End Select move %%Update table given move if movecheck 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; end end iteration = iteration + 1; if moves >= 60 %% printing condition fprintf(fout,'Iteration # %g (%g moves):',iteration,moves); fprintf('Iteration # %g (%g moves):',iteration,moves); for i=1:moves fprintf(fout,'%s%g ',letter(iterationtable(1,i)),iterationtable(2,i)); fprintf('%s%g ',letter(iterationtable(1,i)),iterationtable(2,i)); end fprintf(fout,'\r\n'); fprintf('\n'); end end fclose all; |
i am doing image encryption
where i divide the image 256*256(65536 pixels) into 8*8 matrices can i use your code and can i apply for each matrix is it possible or there is any way to do it(to apply knights tour on any 8*8 matrix like that i have to do for 1024 matrices to complete 256*256 matrix)
If you increase 8×8 to 256×256 you can use it for your problem.