n-puzzlesolver/Tree.java at master · orhungorkem/n-puzzlesolver · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Set;
import java.util.TreeSet;

public class Tree {

	Node root;
	Set<Node>past;

	public Tree(String input) { //Takes input and initiates table,node, makes it root
		Table initial=new Table(input);
		root=new Node(initial,"X");
		past=new HashSet<Node>();
		past.add(root);
	}

	public Node process() { //Creates nodes for possiblities and returns the goal node

		Queue<Node>q=new LinkedList<Node>();
		q.add(root);
		while(!q.isEmpty()) {

			Node current=q.poll();

			if(!current.type.equals("L")) {
				Node r=new Node(Table.right(current.table),"R");
				if(r.table!=null) {
					if(!past.contains(r)) {
						r.parent=current;
						current.right=r;
						q.add(r);
						past.add(r);
						if(r.table.isGoal2()) {
							return r;
						}
					}

				}
			}
			if(!current.type.equals("R")) {
				Node l=new Node(Table.left(current.table),"L");
				if(l.table!=null) {
					if(!past.contains(l)) {
						l.parent=current;
						current.left=l;
						q.add(l);
						past.add(l);
						if(l.table.isGoal2()) { //ISGOAL 1-2 FARKMAZ
							return l;
						}
					}

				}
			}

			if(!current.type.equals("D")) {
				Node u=new Node(Table.up(current.table),"U");
				if(u.table!=null) {
					if(!past.contains(u)) {
						u.parent=current;
						current.up=u;
						q.add(u);
						past.add(u);
						if(u.table.isGoal2()) {
							return u;
						}
					}

				}
			}

			if(!current.type.equals("U")) {
				Node d=new Node(Table.down(current.table),"D");
				if(d.table!=null) {
					if(!past.contains(d)) {
						d.parent=current;
						current.down=d;
						q.add(d);
						past.add(d);
						if(d.table.isGoal2()) {
							return d;
						}
					}

				}
			}

		}
		return null;

	}


	public String getTrajectory(Node goal) { //Returns output for goal node

		if(goal==null) {
			return "N";
		}
		if(goal.equals(root)) {
			return "";
		}
		Node next=goal.parent;
		if(next.down!=null) {
			if(next.down.equals(goal)) {
				return getTrajectory(next)+"D";
			}
		}
		if(next.up!=null) {
			if(next.up.equals(goal)) {
				return getTrajectory(next)+"U";
			}
		}
		if(next.left!=null) {
			if(next.left.equals(goal)) {
				return getTrajectory(next)+"L";
			}
		}

		return getTrajectory(next)+"R";


	}


}