Minimizing Total Distance in Sudoku Number Entry

Mentor: Dr. Kim Factor

Overview: Sudoku has gained a huge following over the decade. It originates from Latin Squares, a combinatorial structure. There has been aspects of the Sudoku puzzle that have been modeled and analyzed using graph. In this project the use of graph theory applies when allowing a 9x9 Sudoku square be modeled using a graph where every one of the 81 squares is represented by a vertex, with an edge between vertices if they share an edge in the puzzle. We will be defining the "distance" between two squares as the graph distance between the vertices and creating a weighted graph from the original graph that will contain only the vertices that need to be filled in and all edges between the vertices where the weight of the shortest path between each is given.