Interactive Knight’s Tour Board: KT_App1. Download from: CAS Knight’s Tour

Workbook 1: From Human Solutions to Program Solutions in Python 3

Dave White & Rae Harbird   Department of Computer Science UCL

The latest Word version (March 8th 2018) of this Course can be downloaded from here:
Knightstour3.4

1       Contents

2      Introduction

 

“Begin at the beginning,” the King said, very gravely,
“and go on till you come to the end: then stop.” 

— Lewis Carroll, Alice’s Adventures in Wonderland &Through the Looking-Glass

This article is for teachers teaching Computer Science to KS3 and KS4+ pupils and makes explicit use of a model of Computational Thinking (CT), and the developing classroom Pedagogy of Computer Science, in problem solving.  Finding human solutions to a problem, sometimes provides a basis for, or serves as a pointer to, devising and implementing algorithms for program solutions, which can in turn lead to solution strategies for program solutions to more complex problems.

In the context of the knight’s tour, we look for possible human solutions which may generate an approach to program solutions, with a view to generalising the programs to solve problems on larger boards, wherehuman soluions become infeasible.

We have provided  interactive software apps: KT_App1, KT_App2 to assist in investigating, recording and counting solutions to knight’s tour problems on a 4×4 board with 12 squares and KT_App3 for a 5×5  board with 25 squares. Download the interactive knight’s tour game boardsKT_App1,2,3 from the link in section 3.1 below.

3 The Problem Stated.

Starting with a knight on a particular square on a chess board, and moving the knight in a series of valid chess knight moves, to find whether a path exists where each and every square on the board is visited once only. This is known as an open knight’s tour(1). And, if it does, to determine how many paths there are. Further to discover whether an open tour exists where it is possible on a further move to return to the starting square. This is known as the closed knight’s tour(2). In more general terms in Graph Theory the problem is known as a Hamiltonian path or cycle, respectively.

3.1      Repository for the Knight’s Tour

The link:CAS Knight’s Tour will allow you to download from a folder with:

• A readme file, which explains how to use the software.
• A discussion booklet: A Course in Computational Thinking, Creativity and Pedagogy in Programming 1:The Knight’s Tour —Part 1: Human Solutions. It’s A Word version, for ease of reference, of the content on this web page, outlining the problems and describing different human solutions leading to program solutions
• A zip file with
  1. A simple knight’s tour interactive chess board,  KT_App1, written in Python3,  — the latest beta version (6th January 2018), to explore human solutions to open and closed  tours of the knight’s tour problem.
  2. a picture of a chess knight,  black.gif, which must be in the same folder as KT_App1  when  you extract the zip file, in order for the program to run.
  3. A simple knight’s tour interactive chess board, complete with stacking facilities,  KT_App2, written in Python 3. By stacking alternative paths at any move, the user is able to generate and count all possible full closed and open knight’s tours.
  4. A simple knight’s tour interactive chess board, KT_App3, written in Python 3 for a 5×5 chess board.

Or you can download an HTML version of this webpage by viewing with Google Chrome Browser, right-clicking and saving, and viewing in local mode.

3.2      CAS Tenderfoot Program, Interactive Knight Chess Boards, Trees and Graph Theory

The recent CAS Tenderfoot program proposed ‘the simple knight’s tour’ for secondary teachers and their pupils as a productive, fertile exercise in the computational thinking necessary to look at human solutions.  In this first article we run with the idea, using guided discovery and enquiry-based learning as a basis for exploration, in which teachers and pupils can attempt to find a variety of human solutions to this and related problems. We show how a simple model of computational thinking, together with creativity, heuristics, symmetry, induction, and deduction, underpins and is integrated with this approach, while using problem representations on a click/touch screen of the interactive chess board, Figure 1(a). We experiment with the problem in its presenting context with the Interactive Chess Board, KT_App1 to find a solution. In the same context, we engage in finding human approaches  to the task of counting  the number of solutions,  using the ‘stacking’ interactive chessboard, KT_App2.  We then move on to other representations of the knight’s tour. before tackling the problem for human solutions with drawings, including tree diagrams and some drawing representations from graph theory. In searching for human solutions, we have an eye out for the programming solutions they may suggest. Discussion of representations and some solutions are included in the final section of this booklet.

3.3      Follow Up Article

