Knight Path

Knight Path 1.0, Commentary

This page contains the puzzle statement, annotated with where to find the code that implements the various requirements.

Given a standard 8x8 chessboard, design a C++ application that accepts two squares

See the position class, for just about everything to do with board squares.

identified by algebraic chess notation.

See operator<< (which calls the position::write method) to write chess positions in algebraic notation to C++ streams, and also operator>> (which calls the position::read class method) to read chess positions in algebraic notation from C++ streams. See the main function for examples of use.

The first square is the starting position, and the second square is the ending position.

See the static process function in the knight-path/main.cc file for where this is done.

Find the shortest sequence of valid moves to take a Knight piece from the starting position to the ending position.

See the solver::solve virtual method does this. See the static process function in the knight-path/main.cc file for where this is called.

Each move must be a legal move by a Knight.

See the position::knight_moves method for where the moves are calculated.

For any two squares there may be more than one valid solution.

Input

Must be two squares identified in algebraic chess notation representing the starting and ending positions of the Knight.

See operator>> (which calls the position::read class method) to read chess positions in algebraic notation from C++ streams.

The two squares are separated by a space.

The the position::read class method discards any leading white space, much like the usual >> operators in the standard library.

Output

Must be a list of squares through which the Knight passes,

This is embodied in the solver::list_t type, as returned by the solver::solve virtual method.

in algebraic chess notation.

See operator<< (which calls the position::write method) to write chess positions in algebraic notation to C++ streams. See the static process function in the knight-path/main.cc file for where this is called.

This must include the ending position, but exclude the starting position.

This is how the solver::solve virtual method is defined.

Example

Example Input: A8 B7

bin/knight-path A8 B7

Example Output: C7 B5 D6 B7

path: B6 A4 C5 B7

Note: For any two squares there may be more than one valid solution, your program need not print this exact solution if it can find another that is equally short.

The knight-path program actually implimentes three different algorithms, and each gives a different answer.

Assignment Brief:

In C++, write a program to find the shortest sequence of moves for a Knight between the starting and ending positions.

The solver::solve virtual method is where this happens. Follow the class hierarchy links at the top of that page to see how the various derived classes solve the problem.

Your program can accept the input and produce the output in whatever form you think is most effective.

There is an additional knight-path “-b” option, that will also print a chess board with the positions marked.

$ knight-path -b A8 B7
path: B6 A4 C5 B7
  +---+---+---+---+---+---+---+---+
8 | 0 |   |   |   |   |   |   |   |
  +---+---+---+---+---+---+---+---+
7 |   | 4 |   |   |   |   |   |   |
  +---+---+---+---+---+---+---+---+
6 |   | 1 |   |   |   |   |   |   |
  +---+---+---+---+---+---+---+---+
5 |   |   | 3 |   |   |   |   |   |
  +---+---+---+---+---+---+---+---+
4 | 2 |   |   |   |   |   |   |   |
  +---+---+---+---+---+---+---+---+
3 |   |   |   |   |   |   |   |   |
  +---+---+---+---+---+---+---+---+
2 |   |   |   |   |   |   |   |   |
  +---+---+---+---+---+---+---+---+
1 |   |   |   |   |   |   |   |   |
  +---+---+---+---+---+---+---+---+
    a   b   c   d   e   f   g   h
$

Include all code to run the program,

See the tarball on the web site.

and whatever build instructions are necessary.

See the README on the web site.