The Knight’s Tour — Looking at Human and Computer Solutions
Finding human solutions to a problem, sometimes provides a basis for, or serves as a pointer to, devising and implementing algorithms for a programmed solution. We use a simple version of the knight’s tour to pursue this idea. At the same time, we illustrate how a model of Computational Thinking underpins this approach
A Simplified Working Model of Computational Thinking (CT)
We use a simplified Model of Computational Thinking in relation to Algorithms and Programming: (ADAGE)
- Algorithmic Thinking — thinking through the steps required to solve a problem.
- Decomposition — breaking a larger problem down into smaller pieces.
- Abstraction — reducing complexity by using or creating tools.
- 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.
The Problem Stated.
A chess knight is placed on the board (Figure 1) at position 1, and we are asked to find if there is a sequence of ‘knight’ moves which will take the knight around the board: 1). So that it visits each of the other 11 numbered squares only once (the open path solution); 2). and returns to the starting position 1 in one more final move (the closed path solution).
Computational Thinking and Some Human Solutions: Overview
If you want to experiment with solutions directly by moving the knight around the board and recording your moves on the screen, download kt_app1 (source code in Python 3) fromRepository_KT in repositories.
A way to tackle the problem in looking for a solution is to break it down into a simpler or partial problem — for example, can we find a shorter knight’s move path that returns to 1, visiting a number of different squares once only.(D) Here’s one: 1,6,12,7,1. How many different paths are there? How do we keep track of different solutions? By asking questions we start to look at ways to tackle the problem (AT). Can we come up with an approach, which we can try, without going into all the detail (A) for the moment. Later, can we compare our solutions (E) and look at generalising how we did it in order to solve a wider class of problem (G).
Can we start at 1 and visit every square on the board once and once only — the open solution. Does a solution exist? None, one, or many? If none can we prove that one doesn’t exist. If many, finite or infinite. If finite, can we find all solutions? Can we find all possible Knight’s Tours, Open and Closed, from all starting points on the board?(G). Will our solution help us to solve the Knight’s Tour problem on a bigger board, say a chess board with 64 squares. Can we devise a programmed solution to help us deal with the complexity more easily? 1. We look at different head on approaches to the open problem. We can tackle it with a made up board, a make-do knight, and pen and paper to record our moves. Or use the KT_APP designed to aid computational thinking in a head on trial and error approach: to construct a path of legitimate knight moves on the board. If we find a solution, or several, how do we take steps to make sure we have found all solutions? If we break the problem down into simpler problems(D) Does symmetry or pattern in the problem help us?
Starting at 1, Our first move takes us to 9, 6, or 7 and we try to exhaust all possible paths for each of these three squares with three possible sets of solutions. Go for it. A short path solution: 1,6,12,7,1.
When we go to 6 we are faced with two possibilities: going to 12 or going to 8 (we discount going back to 1 as one of the shortest paths already counted). If we are to investigate all possible paths, we have to save/remember other possible paths that flow from 1,6,8,… when we have finished searching for paths beyond our trail 1,6,12,… When we look at the simple knight’s tour on the board in Figure 1, we see that every move following a start at 6,7, or 9 takes us to a square which has 1 or 2 or zero possible next moves, if a move has to connect with a square which doesn’t belong to the trail so far. Revisiting possible moves at a juncture on the path when/if we come to a dead end enables us to look at all possible paths.
Closed problem: Beginnings and endings(D)
We can just get on with the head on approach, or use some logical thinking about starting and finishing to refine our approach — some deductions: this time 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 out with 9, why can’t I finish through 9?
- Similarly for 6 and 7.
- If my path starts with 6, why can’t it finish through 7 and similarly starting on 7 can’t finish through 6?
So paths starting at 9 must finish through 6 or 7. Paths starting at 6 or 7 must finish through 9. These logical deductions, give us a simple heuristic to help us as we move: avoid visiting 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 starting from the ending of a path to see if there is a possible meeting point half way. See Figure 2 for starting from 6 and starting from the end point 9. Figure 2 illustrates a way to record the squares we need to save at junctures to be revisited.
3. Could we try to get halfway from a starting point and halfway from an endpoint and see if there is a link up possible at the mid point by joining two distinct half paths together? See figure 2.
4. Why does Figure 3 have the complete set of solutions with starting point 1?
We could try to match a sequence by recording all paths of about 6 moves with different starting points say 9 and 6, or 9 and 7 to see if they join and have each square occurring just once in a combination of half-paths. See figure 2.
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. If we were to draw the structure with lines representing the connections between the squares by possible knight’s moves we would start 1 joined to 6, 7, 9 and from then 6 to… and so on. see Figure 3. Our graph would look like the drawings in Figure 3. In this graph, 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. The Figure 4 is the same graph embedded on a sphere which serves to highlight the symmetry of the structure (how 1 and 12 correspond, for example) and the human solutions are possibly easier to see. Using the graph it may be easier to find the human complete solution and point the way to devise a programming solution.
Programming Solutions: Representing the graph as a data structure; programming to traverse the graph.
We can see in figure 3 that each node has a maximum of 3 edges connecting it so that a data structure to represent the kt graph can be set out: node1=[6,7,9], node2=[,,]…node9=[1,3,0],… node12=[6,7,10]
Starting with 6, 7 or 9 we trace a path down for 6 say, where we connect to node to node and save node in another list to be traced later on when we have exhausted the first path. At each node, any descendant nodes that are not already in the trail are pushed onto the stack with the value of count. And one that is not in the trail is followed. If all descendants are in the trail, the stack is checked and if empty, this marks the end of the paths from this node, but if not empty pop the stack and reinstate value of count and carry on the new path. Stacking untravelled nodes as we descend means that our search is prioritised in depth rather than width. For open paths, we check count when stack is empty, if it equals 10 then we have a path which covers all nodes. If looking for closed path (final move to node1) and count=11 then we have a closed solution. The solutions to open paths are essentially traversing a binary tree, which means stacking a maximum of one descendant node. Returning to node1 for the closed tour means that the tour is on a graph.