4
\$\begingroup\$

I have an assignment to write a knights tour backtracking program in Java where the professor says to:

Eliminate backtracking time by:

Find the knights with the least possible moves
Sort those moves from knight with least moves to greatest moves
Backtrack if that path fails

I have done that with and attempted some other optimizations but my algorithm is still pretty slow for most squares. I went online and found my algorithm was pretty similar to others. I even took the algorithm from here and found it ran slow on the same spaces as mine (ahem pretty much never finishes) I was ready to call it until I took my processor's version from his website and it ran instantaneously on the squares every other version I had seen had run slowly on, he even showed me his code in his office last week and I recall it looking very similar. I have also seen questions on this site asking about their slow backtracking programs for knights tour. How is this possible!? Virtually every other source I have seen can confirm that this algorithm is slow except for my professor. My code:

    /*!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!//
//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!//
//Grid.java THIS IS WHERE THE MEAT AND POATATOS IS!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!//
//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!//
//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!//
//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!*/
public class Grid
{
    //Constants to keep things consistant and avoid errors.//
    public final static char OBSTICLE_TILE_SYMBOLE = '0';
    public final static char OPEN_TILE_SYMBOLE = '1';
    private Tile[][] tileGrid;
    /*************************************************
    ** 'Makes for a nice api to do things this way, **
    ** no construtor discourages the user from *******
    ** making a standalone "Grid" object or **********
    ** or setting it up manually (though they have ***
    ** the choice to), and encourages them to ********
    ** do things the easy magical way. ***************
    *************************************************/
    public static Grid CreateGridFromFile( String fileToLoadMapFrom )
    {
        try
        {
            Grid newGrid = new Grid();
            BufferedReader buffer = new BufferedReader( new FileReader( fileToLoadMapFrom ) );
            String line = "";
            boolean tileGridSetUp = false;
            int y = 0;
            //Standard reading procedure.//
            while( ( line = buffer.readLine() ) != null )
            {
                line = line.trim().replaceAll( "\\s+", "" ).replaceAll( "\n", "" ).replaceAll( "\r", "" );
                final int LINE_LENGTH = line.length();
                if( tileGridSetUp == false ) {
                    newGrid.SetTileGrid( new Tile[ LINE_LENGTH ][ LINE_LENGTH ] );
                    tileGridSetUp = true;
                }
                //Construct nodes in graph.//
                for( int x = 0; x < LINE_LENGTH; ++x ) {
                    newGrid.SubstituteTile( x, y, new Tile( new XY( x, y ), 
                            Tile.DEFAULT_ACCOUNTED_FOR_STATE_FLAG, line.charAt( x ) ) );
                }
                ++y;
            }
            return newGrid;
        }
        catch( Exception exception )
        {
            System.out.println( "Exception::Grid::CreateGridFromFile()::General exception, " + 
                    "\n\tprinting information and stack trace. @Exception::!Cause: " + exception.getCause() + 
                    ",!Message" + exception.getMessage() + "$ Stack Trace: \n" );
            exception.printStackTrace();
            return ( null );
        }
    }
    public void GridToSystemOut()
    {
        for( int i = 0; i < tileGrid.length; ++i )
        {
            for( int j = 0; j < tileGrid[ i ].length; ++j )
                System.out.print( tileGrid[ i ][ j ].GetTileSymbole() );
            System.out.println();
        }
    }
    public void ConditionallyAddToArray( ArrayList< Tile > toAddTo, ADJECENT_COORDINATE_TYPE coordinateFilter, Tile toAdd )
    {
        if( toAdd != null )
        {
            if( ( ( coordinateFilter == ADJECENT_COORDINATE_TYPE.OCCUPIED && toAdd.GetTileSymbole() == Grid.OBSTICLE_TILE_SYMBOLE ) == true ) || 
                    ( ( coordinateFilter == ADJECENT_COORDINATE_TYPE.OPEN && toAdd.GetTileSymbole() == Grid.OPEN_TILE_SYMBOLE ) == true ) || 
                    coordinateFilter == ADJECENT_COORDINATE_TYPE.ALL )
                toAddTo.add( toAdd );
        }
    }
    public Tile ReturnIfInRange( int x, int y )
    {
        if( y > 0 && y < tileGrid.length ) {
            if( x > 0  && x < tileGrid[ 0 ].length )
                return tileGrid[ y ][ x ];
        }
        return ( null );
    }
    public ArrayList< Tile > AdjecentCoordiantes( Grid toReadFrom, Tile adjecentTo, ADJECENT_COORDINATE_TYPE coordinateFilter, boolean excludeAdjecentTo )
    {
        final int AMOUNT_OF_LINES = toReadFrom.GetTileGrid().length;
        if( adjecentTo.AttainY() < AMOUNT_OF_LINES )
        {
            ArrayList< Tile > adjecentCoordinates = new ArrayList< Tile >();
            final int X = adjecentTo.AttainX();
            final int Y = adjecentTo.AttainY();
            if( excludeAdjecentTo == false )
                ConditionallyAddToArray( adjecentCoordinates, coordinateFilter, adjecentTo );
            //Yay for hardcoding!//
            ConditionallyAddToArray( adjecentCoordinates, coordinateFilter, ReturnIfInRange( X + 1, Y - 2 ) );
            ConditionallyAddToArray( adjecentCoordinates, coordinateFilter, ReturnIfInRange( X + 2, Y - 1 ) );
            ConditionallyAddToArray( adjecentCoordinates, coordinateFilter, ReturnIfInRange( X + 2, Y + 1 ) );
            ConditionallyAddToArray( adjecentCoordinates, coordinateFilter, ReturnIfInRange( X + 1, Y + 2 ) );
            ConditionallyAddToArray( adjecentCoordinates, coordinateFilter, ReturnIfInRange( X - 1, Y + 2 ) );
            ConditionallyAddToArray( adjecentCoordinates, coordinateFilter, ReturnIfInRange( X - 2, Y + 1 ) );
            ConditionallyAddToArray( adjecentCoordinates, coordinateFilter, ReturnIfInRange( X - 2, Y - 1 ) );
            ConditionallyAddToArray( adjecentCoordinates, coordinateFilter, ReturnIfInRange( X - 1, Y - 2 ) );
            return adjecentCoordinates;
        }
        return ( null );
    }
    //Uses of the method above because it has so many options.//
    public ArrayList< Tile > AllAdjecentCoordiantes( Grid toReadFrom, Tile adjecentTo, boolean excludeAdjecentTo ) {
        return AdjecentCoordiantes( toReadFrom, adjecentTo, ADJECENT_COORDINATE_TYPE.ALL, excludeAdjecentTo );
    }
    public ArrayList< Tile > OpenAdjecentCoordiantes( Grid toReadFrom, Tile adjecentTo, boolean excludeAdjecentTo ) {
        return AdjecentCoordiantes( toReadFrom, adjecentTo, ADJECENT_COORDINATE_TYPE.OPEN, excludeAdjecentTo );
    }
    public ArrayList< Tile > OccupiedAdjecentCoordiantes( Grid toReadFrom, Tile adjecentTo, boolean excludeAdjecentTo ) {
        return AdjecentCoordiantes( toReadFrom, adjecentTo, ADJECENT_COORDINATE_TYPE.OCCUPIED, excludeAdjecentTo );
    }
    //See if a node in the list is 'accounted for.'//
    public ArrayList< Tile > AttainAccountedFor( ArrayList< Tile > listOfTiles, boolean accountedForState )
    {
        ArrayList< Tile > accountedFor = new ArrayList< Tile >();
        for( Tile currentTile : listOfTiles ) {
            if( currentTile.GetAccountedFor() == accountedForState )
                accountedFor.add( currentTile );
        }
        return accountedFor;
    }
    //See if an object is in the list.//
    public static < ELEMENT_TYPE_T > boolean IsInThisList( ArrayList< ELEMENT_TYPE_T > listToTest, ELEMENT_TYPE_T instanceToTest )
    {
        for( ELEMENT_TYPE_T currentNode : listToTest ) {
            if( currentNode == instanceToTest )
                return ( false );
        }
        return ( true );
    }
    public boolean HopToTile( Tile firstNode ) {
        return HopToTile( this, 0, firstNode );//, goUntil, ( goUntil + 1 ) ) == false )
    }
    public boolean HopToTile( Grid toReadFrom, int order, Tile currentNode )//, int last, int goUntil )
    {
        if( order >= ( ( tileGrid.length * tileGrid[ 0 ].length ) - 1 ) )
            return ( true );
        currentNode.SetOrder( order );
        currentNode.SetAccountedFor( true );
        ArrayList< Tile > hopTiles = AttainAccountedFor( OpenAdjecentCoordiantes( toReadFrom, currentNode, true ), false );
ArrayList< Tile > tilesToTry = new ArrayList< Tile >();
        ArrayList< Integer > tilesToTryLengths = new ArrayList< Integer >();
        for( Tile currentHopTile : hopTiles )
        { 
            ArrayList< Tile > currentNodeTiles = AttainAccountedFor( OpenAdjecentCoordiantes( toReadFrom, currentHopTile, true ), false );
            final int CURRENT_LENGTH = currentNodeTiles.size();
            if( CURRENT_LENGTH > 0 )
            {
                final int AMOUNT_OF_TILES_TO_TRY = tilesToTry.size();
                boolean foundAPlace = false;
                for( int i = 0; i < AMOUNT_OF_TILES_TO_TRY; ++i )
                {
                    if( CURRENT_LENGTH < tilesToTryLengths.get( i ).intValue() )
                    {
                        if( i > 0 )
                        {
                            tilesToTry.add( ( i - 1 ), currentHopTile );
                            tilesToTryLengths.add( ( i - 1 ), Integer.valueOf( CURRENT_LENGTH ) );
                            foundAPlace = true;
                            break;
                        }
                    }
                }
                if( foundAPlace == false ) {
                    tilesToTryLengths.add( Integer.valueOf( CURRENT_LENGTH ) );
                    tilesToTry.add( currentHopTile );
                }
            }
        }
        for( Tile currentHopTile : tilesToTry )//hopTiles )
        {
            if( HopToTile( toReadFrom, ( order + 1 ), currentHopTile ) == true )
                return ( true );
        }
        currentNode.SetOrder( Tile.DEFAULT_ORDER );
        currentNode.SetAccountedFor( Tile.DEFAULT_ACCOUNTED_FOR_STATE_FLAG );
        return ( false );
    }
    /**********************************************************************
    ** * : "Substitute" indicates a convience encuasulated method *********
    **      similar to set (or affectivly set) of something conceptual ****
    **      not reflected in the code or possibly actual ******************
    **      reflected in the code. ****************************************
    ** * : "Modify" indicates a convience encuasulated method similar to **
    **      set (or affectivly set) of something but it is not just *******
    **      a set, it may involve other things, possibly a ****************
    **      "safe set," or a systematic way of setting something. *********
    ** * : "Attain" is similar to both "Modify" and "Substitute," *********
    **      for get, Attain can mean a convience encuasulated method ******
    **      similar to get (or affectivly get) of something conceptal *****
    **      not reflected in the code, or something possibly **************
    **      actual reflected in the code, or it can mean ******************
    **      something similar to get (or affectily get) but may not *******
    **      be a straight get, it could be something like a "safe" ********
    **      or systematic get, the thing being "Attained" can also ********
    **      be generated within the method, non - existant, and or ********
    **      static data, for example a constant string containing *********
    **      the name of a class put in as meta data. **********************
    **********************************************************************/
    public void SetTileGrid( Tile[][] tileGrid_ ) {
        tileGrid = tileGrid_;
    }
    public void SubstituteTile( int x, int y, Tile toSubstitute )
    {
        if( y < tileGrid.length && y >= 0 ) {
            if( x < tileGrid[ 0 ].length )
                tileGrid[ y ][ x ] = toSubstitute;
        }
    }
    public void SetTileRow( int y, Tile[] rowToSubstitute ) {
        if( y < tileGrid.length )
            tileGrid[ y ] = rowToSubstitute;
    }
    public Tile AttainTile( int x, int y )
    {
        if( y < tileGrid.length && y >= 0 ) {
            if( x < tileGrid[ 0 ].length )
                return tileGrid[ y ][ x ];
        }
        return ( null );
    }
    public Tile[] AttainTileRow( int y )
    {
        if( y < tileGrid.length )
            return tileGrid[ y ];
        return ( null );
    }
    public Tile[][] GetTileGrid() {
        return tileGrid;
    }
}

