Final Project MATH 686 Timothy Boafo-Adade Heesoo Jeon **Contents** - Statement of Problem - Mathematical Framework - Methodology (description of algorithm) - Mathematical coding in Mathematica - DATA - Conclusion - Improvements ----------- **Statement of Problem** A jigsaw puzzle is not always easy to accomplish by ones manual handwork. Instead of figuring out each puzzle piece by hands, it can be done mathematically. In this project, we will demonstrate how linear algebra can be used to solve a jigsaw puzzle. ------------------ **Mathematical Framework** If two pieces of a puzzle connect, we assume the artwork on the edges where they connect should be similar. If this is the case, then the pixel values along those edges should be similar as well. If we take the values along the edge as points in $\mathbb{R}^n$ where $n$ is the number of elements that give relevant information, then the distance between these points should be smaller than the distance between the points corresponding to the edge of any other piece. To find the distance between two points, $P_1$ in the first piece and $P_2$ in another piece must create a vector $${\bf v} = \overline{P_2-P_1}.$$ Then we take the norm, $$||{\bf v}|| = \sqrt{v_1^2 + v_2^2 + ... + v_?^2}.$$ Say our puzzle has $p$ pieces, then we should have $p$ norms. The pieces will have the correct orientation so we do not have to worry about the norms of the rotation of each piece. We simply have to pair tops to bottoms and left sides to right sides. We assume that the the pieces with the smallest norms will have the highest probability of matching. --------------------- **Methodology (description of algorithm)** For this project, we will write a code in Mathematica to solve puzzles. We attempted to write a program that takes information about the appearance of each piece and compare them to see if they are a match. We selected puzzles where each piece is oriented in its proper position so we don't have to take any rotations into consideration. We will also ignore the shape of the puzzle for now. First we import an image of each piece into Mathematica. Then we convert each image into a matrix. The entries give information about the pixel in that position of the image. Every component of the matrix is a vector in $\mathbb{R}^4$, where each entry corresponds to the amount of red, blue and green present in each pixel as well as the brightness. $$\begin{pmatrix} red \\ blue \\ green \\ brightness \end{pmatrix}$$ The brightness of each pixel for every image is set to 1 so it does not give us any relevant information about that piece. So we will disregard that component. We break the matrix into three set of matrices where the entries of each matrix are taken from the red, blue and green component of each vector. We will perform our experiment using each set of matrices. For this project, we built our intial code based on a 9-pieces jigsaw puzzle, which will be used to demonstrate how the code works. Then the code will be generalized to any size puzzle. $$\begin{bmatrix} p_{1,1} & p_{1,2} & \dots & p_{1,n}\\ p_{2,1} & p_{2,2} & \dots & p_{2,n}\\ \vdots & \vdots & \ddots & \vdots\\ p_{n,1} & p_{n,2} & \dots & p_{n,n} \end{bmatrix}$$ For this process, we will have to feed the code some initial data, therefore it is up to us to set the first piece in its proper position. Ideally we want to set the piece $p_{1,1}$. From that, the program will use the edge to guess the the next piece in the series. We can either go vertically or horizontally; we will go with the former. The program will begin the process of best match, setting the pieces, $p_{2,1},p_{3,1},...,p_{n,1}$. Once the first column is complete, it will repeat the same process horizontally for each piece until the matrix is filled. --------- **DATA** For this project, we built our intial code based on n x n jigsaw puzzle. Specifically, we will use a 9 pieces puzzle whose final product will be $3 \times 3$. In order to eliminate any variables that will skew our result, any part of the background that is not a part of the piece must be black, so that the RBG norm is 0. The rows and columns associated with outward connections have less information and cannot be used as an edge. However rows and columns associated with inward connections as well as non-connecting edges have significant information. -------------------- **Conclusion** Our code currently does not take into account how many pixel we need to get an accurate result. That is a possible reason why the code does not put the pieces together properly. ----------------- **Improvements** Instead of examining each piece by its pixel value, we would have to look into a shape of the piece and then compare the shape of the edge in each piece to match with the edge in a difference piece.