Analysis of depth-first search and A* search in a peg solitaire game. Assignment for Introduction of Artificial Intelligence classes, given by Dr. Benjamin at Pace University

Main.java

package pegsolitaire;

import java.util.Stack;
import java.util.TreeSet;
import java.util.Vector;

public class Main {
	
	static int iterations=0;
	
	public static void main(String[] args) {
		Peg start = new Peg();
		start.initialState();
		
		//choose below the method:
		//depthFirst(start);
		//aStar(start);
	}
	
	
	
	public static int depthFirst(Peg start){
		Stack<Peg> stack = new Stack<Peg>();
		
		stack.push(start);
		
		//TODO: use stack.contains and check .equals
		while(!stack.isEmpty()){
			Peg p = stack.pop();
			System.out.println(++iterations + "  " + stack.size());
			
			if(p.isGoal()){
				System.out.println("Goal founded. i: "+iterations);
				return 1;
			}
			
			//Algorithm to search for movements
			for(int i=0;i<=6;i++){
				for(int j=0;j<=6;j++){
					if(p.data[i][j] == 0){
						//if the tile is a hole, there is 4 possibilites of movement:
						//first, up-down
						try{
							if(p.data[i-1][j]==1 && p.data[i-2][j]==1){
								
								//do the changes and put q in the stack
								//create a new peg to not override the running one.
								Peg q = new Peg();
								Peg.copy(p,q);
								q.data[i-2][j]=0;
								q.data[i-1][j]=0;
								q.data[i][j]=1;
								stack.push(q);
							}
						}catch(ArrayIndexOutOfBoundsException e){}
						try{
							//down-up
							if(p.data[i+1][j]==1 && p.data[i+2][j]==1){
								Peg q = new Peg();
								Peg.copy(p,q);
								q.data[i+2][j]=0;
								q.data[i+1][j]=0;
								q.data[i][j]=1;
								stack.push(q);
							}
						}catch(ArrayIndexOutOfBoundsException e){}
						try{
							//left-right
							if(p.data[i][j-1]==1 && p.data[i][j-2]==1){
								Peg q = new Peg();
								Peg.copy(p,q);
								q.data[i][j-1]=0;
								q.data[i][j-2]=0;
								q.data[i][j]=1;
								stack.push(q);
							}
						}catch(ArrayIndexOutOfBoundsException e){}
						try{
							//right-left
							if(p.data[i][j+1]==1 && p.data[i][j+2]==1){
								Peg q = new Peg();
								Peg.copy(p,q);
								q.data[i][j+1]=0;
								q.data[i][j+2]=0;
								q.data[i][j]=1;
								stack.push(q);
							}
						}catch(ArrayIndexOutOfBoundsException e){}
					}
				}
			}
		}
		return 0;
	}

	public static int aStar(Peg start){
		TreeSet<Peg> tree = new TreeSet<Peg>();
		tree.add(start);
		
		while(!tree.isEmpty()){
			Peg p = tree.pollFirst();
			System.out.println(++iterations + "  " + tree.size());
			
			if(p.isGoal()){
				System.out.println("Goal founded. i: "+iterations);
				return 1;
			}
			
			
			//Algorithm to search for movements
			for(int i=0;i<=6;i++){
				for(int j=0;j<=6;j++){
					if(p.data[i][j] == 0){
						//if the tile is a hole, there is 4 possibilites of movement:
						//first, up-down
						try{
							if(p.data[i-1][j]==1 && p.data[i-2][j]==1){
								//do the changes and put q in the tree
								//create a new peg to not override the running one.
								Peg q = new Peg();
								Peg.copy(p,q);
								q.data[i-2][j]=0;
								q.data[i-1][j]=0;
								q.data[i][j]=1;
								int h = Peg.firstHeuristic(q,i,j,Peg.UP_DOWN);
								q.heuristic += h+1;
								tree.add(q);
							}
						}catch(ArrayIndexOutOfBoundsException e){}
						try{
							//down-up
							if(p.data[i+1][j]==1 && p.data[i+2][j]==1){
								Peg q = new Peg();
								Peg.copy(p,q);
								q.data[i+2][j]=0;
								q.data[i+1][j]=0;
								q.data[i][j]=1;
								int h = Peg.firstHeuristic(q,i,j,Peg.DOWN_UP);
								q.heuristic += h+1;
								tree.add(q);
							}
						}catch(ArrayIndexOutOfBoundsException e){}
						try{
							//left-right
							if(p.data[i][j-1]==1 && p.data[i][j-2]==1){
								Peg q = new Peg();
								Peg.copy(p,q);
								q.data[i][j-1]=0;
								q.data[i][j-2]=0;
								q.data[i][j]=1;
								int h = Peg.firstHeuristic(q,i,j,Peg.LEFT_RIGHT);
								q.heuristic += h+1;
								tree.add(q);
							}
						}catch(ArrayIndexOutOfBoundsException e){}
						try{
							//right-left
							if(p.data[i][j+1]==1 && p.data[i][j+2]==1){
								Peg q = new Peg();
								Peg.copy(p,q);
								q.data[i][j+1]=0;
								q.data[i][j+2]=0;
								q.data[i][j]=1;
								int h = Peg.firstHeuristic(q,i,j,Peg.RIGHT_LEFT);
								q.heuristic += h+1;
								tree.add(q);
							}
						}catch(ArrayIndexOutOfBoundsException e){}
					}
				}
			}
			for(int i=0;i<=6;i++){
				System.out.println(" ");
				for(int j=0;j<=6;j++)
					System.out.print(p.data[i][j]+" ");
			}
			System.out.println(" ");
		}
		
		
		return 0;
	}
}

