Backtracking

Sometimes the only way we have to find a solution to a problem is by exploring all the possibilities and picking the one (or ones) that leads to a solution! Backtracking is something like "brute force" but only evaluating valid combinations as we generate them. For example, we could use backtracking to generate all the valid combinations for a tic-tac-toe game and as we are generating them we evaluate them to pick the combination where we win! Another, well known, case is for solving a maze where we evaluate a path step by step, if we find another step we continue, if we find the exit then we have found a solution but if we find a wall or a position where we have been before then it's time to go back and evaluate the others combinations. We will see the maze problem im more detail soon!

The Backtracking Algorithm

So, an informal seudocode where we stay with the first solution found can be:

backtracking(partialSolution){

	if(partialSolution is a solution){
		finalSolution= partialSolution;
		return the solution was found;
	}
	else if(partialSolution is a case we want to avoid){
		return the solution was not found;
	}

	For each step {
		newPartialSolution= partialSolution + step;
		if(backtracking(newPartialSolution) has found a solution){
			return the solution was found;
		}
	}

	return the solution was not found;

}
If this does not look clear or is very abstract to you, don't worry it will make more sense with actual examples!

It's important to realize that using backtracking is not always possible, imagine generating all the combinations for a chess game. Also if we are taking only the first solution found, it could lead us not to the best solution for a given problem. To avoid these problems "pure" backtracking can be combined with some heuristic rules to avoid exploring combinations that don't look promising.

Solving a Maze

