From 6a44b074f0169a1b0f9e92347af929c5e471746e Mon Sep 17 00:00:00 2001
From: Camil Staps
Date: Sat, 18 Apr 2015 13:44:44 +0200
Subject: Reorganised projects
---
Week6 Sliding game solver/.gitignore | 3 +
.../Assignment (in Dutch).pdf | Bin 0 -> 223530 bytes
Week6 Sliding game solver/build.xml | 73 +
Week6 Sliding game solver/manifest.mf | 3 +
Week6 Sliding game solver/nbproject/build-impl.xml | 1413 ++++++++++++++++++++
.../nbproject/genfiles.properties | 8 +
.../nbproject/project.properties | 75 ++
Week6 Sliding game solver/nbproject/project.xml | 15 +
Week6 Sliding game solver/src/Configuration.java | 21 +
Week6 Sliding game solver/src/Direction.java | 26 +
Week6 Sliding game solver/src/Main.java | 35 +
Week6 Sliding game solver/src/Node.java | 92 ++
Week6 Sliding game solver/src/SlidingGame.java | 205 +++
Week6 Sliding game solver/src/Solver.java | 55 +
Week6 Sliding game solver/week6.tar.gz | Bin 0 -> 5434 bytes
15 files changed, 2024 insertions(+)
create mode 100644 Week6 Sliding game solver/.gitignore
create mode 100644 Week6 Sliding game solver/Assignment (in Dutch).pdf
create mode 100644 Week6 Sliding game solver/build.xml
create mode 100644 Week6 Sliding game solver/manifest.mf
create mode 100644 Week6 Sliding game solver/nbproject/build-impl.xml
create mode 100644 Week6 Sliding game solver/nbproject/genfiles.properties
create mode 100644 Week6 Sliding game solver/nbproject/project.properties
create mode 100644 Week6 Sliding game solver/nbproject/project.xml
create mode 100644 Week6 Sliding game solver/src/Configuration.java
create mode 100644 Week6 Sliding game solver/src/Direction.java
create mode 100644 Week6 Sliding game solver/src/Main.java
create mode 100644 Week6 Sliding game solver/src/Node.java
create mode 100644 Week6 Sliding game solver/src/SlidingGame.java
create mode 100644 Week6 Sliding game solver/src/Solver.java
create mode 100644 Week6 Sliding game solver/week6.tar.gz
(limited to 'Week6 Sliding game solver')
diff --git a/Week6 Sliding game solver/.gitignore b/Week6 Sliding game solver/.gitignore
new file mode 100644
index 0000000..4523fc2
--- /dev/null
+++ b/Week6 Sliding game solver/.gitignore
@@ -0,0 +1,3 @@
+nbproject/private/
+build/
+dist/
diff --git a/Week6 Sliding game solver/Assignment (in Dutch).pdf b/Week6 Sliding game solver/Assignment (in Dutch).pdf
new file mode 100644
index 0000000..dbf029b
Binary files /dev/null and b/Week6 Sliding game solver/Assignment (in Dutch).pdf differ
diff --git a/Week6 Sliding game solver/build.xml b/Week6 Sliding game solver/build.xml
new file mode 100644
index 0000000..d221676
--- /dev/null
+++ b/Week6 Sliding game solver/build.xml
@@ -0,0 +1,73 @@
+
+
+
+
+
+
+
+
+
+
+ Builds, tests, and runs the project Week6 Sliding game solver.
+
+
+
diff --git a/Week6 Sliding game solver/manifest.mf b/Week6 Sliding game solver/manifest.mf
new file mode 100644
index 0000000..328e8e5
--- /dev/null
+++ b/Week6 Sliding game solver/manifest.mf
@@ -0,0 +1,3 @@
+Manifest-Version: 1.0
+X-COMMENT: Main-Class will be added automatically by build
+
diff --git a/Week6 Sliding game solver/nbproject/build-impl.xml b/Week6 Sliding game solver/nbproject/build-impl.xml
new file mode 100644
index 0000000..7738925
--- /dev/null
+++ b/Week6 Sliding game solver/nbproject/build-impl.xml
@@ -0,0 +1,1413 @@
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+ Must set src.dir
+ Must set test.src.dir
+ Must set build.dir
+ Must set dist.dir
+ Must set build.classes.dir
+ Must set dist.javadoc.dir
+ Must set build.test.classes.dir
+ Must set build.test.results.dir
+ Must set build.classes.excludes
+ Must set dist.jar
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+ Must set javac.includes
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+ No tests executed.
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+ Must set JVM to use for profiling in profiler.info.jvm
+ Must set profiler agent JVM arguments in profiler.info.jvmargs.agent
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+ Must select some files in the IDE or set javac.includes
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+ To run this application from the command line without Ant, try:
+
+ java -jar "${dist.jar.resolved}"
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+ Must select one file in the IDE or set run.class
+
+
+
+ Must select one file in the IDE or set run.class
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+ Must select one file in the IDE or set debug.class
+
+
+
+
+ Must select one file in the IDE or set debug.class
+
+
+
+
+ Must set fix.includes
+
+
+
+
+
+
+
+
+
+ This target only works when run from inside the NetBeans IDE.
+
+
+
+
+
+
+
+
+ Must select one file in the IDE or set profile.class
+ This target only works when run from inside the NetBeans IDE.
+
+
+
+
+
+
+
+
+ This target only works when run from inside the NetBeans IDE.
+
+
+
+
+
+
+
+
+
+
+
+
+ This target only works when run from inside the NetBeans IDE.
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+ Must select one file in the IDE or set run.class
+
+
+
+
+
+ Must select some files in the IDE or set test.includes
+
+
+
+
+ Must select one file in the IDE or set run.class
+
+
+
+
+ Must select one file in the IDE or set applet.url
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+ Must select some files in the IDE or set javac.includes
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+ Some tests failed; see details above.
+
+
+
+
+
+
+
+
+ Must select some files in the IDE or set test.includes
+
+
+
+ Some tests failed; see details above.
+
+
+
+ Must select some files in the IDE or set test.class
+ Must select some method in the IDE or set test.method
+
+
+
+ Some tests failed; see details above.
+
+
+
+
+ Must select one file in the IDE or set test.class
+
+
+
+ Must select one file in the IDE or set test.class
+ Must select some method in the IDE or set test.method
+
+
+
+
+
+
+
+
+
+
+
+
+
+ Must select one file in the IDE or set applet.url
+
+
+
+
+
+
+
+
+ Must select one file in the IDE or set applet.url
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
diff --git a/Week6 Sliding game solver/nbproject/genfiles.properties b/Week6 Sliding game solver/nbproject/genfiles.properties
new file mode 100644
index 0000000..cb500dc
--- /dev/null
+++ b/Week6 Sliding game solver/nbproject/genfiles.properties
@@ -0,0 +1,8 @@
+build.xml.data.CRC32=af7e9351
+build.xml.script.CRC32=13880061
+build.xml.stylesheet.CRC32=8064a381@1.75.2.48
+# This file is used by a NetBeans-based IDE to track changes in generated files such as build-impl.xml.
+# Do not edit this file. You may delete it but then the IDE will never regenerate such files for you.
+nbproject/build-impl.xml.data.CRC32=af7e9351
+nbproject/build-impl.xml.script.CRC32=d44e7934
+nbproject/build-impl.xml.stylesheet.CRC32=876e7a8f@1.75.2.48
diff --git a/Week6 Sliding game solver/nbproject/project.properties b/Week6 Sliding game solver/nbproject/project.properties
new file mode 100644
index 0000000..7e69501
--- /dev/null
+++ b/Week6 Sliding game solver/nbproject/project.properties
@@ -0,0 +1,75 @@
+annotation.processing.enabled=true
+annotation.processing.enabled.in.editor=false
+annotation.processing.processors.list=
+annotation.processing.run.all.processors=true
+annotation.processing.source.output=${build.generated.sources.dir}/ap-source-output
+application.title=Week6 Sliding game solver
+application.vendor=camilstaps
+build.classes.dir=${build.dir}/classes
+build.classes.excludes=**/*.java,**/*.form
+# This directory is removed when the project is cleaned:
+build.dir=build
+build.generated.dir=${build.dir}/generated
+build.generated.sources.dir=${build.dir}/generated-sources
+# Only compile against the classpath explicitly listed here:
+build.sysclasspath=ignore
+build.test.classes.dir=${build.dir}/test/classes
+build.test.results.dir=${build.dir}/test/results
+# Uncomment to specify the preferred debugger connection transport:
+#debug.transport=dt_socket
+debug.classpath=\
+ ${run.classpath}
+debug.test.classpath=\
+ ${run.test.classpath}
+# Files in build.classes.dir which should be excluded from distribution jar
+dist.archive.excludes=
+# This directory is removed when the project is cleaned:
+dist.dir=dist
+dist.jar=${dist.dir}/Week6_Sliding_game_solver.jar
+dist.javadoc.dir=${dist.dir}/javadoc
+endorsed.classpath=
+excludes=
+includes=**
+jar.compress=false
+javac.classpath=
+# Space-separated list of extra javac options
+javac.compilerargs=
+javac.deprecation=false
+javac.processorpath=\
+ ${javac.classpath}
+javac.source=1.7
+javac.target=1.7
+javac.test.classpath=\
+ ${javac.classpath}:\
+ ${build.classes.dir}
+javac.test.processorpath=\
+ ${javac.test.classpath}
+javadoc.additionalparam=
+javadoc.author=false
+javadoc.encoding=${source.encoding}
+javadoc.noindex=false
+javadoc.nonavbar=false
+javadoc.notree=false
+javadoc.private=false
+javadoc.splitindex=true
+javadoc.use=true
+javadoc.version=false
+javadoc.windowtitle=
+main.class=Main
+manifest.file=manifest.mf
+meta.inf.dir=${src.dir}/META-INF
+mkdist.disabled=false
+platform.active=default_platform
+run.classpath=\
+ ${javac.classpath}:\
+ ${build.classes.dir}
+# Space-separated list of JVM arguments used when running the project.
+# You may also define separate properties like run-sys-prop.name=value instead of -Dname=value.
+# To set system properties for unit tests define test-sys-prop.name=value:
+run.jvmargs=-ea
+run.test.classpath=\
+ ${javac.test.classpath}:\
+ ${build.test.classes.dir}
+source.encoding=UTF-8
+src.dir=src
+test.src.dir=test
diff --git a/Week6 Sliding game solver/nbproject/project.xml b/Week6 Sliding game solver/nbproject/project.xml
new file mode 100644
index 0000000..b58c22b
--- /dev/null
+++ b/Week6 Sliding game solver/nbproject/project.xml
@@ -0,0 +1,15 @@
+
+
+ org.netbeans.modules.java.j2seproject
+
+
+ Week6 Sliding game solver
+
+
+
+
+
+
+
+
+
diff --git a/Week6 Sliding game solver/src/Configuration.java b/Week6 Sliding game solver/src/Configuration.java
new file mode 100644
index 0000000..7264c5f
--- /dev/null
+++ b/Week6 Sliding game solver/src/Configuration.java
@@ -0,0 +1,21 @@
+import java.util.Collection;
+
+
+/**
+ * An interface for representing nodes in a state space.
+ *
+ * @author Sjaak Smetsers
+ * @version 1.2
+ * @date 28-02-2015
+ */
+public interface Configuration extends Comparable {
+ /*
+ * To obtain the successors for a specific configuration
+ * @return a collection of configurations containing the successors
+ */
+ public Collection successors ();
+ /*
+ * For marking final / solution configurations.
+ */
+ public boolean isSolution ();
+}
diff --git a/Week6 Sliding game solver/src/Direction.java b/Week6 Sliding game solver/src/Direction.java
new file mode 100644
index 0000000..d4837b9
--- /dev/null
+++ b/Week6 Sliding game solver/src/Direction.java
@@ -0,0 +1,26 @@
+/**
+ * @author Sjaak Smetsers
+ * @version 1.2
+ * @date 28-02-2015
+ * An enumeration type for the 4 points of the compass
+ * Each constant has 2 (final) int attributes indicating
+ * the displacement of each direction on a 2-dimensional grid
+ * of which the origin is located in the upper left corner
+ */
+public enum Direction {
+ NORTH (0,-1), EAST (1,0), SOUTH(0,1), WEST(-1,0);
+
+ private final int dx, dy;
+ private Direction (int dx, int dy) {
+ this.dx = dx;
+ this.dy = dy;
+ }
+
+ public int GetDX () {
+ return dx;
+ }
+
+ public int GetDY () {
+ return dy;
+ }
+}
diff --git a/Week6 Sliding game solver/src/Main.java b/Week6 Sliding game solver/src/Main.java
new file mode 100644
index 0000000..4225013
--- /dev/null
+++ b/Week6 Sliding game solver/src/Main.java
@@ -0,0 +1,35 @@
+/**
+ * Solutions for the assignments of week 6.
+ * @author Camil Staps, s4498062
+ */
+public class Main
+{
+
+ /**
+ * Create a new sliding game, attempt to solve it and if it succeeds show a solution.
+ * @param args command-line arguments are ignored.
+ */
+ public static void main(String[] args) {
+ // Some examples:
+ // N = 5
+ //int[] x = {7,17,9,4,5,1,12,15,6,10,3,23,25,14,8,22,2,18,19,24,16,21,11,13,20}; // May take some time (that is, it did not find a solution after some hours here, I didn't check if there is one)
+ //int[] x = {2,4,6,8,10,1,3,5,7,9,12,14,16,18,20,11,13,15,17,19,21,22,23,24,25}; // Solution in 90
+ // N = 4
+ //int[] x = {2,3,10,11,14,1,13,15,5,4,8,7,6,12,9,16}; // Solution in 112
+ //int[] x = {10,8,16,7,6,13,15,3,14,1,4,2,5,9,12,11}; // Solution in 144
+ //int[] x = {9,12,5,4,2,16,7,11,3,6,10,13,14,1,8,15}; // Solution in 140
+ // N = 3
+ //int[] x = {8,7,6,5,4,3,1,2,9}; // No solution (evaluates 292102 different boards before failing)
+ int[] x = {5,9,3,4,6,2,8,7,1}; // Solution in 35
+
+ SlidingGame sg = new SlidingGame(x);
+ System.out.println("Solving:\n" + sg);
+ Solver s = new Solver(sg);
+ if (s.solve()) {
+ System.out.println("Success!");
+ System.out.println(s.getWinner());
+ } else {
+ System.out.println("Failure...");
+ }
+ }
+}
diff --git a/Week6 Sliding game solver/src/Node.java b/Week6 Sliding game solver/src/Node.java
new file mode 100644
index 0000000..cb5c900
--- /dev/null
+++ b/Week6 Sliding game solver/src/Node.java
@@ -0,0 +1,92 @@
+import java.util.ArrayList;
+
+/**
+ * For maintaining lists of T-elements enabling
+ * a structure suited for backwards traversal
+ *
+ * @author Pieter Koopman, Sjaak Smetsers
+ * @author Camil Staps, s4498062
+ *
+ * @param The element this node is based on
+ */
+@SuppressWarnings("Convert2Diamond") // We disable these warnings for Java <=1.7 compatibility.
+public class Node implements Comparable>
+{
+ // the data field
+ private final T item;
+ // a reference to the predecessor
+ private final Node previous;
+
+ /* A constructor that initializes each node
+ * with the specified values
+ * @param from the node preceding the current node
+ * @param item the initial data item
+ */
+ public Node (Node from, T item) {
+ this.previous = from;
+ this.item = item;
+ }
+
+ /* a getter for the item
+ * @return item
+ */
+ public T getItem() {
+ return item;
+ }
+
+ /*
+ * a getter for the predecessor
+ * @return previous
+ */
+ public Node getPrevious() {
+ return previous;
+ }
+
+ /*
+ * determines the length of the current list
+ * @return the length as an integer
+ */
+ public int length () {
+ int length = 1;
+ Node prev = previous;
+ while ( prev != null ) {
+ prev = prev.previous;
+ length++;
+ }
+ return length;
+ }
+
+ @Override
+ public String toString() {
+ StringBuilder result = new StringBuilder();
+
+ ArrayList> path;
+ path = new ArrayList>();
+ Node prev = this;
+ while ( prev != null ) {
+ path.add(prev);
+ prev = prev.previous;
+ }
+
+ for (int i = path.size() - 1; i >= 0; i--)
+ result.append(path.size() - i - 1).append(":\n").append(path.get(i).getItem().toString());
+
+ return result.toString();
+ }
+
+ /**
+ * Just comparing the items isn't very clever. The Manhattan distance is a fairly small number.
+ * With large queues, many nodes will then have the same priority. It's much better to select
+ * on both Manhattan distance and path length. That way, we will find shorter paths.
+ * Note though that since we're prioritizing on Manhattan distance primarily, this does not
+ * mean that we necessarily find the shortest path.
+ * @param t
+ * @return
+ */
+ @Override
+ public int compareTo(Node t) {
+ if (this.item.compareTo(t.item) == 0)
+ return Integer.compare(length(), t.length());
+ return this.item.compareTo(t.item);
+ }
+}
diff --git a/Week6 Sliding game solver/src/SlidingGame.java b/Week6 Sliding game solver/src/SlidingGame.java
new file mode 100644
index 0000000..0e80797
--- /dev/null
+++ b/Week6 Sliding game solver/src/SlidingGame.java
@@ -0,0 +1,205 @@
+import java.util.ArrayList;
+import java.util.Collection;
+
+/**
+ * @author Pieter Koopman, Sjaak Smetsers
+ * @author Camil Staps, s4498062
+ *
+ * A template implementation of a sliding game also
+ * implementing the Graph interface
+ */
+@SuppressWarnings("Convert2Diamond") // We disable these warnings for Java <=1.7 compatibility.
+public class SlidingGame implements Configuration
+{
+ public static final int N = 3, SIZE = N * N, HOLE = SIZE;
+
+ /*
+ * The board is represented by a 2-dimensional array;
+ * The position of the hole is kept in 2 variables holeX and holeY
+ * We store the summed manhattan of all tiles and the hole in manhattan
+ */
+ private final int [][] board;
+ private int holeX, holeY;
+ private final int manhattan;
+
+ /*
+ * A constructor that initializes the board with the specified array
+ * @param start: a one dimensional array containing the initial board.
+ * The elements of start are stored row-wise.
+ */
+ public SlidingGame (int [] start) {
+ board = new int[N][N];
+
+ assert start.length == SIZE: "Length of specified board incorrect";
+
+ for( int p = 0; p < start.length; p++) {
+ board[p % N][p / N] = start[p];
+ if ( start[p] == HOLE ) {
+ holeX = p % N;
+ holeY = p / N;
+ }
+ }
+
+ manhattan = calculateManhattan();
+ }
+
+ /**
+ * A constructor that initialises the board with a specified 2D array
+ * @param board a 2D array containing the initial board
+ */
+ public SlidingGame (int[][] board) {
+ this.board = new int[N][N];
+
+ assert board.length == N: "Length of specified board incorrect";
+
+ for (int a = 0; a < N; a++) {
+ assert board[a].length == N: "Length of specified board incorrect";
+ for (int b = 0; b < N; b++) {
+ this.board[a][b] = board[a][b];
+ if (board[a][b] == HOLE) {
+ holeX = a;
+ holeY = b;
+ }
+ }
+ }
+
+ manhattan = calculateManhattan();
+ }
+
+ /**
+ * Calculate the summed Manhattan distance for all tiles and the hole
+ * @return the Manhattan distance
+ */
+ private int calculateManhattan() {
+ int result = 0;
+ for (int x = 0; x < N; x++) {
+ for (int y = 0; y < N; y++) {
+ int this_x = (board[x][y] - 1) % N;
+ int this_y = (board[x][y] - 1) / N;
+ result += Math.abs(this_x - x) + Math.abs(this_y - y);
+ }
+ }
+ return result;
+ }
+
+ public int getManhattan() {
+ return manhattan;
+ }
+
+ /**
+ * Attempt to move the hole in a specified direction
+ * @param d the direction in which to move
+ * @return A new instance of this class where the hole has moved
+ * @throws ArrayIndexOutOfBoundsException If the hole cannot be moved
+ */
+ private SlidingGame move(Direction d) throws ArrayIndexOutOfBoundsException {
+ int[][] newboard = new int[N][N];
+ for (int a = 0; a < N; a++)
+ System.arraycopy(board[a], 0, newboard[a], 0, N);
+
+ newboard[holeX][holeY] = newboard[holeX + d.GetDX()][holeY + d.GetDY()];
+ newboard[holeX + d.GetDX()][holeY + d.GetDY()] = HOLE;
+ return new SlidingGame(newboard);
+ }
+
+ /*
+ * Converts a board into a printable representation.
+ * The hole is displayed as a space.
+ * @return the string representation
+ */
+ @Override
+ public String toString() {
+ StringBuilder buf = new StringBuilder();
+ for (int row = 0; row < N; row++) {
+ for (int col = 0; col < N; col++) {
+ int puzzel = board[col][row];
+ // Using String.format to pad left as in http://stackoverflow.com/a/391978/1544337; provides better formatting for puzzles with N > 3
+ buf.append(String.format("%1$" + ((int) Math.log10(SIZE - 1) + 2) + "s", puzzel == HOLE ? " " : puzzel + " "));
+ }
+ buf.append("\n");
+ }
+ return buf.toString();
+ }
+
+ /*
+ * A standard implementation of equals checking whether 2 boards are filled
+ * in exactly the same way.
+ * @return true iff this object and o are equal
+ */
+ @Override
+ public boolean equals(Object o) {
+ if (o == null || o.getClass() != getClass()) {
+ return false;
+ } else {
+ SlidingGame other_puzzle = (SlidingGame) o;
+ for (int row = 0; row < N; row++) {
+ for (int col = 0; col < N; col++) {
+ if (board[col][row] != other_puzzle.board[col][row]) {
+ return false;
+ }
+ }
+ }
+ return true;
+ }
+ }
+
+ @Override
+ public boolean isSolution () {
+ for( int p = 0; p < SIZE; p++) {
+ if (board[p % N][p / N] != p + 1) {
+ return false;
+ }
+ }
+ return true;
+ }
+
+ @Override
+ public Collection successors () {
+ Collection successors = new ArrayList();
+ try {
+ successors.add(move(Direction.EAST));
+ } catch (ArrayIndexOutOfBoundsException e) {}
+ try {
+ successors.add(move(Direction.SOUTH));
+ } catch (ArrayIndexOutOfBoundsException e) {}
+ try {
+ successors.add(move(Direction.WEST));
+ } catch (ArrayIndexOutOfBoundsException e) {}
+ try {
+ successors.add(move(Direction.NORTH));
+ } catch (ArrayIndexOutOfBoundsException e) {}
+ return successors;
+ }
+
+ /**
+ * According to the assignment we should use:
+ * result += board[x][y] * Math.pow(31, x + N*y);
+ * However, this results for even small boards in INT_MAX, so this is not very useful.
+ *
+ * Giving every board a unique hash would be:
+ * result += board[x][y] * Math.pow(SIZE, x + N*y);
+ * However, already with N=4 that results in INT_MAX as well.
+ *
+ * The current implementation uses SIZE as base and subtracts n(n-1) from the exponent.
+ * This results in values well below INT_MAX for N up to 5 (and possibly higher).
+ * Of course, it also means that different puzzles may have the same value.
+ * For N>3 this is unavoidable since 16! > INT_MAX. For N <= 3 we are not too concerned
+ * since the program is fast enough for small programs for us to accept this imperfectness.
+ */
+ @Override
+ public int hashCode() {
+ int result = 0;
+ for (int x = 0; x < N; x++)
+ for (int y = 0; y < N; y++)
+ result += board[x][y] * Math.pow(SIZE, x + N*y - (N-1)*N);
+
+ return result;
+ }
+
+ @Override
+ public int compareTo(Configuration t) {
+ SlidingGame tsg = (SlidingGame) t;
+ return manhattan - tsg.getManhattan();
+ }
+
+}
diff --git a/Week6 Sliding game solver/src/Solver.java b/Week6 Sliding game solver/src/Solver.java
new file mode 100644
index 0000000..9b78f27
--- /dev/null
+++ b/Week6 Sliding game solver/src/Solver.java
@@ -0,0 +1,55 @@
+import java.util.HashSet;
+import java.util.PriorityQueue;
+import java.util.Queue;
+
+/**
+ * A class that implements a breadth-first search algorithm
+ * for finding the Configurations for which the isSolution predicate holds
+ *
+ * @author Pieter Koopman, Sjaak Smetsers
+ * @author Camil Staps, s4498062
+ */
+@SuppressWarnings("Convert2Diamond") // We disable these warnings for Java <=1.7 compatibility.
+public class Solver
+{
+ // A queue for maintaining graphs that are not visited yet.
+ private final Queue> toExamine = new PriorityQueue>();
+ private final HashSet examined = new HashSet();
+
+ private Node winner = null;
+
+ public Solver(Configuration g) {
+ toExamine.add(new Node(null, g));
+ }
+
+ /* A skeleton implementation of the solver
+ * @return a string representation of the solution
+ */
+ public boolean solve () {
+ while (!toExamine.isEmpty()) {
+ Node next = toExamine.remove();
+ Configuration nextConfiguration = (Configuration) next.getItem();
+ examined.add(nextConfiguration);
+ if (nextConfiguration.isSolution()) {
+ winner = next;
+ return true;
+ } else {
+ for (Configuration succ: nextConfiguration.successors()) {
+ if (!examined.contains(succ)) {
+ toExamine.add(new Node(next, succ));
+ }
+ }
+ }
+ }
+ return false;
+ }
+
+ /**
+ * Return the winning Node (from which the path can be reconstructed)
+ * @return the node in which we found a solution
+ */
+ public Node getWinner() {
+ return winner;
+ }
+
+}
diff --git a/Week6 Sliding game solver/week6.tar.gz b/Week6 Sliding game solver/week6.tar.gz
new file mode 100644
index 0000000..b5bca35
Binary files /dev/null and b/Week6 Sliding game solver/week6.tar.gz differ
--
cgit v1.2.3