In a follow up article, we will provide discussion to questions we have posed, delve further into the human solutions we have developed with a view to transforming them, where possible, into program solutions for the knight’s tour and for more general problems. This will require a basic knowledge of Python programming. We will introduce data structure representations for: lists, stacks, arrays, trees and graphs, and programming with non-trivial recursion. No previous knowledge of these concepts is assumed.

4      A Working Model of Computational Thinking (CT)

We use a simplified Model of Computational Thinking in relation to Algorithms and Programming for both human solutions and programmed solutions. (ADAGE). We attempt to make explicit the use of this model of CT in the process of solving problems.

• Algorithmic Thinking — thinking through the steps required to solve a problem
• Decomposition — breaking a larger problem down into smaller ones.
• Abstraction — reducing complexity by using or creating tools or models.
• Generalisation — adapting solutions so that they can be used to solve a wider range of problems.
• Evaluation — assessing whether a program or technique works correctly and efficiently.

Figure 1(a).  KT_App1 : knight’s tour board 1-12. Click on square to move  the knight around the board. Trail so far 1,9,3… next move dashed in blue: 2 or 11. Go for 2 and remember/save 11? Come back for path 1, 9, 3, 11… later?	Figure 1(b). Symmetry in the board at half-way i.e. 6 moves. The next move is to 12.  In what way does square 12 ‘mirror’ or reflect square 1 in board symmetry? Given the sequence from 1, 9, 3, … 6 can you use symmetry to predict the sequence of moves from 12 back to 1? When 1 –> 9, correspondingly 12 –> ?

5   Finding Knight’s Tour Solutions

5.1      Open and Closed solutions — A Computational Thinking Approach

From the outset we apply CT explicitly to the problems:

1. Algorithmic thinking. Can we find a solution? Can we find solutions to 1 and 2 of the problem stated? Is there a solution? If not, can we prove it. And, if a solution exists, can we say how many different solutions there are? Are there solutions starting from different squares on the board? How many?
2. Decomposition To familiarise ourselves with the human solution process, we might try to solve a simpler/partial but related problem: e.g. looking for a shorter tour starting at, and returning to, square 1, after visiting a sequence of squares once only. For example: 1, 6, 12, 7, 1. Is a closed tour of length 4. Figure 2(a).  So a solution exists. How many different closed paths are there of length 2, 3, 4 starting at 1?  Can you demonstrate/prove there are no closed paths of length 3 starting from square 1? Are there closed paths of length 5, 6, …, 12? How many in each category? Can you prove it? See Figure 2(a)(b). Put a different way: How many paths of a particular length are there which start at 1 and finish on squares 6,7 or 9, which present the springboard back to square 1 for a closed tour?  How do we keep track of the number of different solutions? If we have solutions to these problems starting at square 1, can we predict how many solutions from the other peripheral squares on the board (by symmetry?).
3. Abstraction. Can we devise tools/approaches/arguments, which hide detail, but help us to derive/count more solutions? (induction, symmetry, for example)
4. Generalisation. Can we generalise the problem: to find all possible knight’s tours, open and closed, from all starting points on the board? Will our human solution help us to solve both knight’s tour problems on a bigger board, say on a complete 4×4 chess board? Or on a 5×5 or an 8×8 chess board? Is it possible to devise a human solution that finds all solutions on a bigger board say 5×5?
5. Evaluation. What about the internal squares 4,5,8 and 9? Do the algorithms we have used so far from square 1, give us the answers to the problems we pose? Can our algorithms be adapted to suit? Finally, can we devise a program solution to the simpler problems to help us deal with related problems with increasing complexity of counting? Will the extended problems be too complex for our human solutions?

Figure 2(a). Knight’s 4-closed tour from square 1

Figure 2(b).  Knight’s 6-closed tour from square 1

We first look at a number of head on human approaches to the simple knight’s tour.

5.2     Using the Board Directly

We can tackle the reduced problem of a simplified closed knight’s tour of say, 2, 3, 4, 5 moves… with a made up board, a make-do knight, and pen and paper to record our moves. Or use the KT_App1 (run as a Python 3 program), shown in Figure 1, designed to facilitate the process of constructing and recording a trail of legitimate knight moves on the board.

6   Counting Solutions

