THE KNIGHT’S TOUR
Computational Thinking, Creativity and Pedagogy in Programming for Teachers and Pupils
Workbook 1: From Human Solutions to Program Solutions in Python 3
Dave White & Rae Harbird
Department of Computer Science UCL
1Contents
2Introduction
3The Problem Stated
3.1Repository for the Knight's Tour
3.2CAS Tenderfoot Program Interactive Knight Chess Boards, Trees and Graph Theory
3.3Follow Up Article
4A Working Model of Computational Thinking (CT)
5Finding Knight’s Tour Solutions
5.1Open and Closed solutions --- A Computational Thinking Approach
5.2Decomposition and Using the Board Directly
6Counting Solutions
6.1Recording the moves in different ways.
7Some Thoughts and Deductions as We Go: Symmetry in our Approach
8Symmetry at the halfway of a full closed tour starting at square 1
9Looking at the Underlying Structure of a Knight’s Tour Board
9.1Using a Numeric Data Structure to Find a Human Solution
9.2Binary Trees
9.3A Valid Recordable Move
9.4Counting the number of Solutions from Square 1
10Representing the Problem as a Graph.
10.1Knight’s Closed Tour problem: Beginnings, Endings and Symmetry
11Symmetry in the Representation of Solutions to the Knight’s Tour
12Follow Up Questions
13Knight’s Tour on 4x4 Board with 16 Squares
14Knight’s Tour on 5x5 Board with 25 Squares
15Solutions and Representations
15.1Symmetric Planar graph representation
15.2Full Knight's Tour Solutions Open and Closed 4x4 (12 Squares)
15.3A Tree solution and a Graphical Representation on a sphere
15.4KT_App2 For counting solutions
16KT_App3 For Solutions on a 5×5 Knight’s Chess Board
2Introduction
“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 booklet 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. Findinghuman solutions to a problem, sometimes provides a basis for, or serves as a pointer to, devising and implementingalgorithms 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, where humansolutions becomeinfeasible.
We have provided interactive software apps:KT_App1, KT_App2to assist in investigating, recording and counting solutions to knight’s tour problems on a 4x4 board with 12 squares, and KT_App3 for a 5x5 board with 25 squares. Download the Interactive knight’s tour game boards KT_App1, KT_App2 and KT_App3, and other information from:
ispython.com/knights-tour/
3The 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.1Repository for the Knight's Tour
The link: CAS Knight's Tour will allow you to download from a folder with:
- A readme file.
- 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 of web page: ispython.com/knights-tour/, outlining the problems and describing different human solutions leading to program solutions.
A zip file with:
- KT_App1: A simple knight’s tour interactive chess board. Click on the squares to register the knight’s move. A source program written in Python 3. Run with IDLE.
- KT_App2: A simple knight’s tour interactive chess board, complete with stacking facilities, 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.
- KT_App3: A simple knight’s tour interactive chess boardwritten in Python 3 for a 5×5 chess board.
- a picture of a chess knight,black.gif, which must be in the same folder as KT_App1,2,3 when you extract the zip file, in order for the programs to run.
3.2CAS Tenderfoot ProgramInteractive Knight Chess Boards, Trees and Graph Theory
The recent CAS Tenderfoot programme 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, weengage in finding human approachesto the task of countingthe number of solutions, using the 'stacking' interactive chessboard, KT_App2. We then move on to other representations of the knight's tour, tackling the problem for human solutions with drawings, including data lists, 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 section 15 onwards of this booklet.
3.3Follow Up Article
In a follow up article, we will provide discussion for questions we have posed, delvefurther into the human solutions we have developed with a view to transforming them, where possible, into program solutions for the knight’s tourand 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.
4A 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. We add Logic and Creativity, as all processes we undertake should be based on logic and new/different approaches the result of thinking creatively.
- Algorithmic Thinking — thinking through the steps required to solve a problem
- Decomposition — breaking a larger problem down into smaller ones to reduce complexity.
- 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.
- Logic and Creativity --- as simple as ordering a sequence of instructions or creating a new/different order of instructions for your own reasons.
5Finding Knight’s Tour Solutions
5.1Open and Closedsolutions --- A Computational Thinking Approach
From the outset we apply CT explicitly to the problems:
- 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 there is no solution. 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?
- 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 we 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 we 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?).
- Abstraction. Can we devise tools/approaches/arguments, which hide the detail of the operation, but help us to derive/count more solutions? (induction, symmetry,heuristics, for example)
- 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 4x4 chess board? Or on a 5x5 or an 8x8 chess board? Is it possible to devise a human solution that finds all solutions on a bigger board say 5x5?
- 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 programsolution 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?
- Logic. Can we use logic to argue once we choose a first move from Square 1 to either 6, 7 or 9, whether this has consequences for the final move (if one exists?) from 6, 7 or 9 on the final move back to 1?
- Creativity.Can we find other ways to look at this problem other than the board on which it is played --- experiment with other representations of the problem?
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.2Decomposition and Using the Board Directly
We can tackle the reduced problem of say a 2, 3, 4, 5… knight moves closed tour… with a made up board, a make-do knight, and pen and paper to record our moves. Or use the KT_App1 (download latest version from and 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.
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?
Download KT_App1 from ispython.com/knights-tour/ / Figure 1(b). Symmetry in the board at half-way point i.e. after 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 ?)
6Counting 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.1Recording the moves in different ways.
If we take our simple example above of a 4 move closed 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. SeeSection 9.2 below for a full description.
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 tour of 12 moves from square 1?
Figure 3. A tree representation of 3-move paths of the knight’s tour from square 1, in search of a 4 move closed tour.
7Some Thoughts and Deductions as We Go: Symmetry in our Approach
We notice that the ‘board’, Figure 1, is not a full 4x4 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 4 move closed tour in Figure 2(a), we see that square 16 is mirrored by square 127. So we could try half tours from 1, in which the next move after halfway 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 find longer tours.
8Symmetry at the halfway 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 halfway 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) 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 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?)
9Looking at the Underlying Structure of a Knight’s Tour Board
7(a). The complete trace(graph) of all possible knight’s moves on the board, showing the underpinning symmetry, left to right and top to bottom.All sides in this graph are of equal length. / Figure 7(b). A knight’s closed tourtrace 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 showing the symmetry of the solution structure along the diagonals.All sides in this graph are of equal length.9.1Using 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 programa 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.
If we were to generalise to the full 16 squares of the 4x4 board, how would the structure we would draw up for this board differ from Figure 8? And again for the 25 squares for a 5x5 board? Would this method be effective for a human solution to these extended problems?