Difference between revisions of "Sudoku Distances"
From REU@MU
(→Notation and Formalization) |
|||
| (4 intermediate revisions by 2 users not shown) | |||
| Line 1: | Line 1: | ||
| − | The Sudoku Distances problem is a graph theoretic problem closely related to the | + | The Sudoku Distances problem is a graph theoretic problem closely related to the Traveling Salesman Problem. |
== Problem Definition == | == Problem Definition == | ||
| 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 (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''. | ||
| + | |||
| + | == 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. | ||
Latest revision as of 02:09, 4 June 2016
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 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.
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.
