A Knight's Tour

A Knight's Tour

Language: Java

Synopsis:

The following code is a project that I had to complete for my first Data Structures class. It was a dreaded one among students because it was hard to wrap one's head around.

There were three classes that were given to us by our instructor: Application.java(this is an interface); BackTrack.java; and Position.java. These classes we did nothing with--they came as is. The other classes we either wrote from scratch or modified source code from a project from our text Data Structures and the Java Collections Framework, Third Edition called Maze.

Purpose:

The purpose or goal was to get the Knight on a X by X (e.g. 8 by 8) chess board to every square without visiting a square twice. The BackTrack class that we were given was a class with a recursive method that was executed if the square was already visited and so the knight would "BackTrack" until it could continue to a square that was not visited or if there wasn't any squares remaining to be visited.


from: Wikipedia

Classes:
The BackTrack class was for "backtracking" the Knight when  it arrived at a square that had already been visited.

package project3;

import java.util.*;

public class BackTrack {

    protected Application app;

    /**
     * Initializes this BackTrack object from an application.
     *
     * @param app the application
     */
    public BackTrack(Application app) {
        this.app = app;
    } // constructor

    /**
     * Attempts to reach a goal through a given position.
     *
     * @param pos the given position.
     *
     * @return true if the attempt succeeds; otherwise, false.
     */
    public boolean tryToReachGoal(Position pos) {
        Iterator<Position> itr = app.iterator(pos);

        while (itr.hasNext()) {
            pos = itr.next();
            if (app.isOK(pos)) {
                app.markAsPossible(pos);
                if (app.isGoal(pos) || tryToReachGoal(pos)) {
                    return true;
                }
                app.markAsDeadEnd(pos);
            } // pos may be on a path to a goal
        } // while         
        return false;
    } // method tryToReachGoal
} // class BackTrack

The Application Interface was to help us design our knight class.

package project3;
import java.util.*;

public interface Application 
{
     /**
      * Determines if a given position is legal and not a dead end.
      *
      * @param pos - the given position.
      *
      * @return true if pos is a legal position and not a dead end.
      */     
     boolean isOK (Position pos);


     /**
      * Indicates that a given position is possibly on a path to a goal.
      *
      * @param pos the position that has been marked as possibly being on a 
      *                path to a goal.
      */
     void markAsPossible (Position pos);


     /**
      * Indicates whether a given position is a goal position.
      *
      * @param pos the position that may or may not be a goal position.
      *
      * @return true if pos is a goal position; false otherwise.
      */ 
     boolean isGoal (Position pos);
 

     /**
      * Indicates that a given position is not on any path to a goal position.
      *
      * @param pos the position that has been marked as not being on any path to 
      *                a goal position.
      */
     void markAsDeadEnd (Position pos);
 

     /**
      * Converts this Application object into a String object.
      *
      * @return the String representation of this Application object.
      */
     String toString();


     /**
      * Produces an Iterator object that starts at a given position.
      *
      * @param pos the position the Iterator object starts at.
      *
      * @return an Iterator object that accesses the positions directly
      *               available from pos.             
      */
     Iterator<Position> iterator (Position pos);

} // interface Application

The position class was used to keep track of the position at which the knight was on the any given year.

package project3;
public class Position 
{
        protected int row,
                      column;
            

    /**
         * Initializes this Position object to (0, 0).
         */        
        public Position () 
    {
            row = 0;
            column = 0;
        } // default constructor


    /**
         * Initializes this Position object to (row, column).
         *
         * @param row the row this Position object has been initialized to.
         * @param column the column this Position object has been initialized to.
         */
        public Position (int row, int column) 
    {
            this.row = row;
            this.column = column;
        } // constructor


    /**
         * Determines the row of this Position object.
         *
         * @return the row of this Position object.
         */
        public int getRow () 
    {
            return row;
        } // method getRow


    /**
         * Determines the column of this Position object.
         *
         * @return the column of this Position object.
         */        
        public int getColumn () 
    {
            return column;
        } // method getColumn

} // class Position

The Knight Class was the class that gave "knight" it's attributes--it implements the Application class. The Knight class has an inner class as well the KnightIterator Class.

package project3;

import java.util.Iterator;
import java.util.Scanner;

public class Knight implements Application {


    public static byte count = 1;
    public static final byte DEAD_END = 0;
    protected Position start,
            finish;
    protected byte[][] grid;

    public Knight(byte rows, byte columns, Position start) {

        grid = new byte[rows][columns];
        this.start = start;

    } // constructor

    public Position getStart() {
        return start;
    } // method getStart

    public Position getFinish() {
        return finish;
    } // method getFinish

