Difference between revisions of "Sudoku Distances"
From REU@MU
(→Notation and Formalization) |
(→Notation and Formalization) |
||
| Line 8: | Line 8: | ||
* 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<sub>81</sub>''. | * 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<sub>81</sub>''. | ||
* 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. | * 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<sub>1</sub>a<sub>2</sub>...a<sub>n</sub>''. Since our graph is simple (i.e. there is only one edge between two | + | * We define a path ''p'' as a sequence of vertices ''a<sub>1</sub>a<sub>2</sub>...a<sub>n</sub>''. 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. |
* We define the ''cost'' of a path ''c(p)'' to be the sum of ''d(a<sub>i</sub>, a<sub>i+1</sub>)'' for all ''a<sub>i</sub>, a<sub>i+1</sub>'' which are adjacent in ''P''. | * We define the ''cost'' of a path ''c(p)'' to be the sum of ''d(a<sub>i</sub>, a<sub>i+1</sub>)'' for all ''a<sub>i</sub>, a<sub>i+1</sub>'' which are adjacent in ''P''. | ||
Revision as of 17:02, 3 June 2016
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 K81.
- 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 a1a2...an. 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.
- We define the cost of a path c(p) to be the sum of d(ai, ai+1) for all ai, ai+1 which are adjacent in P.
