Skip to content

Commit 43aa8c6

Browse files
author
monsoon
committed
algorithms 4
0 parents  commit 43aa8c6

21 files changed

+2779
-0
lines changed

‎README.md

Whitespace-only changes.

‎src/eightPuzzle/Board.java

Lines changed: 237 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,237 @@
1+
package eightPuzzle;
2+
3+
import java.util.ArrayList;
4+
import java.util.Iterator;
5+
6+
import edu.princeton.cs.algs4.StdRandom;
7+
8+
public class Board {
9+
10+
private final int dimension;
11+
12+
private final int[][] grids;
13+
14+
// construct a board from an n-by-n array of blocks
15+
// (where blocks[i][j] = block in row i, column j)
16+
public Board(int[][] blocks) {
17+
dimension = blocks.length;
18+
grids = new int[dimension][dimension];
19+
for (int i = 0; i < dimension; i++) {
20+
for (int j = 0; j < dimension; j++) {
21+
grids[i][j] = blocks[i][j];
22+
}
23+
}
24+
}
25+
26+
// board dimension n
27+
public int dimension() {
28+
return dimension;
29+
}
30+
31+
// number of blocks out of place
32+
public int hamming() {
33+
int incorrectNum = 0;
34+
for (int i = 0; i < dimension; i++) {
35+
for (int j = 0; j < dimension; j++) {
36+
if (grids[i][j] == 0) {
37+
continue;
38+
}
39+
if (grids[i][j] != (i * dimension + j + 1)) {
40+
incorrectNum++;
41+
}
42+
}
43+
}
44+
return incorrectNum;
45+
}
46+
47+
// sum of Manhattan distances between blocks and goal
48+
public int manhattan() {
49+
int manhattan_dis = 0;
50+
for (int i = 0; i < dimension; i++) {
51+
for (int j = 0; j < dimension; j++) {
52+
if (grids[i][j] == 0) {
53+
continue;
54+
}
55+
if (grids[i][j] != (i * dimension + j + 1)) {
56+
int x_cor = grids[i][j] % dimension == 0? grids[i][j] / dimension - 1 : grids[i][j] / dimension;
57+
int y_cor = grids[i][j] - x_cor * dimension - 1;
58+
int x_dis = x_cor - i > 0 ? x_cor - i : i - x_cor;
59+
int y_dis = y_cor - j > 0 ? y_cor - j : j - y_cor;
60+
manhattan_dis += x_dis + y_dis;
61+
}
62+
}
63+
}
64+
return manhattan_dis;
65+
}
66+
67+
// is this board the goal board?
68+
public boolean isGoal() {
69+
return manhattan() == 0;
70+
}
71+
72+
// a board that is obtained by exchanging any pair of blocks
73+
public Board twin() {
74+
Position positionOne = new Position(StdRandom.uniform(dimension), StdRandom.uniform(dimension));
75+
Position positionTwo = new Position(StdRandom.uniform(dimension), StdRandom.uniform(dimension));
76+
int[][] twin = new int[dimension][dimension];
77+
for (int i = 0; i < dimension; i++) {
78+
for (int j = 0; j < dimension; j++) {
79+
twin[i][j] = grids[i][j];
80+
}
81+
}
82+
while (true) {
83+
if(twin[positionOne.x][positionOne.y] == 0 || positionOne.equals(positionTwo)){
84+
positionOne.x = StdRandom.uniform(dimension);
85+
positionOne.y = StdRandom.uniform(dimension);
86+
}
87+
if(twin[positionTwo.x][positionTwo.y] == 0 || positionOne.equals(positionTwo)){
88+
positionTwo.x = StdRandom.uniform(dimension);
89+
positionTwo.y = StdRandom.uniform(dimension);
90+
}
91+
if(!positionOne.equals(positionTwo)){
92+
break;
93+
}
94+
}
95+
int tempValue = twin[positionOne.x][positionOne.y];
96+
twin[positionOne.x][positionOne.y] = twin[positionTwo.x][positionTwo.y];
97+
twin[positionTwo.x][positionTwo.y] = tempValue;
98+
return new Board(twin);
99+
}
100+
101+
// does this board equal y?
102+
public boolean equals(Object y) {
103+
if(null == y) return false;
104+
if (this == y)
105+
return true;
106+
if (y.getClass() == this.getClass()) {
107+
if (this.dimension != ((Board) y).dimension())
108+
return false;
109+
String other = ((Board) y).toString();
110+
String[] x_cor = other.split("\n");
111+
if (x_cor.length -1 != dimension)
112+
return false;
113+
for (int i = 0; i < x_cor.length - 1; i++) {
114+
String[] y_cor = x_cor[i + 1].trim().split(" ");
115+
if (y_cor.length != dimension)
116+
return false;
117+
for (int j = 0; j < y_cor.length; j++) {
118+
if (this.grids[i][j] != Integer.parseInt(y_cor[j])) {
119+
return false;
120+
}
121+
}
122+
}
123+
}
124+
return true;
125+
}
126+
127+
// all neighboring boards
128+
public Iterable<Board> neighbors() {
129+
return new BoardIterator();
130+
}
131+
132+
private class BoardIterator implements Iterable<Board> {
133+
134+
private ArrayList<Board> neighbors = new ArrayList<>();
135+
136+
BoardIterator() {
137+
Position zeroPosition = null;
138+
for (int i = 0; i < dimension; i++) {
139+
for (int j = 0; j < dimension; j++) {
140+
if (grids[i][j] == 0) {
141+
zeroPosition = new Position(i, j);
142+
break;
143+
}
144+
}
145+
}
146+
// 0上放的Board
147+
if (zeroPosition.x > 0) {
148+
neighbors.add(oneNeighbour(zeroPosition, new Position(zeroPosition.x - 1, zeroPosition.y)));
149+
}
150+
// 0右侧的Board
151+
if (zeroPosition.y < dimension - 1) {
152+
neighbors.add(oneNeighbour(zeroPosition, new Position(zeroPosition.x, zeroPosition.y + 1)));
153+
}
154+
// 0下方的Board
155+
if (zeroPosition.x < dimension - 1) {
156+
neighbors.add(oneNeighbour(zeroPosition, new Position(zeroPosition.x + 1, zeroPosition.y)));
157+
}
158+
// 0左方的Board
159+
if (zeroPosition.y > 0) {
160+
neighbors.add(oneNeighbour(zeroPosition, new Position(zeroPosition.x, zeroPosition.y - 1)));
161+
}
162+
}
163+
164+
@Override
165+
public Iterator<Board> iterator() {
166+
return neighbors.iterator();
167+
}
168+
169+
private Board oneNeighbour(Position froPos, Position toPos) {
170+
int[][] copyGrids = new int[dimension][dimension];
171+
for (int i = 0; i < dimension; i++) {
172+
for (int j = 0; j < dimension; j++) {
173+
copyGrids[i][j] = grids[i][j];
174+
}
175+
}
176+
int tempValue = copyGrids[froPos.x][froPos.y];
177+
copyGrids[froPos.x][froPos.y] = copyGrids[toPos.x][toPos.y];
178+
copyGrids[toPos.x][toPos.y] = tempValue;
179+
return new Board(copyGrids);
180+
}
181+
}
182+
183+
// string representation of this board (in the output format specified below)
184+
public String toString() {
185+
StringBuilder sb = new StringBuilder();
186+
sb.append(dimension).append("\n");
187+
for (int i = 0; i < dimension; i++) {
188+
sb.append(" ");
189+
for (int j = 0; j < dimension; j++) {
190+
sb.append(grids[i][j]).append(" ");
191+
}
192+
sb.append("\n");
193+
}
194+
return sb.toString();
195+
}
196+
197+
// unit tests (not graded)
198+
public static void main(String[] args) {
199+
int[][] test = { { 0, 1, 3 }, { 4, 2, 5 }, { 7, 8, 6 } };
200+
int[][] testeq = { { 0, 1, 3 }, { 4, 2, 5 }, { 7, 8, 6 } };
201+
int[][] tess = {{0,2},{1,3}};
202+
Board board = new Board(test);
203+
Board boardd = new Board(testeq);
204+
System.out.println(board.equals(boardd));
205+
System.out.println(board);
206+
System.out.println(board.twin());
207+
/* System.out.println(board.dimension());
208+
System.out.println(board.hamming());
209+
System.out.println(board.manhattan());
210+
System.out.println(board);
211+
System.out.println(board.twin());
212+
System.out.println(boardd);
213+
System.out.println(boardd.twin());*/
214+
215+
}
216+
217+
private class Position {
218+
private int x;
219+
220+
private int y;
221+
222+
Position(int x, int y) {
223+
this.x = x;
224+
this.y = y;
225+
}
226+
227+
@Override
228+
public boolean equals(Object obj) {
229+
if (super.equals(obj))
230+
return true;
231+
if (obj.getClass().equals(Position.class))
232+
return this.x == ((Position) obj).x && this.y == ((Position) obj).y;
233+
return false;
234+
}
235+
}
236+
237+
}

