In the demonstration program, the computer performs a shortening algorithm that is based on a simple idea. Since starts with all markers in their home boxes, performs a sequence of transpositions, and eventually returns every marker to its home box, the first marker moved is eventually going to be brought home. There is a potential for shortening the sequence of transpositions by eliminating the transposition that moves this first marker away and the transposition that moves it back home.
To produce a shortening algorithm built on this idea, all one needs is to devise rules for modifying the sequence of transpositions to adjust for the elimination of the two transpositions we have identified. We will set forth some rules that meet this objective. Building on our hands-on experience with the demonstration program, let us state the rules for the algorithm in terms of the computer’s response with the blue markers to the transpositions that the human user performs with the green markers.
If one follows the procedure described here, it will produce a modified truncated sequence of transpositions that has two fewer transpositions at the point that the original sequence returns the first marker moved to its home box. Since the modified truncated sequence is the same as the original one from that point on, it uses two fewer transpositions in the end when each has returned all of the markers to their home boxes.
You may wish to work out the proof that this algorithm leads to the Reduction Lemma on your own, or you can follow this link for a proof.