We can start with a trial-and-error approach (induction) looking out for symmetry and pattern. If we find a solution, or several, how do we take steps to make sure we have found all solutions in that category? Starting at square 1, our first move takes us to 6, 9, or 7 and we could try to exhaust all possible paths for each of these three squares with three possible sets of solutions for all possible knight’s tour problems starting from square 1. With patience, trial and error and perseverance, we are likely to find a solution, if one exists, to each of these reduced problems. But how do we keep track of how many different solutions there are in each category?

6.1      Recording the moves in different ways.

If we take our simple example above of a closed 4 tour, we might start drawing as follows in Figure 3, where we represent our possible moves in a representation, known as a tree. We note that after the first move to 6,7 or 9 the subsequent moves form a special form of tree – a binary tree characterised by only 0, 1 or 2 possible moves on each level. See Section 8.2  below for a full description.

Figure 3. A tree representation of 3-move paths of the knight’s tour from square 1, in search of a closed 4-tour.

From Figure 3, can you deduce how many closed 4-tours there are from square 1? How would you develop the tree in Figure 3 to find out if there are closed 5-tours, closed 6-tours… and to count how many? Could you make this method work (evaluation) for the original problem stated: the open tour of 11 moves and the closed-12 move tour from square 1?

7       Some Thoughts and Deductions as We Go: Symmetry in our Approach

We notice that the ‘board’, Figure 1, is not the full 4×4 squares board, but is made up of a symmetric pattern of a cross of 12 squares. And the knight’s move is a reversible one; and therefore a trail of knight’s moves is reversible. So one closed solution from square 1 immediately gives rise to another, by reversing the sequence. Does symmetry or pattern in the problem help us? Is there symmetry in the closed path 1, 6, 12, 7, 1 mentioned above? Can we see its symmetry on the board?

It is fairly evident, that the closed 4-move tour 1, 6, 12, 7, 1 yields another 4-closed tour – the original tour in reverse. And of course this will be true for all closed tours of whatever length. But we could utilise the double mirror symmetry (top to bottom, left to right) in which square 12 is the symmetric counterpart to square 1. For example, in the closed 4 move tour in Figure 2(a), we see that square 1–>6 is mirrored by square 12–>7. So we could try half tours from 1, in which the next move after half-way takes us to 12 and use the mirror image from 12 back to 1 for the other half tour and so complete a tour. This might be a tactic that proves fruitful, and involve less work, as we look for ways to solve longer tours.

8       Symmetry at the Half-way Point of a Full Closed Tour Starting at Square 1

In the case of the full closed tour, after 6 moves from 1, can I end up at 12 on the seventh move? If so can I then use the double mirror image of the path from 1 as the return path from 12 to 1. The answer is yes providing the symmetry is such that I do not revisit a square already visited in the first half tour.  See Figures 2, 3, 4 and 5 as illustrations. How many different possible half paths are there from square 1?

If we find the number of closed paths from 1 can we predict the number of closed paths from any other square on the board? (Yes — and why always the same answer?!)

Are there different answers for open tours? For example, is the number of open tours starting from an edge square like 1, different from the number of tours starting from an internal square like 4? We can use a trial and error approach on the board, before we look at approaches which examine the underlying structure of a ‘knight’s tour’ board.

Figure 4. Symmetric half-way patterns starting at 1. Can you predict the return half paths from 12 to 1? If you proceed by trial and error you may find open solutions to the knight’s tour on this board. An open solution (11 moves from Square 1) does not necessarily lead to a closed solution (12 moves: returning to 1). Note that these diagrams also illustrate knight’s 6-move closed tour solutions starting at square 1.

Figure 5. More symmetric path patterns from 1. Can you predict the return half paths from 12 to 1? Are there any other half paths from 1 to 6, 7 or 9? Have we exhausted all the closed paths from 1?

Figure 6. Do either of these half paths form the first half of a closed tour starting from square 1? Can you tell from the double symmetry/lack of double symmetry of the board pattern in green whether a closed solution is possible by moving to square 12 and following on with a mirror path from square 12 as in Figure 4? (Note the symmetries here in these diagrams are not the double symmetry (across the diagonals) we have described earlier—they are symmetries of a single mirror reflection, one top to bottom, the other left to right. By continuing from 12, is it possible to form a full open knight’s tour?)

9   Looking at the Underlying Structure of a Knight’s Tour Board

