Difference between revisions of "Sudoku Distances"
From REU@MU
(→Notation and Formalization) |
|||
| (2 intermediate revisions by the same user 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 10: | Line 10: | ||
* 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 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.
