Knight Tour

package horsejump;

import java.util.LinkedList;
import java.util.List;


public class Knight_Tour {

	Board board;
	Pos currentPos;
	private boolean complete = false;
	private final Pos[] JUMP = { new Pos(2,1), new Pos(2,-1),
			new Pos(-2,1), new Pos(-2,-1), new Pos(1,2),
			new Pos(1,-2), new Pos(-1,2), new Pos(-1,-2)};
	int[] bestchoice;
	Pos followUp;

	public Knight_Tour(int boardsize){
		this(boardsize, new Pos(0,0));
	}


	public Knight_Tour(int boardsize, Pos start){
		board = new Board(boardsize);
		bestchoice = new int[JUMP.length];
		solve(start, 0);
	}

	public Pos[] getOptions(Pos current, int boardsize){

		List<Pos> result = new LinkedList<Pos>();

		for(Pos option: JUMP){
			int x = current.getX() + option.getX();
			int y = current.getY() + option.getY();
			Pos futurePos = new Pos(x,y);
			if(x >= 0 && x < boardsize && y >= 0 && y < boardsize){
				if(board.getBoard(futurePos) == 0){
					result.add (futurePos);
				}
			}
		}
		//System.out.println(options);
		return result.toArray(new Pos[result.size()]);
	}

	public boolean solve(Pos current, int steps){
		System.out.println(board);
		if (boardFilled()) {
			System.out.println(board);
			return true;
		}

		Pos [] successors = getOptions (current,board.getBoardsize());

		if (successors.length == 0) {

			return false;
		}

		for (int i = 0; i < successors.length; i++) {
			followUp = successors [i];
			board.set(followUp, steps);
			if (solve (followUp, steps+1)) {
				return true;
			} else {
				board.set(followUp, 0);
			}

		}
		return false;
	}


	public boolean boardFilled(){
		for (int i = 0; i < board.getBoardsize(); i++) {
			for (int j = 0; j < board.getBoardsize(); j++) {
				Pos pos = new Pos (i,j);
				if (board.getBoard(pos) == 0) {
					return false;
				}
			}
		}
		return true;
	}

}