Figure 7(a). The complete trace (graph) of all possible knight’s moves  from all squares on the board showing the underpinning symmetry of the problem structure: left to right and top to bottom. All sides in this graph are of equal length.	Figure 7(b). A knight’s closed tour trace, starting from Square 1, showing the symmetry of a solution structure along the diagonals. All sides in this graph are of equal length.	Figure 7(c). Another closed tour trace, starting from Square 1, showing the symmetry of the solution structure along the diagonals. All sides in this graph are of equal length.

9.1      Using a Numeric Data Structure to Find a Human Solution

This approach, in Figure 8, may give us a solution, and it may hold the key to finding all human solutions for the simple knight’s tour. More importantly for our purposes, because it presents the problem structure as an array or list of numbers, it may lead us to a way to program a solution. Further, we may be able to generalise this structure for bigger boards. However, it doesn’t seem to give us any clues about portraying the symmetry of solutions, which might reflect the symmetry of the board and the symmetry of the knight’s move. It certainly offers an approach with paper and pencil, which, with patience, should yield some results.

Figure 8. Trail from square 1, hitting a dead end at square 9, backtracking to 11, saving square 10, and following on to square 5:   0, 1, 6, 8, 2, 3, 11, 5… level = 7

If we were to generalise to the full 16 squares of the 4×4 board, how would the structure we would draw up for this board differ from Figure 8? And again for the 25 squares for a 5×5 board? Would this method be effective for a human solution to these extended problems?

9.2      Binary Trees

Say from square 1 we choose square 6 as our first move. After that, we are faced with two possibilities: going to 8 or going to 12; we discount going back to 1 because it is a square already in the trail. In fact, for all succeeding squares on our trail, we are faced with

• option (a): no possible moves,
• option (b) only one possible move which we take,
• option (c) two possible moves, one we move to, and the other we save/remember.

You may recognise this structural description as a binary tree, a recursively defined structure in which each descendant node is again a binary tree with the same three options (a), (b), and (c). See Figures 5 and 8. This reveals the structures stemming forward from squares 6, 7 and 9 as binary trees. And our problem in solution (and programming) terms for the open tours then becomes: how to find and traverse these binary trees from their roots. The closed tours are the open tours which can return to square 1 in one more final move.

9.3      A Valid Recordable Move

A move to a square is only possible to follow and add to our trail, if that square is not already listed in the trail, otherwise we are visiting a square twice. Tracking back to other possible moves we have not taken but remembered at a juncture on the trail, when/if we come to a dead end, (as in option (a)), or end a successful trail, enables us to look at all possible trails. For example, if we follow 1, 6, 8… we must take note that there are other possible paths that start 1,6,12… if we are to investigate all possible paths. We need to save/remember the other path, whenever we are faced on our trail with two or more possible moves (as in option (c)), see Figure 9.

9.4     Counting the number of Solutions from Square 1

Every full solution from Square 1, open or closed that we find we can record. If we record every alternative path we encounter with option (c) we can then be sure we have eventually recorded all  tours from Square 1.

See the human process of recording alternative paths by stacking them in Figure 9.  The stack process: last in first out,  drives our search deeper for a full tour before going wider on the tree.

