Please participate in a vote to determine the future copyright terms of Wikimedia projects (vote ends May 3, 2009). Vote now!
Scholarship applications for Wikimania 2009 are now open. Apply now!
[Hide]
[Help us with translations!]

Knight's tour

From Wikipedia, the free encyclopedia

Jump to: navigation, search
An open knight's tour of a chessboard
An animation of the Knight's Tour.
Knight's graph showing all possible paths for a Knight's tour on a standard 8×8 chessboard. The numbers on each node indicate the number of possible moves that can be made from that position.
The Knight's tour as solved by The Turk, a chess-playing machine hoax. This particular solution is closed (circular), and can be completed from any point on the board.

The Knight's Tour is a mathematical problem involving a knight on a chessboard. The knight is placed on the empty board and, moving according to the rules of chess, must visit each square exactly once. A knight's tour is called a closed tour if the knight ends on a square attacking the square from which it began (so that it may tour the board again immediately with the same path). Otherwise the tour is open. The exact number of open tours is still unknown. Creating a program to solve the knight's tour is a common problem given to computer science students.[1] Variations of the knight's tour problem involve chessboards of different sizes than the usual 8 × 8, as well as irregular (non-rectangular) boards.

Contents

[hide]

[edit] Theory

The knight's tour problem is an instance of the more general Hamiltonian path problem in graph theory. The problem of finding a closed knight's tour is similarly an instance of the hamiltonian cycle problem. Note however that, unlike the general Hamiltonian path problem, the knight's tour problem can be solved in linear time.[2]

[edit] History

The earliest known references to the Knight's Tour problem date back to the 9th century CE. The pattern of a knight's tour on a half-board has been presented in verse form (as a literary constraint) in the highly stylized Sanskrit poem Kavyalankara[3] written by the 9th century Kashmiri poet Rudrata, which discusses the art of poetry, especially with relation to theater (Natyashastra). As was often the practice in ornate Sanskrit poetry, the syllabic patterns of this poem elucidate a completely different motif, in this case an open knight's tour on a half-chessboard.

The first algorithm for completing the Knight's Tour was Warnsdorff's algorithm, first described in 1823 by H. C. Warnsdorff.

In the 20th century the Oulipo group of writers used it among many others. The most notable example is the 10 × 10 Knight's Tour which sets the order of the chapters in Georges Perec's novel Life: A User's Manual.

[edit] Closed tours

On an 8 × 8 board, there are exactly 26,534,728,821,064 (directed, i.e. two tours along the same path that travel in opposite directions are counted separately) closed tours.[4][5][6] The number of undirected closed tours is half this number, since every tour can be traced in reverse. There are 9,862 undirected closed tours on a 6 × 6 board.[7] No closed tours exist for smaller boards (this is a corollary of the following theorem).

[edit] Schwenk's Theorem

For any m × n board with m less than or equal to n, a closed knight's tour is always possible unless one or more of these three conditions are true:

  1. m and n are both odd
  2. m = 1, 2, or 4; m and n are not both 1
  3. m = 3 and n = 4, 6, or 8

[edit] Condition 1

One can show that condition 1 prohibits closed tours by a simple argument based on parity and coloring. For the standard black-and-white coloring of the chessboard, the knight must move either from a black square to a white square or from a white square to a black square. Thus in a closed tour the knight must visit the same number of white squares as black squares, and the number of squares visited in total must therefore be even. But if m and n are both odd, the total number of squares is odd. (For example, in a 5 × 5 checkerboard there are 13 of one color and 12 of the other.) Therefore closed tours do not exist. Open tours may still exist.

[edit] Condition 2

Condition 2 states that when the shorter side is of length 1, 2, or 4, no closed tour is possible.

When m = 1 or 2, no closed tour is possible because the knight would not be able to reach every square (with the exception of the trivial case 1 × 1). It can be shown that a 4 × n board cannot have a closed tour either, by using a coloring argument.

The knight must alternate between green and red.

Start by assuming that a 4 × n board has a closed knight's tour. Let A1 be the set of all squares that would be black and A2 all the squares that would be white, if they were colored according to the alternating black-and-white checkerboard scheme. Consider the figure at right. Define B1 to be the set of green squares and B2 as the set of red squares. There are an equal number of red squares as green squares. Note that from a square in B1 the knight must next jump to a square in B2. And since the knight must visit every square once, when the knight is on a square in B2 it must move to a square in B1 next (otherwise the knight will need to travel to two squares in B1 later).

If we follow the hypothetical knight's tour we will find a contradiction.

  1. The first square the knight goes to will be a square of A1 and B1. If it is not, we switch the definitions of B1 and B2 so that it is true.
  2. The second square must be an element of the sets A2 and B2.
  3. The third square must be an element of A1 and B1.
  4. The fourth square must be an element of the sets A2 and B2.
  5. And so on.

It follows that set A1 has the same elements as set B1, and set A2 has the same elements as set B2. But this is obviously not true, as the red and green pattern shown above is not the same as a checkerboard pattern; the set of red squares is not the same as the set of black squares (or white, for that matter).

So our above assumption was false and there are no closed knight's tours for and 4 × n board, for any n.

[edit] Condition 3

Condition 3 may be proved using casework. Attempting to construct a closed knight's tour on a 3 by 4, 3 by 6, or 3 by 8 will lead to definite failure. 3 by n boards with n not equal to 4, 6, or 8 can be shown to have closed tours by induction (a repeating pattern).

[edit] All other cases

Simply proving the above three conditions does not prove the theorem; it is still required to prove that all rectangular boards that do not fall in one of the above three categories have closed knight's tours. [8]

