Skip to content

YlmzCmlttn

Cemalettin Yılmaz Blog

Menu
  • Home
  • About Me
  • Projects
    • Iot-AR
    • Magnifi-AR
    • Smarthome-IOS
    • Others
  • Categories
    • Articles
    • Augmented Reality
    • Capture The Flag
      • Google CTF
        • 2018
    • Embedded Systems
    • IoT
    • Logisim
    • My Essays
    • Nvidia Jetson
      • Jetson TX1
    • Operating Systems
      • Kali
      • Raspbian
      • Ubuntu
    • Personal
    • Programming
      • Arduino
      • C
      • C#
      • Css
      • Html
      • Js
      • Matlab
      • Node.js
      • Python
      • Swift
      • VHDL
    • Projects
      • Embedded Systems
      • Electric
      • IoT
      • IoT-AR
      • Logisim
      • Magnifi-AR
      • Pose Estimation
    • Raspberry Pi
    • Xilinx
    • Others
Menu

Knight’s Tour | Matlab Examples

Posted on December 8, 2018February 20, 2019 by Yılmaz Cemalettin

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:

MATLAB
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;

 

 

2 thoughts on “Knight’s Tour | Matlab Examples”

  1. ramesh says:
    March 17, 2019 at 11:47 am

    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)

    Reply
    1. Yılmaz Cemalettin says:
      March 17, 2019 at 3:56 pm

      If you increase 8×8 to 256×256 you can use it for your problem.

      Reply

Leave a Reply Cancel reply

Your email address will not be published. Required fields are marked *

My Motto

“Learn to share, Share to learn”

LinkedIn Badge

Cemalettin Yılmaz

Ads

Archives

Categories

  • Articles (1)
  • Augmented Reality (3)
  • Capture The Flag (23)
    • Google CTF (22)
      • 2018 (13)
      • 2019 (9)
    • PicoCTF (1)
      • 2019 (1)
  • Embedded Systems (3)
  • IoT (3)
  • Logisim (1)
  • My Essays (3)
  • Nvidia Jetson (5)
    • Xavier (5)
  • Operating Systems (24)
    • Kali (3)
    • Raspbian (2)
    • Ubuntu (21)
  • Others (1)
  • Personal (1)
  • Programming (44)
    • Arduino (4)
    • C (10)
    • C# (4)
    • C++ (5)
    • Css (1)
    • CUDA (6)
    • Html (1)
    • Js (2)
    • Libraries (5)
      • OpenCV (3)
      • OpenGL (2)
    • Matlab (14)
    • Node.js (5)
    • Python (6)
    • Swift (3)
  • Programs (4)
    • Tools (4)
  • Projects (21)
    • Books Solutions (8)
    • Electric (2)
    • Embedded Systems (2)
    • Energy Harvesting (1)
    • IoT (2)
    • IoT-AR (1)
    • Logisim (1)
    • Magnifi-AR (3)
    • Pose Estimation (3)
    • Smarthome-Ios (1)
  • Raspberry Pi (3)
  • Uncategorized (2)
  • YZlib (1)

Recent Posts

  • atof stof stod problems with local floating point separator in C/C++
  • Pico CTF 2019 Answers
  • YZlib: Personal C++ Library
  • Drive to target | Google CTF 2019
  • FriendSpaceBookPlusAllAccessRedPremium | Google CTF 2019

Recent Comments

  • AbaShelha on Ghidra Installation on Ubuntu |18.04, 16.04, 14.04
  • Peter on Ghidra Installation on Ubuntu |18.04, 16.04, 14.04
  • Yılmaz Cemalettin on Ghidra Installation on Ubuntu |18.04, 16.04, 14.04
  • Yılmaz Cemalettin on 16-Bit CPU on Logisim
  • Jenny on 16-Bit CPU on Logisim
  • MOON on 16-Bit CPU on Logisim
  • anti on Ghidra Installation on Ubuntu |18.04, 16.04, 14.04
  • hunkerjr on STOP GAN | Google CTF 2019
  • Shaq on 16-Bit CPU on Logisim
  • NURUL AFIQAH MOHD HASBULLAH on 16-Bit CPU on Logisim

Linkedln

© 2022 YlmzCmlttn | Powered by Superbs Personal Blog theme