Figure 9. Pursuing a trail from 1, 6:  1, 6, 8, 2, 3, 9 (at level 5 we meet a dead end option (c) when  moving to Square 9), while remembering trails passed on the way by pushing them onto a stack. Next trail is 1, 6, 8, 2, 3, 11…(node 11 and level 4 are taken from the top of the stack (popped)  to provide this next path to explore after the dead end at 9.

(We have made the process of saving/remembering and eventually reinstating an  alternative path an explicit user facility on the KT_App2, (a working version in development) see Figure 18, with the buttons ‘Stackit’ (toggle) and ‘Popstack’. When you want to save alternative path(s), you press ‘Stackit’ and click on the squares you want to save, then press ‘Stackit’ again, (toggle) before you make the chosen knight’s move. When you come to a dead end, or you complete a successful path, click on ‘popstack’ to follow the next alternative path sitting on the top of the stack.(See the human process in Figure 9). Notice that by storing a square and level to the start of an alternative path on a stack (last in, first out when you pop the stack) the process drives your search deeper rather than wider in traversing the tree, and therefore favours a quicker solution to a full tour, open or closed.

10       Representing the Problem as a Graph.

A graph (from graph theory, an area of discrete mathematics) is a set of nodes (points) together with the set of edges joining the points. We might be tempted to draw the structure which illustrates the potential moves of the knight as a graph, where the numbered squares on the board are the numbered nodes and the edges are lines joining nodes which represent knight possible moves. In order to draw the graph to represent possible knight’s moves on the board we start at 1, join it to 6, 7, 9; and then from 6 to 8 and 6 to 12 and so on.  Our graph could be made to look like the drawings in Figure 10.

Figure 10. Constructing a graph corresponding to the Simple Knight’s Tour. By repositioning nodes and edges we can achieve a graph that illustrates the symmetry of the structure. It is then more evident that a solution starting 1, 6, 8… for example, arguing from your symmetrical representation, is symmetrical to a solution starting 1, 7, 5…

In this graph in Figure 10, which represents the moves possible for a knight on the board, the graph can be drawn in any way we like as long as it preserves the connections between the nodes (squares). The completed final drawing from Figure 10, lays out the symmetrical structure of the problem of the simple knight’s tour. We may hope that symmetry will figure in the solution structure also.  Figure 17 is the same graph embedded on a sphere which serves to highlight in a slightly different way, the symmetry of the structure (how squares 1 and 12 correspond, for example) and lends itself to using symmetry in counting all possible solutions. It is evident that the solutions derived from this symmetrical graph representation are likely to be more accessible to a human than the board representation. Using the graph representation, an abstraction  of the board representation, it may be easier to find a human complete solution to both problems, and it may point the way to a data structure representation (triple numbers for each node, for example) and so form the basis for one approach to a program solution.

10.1      Closed Knight’s Tour problem: Beginnings, Endings and Symmetry

We can just get on with the head on approach, or use some logical thinking based on the symmetry of the graph in Figure 10. Thinking may save us a lot of work… And in the case of the closed tours we may use our knowledge about starting and finishing to refine our approach by looking at some of the properties of the knight’s move and the paths built through a succession of moves.

Some Deductions: In the closed problem starting from Square 1, we have knowledge of the last move as well as the starting move, which must be through 9, 6 or 7 to return to 1. We put these thoughts as questions: If my path starts first move to 9, why can’t I finish through 9 to 1? Similar reasoning for 6 and 7. Further, if my path  first move starts with 6, why can’t it finish through 7 to 1 and similarly starting on 7 can’t finish through 6 to 1? So paths starting at 9 finish through 6 or 7 to 1. Paths starting at 6 or 7 finish through 9 to 1. These logical deductions, give us a simple heuristic to help us to improve our chances of discovering a solution, if there is one, by avoiding obvious dead ends: do not visit the finishing square if available as a move earlier on in the path.
Since we know about the beginnings and endings, we could try a strategy of starting from the beginning and, because the knight’s move is reversible, starting from the ending of a path to see if there is a possible meet-up point half way. See Figure 11.

Figure 11. Half trails starting at 1, 6 and 1, 9. The nodes 5, 12, 8 at Level =7, are possible link-ups. One solution (no re-occurring nodes in linked up halves, and each node visited once only): 1,6,8,2,10,4,12,7,5,11,3,9,1. To complete all closed solutions from square 1, draw the half-tree starting 1,7, … and again look for linking half  trails from 1, 9, 3, …

11 Symmetry in the Representation of Solutions to Knight’s Tour

A knight’s move is reversible. And consequently a closed solution, a loop, is reversible too, and therefore presents another closed solution. Every knight’s move on the board is an equal distance on the board. So if we find a closed solution, maybe a useful representation for the solution structure would be as a loop, with the nodes equally spaced on a circle as a dodecagon Figure 12(a) or equally spaced as a 12 point star (dodecagram) Figure 13(a).

Figure 12(a) Closed solution 1, 6, …, 9, 1  from square 1 symmetrically arranged in a regular  dodecagon as a loop on a circle. This representation of a solution structure preserves the equidistance in the moves. (And gives us two closed solutions and two open solutions from every square on the board).>	Figure 12(b) Another solution 1, 7, …, 9, 1 from square 1, which we have superimposed on the representation layout in Figure 12(a), traces out a different symmetric shape. This solution does not reflect equidistance in the moves and has crossing points which are not nodes. However, it could be arranged as a regular polygon shape solution 1, 7, …, 9, 1  with equidistant moves, as shown in Figure12(a)
Figure 13(a) Solution 1,6, …, 9, 1 arranged  in a 12 point star with nodes above equidistant in a star (dodecagram) on a circle with a dodecagon in the centre. This solution graph is symmetrical and includes intersections which are not necessarily nodes.	Figure 13(b) Solution 1, 7, …, 9, 1 is superimposed on the solution structure layout in 12(a).  This solution structure yields a symmetric representation with a regular central octagon. Again this can open out into a regular polygon solution like 12(a). Not all adjacent nodes are equally spaced and again there are intersections in this solution graph which are not nodes.
Figure 14(a) Symmetric complete graph of the knight’s tour problem structure, with one closed solution 1,6,8,…,1 equi-spaced on a dodecagon as in Figure 12(a) and the remaining joining edges filled in, which includes crossing points which are not nodes.	Figure 14(b).  Symmetric complete graph of the knight’s tour  problem structure, with one closed solution 1,6,8,…,1 equi-spaced on a star (dodecagram) and the remaining joining edges filled in, which includes crossing points which are not nodes. This representation does not have equidistance between all nodes connected by a single move. E.g. (1,7) is not equal to (1,6) although 6 and 7 are both adjacent to 1.

12 Follow Up Questions

1. Using the KT_App1, construct a 6 move symmetric pattern, as in Figure 2(b) starting 1, 9, …, to 7 and use the symmetry to continue the tour from 12 back to 1.
2. Repeat the procedure in Q.1 starting 1, 6,…, ending 9, 1
3. Repeat the procedure in Q.1 starting 1, 7,…, ending 9, 1
4. Using the KT_App1 and appealing to symmetry, starting at square 12, repeat the procedure in Q.1 and find a closed tour from square 12.
5. Hence, since a closed tour is a loop, which includes all squares, what can you deduce about the number of closed tours starting at a particular square in relation to tours starting at another square.
6. Using KT_App2  find a full open tour from square 1, stacking alternative paths as you go and popping the stack whenever you come to a dead end where you cannot move.
7. Using KT_App2 find a full closed tour from square 1, stacking alternative paths as you go and popping the stack: 1whenever you come to a dead end where you cannot move and 2 whenever you complete a full tour.
8. If you are able to stack all alternative paths as you go — systematically for example choosing the lesser square number to stack when an alternative presents itself — you will find listed at the end of your efforts all open and closed full tours from Square 1.
9. Using KT_App2, count the number of full open and closed tours from square 4 using the same procedure as in Q8. Is the number of open full tours starting at square 1 the same as starting from square 4? Closed  full tours?
10. How many open and closed full paths are there from each square on the board?
11. Construct a representation for the simple knight’s tour in which the distance between nodes is the same for each knight’s move and in the graph that you draw there are no crossing points which are not nodes. You may want to construct your representation in 3-dimensions. (For example on the surface of a cylinder)
12. Construct,  in tree form, the half trail knight’s tour starting from 1, 7 … as in Figure 11. Hence find all possible solutions to the knight’s tour, open and closed, which start from square 1.
13. From Q5, therefore, how many complete (12 moves) closed tours are there in total for all squares on the board.
14. Draw the loop and star layout corresponding to Figures 12(a) and 13(a) for a solution starting 1, 7, … 9, 1. Would you expect to have similar drawings as in Figures 12(b) and 13(b) when you trace out a solution for 1, 6, … 9, 1 on your layout?
15. In Figure 17, does the graph on the left contain all full solutions, open and closed of the knight’s tour from square 1? Draw the similar trees starting at 1, 6, … and 1, 7, … to check for yourself.
16. If you are able to find how many open and closed solutions there are from the square 1 in Figure 1, can you deduce how many solutions there are starting from the other edge squares 2, 3, 6, 7, 10, 11, 12?
17. How many full solutions, if any, are there, open and closed, starting from the central square 4? Use any of the three approaches described above which work best for you, or otherwise to find your answer. How many solutions are there starting from the other interior squares 5, 8, 9?
18. How many solutions, open and closed, are there in total for the full knights tour starting from every point on the board?
19. How would you make a start at constructing a program solution?
20. Draw, using a pencil, ruler/compass and protractor
    1. A regular 12-sided polygon
    2. A regular 12-sided star
    3. Draw the circle which passes through the 12 sided polygon (dodecagon).(****difficult)
21. Write a program in Scratch or Python to tackle Q.15(c), (download Action Geometry – Polygons and Stars  from ispython.com/repository-2/ for help with this task)

13 Knight’s Tour on 4×4 Board with 16 Squares

22. We consider a 4×4 chess board with all 16 squares numbered starting top left with square 1. Using the sort of arguments/deductions we used previously about starting and finishing, or otherwise, can you show why there is no closed knight’s tour starting from square 1 on this board taking in all 16 squares? (You need only to consider the squares that link with 1 and 16). What further deductions can you make about the closed knight’s tour from other squares on this board?

23 . What is the longest path from square 1 on this board?

24. Is there a longer path from another square?

25. Is it easier in the long run to write a program solution when you have a lot of questions to answer?

14 Knight’s Tour on 5×5 Board with 25 Squares

26. How would you tackle the knight’s tour on a 5×5 chess board with 25 squares from Square 2? Can you find a full closed solution? Is using KT_App3 an option? See Figure 15.

(a) For a human solution use any approach (including KT_App3 )   (b) For a program solution

27. Write a program in Scratch or Python to draw regular polygons and regular stars with (a) 25 sides (b) n sides (download Action Geometry – Polygons and Stars) from ispython.com/repository-2/

In our Workbooklet 2, we intend to present and discuss answers to the follow up questions, and approaches to program solutions to the simple knight’s tour problem in Python 3, and extensions of the problem to larger chess boards.

15 Solutions and Representations

15.1 Symmetric Planar Graph Representation

We include here in Figure 15 for completeness the symmetric embedding as a planar graph of the structure of the simple knight’s tour. See Figure 10 as a starting point.

Figure 15. Knight’s Tour Graph Representation Leading to a Symmetrical Planar Graph. The human solutions of the closed tour from Square 1 are probably more readily discovered from this symmetric representation than from any other approach. So too are the additional open tours starting from Square 1.

15.2    Full Knight’s Tour Solutions Open and Closed

Figure 16. Example of a full closed Knight’s tour from Square 1 and a full open tour from Square 1. Using the symmetry of the problem structure of the graph, can you find other full solutions, closed or open, starting at Square 1?

 

15.3   A Tree Solution and a Graphical Representation on a Sphere

Figure 17. Q 15. The graph on the left records all the open and closed knight’s tours starting 1, 9, 3, … Does it do more than this? Check it out by drawing the tree starting 1, 6… and arguing symmetrically for 1, 7. Or can you argue, from a symmetric graph representation, about the existence, or otherwise, of full open solutions starting 1,6 or 1,7… and hence answer the question.
The symmetric graph on the right is embedded on a sphere which illustrates again the symmetry of the problem structure and indicates the first moves of some full open and closed symmetric solutions starting at 1, 9, 3…

15.4   KT_App2 For Counting Solutions

Figure 18.  This is KT_App2 working version (under development). And See Figure 1(a). Finding all solutions from Square 1.   Starting at Square 1, when about to move to Square 9, we press ‘stackit’ followed by clicking Square 6 and Square 7 and then ‘stackit’ again (toggle to save those paths for later). We complete our move to Square 9. We then move to Square 3 (no choice) and we have a choice to proceed to Square 2 or Square 11. But before we do, we stack one of them, using the ‘stackit’ process described above, before moving to the other. If at some point, we are unable to move to a square, see Figure 9 for an example, or we have completed a knight’s tour, we press popstack to set us up to follow the latest path to be stacked…

Figure 19. Using KT_App2, all full solutions open and closed from Square 1 can be traced and printed in one run. Can you produce similar results starting at an interior location like Square 4?

16   KT_App3 For Solutions on a 5×5 Knight’s Chess Board

Figure 20. Two solutions to the Knight’s Open Tour on a 5×5 Chess board. See Figures 21,22.

Figure 21. Using KT_App3: A full open solution on a 5×5 board starting at Square 1.

Figure 22. Another full open solution from Square 1.

In trying to find a full open solution starting at Square 1, both solutions end at Square 13. Is this just a coincidence, lucky 13, or is there a more likely explanation?

Figure 23. KT_App 3: Does this start at a trial and error successful solution of a full open solution to the knight’s tour suggest a heuristic you might adopt when attempting a full open solution starting at Square 1? What is the logic behind your heuristic? Can you demonstrate that there is no full closed solution from Square 1?

Figure 24. The Complete Graph of 5×5 Knight’s Chessboard. Showing all possible moves from each square with all sides of equal length and the symmetry of the problem structure.

Figure 25. List of Possible Knight’s moves from each Square on the 5×5 Chess Board.