4 ms·
These crosswords are NP-hard! D: Here's a short encoding of 3SAT: Alphabet: [01] Number of variables: N Columns: one for each clause, i.e.: r/.0...|..1.
by throwaway_yy2Di 12y ago
These crosswords are NP-hard! D: Here's a short encoding of 3SAT:
Alphabet: [01]
Number of variables: N
Columns: one for each clause, i.e.:
r/.0...|..1..|....1/
(-x2 V x3 V x5)
They're disjunctions of three regexps of length N. Each alternative fixes one positional variable to either 0 or 1, and ignores the rest.
Rows: one for each variable, forcing it to be single-valued across the clauses:
r/0+|1+/
- schoen 12y agoWell, that sure cured me of the intuition that these square grid regexp crossword puzzles were inherently easier than the original hexagonal grid version!