Report.tex

\documentclass{article}

\title{(short) Report on N puzzle solver.}
\author{F Engelbrecht}
\date{13 May 2015}

\begin{document}
	\maketitle

	\section{Introduction.}

	The problem is to solve a N puzzle problem in the least amount of moves and
	to find out what those moves are in the least amount of time.

	\section{Design and Implementation.}

	\subsection{Algorithm for checking unsolvable.}

	Create two Linklists. The first Linklist has two values, weight and value.
	The first node has a value of 1 and the last node has a value of N*N-1 (N
	is the board width/height). The weight for each node is 0. Read through 
	the current board.  As a number is read travers through the linklist 
	incrementing each node weight until a node with the same value as the 
	number read. Pop off the value and add it to the second Linklist.
	\\
	If N*N is odd and the sum of all the weights in the second Linklist is even
	then the board is solvable. If N*N is even and the sum of the sum of the
	weights in the second Linklist and the row position is odd then the board
	is also solvable. If the board does not fulfill these requirements then the
	board is unsolvable.

	\subsection{Algorithm for solving.}

	A Linklist is created with the following values. A two dimensional array 
	that stores the current board state. A value that stores the current weight
	of the board. A value that stores the amount of moves made by this current
	state. Two values that store the y and x coordinates of the empty space. A
	Linklist of previous moves and a pointer to another state in the list.
	\\
	The node at the head of the Linklist is popped off and then all possible 
	moves are played on the board and saved as new states. The states are then
	added to the Linklist in ascending order determined by the weight. The top 3
	nodes are then evaluated to see if there are finished boards among them. The
	process is then repeated until a finished board is found.

	\subsection{Algorithm for parallel solving.}

	A Linklist is created with the following values. A two dimensional array
	that stores the current board state. A value that stores the current weight
	of the board. A value that stores the amount of moves made by this current 
	state. Two values that store the y and x coordinates of the empty space. A
	Linklist of previous moves and a pointer to another state in the list.

	The original node is then popped off and then all possible moves are played
	on the board and saved as new states. The states are then added to the
	Linklist in ascending order determined by the weight.

	The top 3 nodes are then evaluated to see if there are finished boards among
	them. All the nodes in the Linklist are then popped off and all their
	possible moves are then played and saved as new states. The states are then
	added to the Linklist in ascending order determined by the weight. This
	process is repeated once more.

	The link list now has a min size of 10 (for N > 3). The board states are
	then equally divided between all processes except the last one. From here on
	the solution is solved serially with a few MPI messages sent between the
	processes to determine termination.

	The message being sent is an array. Each indecency corresponds to a
	processor rank which represents the maximum moves the process is allowed to
	make. This value changes when one of the processes reaches a solved board. 
	It changes its value to the amount of moves it took to solve the board and
	then sends the array to the next process ( (rank + 1) \% nr of processes ).

	The process then receives the array and stores it in a temporary array. It 
	then loops through the array and compares its values with those of the 
	array’s values updating them if they are less than its current values, it 
	then also updates its own maximum moves to that value if the value is more 
	than or equal to 0.

	The new maximum move limit could cause a process to throughout its entire
	Linklist. When this happens the process will set its maximum move limit to
	-1. The process will then send its array of maximum moves to the next
	process.

	The receive process is the same as previously described. If none of these
	events occur then the process just sends its array of  maximum moves. The 
	process then does the receiving process as previously described.

	The processes that either finds a solution or has an empty link list will go
	into a loop. In the loop they will send their current array and receive as
	previously described, but when a maximum moves is found that is than their
	current one and is more than or equal to 0 it will change its own value to 
	-1. They will then loop through the array and count how many negative one's
	are there and break the loop if there was only one value that was not 
	negative one.

	The rank that did not have a negative one has the solution.



\end{document}