Peg.java

public class Peg implements Comparable<Peg>{
	public static int UP_DOWN = 0;
	public static int DOWN_UP = 1;
	public static int LEFT_RIGHT = 2;
	public static int RIGHT_LEFT = 3;
	
	
	int[][] data;
	int heuristic;
	
	Peg(){
		this.data = new int[7][7];
	}
	
	Peg(int heuristic){
		this.data = new int[7][7];
		this.heuristic=heuristic;
	}
	
	public void initialState(){
		for(int i=0;i<=6;i++)
			for(int j=0;j<=6;j++)
				this.data[i][j]=1;
		
		for(int i=0;i<=1;i++)
			for(int j=0;j<=1;j++)
				this.data[i][j]=-1;
		
		for(int i=0;i<=1;i++)
			for(int j=5;j<=6;j++)
				this.data[i][j]=-1;
		
		for(int i=5;i<=6;i++)
			for(int j=0;j<=1;j++)
				this.data[i][j]=-1;
		
		for(int i=5;i<=6;i++)
			for(int j=5;j<=6;j++)
				this.data[i][j]=-1;
		
		this.data[3][3]=0;		
	}
	
	public static Peg goal(){
		Peg p = new Peg();
		
		for(int i=0;i<=6;i++)
			for(int j=0;j<=6;j++)
				p.data[i][j]=0;
		
		for(int i=0;i<=1;i++)
			for(int j=0;j<=1;j++)
				p.data[i][j]=-1;
		
		for(int i=0;i<=1;i++)
			for(int j=5;j<=6;j++)
				p.data[i][j]=-1;
		
		for(int i=5;i<=6;i++)
			for(int j=0;j<=1;j++)
				p.data[i][j]=-1;
		
		for(int i=5;i<=6;i++)
			for(int j=5;j<=6;j++)
				p.data[i][j]=-1;
		
		p.data[3][3]=1;	
		
		return p;
	}

	public boolean isGoal(){
		boolean result = true;
		Peg goal = Peg.goal();
		for(int i=0;i<=6;i++){
			for(int j=0;j<=6;j++){
				if(this.data[i][j] != goal.data[i][j])
					result=false;				
			}
		}
			return result;
	}
	
	public static void copy(Peg p, Peg q){
		for(int i=0; i<q.data.length; i++)
			  for(int j=0; j<q.data[i].length; j++)
			    q.data[i][j]=p.data[i][j];
	}

	@Override
	public int compareTo(Peg o) {
			return this.heuristic - o.heuristic;		
	}
	
	//when a movement is done, it leaves 2 blank holes in the way. This heuristic
	//analyzes the amount of movement between these 2 blank holes.
	public static int firstHeuristic(Peg q,int i,int j,int typeMov){
		int i1 = 0,i2=0,j1=0,j2=0;
		if(typeMov == UP_DOWN){
			i1=i-1;
			j1=j;
			
			i2=i-2;
			j2=j;
		}else if(typeMov == DOWN_UP){
			i1=i+1;
			j1=j;
			
			i2=i+2;
			j2=j;
		}else if(typeMov == LEFT_RIGHT){
			i1=i;
			j1=j-1;
			
			i2=i;
			j2=j-2;
		}else if(typeMov == RIGHT_LEFT){
			i1=i;
			j1=j+1;
			
			i2=i;
			j2=j+2;
		}
		
		int h=0;
		
		try { //up-down
			if(q.data[i1-1][j1]==1 && q.data[i1-2][j1]==1) h++;
		} catch (ArrayIndexOutOfBoundsException e) {	}
		try {//down-up
			if(q.data[i1+1][j1]==1 && q.data[i1+2][j1]==1) h++;
		} catch (ArrayIndexOutOfBoundsException e) {}
		try {//left-right
			if(q.data[i1][j1-1]==1 && q.data[i1][j1-2]==1) h++;
		} catch (ArrayIndexOutOfBoundsException e) {}
		try {//right-left
			if(q.data[i1][j1+1]==1 && q.data[i1][j1+2]==1) h++;
		} catch (ArrayIndexOutOfBoundsException e) {}
		try {
			if(q.data[i2-1][j2]==1 && q.data[i2-2][j2]==1) h++;
		} catch (ArrayIndexOutOfBoundsException e) {}
		try {
			if(q.data[i2+1][j2]==1 && q.data[i2+2][j2]==1) h++;
		} catch (ArrayIndexOutOfBoundsException e) {}
		try {
			if(q.data[i2][j2-1]==1 && q.data[i2][j2-2]==1) h++;
		} catch (ArrayIndexOutOfBoundsException e) {}
		try {
			if(q.data[i2][j2+1]==1 && q.data[i2][j2+2]==1) h++;
		} catch (ArrayIndexOutOfBoundsException e) {}
		
		return 8-h;
	}
	
	public static int secondHeuristic(Peg p,int i, int j,int typeMov){
		if(typeMov == UP_DOWN){
			return 1;
		}
		return 0;
	}
	

}