Nonrepetitive Paths and Cycles in Graphs with Application to Sudoku

Details Nonrepetitive Paths and Cycles in Graphs with Application to Sudoku Nonrepetitive Paths and Cycles in Graphs with Application to Sudoku

2005-07-20

arxiv.org/abs/cs/0507053v1

Computer Science

Data Structures and Algorithms

17 pages, 11 figures

Scientific paper

We provide a simple linear time transformation from a directed or undirected graph with labeled edges to an unlabeled digraph, such that paths in the input graph in which no two consecutive edges have the same label correspond to paths in the transformed graph and vice versa. Using this transformation, we provide efficient algorithms for finding paths and cycles with no two consecutive equal labels. We also consider related problems where the paths and cycles are required to be simple; we find efficient algorithms for the undirected case of these problems but show the directed case to be NP-complete. We apply our path and cycle finding algorithms in a program for generating and solving Sudoku puzzles, and show experimentally that they lead to effective puzzle-solving rules that may also be of interest to human Sudoku puzzle solvers.

Affiliated with

Also associated with

No associations

Rating

Nonrepetitive Paths and Cycles in Graphs with Application to Sudoku does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Nonrepetitive Paths and Cycles in Graphs with Application to Sudoku, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Nonrepetitive Paths and Cycles in Graphs with Application to Sudoku will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-491193