//Tile.java
public class Tile
{
    private XY coordinate;
    private boolean accountedFor;
    private int order;
    private char tileSymbole;
    //Constants to keep things orginised and grounded.//
    public static final boolean DEFAULT_ACCOUNTED_FOR_STATE_FLAG = false;
    public static final char DEFAULT_TILE_SYMBOLE = Grid.OBSTICLE_TILE_SYMBOLE;
    public static final int DEFAULT_ORDER = ( -1 );
    public static final XY DEFAULT_COORDINATES = new XY( ( -1 ), ( -1 ) );
    public Tile() {
        this( DEFAULT_COORDINATES );
    }
    public Tile( XY coordinate_ ) {
        this( coordinate_, DEFAULT_ACCOUNTED_FOR_STATE_FLAG );
    }
    public Tile( XY coordinate_, boolean accountedFor_ ) {
        this( coordinate_, accountedFor_, DEFAULT_TILE_SYMBOLE );
    }
    public Tile( XY coordinate_, boolean accountedFor_, char tileSymbole_ ) {
        this( coordinate_, accountedFor_, tileSymbole_, DEFAULT_ORDER );
    }
    public Tile( XY coordinate_, boolean accountedFor_, char tileSymbole_, int order_ )
    {
        coordinate = coordinate_;
        accountedFor = accountedFor_;
        tileSymbole = tileSymbole_;
        order = order_;
    }
    public void SubstituteX( int x ) {
        coordinate.SetX( x );
    }
    public void SubstituteY( int y ) {
        coordinate.SetY( y );
    }
    public void SetCoordinate( XY coordinate_ ) {
        coordinate = coordinate_;
    }
    public void SetAccountedFor( boolean accountedFor_ ) {
        accountedFor = accountedFor_;
    }
    public void SetTileSymbole( char tileSymbole_ ) {
        tileSymbole = tileSymbole_;
    }
    public void SetOrder( int order_ ) {
        order = order_;
    }
    public int AttainX() {
        return coordinate.GetX();
    }
    public int AttainY() {
        return coordinate.GetY();
    }
    public XY GetCoordinate() {
        return coordinate;
    }
    public boolean GetAccountedFor() {
        return accountedFor;
    }
    public char GetTileSymbole() {
        return tileSymbole;
    }
    public int GetOrder() {
        return order;
    }
}
\$\endgroup\$
4
\$\begingroup\$

Broken sort

When inserting elements into your list in sorted order, you don't insert the element at the correct index:

       for( int i = 0; i < AMOUNT_OF_TILES_TO_TRY; ++i )
        {
            if( CURRENT_LENGTH < tilesToTryLengths.get( i ).intValue() )
            {
                if( i > 0 )
                {
                    tilesToTry.add( ( i - 1 ), currentHopTile );
                    tilesToTryLengths.add( ( i - 1 ), Integer.valueOf( CURRENT_LENGTH ) );
                    foundAPlace = true;
                    break;
                }
            }
        }

Suppose you had 10 elements already sorted and your new element were larger than index 4 but smaller than index 5. Your new element should be inserted at index 5 and shift all the other elements down. In your code, however, you are inserting at index 4, which is incorrect. You also have a check for i > 0 which is wrong. Your code should be changed to this:

           for (int i = 0; i < AMOUNT_OF_TILES_TO_TRY; ++i)
           {
                if (CURRENT_LENGTH < tilesToTryLengths.get(i).intValue())
                {
                    tilesToTry.add(i, currentHopTile);
                    tilesToTryLengths.add(i, Integer.valueOf(CURRENT_LENGTH));
                    foundAPlace = true;
                    break;
                }
           }
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.