# Sudoku Distances

From REU@MU

The Sudoku Distances problem is a graph theoretic problem closely related to the Traveling Salesman Problem.

## Problem Definition

Consider a 9 by 9 Sudoku grid. Suppose that within this grid, the player wishes to write one specific digit in *k* different squares around the grid. From an arbitrary starting point, what is the shortest path for the player to take through all *k* squares?

## Notation and Formalization

- We represent a Sudoku grid as a weighted graph, in which every square is represented by a vertex, and edges connect all vertices. In other words, we represent a Sudoku grid as
*K*._{81} - The edge between two squares
*a*and*b*is weighted according to the distance between*a*and*b*, which is determined by some distance metric. We use*d(a,b)*to denote the distance between two points. - We define a path
*p*as a sequence of vertices*a*. Since our graph is simple (i.e. there is only one edge between any two vertices), we can omit the edges from our representation of a path._{1}a_{2}...a_{n} - We define the
*cost*of a path*c(p)*to be the sum of*d(a*for all_{i}, a_{i+1})*a*which are adjacent in_{i}, a_{i+1}*P*.

## Project Goals

- Use a smaller to larger approach to determine formations for k = 2, 3, 4, ... and solve the shortest path question for the puzzle.
- Prove that the result is the shortest path.
- Develop algorithms that are best for each of the distance definitions.