IMI Interdisciplinary Mathematics InstituteCollege of Arts and Sciences

The complexity of some regex crossword problems

  • Jan. 23, 2015
  • 2:15 p.m.
  • LeConte 312


In a regex crossword puzzle, you are given two lists $R _ 1, \ldots, R _ m$ and $C _ 1, \ldots, C _ n$ of regular expressions, and your goal is to fill in an $m$-by-$n$ grid with letters so that the $i^{th}$ row matches $R _ i$ and the $j^{th}$ column matches $C _ j$, for all $i$ and $j$. Such a grid is a solution to the puzzle. It is known that determining whether a solution exists is NP-complete. We consider a number of restrictions and variants to this problem where all the $R _ i$ are equal to some regular expression $R$, and all the $C _ j$ are equal to some regular expression $C$.

See for example puzzles.

© Interdisciplinary Mathematics Institute | The University of South Carolina Board of Trustees | Webmaster