Sudoku Distances

The Sudoku Distances problem is a graph theoretic problem closely related to the Travelling 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<\sub>.
• The edge between two points 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 walk w as a sequence of vertices a₁a₂...a_n. Since our graph is simple (there is only one edge between two specific vertices), we can omit the edges from our representation of a path.
• We define the cost of a path <math> \sum_{i=0}^n-1 d(a_i,a_i+1) <\math>