Nonrepetitive Paths and Cycles in Graphs with Application to Sudoku

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.

• Publication year

  2005

• Venue

  arXiv.org

• Publication date

  2005-07-20

• Fields of study

  Mathematics, Computer Science

• Identifiers
  arXiv cs/0507053
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Complexity and Completeness of Finding Another Solution and Its Application to Puzzles

  2003influential reference
• Unique maximum matching algorithms

  1999cited by this paper
• Path problems in skew-symmetric graphs

  1994cited by this paper
• Paths, Trees, and Flowers

  1965cited by this paper
• Color Coding

  1962cited by this paper
• and as an in

  year unknowninfluential reference

• Unveiling Order in Chaos: A Systematic Approach Based on Graph Theory in Enumerating Sudoku Grids of Rank n

  2025cites this paper
• Comparison of Sudoku Solving Skills of Preschool Children Enrolled in the Montessori Approach and the National Education Programs Yıldız Güven1, Cihat Gültekin1, A. Beyzanur Dedeoğlu1

  2020cites this paper
• Latin Puzzles

  2016cites this paper
• A Novel Hybrid Flower Pollination Algorithm with Chaotic Harmony Search for Solving Sudoku Puzzles

  2014cites this paper
• A Comparative Study On The Performance CharacteristicsOf Sudoku Solving Algorithms

  2014cites this paper
• Solution and Level Identification of Sudoku Using Harmony Search

  2013cites this paper
• Solving Single-Digit Sudoku Subproblems

  2012influential citation
• Automated word puzzle generation using topic models and semantic relatedness measures

  2012cites this paper
• Orthogonal Sudoku Square Designs with Block Effect Discrimination

  2011cites this paper
• An Efficient Approach to Solve Sudoku Problem by Harmony Search Algorithm

  2011cites this paper
• Modeling the 8-queens problem and Sudoku using an algorithm based on projections onto nonconvex sets

  2010cites this paper
• A Comparison of Two Methods for Completing Sudoku Puzzles

  2010cites this paper
• Permutation matrices related to Sudoku

  2009cites this paper
• A general approach to using problem instance data for model refinement in constraint satisfaction problems

  2008influential citation
• A SURVEY OF NP-COMPLETE PUZZLES

  2008cites this paper
• Solving Sudoku Using Combined Message Passing Algorithms

  2007influential citation
• Harmony Search Algorithm for Solving Sudoku

  2007cites this paper
• Software for Teaching Modeling of Integer Programming Problems

  2006influential citation
• Searching for Memories, Sudoku, Implicit Check Bits, and the Iterative Use of Not-Always-Correct Rapid Neural Computation

  2006cites this paper
• Sudoku as a Constraint Problem

  2005cites this paper
• Rapid Mathematical Programming or How to Solve Sudoku Puzzles in a Few Seconds

  2005influential citation