maze with a mouse and cheese
Our goal, of course, is to reach the cheese. We don't have an overall vision of all the maze, we can only see what we have just in front of us! So applying backtracking we start in one path, looking ahead until we find the exit and we finish or we hit a wall (or a place we've been before) so we go back to the immediately previous point were we have another option and we take it. (If we can't go back any more, it means there is no way out!)
Using recursion for this, makes the thing simpler. Here our Java source code:

package games;


/**
 *
 * Solves a maze. Just for demo!
 * 
 * @author kriche
 *
 */
public class MazeSolver {
    
    // These 3 can have the same value, if wanted:
    private static final char START = 'S';
    private static final char CURRENT_POSITION = 'C';
    private static final char CURRENT_PATH = '#';
    private static final char PATH = ' ';
    private static final char WALL = 'X';
    private static final char BREADCRUM = '*';
    private static final char FINISH = 'F';

    private static final int INI_X= 26;
    private static final int INI_Y= 41;
    
    private static long DELAY= 150;

    public static void main(String args[]) {
        
        char[][] theMaze= generateMaze();

        boolean solutionFound= findPath(theMaze, INI_X, INI_Y);

        // After we are done, just remove the breadcrums and mark the starting point with a
        // different symbol to show where all began.
        removeBreadCrums(theMaze);
        theMaze[INI_X][INI_Y]= START;
        printMaze(theMaze);

        if (!solutionFound) {
            System.out.println("Oops, this maze has no solution.");
        }

    }

    /**
     * Prints the first solution it finds into the maze.
     * @param maze
     * @param x
     * @param y
     * @return true only if a solution was found.
     */
    private static boolean findPath(char[][] maze, int x, int y) {

        switch(maze[x][y]){

            // We have found a way out!
            case FINISH:
                return true;

            // Oops, there is a wall!
            case WALL:
            // Oops, we have been here before!
            case BREADCRUM:
            case CURRENT_PATH:
                return false; //So this is not a way out!

            default:

                // We are inside the maze yet (PATH)!

                //Show where we are:
                maze[x][y]= CURRENT_POSITION;
                printMaze(maze);

                // And we continue in each direction possible (one at the time) to see what we find.
                // Note that as soon as we find one solution we don't explore the rest!
                // Java || operator is lazy
                maze[x][y]= CURRENT_PATH;
                boolean found= findPath(maze, x + 1, y) ||
                                findPath(maze, x - 1, y) ||
                                findPath(maze, x, y + 1) ||
                                findPath(maze, x, y - 1);
                
                if (found){
                    // we are in a solution path!
                    return true;
                }

                //Show where we are when backtracking as well:
                maze[x][y]= CURRENT_POSITION;
                printMaze(maze);

                //Restore the breadcrum (no longer current path):
                maze[x][y]= BREADCRUM;
                   
                // There wasn't a solution from this possition so return false.                
                return false;
        }

    }

    /**
     *
     * @return a maze form only by WALL, PATH, or FINISH symbols! There perimeter cannot contain PATH symbols!
     */
    private static char[][] generateMaze(){

        // TODO the maze could be randomly generated using backtracking as well!
        return new char[][] {
        "XXXXXXXXXFXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX".toCharArray(),
        "XXXXXXXXX XXXXXX         XXXXXXXXXXXX  XXXXXXXXXXXXXXXXXX                 XXXXXX      XXX".toCharArray(),
        "XXXXX            XXXXXXX XXXXXXXXXXXXX       XXXXX XXXXXX XXXXXXXXXXXXXXX        XXXX XXX".toCharArray(),
        "XXXXXXXXXXXXXXXX XXXXXXX         XXXXXXXXXXX XXXXX      X XXXXXXXXXXXXXXXXXXXXXX XXXX XXX".toCharArray(),
        "XXXXX        XXX XXXXXXXXXXXXXX XXXX       X       XXXXXX XXXXX      XXXX     XX XXXX XXX".toCharArray(),
        "XXXXX XXXXXX XXX        XXXXXXX XXXX XXXXX XXXXXXX XXXXXX XXXXX XXXX XXXX XXX XX XXXX XXX".toCharArray(),
        "XXXXX XXX XX XXXXXXXXXX        XXXXX XXXXX       X XXXXXX XXXXX XXXX XXXX XXX XX XXXX XXX".toCharArray(),
        "XXXXX XXX XX XXXXX XXXXXXXXXXX       XXXXXXX XXX X    XXX XXXXX XXXX      XXX XX XXXX XXX".toCharArray(),
        "XXXXX XXX    XXXXX  XXXXXXXXXXXXXXXXXXXXXXXX XXX XXXX XXX XXXXX XXXXXXXXXXXXX    XXXX XXX".toCharArray(),
        "XXXXX XXXX XXXXXXXXX XXX   XXXXXXXXXXXXXXXXX XXX XXXX     XXXXX XXXXXXXXXXXXXXXX XXXX XXX".toCharArray(),
        "XXXXX      XXXXXXXXX XXXXX   XXXXXXXXXXX XXX XXX XXXXXX XXXXXXX XXXXXXXXXXXXXXXX        X".toCharArray(),
        "XXXXXXX XX XXXXX        XXXX XXXXXXXXXXX XXX XXX XXXXXX XXXXXXX                  XXXXXX X".toCharArray(),
        "XXXXXXX XX XXXXX XXXXXX XXXX XXXXXXXXXXX X                   XX  X XXXXXXXXXXXXX XX   X X".toCharArray(),
        "XXX     XX XXXXX XXXXXX XXXX   XX XXXXXX XXXXXXX XXXXXXXXXXX  XXXX XXXXXXXXXXXXX XX X X X".toCharArray(),
        "XXXX XXXXX XXXXX XXXXXX XXXXXX    XXXXXX XXXXXXXXXXXXXXXX XXX   XX XXXXX  XXXXXX XX X X X".toCharArray(),
        "XXXX XXXXX       XXXXXX XXXXXXXXX XXXXXX XXXXXXXXXXX      X XXX    XXXXX  XXXXXX XX     X".toCharArray(),
        "XXXX XXXXXXXXXXXXXXXXXX XXXXXXXXX             XXXXXX XXX XX XXXXXX XXXXX XXXXXXX XXXXXX X".toCharArray(),
        "XXXX XXXXXXXXXXXXXXXXXX XXXXXXXXX XXXXXXXXXXXXXXXXXX XXX XX XX XXX XXXXX XXXXXX  XXXXXXXX".toCharArray(),
        "XXXX X        XXXXXXXXX XXXXXXXXX XXXXXXXXXXXXXXXXXX XXXXXX XX XXX XXXXX XXX    XXXXXXXXX".toCharArray(),
        "XXXX X XXXXXX XXXXXXXXX XXXXXXXXX XXXXXXXXXXXXXXXX          XX XXX XXXXX XXXX XXXXXXXXXXX".toCharArray(),
        "XXXX X XXXXXX XXXXXXXXX                   XXXXXXXX XXXXXXXX XXXXXX XXXXX XXXX XXXX    XXX".toCharArray(),
        "XXXX X XXXXXX XXXXXXXXXXXXXXXX XXXXXXXXXX XXXXX    XXXXXXXX XXXXXX XXXXXXXXXX XXXX XX XXX".toCharArray(),
        "XXXX X XXXXXX XXXX             XXXX XX XX XXXXX XXXXXXXXXXX XXXXXX XXXXXXXXXX XXXX XX XXX".toCharArray(),
        "XXXX X XXXXXXXXXXX XXXXXXXXXXX XXXX XX XX XXXXX XXXXXXXXXXXXXXXXXX XXXXXXXXXX      XX XXX".toCharArray(),
        "XXXX X             XXXXXXXXXXX XXXX XX XX                          XXXXXXXXXXXXXXXXXX XXX".toCharArray(),
        "XXXX XXXXXXXXXXXXX             XXXX XX XX XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX XXX".toCharArray(),
        "XXXX     XXXXXXXXXXXXXXXXXXXXXXXXXX XX XX XXXXXXXXXXXXXXXXXXXX XXXXXXXXXX             XXX".toCharArray(),
        "XX   XXX      XXXXXXXXXXXXXXXX            XXXX    XXXXXXXXXXXX            XXXXXXXXXXXXXXX".toCharArray(),
        "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX".toCharArray(),};

    }


    /**
     * prints the maze and sleeps for a while only for visual effects.
     * @param theMaze
     */
    private static void printMaze(char[][] theMaze) {

        for (char[] row : theMaze) {
            for (char col : row) {
                System.out.print(col);
            }
            System.out.println();
        }
        System.out.println("\n\n");        

        try {
            Thread.sleep(DELAY);
        } catch (InterruptedException ex) {
            throw new Error(ex);
        }

    }

    private static void removeBreadCrums(char[][] theMaze) {

        for(int r= 0; r < theMaze.length; r++){
            for(int c= 0; c < theMaze[r].length; c++){
                if(theMaze[r][c]==BREADCRUM){
                    theMaze[r][c]= PATH;
                }
            }
        }

    }


}

It's amazing how compact the method findPath is! Now, go back to the seudocode above and try to match it against this method!

If you run this code, you will end up with the maze solved as follows:

XXXXXXXXXFXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXX#XXXXXX         XXXXXXXXXXXX  XXXXXXXXXXXXXXXXXX#################XXXXXX      XXX
XXXXX    ########XXXXXXX XXXXXXXXXXXXX       XXXXX XXXXXX#XXXXXXXXXXXXXXX########XXXX XXX
XXXXXXXXXXXXXXXX#XXXXXXX         XXXXXXXXXXX XXXXX      X#XXXXXXXXXXXXXXXXXXXXXX#XXXX XXX
XXXXX        XXX#XXXXXXXXXXXXXX XXXX#######X       XXXXXX#XXXXX      XXXX     XX#XXXX XXX
XXXXX XXXXXX XXX########XXXXXXX XXXX#XXXXX#XXXXXXX XXXXXX#XXXXX XXXX XXXX XXX XX#XXXX XXX
XXXXX XXX XX XXXXXXXXXX########XXXXX#XXXXX#######X XXXXXX#XXXXX XXXX XXXX XXX XX#XXXX XXX
XXXXX XXX XX XXXXX XXXXXXXXXXX#######XXXXXXX XXX#X    XXX#XXXXX XXXX      XXX XX#XXXX XXX
XXXXX XXX    XXXXX  XXXXXXXXXXXXXXXXXXXXXXXX XXX#XXXX XXX#XXXXX XXXXXXXXXXXXX   #XXXX XXX
XXXXX XXXX XXXXXXXXX XXX   XXXXXXXXXXXXXXXXX XXX#XXXX  ###XXXXX XXXXXXXXXXXXXXXX#XXXX XXX
XXXXX      XXXXXXXXX XXXXX   XXXXXXXXXXX XXX XXX#XXXXXX#XXXXXXX XXXXXXXXXXXXXXXX#       X
XXXXXXX XX XXXXX        XXXX XXXXXXXXXXX XXX XXX#XXXXXX#XXXXXXX   ###############XXXXXX X
XXXXXXX XX XXXXX XXXXXX XXXX XXXXXXXXXXX X      ########     XX  X#XXXXXXXXXXXXX XX   X X
XXX     XX XXXXX XXXXXX XXXX   XX XXXXXX XXXXXXX XXXXXXXXXXX  XXXX#XXXXXXXXXXXXX XX X X X
XXXX XXXXX XXXXX XXXXXX XXXXXX    XXXXXX XXXXXXXXXXXXXXXX XXX   XX#XXXXX  XXXXXX XX X X X
XXXX XXXXX       XXXXXX XXXXXXXXX XXXXXX XXXXXXXXXXX      X XXX   #XXXXX  XXXXXX XX     X
XXXX XXXXXXXXXXXXXXXXXX XXXXXXXXX             XXXXXX XXX XX XXXXXX#XXXXX XXXXXXX XXXXXX X
XXXX XXXXXXXXXXXXXXXXXX XXXXXXXXX XXXXXXXXXXXXXXXXXX XXX XX XX XXX#XXXXX XXXXXX  XXXXXXXX
XXXX X        XXXXXXXXX XXXXXXXXX XXXXXXXXXXXXXXXXXX XXXXXX XX XXX#XXXXX XXX    XXXXXXXXX
XXXX X XXXXXX XXXXXXXXX XXXXXXXXX XXXXXXXXXXXXXXXX          XX XXX#XXXXX XXXX XXXXXXXXXXX
XXXX X XXXXXX XXXXXXXXX                   XXXXXXXX XXXXXXXX XXXXXX#XXXXX XXXX XXXX    XXX
XXXX X XXXXXX XXXXXXXXXXXXXXXX XXXXXXXXXX XXXXX    XXXXXXXX XXXXXX#XXXXXXXXXX XXXX XX XXX
XXXX X XXXXXX XXXX             XXXX XX XX XXXXX XXXXXXXXXXX XXXXXX#XXXXXXXXXX XXXX XX XXX
XXXX X XXXXXXXXXXX XXXXXXXXXXX XXXX XX XX XXXXX XXXXXXXXXXXXXXXXXX#XXXXXXXXXX      XX XXX
XXXX X             XXXXXXXXXXX XXXX XX XX##########################XXXXXXXXXXXXXXXXXX XXX
XXXX XXXXXXXXXXXXX             XXXX XX XX#XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX XXX
XXXX     XXXXXXXXXXXXXXXXXXXXXXXXXX XX XXSXXXXXXXXXXXXXXXXXXXX XXXXXXXXXX             XXX
XX   XXX      XXXXXXXXXXXXXXXX            XXXX    XXXXXXXXXXXX            XXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX


If you think this example was amazing, wait to see what's coming!

The Nim Game

This game consists of several rows, each of it with a given number of balls. The two players take turns to take away any number of balls for one row each time. The player that takes the last ball wins. nim game
Similarly to the maze problem, here all we have to do is to compute all the possible movements and pick one where we win. But how do we know when a movement leads us to winning the game? A movement will be good (for us) if it takes us to a good possition. Okay... And what's a good possition? A good possition is such that makes us win the game or makes our opponent not able to find a good move!
Let's try to write this down as some seudocode...

goodMove(for us) leads to goodPossition(for us);
goodPossition(for us) does not lead to a goodMove(for opponent);
As you can see there is recursion going on here!

findGoodMove(){

	// a good move can be found if there is a good possition for us

	for(all possible movements){

		make move;

		if(isGoodPosittion()){
			return move;
		}

		undo move;
	}

	
	// There was no good movement
	return null;

}


isGoodPosittion(){
    
	if(no movement can be made, this is, there are no balls left){
		// we win since we took the last ball!
		return true;
	}

	// It will be good, if it cannot lead to a good move (because it's opponent turn!!).
	return findGoodMove()==null;
}
We are looking for a move that minimizes our oppenent chances to win. This technique is called minimax.
Is this going to work? See to believe:
package games.nim.player;

/**
 * Immutable and final class to be used by all the players (including the untrusted ones)!
 * Represents a movement done by a player.
 *
 * @author kriche
 */
public final class Movement {

    public final int ballsToRemove;
    public final int row;

    public Movement(int ballsToRemove, int row) {
        this.ballsToRemove = ballsToRemove;
        this.row = row;
    }

    @Override
    public String toString() {
        return "Taking " + ballsToRemove + " balls from row: " + (row+1) + ".";
    }
    

}
package games.nim.player;

import games.nim.GameBoard;

/**
 * Represents what a class needs to know to be a player
 *
 * @author kriche
 * 
 */
public interface Player {

    /**
     * 
     * @param theGameBoard
     * @return a valid movement according to theGameBoard or null to leave the game.
     */
    Movement makeYourMove(GameBoard theGameBoard);
        

    /**
     *
     * @return the player name.
     * Added here to explicitly show that this method will be invoked.
     */
    @Override
    String toString();

}
package games.nim.player;

import games.nim.GameBoard;

/**
 *
 * This guy does all the work, it knows how to play but has no memory (cache) and
 * it can take too long to make a move!
 * It uses MiniMax algorithm
 * It's the base class for more sophisticated players!
 *
 * @author kriche
 */
public class MachinePlayer implements Player {

    private String name;
    private final boolean isReserved;
    
    public MachinePlayer(String name, boolean isReserved) {
        this.name= name;
        this.isReserved= isReserved;
    }

    @Override
    public String toString() {
        return name;
    }


    @Override
    public Movement makeYourMove(GameBoard theGameBoard) {

        Movement move= findGoodMove(theGameBoard);

        if(move==null) {
            //Okay: no good move so what to do? choose the less bad...
            move= findLessBadMove(theGameBoard);
        }

        return move;

    }

    
    protected Movement findGoodMove(GameBoard possition) {

        // a good move can be found if there is a good possition for us

        for (int r = 0; r < possition.board.length; r++) {

            int balls;

            if ((balls = possition.board[r]) > 0) {

                //try leaving the current row with 0 to (balls-1) balls
                for (int n = 0; n < balls; n++) {

                    possition.board[r]= n;                                        
                    if (isGoodPosittion(possition)) {
                        // We restore the board not only because we are not
						// supposed to modify it but also because
                        // we are in a recursive method and if we don't restore
						// it, it will be in a game over state!
                        possition.board[r] = balls;
                        return new Movement(balls-n, r);
                    }
                }

                //No good moves with this row, we leave it as it was and try the next row
                possition.board[r]= balls;

            }
        }

        //Also here we could end with no good moves!!
        return null;

    }

    // Using Boolean instead of boolean to allow extensions to return null, see
	// thread version to understand the reason behind this.
    protected Boolean isGoodPosittion(GameBoard possition) {
        
        for(int balls: possition.board){
            if( balls>0){
                // Not in base case yet! It will be good, if
				// it cannot lead to a good move (because it's opponent turn).
                return findGoodMove(possition)==null;
            }
        }
        
        // Base case: no more balls left, if not reversed then
		// we win since we took the last ball.
        // Otherwise we lost!        
        return !isReserved;

    }

    protected Movement findLessBadMove(GameBoard theGameBoard) {
        //TODO: Not ready yet, just making a silly move
        return findSillyMove(theGameBoard);
    }


    protected Movement findSillyMove(GameBoard theGameBoard) {

        for (int r = theGameBoard.board.length; r-- > 0; ) {
            int balls;
            if ((balls=theGameBoard.board[r]) > 0) {
                return new Movement(balls, r);
            }
        }

        throw new IllegalStateException("unable to perform any movement!! I cannot play when game is over!");
    }


}
Amazing!! I also added the option to play in "reversed mode" where the last player to take a ball lose the game! But wait!!! There is more!!
What if each player has a certain amount of time to make a move? Or after the "first round" when we need to do another move, we will be in a subset of the set we were before, so why don't to remember the movements? Here you have two more players that by inheritance add these features! But first, the Gameboard and the Game classes:
package games.nim;

import java.util.Arrays;

/**
 * Not much roles for this class only to keep the state of the game board, clone it, compare it
 * to another one and print it.
 *
 * @author kriche
 *
 */
public class GameBoard {

    public int[] board = new int[]{1,3,8,12,15,18,21,};
    private int maxRowLength= 21;
    
    /**
     * 
     * @return a another instance with the same state.
     */
    public GameBoard copy() {
        GameBoard aCloneOfMine= new GameBoard();
        aCloneOfMine.maxRowLength= maxRowLength;
        aCloneOfMine.board= board.clone();        
        return aCloneOfMine;
    }

    public void print() {

        System.out.println();
        for(int row=0; row < board.length; row++){
            System.out.print("row: "+(row+1)+"     ");
            print(board[row]);
        }
        System.out.println("\n");

    }

    private void print(int row) {

        int spaces= maxRowLength - row ;

        for(int i=0; i < spaces / 2; i++){
            System.out.print(" ");
        }

        int balls= row;
        while(row-->0){
            System.out.print("*");
        }

        for(int i=spaces/2; i < spaces; i++){
            System.out.print(" ");
        }

        System.out.print("     Balls: "+ balls);

        System.out.println();

    }


    @Override
    public boolean equals(Object obj) {

        if (obj == null || getClass() != obj.getClass()) {
            return false;
        }
        
        return Arrays.equals(board, ((GameBoard) obj).board);
    }

    @Override
    public int hashCode() {        
        return  Arrays.hashCode(board);
    }
    

}
package games.nim;

import games.nim.player.HumanPlayer;
import games.nim.player.Player;
import games.nim.player.MachinePlayerCached;
import games.nim.player.Movement;

/**
 * Represents a game between two players, manage the turns for each player and keep
 * track of the game board and who wins.
 *
 * @author kriche
 */
public class NimGame {

    private static final long MACHINE_MAX_MOVE_MILLI_SEC = 10000;
    

    /**
     * Prints the games rules.
     */
    public static void printIntro() {
        System.out.println("Welcome to Nim!\n" +
                "Each player takes away any number of balls from any horizontal row.\n" +
                "In \"not reversed\" mode the player that takes the last ball wins the game.\n"+
                "In \"reversed\" mode the player that takes the last ball loses the game.\n\n"+
                "Type \"reversed\" or \"not reversed\" to start playing...");
    }

    /**
     * Plays the game Human Vs Machine
     * @param isReserved
     */
    public void play(boolean isReserved) {

        GameBoard theGameBoard = new GameBoard();
        Player user = new HumanPlayer("Human");
        Player machine = new MachinePlayerCached("Machine", isReserved, MACHINE_MAX_MOVE_MILLI_SEC);
        Movement currentMove;

                
        Player currentPlayer= user;

        while (!gameOver(theGameBoard)) {

            theGameBoard.print();

            System.out.println(currentPlayer + "'s turn:");
            
            //We pass a copy of the gameboard because we don't trust ours players!
            if ((currentMove= currentPlayer.makeYourMove(theGameBoard.copy()))==null) {
                System.out.println(currentPlayer + " leaves the game!\n");
                return;
            }
            
            if(!executeMove(theGameBoard, currentMove)){
                System.out.println(currentPlayer + " loses the game!\n");
                return;
            }


            // It's the turn of the next player!
            if(currentPlayer==user) {
                currentPlayer= machine;
            } else {
                currentPlayer= user;
            }

        }


        theGameBoard.print();


        // if not reversed we need to swap again to left in currentPlayer the winner!
        if (!isReserved) {
            if(currentPlayer==user) {
                currentPlayer= machine;
            } else {
                currentPlayer= user;
            }
        }      
        

        System.out.println(currentPlayer + " wins the game!\n");


    }


    /**
     * 
     * @param theGameBoard
     * @param currentMove
     * @return true is the move is valid
     */
    private boolean executeMove(GameBoard theGameBoard, Movement currentMove) {

        System.out.println(currentMove);
        
        //Validate if the movement is legal:
        if( currentMove.row < 0 || currentMove.row > theGameBoard.board.length-1 ||
            currentMove.ballsToRemove < 1 ||
			currentMove.ballsToRemove > theGameBoard.board[currentMove.row] ){
            System.out.println("Invalid movement!!");
            return false;
        }        

        theGameBoard.board[currentMove.row] -= currentMove.ballsToRemove;
        return true;

    }

    /**
     * 
     * @param theGameBoard
     * @return true is the game is over
     */
    private boolean gameOver(GameBoard theGameBoard) {

        for (int balls : theGameBoard.board) {
            if (balls > 0) {
                return false;
            }
        }

        //All the rows have 0 balls so game over!!
        return true;
    }

}
package games.nim.player;

import games.nim.GameBoard;

/**
 *
 * This guy guarantee to give a move in no more than a given amount of time!
 * Not always that movement will be a good one, but it will try!!
 *
 * @author kriche
 * 
 */
public class MachinePlayerTimeLimited extends MachinePlayer {
        
    private long maxMilliSecs;
    private volatile Movement bestMove;
    private volatile boolean bestMoveFinderDone;
    
    public MachinePlayerTimeLimited(String name, boolean isReversed,long maxMilliSecs) {
        super(name, isReversed);
        this.maxMilliSecs = maxMilliSecs;
    }

    @Override
    public Movement makeYourMove(final GameBoard theGameBoard) {

        Runnable bestMoveFinder = new Runnable() {

            public void run() {

                // We use a copy of the game board since if interrupted the original game board
                // would be changed in an "incomplete" way
                GameBoard tempGameBoard = theGameBoard.copy();                
                Movement move= MachinePlayerTimeLimited.super.makeYourMove(tempGameBoard);

                synchronized (MachinePlayerTimeLimited.this) {
                    if (!Thread.currentThread().isInterrupted()) {
                        theGameBoard.board= tempGameBoard.board;
                        bestMove= move;
                        bestMoveFinderDone= true;				

                        // By the way this is done only one thread will be waiting.		
                        MachinePlayerTimeLimited.this.notify();
                    }
                }
            }
        };

        Thread bestMoveFinderThread = new Thread(bestMoveFinder,"bestMoveFinder");
        bestMoveFinderThread.setDaemon(true);
        bestMoveFinderDone= false;
        bestMoveFinderThread.start();

        Movement theMovement;

        synchronized (this) {

            try {

                // wait until bestMoveFinderThread completes or timeout:

                long waitTime = maxMilliSecs;
                long elapsedTime = 0;
                long iniTime = System.currentTimeMillis();

                while (waitTime > 0 && !bestMoveFinderDone) {

                    System.out.println("Thinking, please wait...");
                    wait(waitTime);

                    elapsedTime = System.currentTimeMillis() - iniTime;
                    waitTime -= elapsedTime;
                }

                if (!bestMoveFinderDone) {
                    bestMoveFinderThread.interrupt();                    
                    theMovement= findFastMove(theGameBoard);
                }else{
                    theMovement= bestMove;
                }

            } catch (InterruptedException ex) {
                throw new Error(ex);
            }

        }
        
        return theMovement;

    }



    @Override
    protected Movement findGoodMove(GameBoard possition) {

        Movement move;

        try{
            move= super.findGoodMove(possition);
        }catch(NullPointerException npe){
            //Timeout and not able to find a goodmove!
            move= null;
        }

        return move;
    }


    @Override
    protected Boolean isGoodPosittion(GameBoard possition) {

        if (Thread.currentThread().isInterrupted()) {
            /*
             * Stop since it was interrupted!
             * We don't know if it is good or bad so we return null (so it will
             * not be cached or used). This will cause a null pointer exception
             * in the executing thread but it will be catched and anyway it
             * wont affect the program execution.
             */
            return null; 
        }

        return super.isGoodPosittion(possition);
    }

    @Override
    protected Movement findLessBadMove(GameBoard theGameBoard) {

        if (Thread.currentThread().isInterrupted()) {
            // stop since it was interrupted
            return null; //Here the important thing is to return, not the movement returned.
        }        
        
        return super.findLessBadMove(theGameBoard);

    }

    protected Movement findFastMove(GameBoard theGameBoard) {
        return findSillyMove(theGameBoard);
    }

}
See more about this in Threads section!
package games.nim.player;

import games.nim.GameBoard;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * This guy adds cache so it will remember previous
 * games knowing if they can or cannot lead to
 * a winning move. By using cache the execution
 * becomes much faster!
 *
 * @author kriche
 * 
 */
public class MachinePlayerCached extends MachinePlayerTimeLimited {

    private final PossitionCache possitionCache = new PossitionCache();

    public MachinePlayerCached(String name, boolean isReversed, long maxMilliSecs) {
        super(name, isReversed, maxMilliSecs);
    }

    
    // Adding cache!!
    @Override
    protected Boolean isGoodPosittion(GameBoard possition) {

        Boolean isGood;
        if((isGood= possitionCache.isGoodPossition(possition)) != null){            
            return isGood;
        }

        isGood= super.isGoodPosittion(possition);
        possitionCache.putPossition(possition, isGood);        
        return isGood;
    }

    @Override
    public Movement makeYourMove(GameBoard theGameBoard) {    
        return super.makeYourMove(theGameBoard);
    }

}

class PossitionCache {

    private Map cache = new HashMap();

    Boolean isGoodPossition(GameBoard possition) {
        return cache.get(normalicePossition(possition));
    }

    void putPossition(GameBoard possition, Boolean isGood) {
        if(isGood!=null){
            cache.put(normalicePossition(possition), isGood);
        }
    }

    private static GameBoard normalicePossition(GameBoard possition) {
        GameBoard nomalized = possition.copy();
        Arrays.sort(nomalized.board);
        return nomalized;
    }

}
In case I forgot some file, here you have the source code and the class files: runnable and source

To sum up

It is interesting to note that this strategy (as it is in the code above) cannot always give us the best solution for a game! Let's define all the sequence of movements of a match as the "path" of the match, it could happen that two different paths (one where we win and the other where we lose) start with the same sequence of movements, but also there could be a third path where we win and has no common first movements with a path where we lose. So the best choice will be this third one since it will force our opponent to lose! We could adapt our code to pick a winning path that has no commons moves with a losing one! Also there could be games where no one wins, this is, a draw or paths so long that there is no computer or group of computers able to compute them. For these cases, we can adapt our code to instead of saying if a possition is good or bad to return a number to rank a possition and also combine this technique with some heuristics to cut paths that don't look promising!