    public byte[][] getGrid() {
        byte[][] gridCopy = new byte[grid.length][grid[0].length];

        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                gridCopy[i][j] = grid[i][j];
            }
        }
        return gridCopy;
    } // method gridCopy

    @Override
    public boolean isOK(Position pos) {

        return pos.getRow() >= 0 && pos.getRow() < grid.length
                && pos.getColumn() >= 0 && 
                pos.getColumn() < grid[0].length
                && grid[pos.getRow()][pos.getColumn()] == 0;

    }//method isOk

    @Override
    public void markAsPossible(Position pos) {
        if (this.isOK(pos)) {
            grid[pos.getRow()][pos.getColumn()] = count;
            count++;
        }

    }//method markAsPossible

    @Override
    public boolean isGoal(Position pos) {
        if (count == (grid.length * grid[0].length) + 1) {
            return true;
        } else {
            return false;
        }

    }//Method isGoal

    @Override
    public void markAsDeadEnd(Position pos) {

        grid[pos.getRow()][pos.getColumn()] = DEAD_END;
        count--;
    }//method markAsDeadEnd

    @Override
    public String toString() {
        String result = "\n";

        for (int row = 0; row < grid.length; row++) {
            for (int column = 0; column < grid[0].length; column++) {
                result += String.valueOf(grid[row][column]) + ' ';
            }
            result += "\n";
        } // for row = 0
        return result;
    } // method toString

    @Override
    public Iterator<Position> iterator(Position pos) {
        return new KnightIterator(pos);
    }

    protected class KnightIterator implements Iterator<Position> {

        //protected static final int MAX_MOVES = ;
        protected int row,
                column, count2;

        /**
         * Initializes this KnightIterator object to start at 
         * a given position.
         *
         * @param pos the position the Iterator objects starts at.
         */
        public KnightIterator(Position pos) {
            row = pos.getRow();
            column = pos.getColumn();
            count2 = 0;

        } // constructor

        /**
         * Determines if this KnightIterator object can advance to another
         * position.
         *
         * @return true if this KnightIterator object can advance; false
         * otherwise.
         */
        @Override
        public boolean hasNext() {
            return count2 < 8;
        } // method hasNext

        /**
         * Advances this KnightIterator object to the next position.
         *
         * @return the position advanced to.
         */
        @Override
        public Position next() {
            Position nextPosition = new Position();
            switch (count2++) {

                case 0:
                    nextPosition = new Position(row - 2, column + 1);
                    break;
                case 1:
                    nextPosition = new Position(row - 1, column + 2);
                    break;
                case 2:
                    nextPosition = new Position(row + 1, column + 2);
                    break;
                case 3:
                    nextPosition = new Position(row + 2, column + 1);
                    break;
                case 4:
                    nextPosition = new Position(row + 2, column - 1);
                    break;
                case 5:
                    nextPosition = new Position(row + 1, column - 2);
                    break;
                case 6:
                    nextPosition = new Position(row - 1, column - 2);
                    break;
                case 7:
                    nextPosition = new Position(row - 2, column - 1);
                    break;
            } // switch;                
            return nextPosition;
        } // method next

        @Override
        public void remove() {
            // removal is illegal for a KnightIterator object
            throw new UnsupportedOperationException();
        } // method remove
    } // class KnightIterator

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
    }//main Method
}

The KnightUser class actually took the knight around the board. This class I modified from one of the book's source codes file you can find those on the books site.

package project3;

import java.io.*;
import java.util.*;

public class KnightUser {

    final String START_INVALID = "The start position is invalid.";
    final String SUCCESS = "\n\nA solution has been found:";
    final String FAILURE = "\n\nThere is no solution:";
    BackTrack backTrack;

    public static void main(String[] args) {
        new KnightUser().run();
    } // method main

    public void run() {

        //Get size of board and starting position from User

        System.out.print("Enter a number for the board size(Example: "
                + "8 would yield 8 X 8): ");
        Scanner keyboard = new Scanner(System.in);
        byte rows = keyboard.nextByte();
        byte columns = rows;
        System.out.print("Enter the starting row and column: ");
        Position start = new Position(keyboard.nextInt(), keyboard.nextInt());
        boolean isValid = false;

        while (!isValid) {
            try {
                Knight knight = new Knight(rows, columns, start);
                if (!knight.isOK(knight.getStart())) {
                    System.out.println(START_INVALID);
                } else {
                    if (searchBoard(knight)) {
                        System.out.println(SUCCESS);
                    } else {
                        System.out.println(FAILURE);
                    }
                    System.out.println(knight);
                } // else 
                isValid = true;
            } // try
            catch (NumberFormatException e) {
                System.out.println("\n" + e);
            } // catch
            catch (RuntimeException e) {
                System.out.println("\n" + e);
            } // catch
        }// while
    } // method run

    /**
     * Performs the Board search.
     *
     * @param knight – the knight to traverse that board.
     *
     * @return true - if a path from start to finish was found; otherwise, 
     * false
     */
    public boolean searchBoard(Knight knight) {
        Position start = knight.getStart();
        knight.markAsPossible(start);
        backTrack = new BackTrack(knight);

        if (knight.isGoal(start) || backTrack.tryToReachGoal(start)) {
            return true;
        }
        knight.markAsDeadEnd(start);
        return false;
    } // method searchMaze
} // class MazeUser

There were two other classes that I wrote that were test classes for the Knight class and the KnightUser class that used junit. My Grade on this one was 98%.