[edit] Computer algorithms

Algorithms other than the simple brute-force search to find knight's tour solutions are discussed below.

[edit] Neural network solutions

Closed Knight's Tour on a 24 × 24 board solved by a neural network.

The Knight's Tour problem also lends itself to being solved by a neural network implementation.[9] The network is set up such that every legal knight's move is represented by a neuron, and each neuron is initialized randomly to be either "active" or "inactive" (output of 1 or 0), with 1 implying that the neuron is part of the final solution. Each neuron also has a state function (described below) which is initialized to 0.

When the network is allowed to run, each neuron can change its state and output based on the states and outputs of its neighbors (adjacent knight's moves) according to the following transition rules:

U_{t+1} (N_{i,j}) = U_t(N_{i,j}) + 2 - \sum_{N \in G(N_{i,j})} V_t(N)
V_{t+1} (N_{i,j}) = \left\{ \begin{array}{ll} 1 & \mbox{if}\,\, U_{t+1}(N_{i,j}) > 3\\ 0 & \mbox{if}\,\, U_{t+1}(N_{i,j}) < 0\\ V_t(N_{i,j}) & \mbox{otherwise}, \end{array} \right.

where t represents discrete intervals of time, U(Ni,j) is the state of the neuron connecting square i to square j, V(Ni,j) is the output of the neuron from i to j, and G(Ni,j) is the set of neighbors of the neuron.

Although divergent cases are possible, the network should eventually converge, which occurs when no neuron changes its state from time t to t + 1. When the network converges, a solution is found. The solution found by the network will be either a knight's tour, or a series of two or more independent knight's tours within the same board.

[edit] Warnsdorff's algorithm

A graphical representation of the Knight's Tour implemented using Warnsdorff's Algorithm. The numbers in red circles denote the number of next possible moves that the knight could make if it moves from the start position to the one with the circle on it.

Warnsdorff's algorithm is a heuristic method for solving the knight's tour, based on the rule of choosing the square among those immediately accessible by the knight move that would give the fewest possible knight's moves following the move to that square. In graph-theoretic terms, each move is made to the adjacent vertex with the least degree. (Pohl has devised a rule for breaking ties.) This algorithm may also more generally be applied to any graph. Although the Hamiltonian path problem is NP-hard in general, on many graphs that occur in practice this heuristic is able to successfully locate a solution in linear time.[10] The knight's tour is a special case.[11]

The algorithm was first described in "Des Rösselsprungs einfachste und allgemeinste Lösung" by H. C. Warnsdorff in 1823.[12]

[edit] Algorithm

Warnsdorff’s algorithm will do for any initial position of the knight on the board. All the possible squares which may be reached in one move from this position are located, and the number of moves that the knight would be able to make from each of these squares is found. [13] Then, the algorithm dictates that the knight move to the square that has the least number of possible following moves. The process is then repeated until each square has been visited.[14][15]

[edit] In Pseudocode

Some definitions:

  • A position Q is accessible from a position P if P can move to Q by a single knight's move, and Q has not yet been visited.
  • The accessibility of a position P is the number of positions accessible from P.

Algorithm:

set P to be a random initial position on the board
mark the board at P with the move number "1"
for each move number from 2 to the number of squares on the board,
	let S be the set of positions accessible from the input position
	set P to be the position in S with minimum accessibility
	mark the board at P with the current move number
return the marked board -- each square will be marked with the move number on which it is visited.

[edit] In C

The following C code solves the Knight's Tour problem starting from a random position on a 10x10 chess board.

#include <stdlib.h>
#include <stdio.h>
#include <time.h>
 
#define NUMMOVES 8
#define BOARDSIZE 10
 
const int moves[NUMMOVES][2]={{2,1},{2,-1},{1,2},{1,-2},{-1,2},{-1,-2},{-2,1},{-2,-1}};
int board [BOARDSIZE][BOARDSIZE];
 
int inRangeAndEmpty(const int posx, const int posy) {
	return (posx < BOARDSIZE && posx >= 0 && posy < BOARDSIZE && posy >= 0
		    && board[posx][posy] == 0);
}
 
int getAccessibility(const int x, const int y) {
	int accessibility = 0;
	int i;
	for(i=0;i<NUMMOVES;i++)
		if(inRangeAndEmpty(x+moves[i][0],y+moves[i][1]))
			accessibility++;
 
	return accessibility;
}
 
void getNextMoves(int move[]) {
	int positionx = move[0];
	int positiony = move[1];
	int newx,newy,newacc;
	int i;
	int accessibility=NUMMOVES;
	for(i=0;i<NUMMOVES;i++) {
		newx=positionx+moves[i][0];
		newy=positiony+moves[i][1];
		newacc=getAccessibility(newx,newy);
		if(inRangeAndEmpty(newx,newy) && newacc < accessibility) {
			move[0]=newx;
			move[1]=newy;
			accessibility=newacc;
		}
	}
}
 
int main() {
	srand((unsigned)time(0));
	int positionx = (rand()%BOARDSIZE);
	int positiony = (rand()%BOARDSIZE);
	int moveNumber = 2;
	int move [2];
	int i, j;
 
	// initialize board
	for (i = 0; i < BOARDSIZE; i++)
		for (j = 0; j < BOARDSIZE; j++)
			board[i][j] = 0;
	board[positionx][positiony] = 1;
 
	// compute moves
	for (i = 1; i < BOARDSIZE*BOARDSIZE; i++) {
		move[0] = positionx;
		move[1] = positiony;
		getNextMoves(move);
		positionx = move[0];
		positiony = move[1];
		board[positionx][positiony] = moveNumber;
		moveNumber++;
	}
 
	// print board
	for (i = 0; i < BOARDSIZE; i++) {
		for (j = 0; j < BOARDSIZE; j++) {
			printf("%d\t",board[i][j]);
		}
		printf("\n\n");
	}
	return 0;
}

[edit] In Java

In java the above code looks like this:

import java.util.Random;
 
public class ChessBoardTester {
   public static void main(String[] args) {
 
      // Helper methods... The tester is at the bottom.
      class ChessBoard {
         public ChessBoard(){
            boardLength = BOARD_SIZE;
            boardWidth = BOARD_SIZE;
            theBoard = new int[boardLength][boardWidth];
            moveNumber=0;
         }
 
         public int[] initialPosition(){
            Random generator = new Random();
            int[] pos = new int[2];
            pos[0] = generator.nextInt(boardLength);
            pos[1] = generator.nextInt(boardWidth);
            theBoard[ pos[0] ][ pos[1] ] = ++moveNumber;
            return pos;
         }
 
         public int[] nextMove(int[] pos){
            int xPos = pos[0];
            int yPos = pos[1];
            int accessibility = NUM_OF_MOVES;
 
            for (int i=0 ; i< NUM_OF_MOVES ; i++){
               int newX = xPos + MOVES[i][0];
               int newY = yPos + MOVES[i][1];
               int newAccessibility = getAccessibility(newX, newY);
 
               if( inRangeAndEmpty(newX, newY) && newAccessibility < accessibility ){
                  pos[0] = newX;
                  pos[1] = newY;
                  accessibility = newAccessibility;
               }
            }
 
            theBoard[ pos[0] ][ pos[1] ] = ++moveNumber;
            return pos;
         }
 
         private int getAccessibility(int x, int y){
            int accessibility = 0;
            for(int i=0; i < NUM_OF_MOVES ; i++){
               if ( inRangeAndEmpty(x + MOVES[i][0], y + MOVES[i][1] ) )
                  accessibility++;
            }
            return accessibility;
         }
 
         private boolean inRangeAndEmpty(int x, int y){
            return ( x < boardLength  && x >= 0 && y < boardWidth   && y >=0  &&
                theBoard[x][y] == 0 );
         }
 
         public void printBoard(){
            for (int i=0; i < boardLength ; i++){
               for (int j=0; j < boardWidth ; j++){
                  System.out.print(theBoard[i][j] + "\t");
               }
               System.out.print("\n");
            }
         }
 
         public int getSize(){
            return boardLength * boardWidth;
         }
 
         private final int BOARD_SIZE=10;
         private final int NUM_OF_MOVES = 8;
         private final int[][] MOVES ={{2,1},{2,-1},{1,2},{1,-2},{-1,2},{-1,-2},{-2,1},{-2,-1}};
 
         private int moveNumber;
         private int[][] theBoard;
         private int boardLength;
         private int boardWidth;
      }
 
/*********************************
 * Beggining of the Tester class *
 *********************************/
      // Initialize board 
      ChessBoard knightsChessBoard = new ChessBoard();
      int[] position = knightsChessBoard.initialPosition();
 
      // Determine the next position
      for (int i=1; i< knightsChessBoard.getSize() ; i++){
         position = knightsChessBoard.nextMove(position);
      }
 
      // Print board
      knightsChessBoard.printBoard();
 
   }
}

[edit] Generic Knight’s Tour Sequence

A generic version of the Knight’s Tour incorporates 1. modifying the game board and movement environment and 2. changing the local or global conditions on an individual Knight’s Move or sequence of Knight’s Move s.

For example, consider the Knight’s Tour for the following game board and movement environment, referred to as a keypad here for obvious reasons.

Knight’s Tour Keypad

On this particular case, a Knight’s Move is made on the keypad in one of the following ways:

1. Move two steps horizontally and one step vertically.

2. Move two steps vertically and one step horizontally.

For example, start from the initial key "A" (considered the first key in a sequence of keys or Knight’s Move s), then one possible move from the initial key "A" is to the key "L" as shown.

From the initial key "A" to the next key "L".

The sequence of moves thus far is "AL". From the present key "L", one next possible move is to the key "3" as shown.

From the present key "L" to the next key "3".

The sequence of moves thus far is "AL3". From the present key "3", one next possible move is to the key "H" as shown.

From the present key "3" to the next key "H".

The sequence of moves thus far is "AL3H" and in this way, a sequence of Knight’s Moves is created for this particular game board and movement environment, each move fulfilling the Knight Conditions as shown.

[edit] Knight’s Tour on a Keypad

Now if we pose a general problem like:

Find all 10-key sequences that can be keyed into the keypad in the following manner:

• The initial keypress can be any of the keys.

• Each subsequent keypress must be a Knight’s Move from the previous keypress.

• There can be at most 2 vowels in the sequence.

then we might want to consier a transformation in either the representation of the keypad or the Knight's Moves for ease in implementation of a solution.

A simple enumeration transformation of the particular keypad like:

Transformed keypad used in implementing the modified game board and movement environment in the computed solution.

turns out to be useful in the algorithmic implementation of solution as follows

[edit] Change of Representation

Perhaps not obvious, the reason for the transformation to the base-18 keypad representation is so that each keypress on the keypad is a minimal unique number in a sequence of keypresses with the simple sum hashcode from summing each keypress value multiplied by the base-18 raised to the power of each keypress' sequence order.

With this enumeration of the keypad, the algorithm for implementation of a solution to the problem takes the following generic pseudo-code form:

[edit] 3GHef Generic Algorithm

A generic algorithm that addresses the Generic Knight's Tour and makes use of the change of keypad representation is:

set the initial key, k0, to a random initial position on the modified, enumerated board
add k0 to the Knight’s Tour hashed sequence using the hashing code with the number "0"
for each keyed entry, ki, from 1 to the total number of keyed entries of interest on the keypad, K,
	let K be an ordered set of positions accessible from the last given input position
	iterate on K to add each unique ki to each hashed sequence using the hashing code with the number "i"
return each hashed sequence of the keypad that have the total number of keyed entries of interest on the keypad, K, and fulfill any additional sequence specific criteria

As an example of implementation of the algorithm, suppose we have the original 10-key press keypad sequence of

'A' -> 'H' -> 'A' -> 'H' -> 'K' -> 'B' -> 'K' -> 'B' -> 'K' -> 'B'

This is written as a 10-key press sequence for a base 18 keypad equivalently as

'0' -> '7' -> '0' -> '7' -> '10' -> '1' -> '10' -> '1' -> '10' -> '1'

Although hashed sequence are produced dynamically, the final returned total hash code sequence is going to be returned as 309514218678.

The equivalent KeyPressSequence Long 309514218678 was calculated from Base 18 Keypad with each keypress as:

KeyPressSequence 0 7 0 7 10 1 10 1 10 1

KeyPressSequence Base 18 0 126 0 40824 1049760 1889568 340122240 612220032 110199605760 198359290368

KeyPressSequence Base 18 Long 309514218678

Explicitly, the hash code is equivalent to summing over the values of the transformed key representatioin times each keypress factor where factors for the 10-=key sequence are accordingly:

KeyPress = 0 1 2 3 4 5 6 7 8 9

18^(KeyPress) = 1 18 324 5832 104976 1889568 34012224 612220032 11019960576 198359290368

[edit] C# Code

The following C# code tracks the sequence of Knight's Tour problem starting from a random position on the modifyied game board and movement environment, keypad.

using System;
using System.IO;
 
namespace Sequences
{
 
    class KeySequences
    {
 
        public static int KEYS_IN=10;
        public static int KEYPAD_BASE = 18;
        public static long lngKeySequenceCount = 0;
        public static int intStart = 0;
        public static char chrStart ;
        public static string strStart = null;
        public static int intAutoKeySequences = 0;
        public static long lngAutoKeySequences = 0;
        public static string strAutoKeySequences = null;
        public static bool bolAutoKeySequences = false;
        public static string strPrintOutputKeySequences = null;
        public static bool bolPrintOutputKeySequences = false;
        public static string strWriteOutputKeySequences = null;
        public static bool bolWriteOutputKeySequences = false;
        public static TextWriter oTextWriter;
        public static string strFilePath  = "C:\\SequenceCount_Default.txt";
        public static char[] enmAutoKeySequences = { 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', '1', '2', '3' };
 
        public static void OutputKeySequences(long lngKeySequence)
        {
            // OutputKeySequences 
            string strRem = "";
            long lngDiv = lngKeySequence;
            long lngRem = 0;
            while (lngDiv > 0) {
                lngDiv = System.Math.DivRem(lngDiv, KEYPAD_BASE, out lngRem);
                strRem = lngRem + ",\t" + strRem;
            };
            if (intStart==0) {
                strRem = intStart.ToString() + ",\t" + strRem;
            };
            if (bolPrintOutputKeySequences) Console.Write(strRem + "\n");
            if (bolWriteOutputKeySequences) oTextWriter.WriteLine(strRem);
        }
 
        public static bool chkVowelsLimit(long lngKeySequence)
        {
            // chkVowelsLimit 
            long lngDiv = lngKeySequence;
            long lngRem = 0;
            int intVowels = 0;
            if (intStart == 0) // Special case to handle intStart == 0 since later require lngDiv > 0 
                intVowels += 1;
            while (lngDiv > 0)
            {
                lngDiv = System.Math.DivRem(lngDiv, KEYPAD_BASE, out lngRem);
                if ( (lngRem == 0L) | (lngRem == 4L)  |  (lngRem == 8L)  |  (lngRem == 14L) )
                    intVowels += 1;
            };
//            Console.Write(intVowels + ": ");
//            OutputKeySequences(lngKeySequence);
            if (intVowels > 2) 
                return true;
            return false;
        }
 
        public static long getKeySequencesCount(int intKeyCount, int intLastMove, long lngKeySequence)
        {
            // getKeySequencesCount
            if (intKeyCount >= KEYS_IN-1)
            {
                if (chkVowelsLimit(lngKeySequence)) return (lngKeySequenceCount);
                if ((bolPrintOutputKeySequences) | (bolWriteOutputKeySequences)) OutputKeySequences(lngKeySequence);
                lngKeySequenceCount+=1;
                return(lngKeySequenceCount); 
            };
 
            int intKeyMove;
            switch (intLastMove) {
                case 0 :
                    intKeyMove = 7;
                    getKeySequencesCount(intKeyCount+1, intKeyMove, intKeyMove+lngKeySequence*KEYPAD_BASE);
                    intKeyMove = 11;
                    getKeySequencesCount(intKeyCount+1, intKeyMove, intKeyMove+lngKeySequence*KEYPAD_BASE);
                    break;
                case 1:
                    intKeyMove = 8;
                    getKeySequencesCount(intKeyCount+1, intKeyMove, intKeyMove+lngKeySequence*KEYPAD_BASE);
                    intKeyMove = 10;
                    getKeySequencesCount(intKeyCount+1, intKeyMove, intKeyMove+lngKeySequence*KEYPAD_BASE);
                    intKeyMove = 12;
                    getKeySequencesCount(intKeyCount+1, intKeyMove, intKeyMove+lngKeySequence*KEYPAD_BASE);
                    break;
                case 2:
                    intKeyMove = 5;
                    getKeySequencesCount(intKeyCount+1, intKeyMove, intKeyMove+lngKeySequence*KEYPAD_BASE);
                    intKeyMove = 9;
                    getKeySequencesCount(intKeyCount+1, intKeyMove, intKeyMove+lngKeySequence*KEYPAD_BASE);
                    intKeyMove = 11;
                    getKeySequencesCount(intKeyCount+1, intKeyMove, intKeyMove+lngKeySequence*KEYPAD_BASE);
                    intKeyMove = 13;
                    getKeySequencesCount(intKeyCount+1, intKeyMove, intKeyMove+lngKeySequence*KEYPAD_BASE);
                    break;
                case 3:
                    intKeyMove = 6;
                    getKeySequencesCount(intKeyCount+1, intKeyMove, intKeyMove+lngKeySequence*KEYPAD_BASE);
                    intKeyMove = 12;
                    getKeySequencesCount(intKeyCount+1, intKeyMove, intKeyMove+lngKeySequence*KEYPAD_BASE);
                    intKeyMove = 14;
                    getKeySequencesCount(intKeyCount+1, intKeyMove, intKeyMove+lngKeySequence*KEYPAD_BASE);
                    break;
                case 4:
                    intKeyMove = 7;
                    getKeySequencesCount(intKeyCount+1, intKeyMove, intKeyMove+lngKeySequence*KEYPAD_BASE);
                    intKeyMove = 13;
                    getKeySequencesCount(intKeyCount+1, intKeyMove, intKeyMove+lngKeySequence*KEYPAD_BASE);
                    break;
                case 5:
                    intKeyMove = 2;
                    getKeySequencesCount(intKeyCount+1, intKeyMove, intKeyMove+lngKeySequence*KEYPAD_BASE);
                    intKeyMove = 12;
                    getKeySequencesCount(intKeyCount+1, intKeyMove, intKeyMove+lngKeySequence*KEYPAD_BASE);
                    intKeyMove = 15;
                    getKeySequencesCount(intKeyCount+1, intKeyMove, intKeyMove+lngKeySequence*KEYPAD_BASE);
                    break;
                case 6:
                    intKeyMove = 3;
                    getKeySequencesCount(intKeyCount+1, intKeyMove, intKeyMove+lngKeySequence*KEYPAD_BASE);
                    intKeyMove = 13;
                    getKeySequencesCount(intKeyCount+1, intKeyMove, intKeyMove+lngKeySequence*KEYPAD_BASE);
                    intKeyMove = 16;
                    getKeySequencesCount(intKeyCount+1, intKeyMove, intKeyMove+lngKeySequence*KEYPAD_BASE);
                    break;
                case 7:
                    intKeyMove = 0;
                    getKeySequencesCount(intKeyCount+1, intKeyMove, intKeyMove+lngKeySequence*KEYPAD_BASE);
                    intKeyMove = 4;
                    getKeySequencesCount(intKeyCount+1, intKeyMove, intKeyMove+lngKeySequence*KEYPAD_BASE);
                    intKeyMove = 10;
                    getKeySequencesCount(intKeyCount+1, intKeyMove, intKeyMove+lngKeySequence*KEYPAD_BASE);
                    intKeyMove = 14;
                    getKeySequencesCount(intKeyCount+1, intKeyMove, intKeyMove+lngKeySequence*KEYPAD_BASE);
                    intKeyMove = 15;
                    getKeySequencesCount(intKeyCount+1, intKeyMove, intKeyMove+lngKeySequence*KEYPAD_BASE);
                    intKeyMove = 17;
                    getKeySequencesCount(intKeyCount+1, intKeyMove, intKeyMove+lngKeySequence*KEYPAD_BASE);
                    break;
                case 8:
                    intKeyMove = 1;
                    getKeySequencesCount(intKeyCount+1, intKeyMove, intKeyMove+lngKeySequence*KEYPAD_BASE);
                    intKeyMove = 11;
                    getKeySequencesCount(intKeyCount+1, intKeyMove, intKeyMove+lngKeySequence*KEYPAD_BASE);
                    intKeyMove = 16;
                    getKeySequencesCount(intKeyCount+1, intKeyMove, intKeyMove+lngKeySequence*KEYPAD_BASE);
                    break;
                case 9:
                    intKeyMove = 2;
                    getKeySequencesCount(intKeyCount+1, intKeyMove, intKeyMove+lngKeySequence*KEYPAD_BASE);
                    intKeyMove = 12;
                    getKeySequencesCount(intKeyCount+1, intKeyMove, intKeyMove+lngKeySequence*KEYPAD_BASE);
                    intKeyMove = 17;
                    getKeySequencesCount(intKeyCount+1, intKeyMove, intKeyMove+lngKeySequence*KEYPAD_BASE);
                    break;
                case 10:
                    intKeyMove = 1;
                    getKeySequencesCount(intKeyCount+1, intKeyMove, intKeyMove+lngKeySequence*KEYPAD_BASE);
                    intKeyMove = 7;
                    getKeySequencesCount(intKeyCount+1, intKeyMove, intKeyMove+lngKeySequence*KEYPAD_BASE);
                    intKeyMove = 16;
                    getKeySequencesCount(intKeyCount+1, intKeyMove, intKeyMove+lngKeySequence*KEYPAD_BASE);
                    break;
                case 11:
                    intKeyMove = 0;
                    getKeySequencesCount(intKeyCount+1, intKeyMove, intKeyMove+lngKeySequence*KEYPAD_BASE);
                    intKeyMove = 2;
                    getKeySequencesCount(intKeyCount+1, intKeyMove, intKeyMove+lngKeySequence*KEYPAD_BASE);
                    intKeyMove = 8;
                    getKeySequencesCount(intKeyCount+1, intKeyMove, intKeyMove+lngKeySequence*KEYPAD_BASE);
                    intKeyMove = 17;
                    getKeySequencesCount(intKeyCount+1, intKeyMove, intKeyMove+lngKeySequence*KEYPAD_BASE);
                    break;
                case 12:
                    intKeyMove = 1;
                    getKeySequencesCount(intKeyCount+1, intKeyMove, intKeyMove+lngKeySequence*KEYPAD_BASE);
                    intKeyMove = 3;
                    getKeySequencesCount(intKeyCount+1, intKeyMove, intKeyMove+lngKeySequence*KEYPAD_BASE);
                    intKeyMove = 5;
                    getKeySequencesCount(intKeyCount+1, intKeyMove, intKeyMove+lngKeySequence*KEYPAD_BASE);
                    intKeyMove = 9;
                    getKeySequencesCount(intKeyCount+1, intKeyMove, intKeyMove+lngKeySequence*KEYPAD_BASE);
                    break;
                case 13:
                    intKeyMove = 2;
                    getKeySequencesCount(intKeyCount+1, intKeyMove, intKeyMove+lngKeySequence*KEYPAD_BASE);
                    intKeyMove = 4;
                    getKeySequencesCount(intKeyCount+1, intKeyMove, intKeyMove+lngKeySequence*KEYPAD_BASE);
                    intKeyMove = 6;
                    getKeySequencesCount(intKeyCount+1, intKeyMove, intKeyMove+lngKeySequence*KEYPAD_BASE);
                    intKeyMove = 15;
                    getKeySequencesCount(intKeyCount+1, intKeyMove, intKeyMove+lngKeySequence*KEYPAD_BASE);
                    break;
                case 14:
                    intKeyMove = 3;
                    getKeySequencesCount(intKeyCount+1, intKeyMove, intKeyMove+lngKeySequence*KEYPAD_BASE);
                    intKeyMove = 7;
                    getKeySequencesCount(intKeyCount+1, intKeyMove, intKeyMove+lngKeySequence*KEYPAD_BASE);
                    intKeyMove = 16;
                    getKeySequencesCount(intKeyCount+1, intKeyMove, intKeyMove+lngKeySequence*KEYPAD_BASE);
                    break;
                case 15:
                    intKeyMove = 5;
                    getKeySequencesCount(intKeyCount+1, intKeyMove, intKeyMove+lngKeySequence*KEYPAD_BASE);
                    intKeyMove = 7;
                    getKeySequencesCount(intKeyCount+1, intKeyMove, intKeyMove+lngKeySequence*KEYPAD_BASE);
                    intKeyMove = 13;
                    getKeySequencesCount(intKeyCount+1, intKeyMove, intKeyMove+lngKeySequence*KEYPAD_BASE);
                    break;
                case 16:
                    intKeyMove = 6;
                    getKeySequencesCount(intKeyCount+1, intKeyMove, intKeyMove+lngKeySequence*KEYPAD_BASE);
                    intKeyMove = 8;
                    getKeySequencesCount(intKeyCount+1, intKeyMove, intKeyMove+lngKeySequence*KEYPAD_BASE);
                    intKeyMove = 10;
                    getKeySequencesCount(intKeyCount+1, intKeyMove, intKeyMove+lngKeySequence*KEYPAD_BASE);
                    intKeyMove = 14;
                    getKeySequencesCount(intKeyCount+1, intKeyMove, intKeyMove+lngKeySequence*KEYPAD_BASE);
                    break;
                case 17:
                    intKeyMove = 7;
                    getKeySequencesCount(intKeyCount+1, intKeyMove, intKeyMove+lngKeySequence*KEYPAD_BASE);
                    intKeyMove = 9;
                    getKeySequencesCount(intKeyCount+1, intKeyMove, intKeyMove+lngKeySequence*KEYPAD_BASE);
                    intKeyMove = 11;
                    getKeySequencesCount(intKeyCount+1, intKeyMove, intKeyMove+lngKeySequence*KEYPAD_BASE);
                    break;
                default : 
                    Console.Write("Err: {0} {0} {0}\t", intKeyCount,  intLastMove,  lngKeySequence);
                    break;
            };
            return (lngKeySequenceCount); 
 
        }
 
        public static int Main(string[] args){
            intStart = 0;
            int i;
            char chrStart;
 
            // AutoKeySequences to console (Yes='y', else default No)
            Console.Write("AutoKeySequences to console (Yes='y', else default No)?");
            strAutoKeySequences = Console.ReadLine();
            if ((strAutoKeySequences != "") & (strAutoKeySequences != null))
            {
                bolAutoKeySequences = ((char)strAutoKeySequences[0] == 'y');
            }
 
            // PrintOutputKeySequences to console (Yes='y', else default No)
            Console.Write("PrintOutputKeySequences to console (Yes='y', else default No)?");
            strPrintOutputKeySequences = Console.ReadLine();
            if ((strPrintOutputKeySequences != "") & (strPrintOutputKeySequences != null))
            {
                bolPrintOutputKeySequences = ((char)strPrintOutputKeySequences[0] == 'y');
            }
 
            // WriteOutputKeySequences to file (Yes='y', else default No)
            Console.Write("WriteOutputKeySequences to file (Yes='y', else default No)?");
            strWriteOutputKeySequences = Console.ReadLine();
            if ((strWriteOutputKeySequences != "") & (strWriteOutputKeySequences != null))
            {
                bolWriteOutputKeySequences = ((char)strWriteOutputKeySequences[0] == 'y');
                // StreamWriter default to "C:\\SequenceCount_{0}.txt"
                oTextWriter = new StreamWriter(strFilePath);
            }
            intAutoKeySequences = 0;
            lngAutoKeySequences = 0;
            while (true)
            {
                Console.Write("Please, enter the start key: ");
                if (bolAutoKeySequences) 
                {
                    if (intAutoKeySequences>=KEYPAD_BASE) break;
                    chrStart = enmAutoKeySequences[intAutoKeySequences];
                    Console.Write("{0} ", chrStart);
                    intAutoKeySequences += 1;
                } else {
                    strStart = Console.ReadLine();
                    if ((strStart == null) | (strStart == "")) break;
                    chrStart = (char)strStart[0];
                }
                i = (int)chrStart;
                if ((i >= 'A') & (i <= 'O'))
                {
                    intStart = i - 'A';
                }
                else if ((i >= 'a') & (i <= 'o'))
                {
                    intStart = i - 'a';
                }
                else if ((i >= '1') & (i <= '3'))
                {
                    intStart = i - '1' + 15;
                }
                else
                {
                    Console.Write("You entered '{0}'. Please enter keypad chars from 'A' to 'O' or '1' to '3'.", chrStart);
                    break;
                }
                int intKeyCount = 0;
                int intKeyMove = intStart;
                long lngKeySequence=0;
                lngKeySequenceCount = 0;
                if (bolWriteOutputKeySequences)
                {
                    // StreamWriter default to "C:\\SequenceCount_{0}.txt"
                    strFilePath = "C:\\SequenceCount_" + intStart + ".txt";
                    oTextWriter = new StreamWriter(strFilePath);
                }
 
                lngKeySequenceCount = getKeySequencesCount(intKeyCount, intKeyMove, intKeyMove+lngKeySequence*KEYPAD_BASE);
                lngAutoKeySequences += lngKeySequenceCount;
 
                Console.Write("lngKeySequenceCount: {0}\n", lngKeySequenceCount);
                if (bolWriteOutputKeySequences) 
                {
                    oTextWriter.Write("lngKeySequenceCount: {0}\n", lngKeySequenceCount);
                    // Close  StreamWriter
                    oTextWriter.Close();
                }
            }
            Console.Write("\nDone! The Total Num of Your Key Sequences Run ={0}.", lngAutoKeySequences);
            Console.ReadLine(); // Wait for next key input before exiting
            return (0);
        }
 
    }   
}

[edit] C# Code Results

Now, to run the c# application, you will need to specify 1. AutoKeySequences to run all initial keypress in sequence

{ 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', '1', '2', '3' } -> AutoKeySequences to console (Yes='y', else default No)? y

2. PrintOutputKeySequences to print out the keypress sequences to the console

-> PrintOutputKeySequences to console (Yes='y', else default No)? y

3. WriteOutputKeySequences to write out the keypress sequences to the .txt file (default to "C:\\SequenceCount_" + intStart + ".txt" where intStart is the KeySequence equivalent of the key pressed)

-> WriteOutputKeySequences to file (Yes='y', else default No)? y

For example, choosing y, n, n, respectively in the console gives console output of

AutoKeySequences to console (Yes='y', else default No)?y

PrintOutputKeySequences to console (Yes='y', else default No)?

WriteOutputKeySequences to file (Yes='y', else default No)?

Please, enter the start key: A lngKeySequenceCount: 30004

Please, enter the start key: B lngKeySequenceCount: 49154

Please, enter the start key: C lngKeySequenceCount: 73664

Please, enter the start key: D lngKeySequenceCount: 48320

Please, enter the start key: E lngKeySequenceCount: 32520

Please, enter the start key: F lngKeySequenceCount: 64608

Please, enter the start key: G lngKeySequenceCount: 51053

Please, enter the start key: H lngKeySequenceCount: 90089

Please, enter the start key: I lngKeySequenceCount: 33308

Please, enter the start key: J lngKeySequenceCount: 64021

Please, enter the start key: K lngKeySequenceCount: 57937

Please, enter the start key: L lngKeySequenceCount: 63155

Please, enter the start key: M lngKeySequenceCount: 63584

Please, enter the start key: N lngKeySequenceCount: 70622

Please, enter the start key: O lngKeySequenceCount: 37721

Please, enter the start key: 1 lngKeySequenceCount: 64287

Please, enter the start key: 2 lngKeySequenceCount: 56730

Please, enter the start key: 3 lngKeySequenceCount: 62621

Please, enter the start key:

Done! The Total Num of Your Key Sequences Run =1013398.


Another example, choosing y, n, y, respectively in the console gives console output from above as well as writes out each key press sequence for the Knight's Tour in the transformed base-18 representation of the keypad. The first text file output is called "SequenceCount_0.txt" and has 10-Key sequences of the form:

0, 7, 0, 7, 10, 1, 10, 1, 10, 1,

0, 7, 0, 7, 10, 1, 10, 1, 10, 7,

0, 7, 0, 7, 10, 1, 10, 1, 10, 16,

0, 7, 0, 7, 10, 1, 10, 1, 12, 1,

0, 7, 0, 7, 10, 1, 10, 1, 12, 3,

0, 7, 0, 7, 10, 1, 10, 1, 12, 5,

0, 7, 0, 7, 10, 1, 10, 1, 12, 9,

0, 7, 0, 7, 10, 1, 10, 7, 10, 1,

0, 7, 0, 7, 10, 1, 10, 7, 10, 7,

0, 7, 0, 7, 10, 1, 10, 7, 10, 16,

...

[edit] C# Code Modifications

Notice that the code above is written in generic enough manner that it easily accommodates new scenarios that 1. modify the game board and movement environment ...simply re-specify a unique base keypad representation transformation from 18 to whatever the total number of possible positions is and add (or delete) the additional cases and re-specify the allowed moves as necessary in the switch statement...

...
 
            switch (intLastMove) {
                case 0 :
                    intKeyMove = 7;
                    getKeySequencesCount(intKeyCount+1, intKeyMove, intKeyMove+lngKeySequence*KEYPAD_BASE);
                    intKeyMove = 11;
                    getKeySequencesCount(intKeyCount+1, intKeyMove, intKeyMove+lngKeySequence*KEYPAD_BASE);
                    break;
...

and 2. change the local or global conditions on an individual Knight’s Move or sequence of Knight’s Move s ...simply re-specify chkVowelsLimit and / or add (or delete) any additional conditional limitation functions on the sequence of Knight’s Move s

...
        public static bool chkVowelsLimit(long lngKeySequence)
        {
            // chkVowelsLimit 
            long lngDiv = lngKeySequence;
            long lngRem = 0;
            int intVowels = 0;
            if (intStart == 0) // Special case to handle intStart == 0 since later require lngDiv > 0 
                intVowels += 1;
            while (lngDiv > 0)
            {
                lngDiv = System.Math.DivRem(lngDiv, KEYPAD_BASE, out lngRem);
                if ( (lngRem == 0L) | (lngRem == 4L)  |  (lngRem == 8L)  |  (lngRem == 14L) )
                    intVowels += 1;
            };
//            Console.Write(intVowels + ": ");
//            OutputKeySequences(lngKeySequence);
 
...  add (or delete) any additional conditional limitations here...
 
            if (intVowels > 2) 
                return true;
 
...
 
            return false;
        }
...

[edit] See also

[edit] Notes

  1. ^ H. M. Deitel, P. J. Deitel. "Java How To Program Fifth Edition." Prentice Hall, Upper Saddle River, New Jersey, pp. 326-328. 2003.
  2. ^ A. Conrad, T. Hindrichs, H. Morsy, and I. Wegener. "Solution of the Knight's Hamiltonian Path Problem on Chessboards." Discrete Applied Math, volume 50, no.2, pp.125-134. 1994.
  3. ^ Satyadev, Chaudhary. Kavyalankara of Rudrata (Sanskrit Text, with Hindi translation);. Delhi: Parimal Sanskrit Series No. 30. 
  4. ^ Martin Loebbing; Ingo Wegener (1996). "The Number of Knight's Tours Equals 33,439,123,484,294 — Counting with Binary Decision Diagrams". The Electronic Journal of Combinatorics 3 (1): R5. http://www.combinatorics.org/Volume_3/Abstracts/v3i1r5.html.  Remark: The authors later admitted that the announced number is incorrect. According to McKay's report, the correct number is 13,267,364,410,532.
  5. ^ Brendan McKay (1997). "Knight's Tours on an 8x8 Chessboard". Technical Report TR-CS-97-03 (Department of Computer Science, Australian National University). http://www.combinatorics.org/Volume_3/Comments/v3i1r5.01.ps. 
  6. ^ Wegener, I. (January 1, 1987). Branching Programs and Binary Decision Diagrams. Society for Industrial & Applied Mathematics. ISBN 0-898-71458-3. 
  7. ^ Eric W. Weisstein, Knight's Tour at MathWorld.
  8. ^ Watkins, John J. (2004), Across the Board: the Mathematics of Chessboard Problems, Princeton University Press, ISBN 0691115036 
  9. ^ Y. Takefuji, K. C. Lee. "Neural network computing for knight's tour problems." Neurocomputing, 4(5):249-254, 1992.
  10. ^ Pohl, Ira (July 1967). "A method for finding Hamilton paths and Knight's tours". Communications of the ACM 10 (7): 446–449. doi:10.1145/363427.363463. http://portal.acm.org/citation.cfm?id=363463. 
  11. ^ Alwan, Karla; K. Waters (1992), "Finding Re-entrant Knight's Tours on N-by-M Boards" (PDF), ACM Southeast Regional Conference, New York, New York: ACM, pp. 377-382 
  12. ^ Alwan, Karla; K. Waters (1992), "Finding Re-entrant Knight's Tours on N-by-M Boards" (PDF), ACM Southeast Regional Conference, New York, New York: ACM, pp. 377-382 
  13. ^ Törnberg, Gunno (1999). "Warnsdorff's rule". http://web.telia.com/~u85905224/knight/eWarnsd.htm. Retrieved on 2008-9-25. 
  14. ^ Alwan, Karla; K. Waters (1992), "Finding Re-entrant Knight's Tours on N-by-M Boards" (PDF), ACM Southeast Regional Conference, New York, New York: ACM, pp. 377-382 
  15. ^ Cancela, Hector; Ernesto Mordecki (2006-08-31) (PDF). Counting Knight’s Tours through the Randomized Warnsdorff Rule. 

[edit] External links

[edit] Implementations

Retrieved from "http://en.wikipedia.org/wiki/Knight%27s_tour"
Create a book