‎src/eightPuzzle/Solver.java

Lines changed: 158 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,158 @@
1+
package eightPuzzle;
2+
3+
import java.util.ArrayList;
4+
import java.util.Comparator;
5+
6+
import edu.princeton.cs.algs4.In;
7+
import edu.princeton.cs.algs4.MinPQ;
8+
import edu.princeton.cs.algs4.StdOut;
9+
10+
public class Solver {
11+
12+
private static final Comparator<Node> BY_PRIORITY = new ByPriority();
13+
14+
private boolean unsolvable = false;
15+
16+
private ArrayList<Board> stepList = null;
17+
18+
private int moves = 0;
19+
20+
private class Node {
21+
22+
private Node father;
23+
24+
private Board board;
25+
26+
private int moves;
27+
28+
private int priority;
29+
30+
Node(Node father, Board board, int moves) {
31+
this.father = father;
32+
this.board = board;
33+
this.moves = moves;
34+
this.priority = moves + board.manhattan();
35+
}
36+
}
37+
38+
private static class ByPriority implements Comparator<Node> {
39+
@Override
40+
public int compare(Node o1, Node o2) {
41+
return o1.priority == o2.priority ? 0 : (o1.priority > o2.priority ? 1 : -1);
42+
}
43+
}
44+
45+
// find a solution to the initial board (using the A* algorithm)
46+
public Solver(Board initial) {
47+
if (null == initial) {
48+
throw new NullPointerException();
49+
}
50+
MinPQ<Node> boardPQ = new MinPQ<Node>(BY_PRIORITY);
51+
52+
MinPQ<Node> twinPQ = new MinPQ<Node>(BY_PRIORITY);
53+
54+
ArrayList<Node> closes = new ArrayList<Node>();
55+
56+
ArrayList<Node> twinCloses = new ArrayList<Node>();
57+
58+
Node goalNode = null;
59+
60+
boardPQ.insert(new Node(null, initial, 0));
61+
// 設置twin的初始隊列，用於檢測是否unsolvable
62+
twinPQ.insert(new Node(null, initial.twin(), 0));
63+
while (!boardPQ.isEmpty() && !twinPQ.isEmpty()) {
64+
Node minNode = boardPQ.delMin();
65+
Node minTwinNode = twinPQ.delMin();
66+
// maintain close list
67+
closes.add(minNode);
68+
twinCloses.add(minTwinNode);
69+
if (minNode.board.isGoal()) {
70+
break;
71+
}
72+
if (minTwinNode.board.isGoal()) {
73+
unsolvable = true;
74+
break;
75+
}
76+
Iterable<Board> neighbors = minNode.board.neighbors();
77+
Iterable<Board> twinNeighbors = minTwinNode.board.neighbors();
78+
// 添加不重复的neighbor
79+
appendNeighbors(minNode, neighbors, closes, boardPQ);
80+
appendNeighbors(minTwinNode, twinNeighbors, twinCloses, twinPQ);
81+
}
82+
if (!unsolvable) {
83+
goalNode = closes.get(closes.size() - 1);
84+
moves = goalNode.moves;
85+
ArrayList<Board> toReserve = new ArrayList<Board>();
86+
while (true) {
87+
toReserve.add(goalNode.board);
88+
if(goalNode.father == null){
89+
break;
90+
}
91+
goalNode = goalNode.father;
92+
}
93+
stepList = new ArrayList<Board>(toReserve.size());
94+
for (int i = toReserve.size() - 1; i >= 0; i--) {
95+
stepList.add(toReserve.get(i));
96+
}
97+
}
98+
99+
}
100+
101+
// is the initial board solvable?
102+
public boolean isSolvable() {
103+
return !unsolvable;
104+
}
105+
106+
// min number of moves to solve initial board; -1 if unsolvable
107+
public int moves() {
108+
if (!unsolvable) {
109+
return moves;
110+
}
111+
return -1;
112+
}
113+
114+
// sequence of boards in a shortest solution; null if unsolvable
115+
public Iterable<Board> solution() {
116+
return stepList;
117+
}
118+
119+
private void appendNeighbors(Node parentNode, Iterable<Board> boards, ArrayList<Node> closes,
120+
MinPQ<Node> PQ) {
121+
if (closes != null && closes.size() > 0) {
122+
for (Board board : boards) {
123+
boolean isExist = false;
124+
for (Node node : closes) {
125+
if (node.board.equals(board)) {
126+
isExist = true;
127+
continue;
128+
}
129+
}
130+
if (!isExist) {
131+
PQ.insert(new Node(parentNode, board, parentNode.moves + 1));
132+
}
133+
}
134+
}
135+
}
136+
137+
// solve a slider puzzle (given below)
138+
public static void main(String[] args) {
139+
// create initial board from file
140+
In in = new In(args[0]);
141+
int n = in.readInt();
142+
int[][] blocks = new int[n][n];
143+
for (int i = 0; i < n; i++)
144+
for (int j = 0; j < n; j++)
145+
blocks[i][j] = in.readInt();
146+
Board initial = new Board(blocks);
147+
// solve the puzzle
148+
Solver solver = new Solver(initial);
149+
// print solution to standard output
150+
if (!solver.isSolvable())
151+
StdOut.println("No solution possible");
152+
else {
153+
StdOut.println("Minimum number of moves = " + solver.moves());
154+
for (Board board : solver.solution())
155+
StdOut.println(board);
156+
}
157+
}
158+
}

0 commit comments

Comments
 (0)