Knight’s Tour

From Human Solutions to Program Solutions

Computational Thinking, Creativity and Pedagogy in Programming

The Knight’s Tour

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

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 as  a basis for discussion, 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, including creativity, heuristics, symmetry, induction, and deduction, underpins this approach.  In our discussion, we make use of problem representations:  with  diagrams,  some ideas from graph theory and directly  on  click/touch screens of interactive game boards (Figure 1).

In the discussions in the follow up article, we will look 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 involve introducing data structure representations for: lists, stacks, arrays, trees and graphs, and programming with non-trivial recursion. No previous knowledge of these concepts is assumed.

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).

App: knight's tour board 1-12. Trail so far 1,9,3... Download python program from repositorykt

Figure 1. KT_App: knight’s tour board 1-12. Trail so far 1,9,3… next move: 2 or 11. (Download kt_app1 — a python program from REPOSITORY_KT in Repositories to experiment with knight moves by clicking on the screen)

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?

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?

Open problem

Starting at 1, Our first move takes us to 9, 6, or 7. From then on, all our moves can be represented as moves on a binary tree. And we can 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.

Discussion

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 the other path: 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:

  1. If my path starts out with 9, why can’t I finish through 9?
  2. Similarly for 6 and 7.
  3. 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.

Figure 2. Half trees 6 and 9

Figure 2. Half trees 6 and 9 give a solution 1,6,8,2,10,4,12,7,5,11,3,9,1

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.

Figure 3. Complete Solution to the Simple Knight's  Tour from 1.

Figure 3. Complete Solution to the Simple Knight’s Tour from 1.

4. 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 drawings in Figure 4. 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 4 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]
Graph=[node1,node2,node3,…node12]
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.

knight's tour

Figure 4. knight’s tour

Symmetric representation embedded  on a sphere

Figure 5. Symmetric representation embedded on a sphere