Is it a Valid Crossword Grid?

Question

In crossword terminology, the grid is the region into which the crossword answers are inserted, consisting of white and black squares. The crossword answers, called entries, are inserted into contiguous sequences of white squares in a row or column, separated by black squares.

For straight (American) crosswords, the grids usually follow a specific set of rules:

• They should have 180 degree rotational symmetry (if there is a black square in the \$x\$th row and \$y\$th column, there should be a black square in the \$x\$th-to-last row and \$y\$th-to-last column).
• All entries must be at least 3 squares long.
• All white squares must be joined in a single region.
• No row/column can be completely filled with black squares.
• Every white cell/square must be the intersection of both a horizontal and a vertical entry.

Some examples of invalid and valid crossword grids:

Your challenge: given a grid consisting of two unique values representing black and white squares, determine if it's a valid crossword grid. Assume that it's a square grid with \$n\$ rows and columns (so there are \$n^2\$ white/black cells), where \$n \geq 3\$. (You can take input in any reasonable format -- e.g. a 2D array.) For example, if \$n=3\$ there is only one valid grid (I'm using . for white cells and # for black cells):

...
...
...

If \$n=4\$, there are 3 valid grids:

....  #...  ...#
....  ....  ....
....  ....  ....
....  ...#  #...

If \$n=5\$, there are 12 valid grids:

.....  #....  ##...  #....  ##...  ##...  
.....  .....  .....  #....  #....  ##...  
.....  .....  .....  .....  .....  .....  
.....  .....  .....  ....#  ....#  ...##  
.....  ....#  ...##  ....#  ...##  ...##  

....#  ...##  ....#  ...##  ...##  #...#  
.....  .....  ....#  ....#  ...##  .....  
.....  .....  .....  .....  .....  .....  
.....  .....  #....  #....  ##...  .....  
#....  ##...  #....  ##...  ##...  #...#  

Examples:

Input	Output	Explanation
.........	True	Valid grid
#..............#	True	Valid grid
...#........#...	True	Valid grid
.........................	True	Valid grid
##...#.............#...##	True	Valid grid
.................................................	True	Valid grid
........................#........................	True	Valid grid
....###.....##......##.....##......##.....###....	True	Valid grid
................................................................	True	Valid grid
##....####....##...........##......##...........##....####....##	True	Valid grid
...##.......#...........##.....##.....##...........#.......##...	True	Valid grid
#...............	False	No 180 degree symmetry
#...#......#...#	False	2-letter entries
#..##..##..##..#	False	2-letter entries, filled-in columns
#........................	False	No 180 degree symmetry
.......#...###...#.......	False	1-letter and 1-letter entries
######....#....#....#....	False	No 180 degree symmetry, filled-in column & row
######...##...##...######	False	Filled-in columns & rows
...#......#......#......#......#......#......#...	False	White squares not contiguous, filled-in column
.................###....#....###.................	False	1-letter entries
...#......#...............##.....................	False	No 180-degree symmetry
....#.......#.......#........######........#.......#.......#....	False	White squares not contiguous
..#.........#.......#......##......#.......#.......#.........#..	False	1-letter and 2-letter entries
.#......#..............................................#......#.	False	1-letter entries, white squares not contiguous
...........................##......#............................	False	No 180-degree symmetry
####............................................................	False	No 180-degree symmetry
#......##......##......##......##......##......##......##......#	False	Filled-in columns

Standard loopholes are forbidden. Shortest code wins.

Answer 1

Jelly, 40 35 33 bytes

-5 thanks to Nick Kennedy!

;ZµŒg§’:2;§Ȧ
ŒṪḢạ§ỊẸʋƇ@ƬiƊȧÇȧU⁼ṚƊ

A monadic Link that accepts a list of lists of 1s (white) and 0s (black) that yields 1 if valid or 0 if not.

Try it online! Or see the test-suite.

How?

;ZµŒg§’:2;§Ȧ - Link 1 (check entry lengths & presence): list of lists of 1/0, Grid
;Z           - concatenate the columns
  µ          - start a new monadic chain - f(rows + columns)
   Œg        - group runs of equal elements of each row/column
     §       - sums of each run
      ’      - decrement (i.e... all black: -1, 1:0, 2:1, 3:2, 4:3, 5: 4, ...)
       :2    - integer divide by two        -1    0    0    1,   1,    2, ...
          §  - {rows + columns} sums
         ;   - concatenate
           Ȧ - any and all? -> 0 if either: an entry of length 1 or 2 exists, or
                                            any row or column has no entry
                               else 1

ŒṪḢạ§ỊẸʋƇ@ƬiƊȧÇȧU⁼ṚƊ - Main Link: list of lists of 1/0, Grid
ŒṪ                   - multidimensional truthy indices -> "WhiteCoordinates)
            Ɗ        - last three links as a monad - f(WhiteCoordinates):
  Ḣ                  -   head (first coordinate -> initial "Current")
          Ƭ          -   collect up while distinct, applying:
         @           -     with swapped arguments - i.e. f(WhiteCoordinates, Current):
        Ƈ            -       filter keep those (of WhiteCoordinates) for which:
       ʋ             -         last four links as a dyad - i.e. f(WhiteCoordinates, Current):
   ạ                 -           absolute difference (vectorises)
    §                -           sum each
     Ị               -           insignificant? (effectively "in (0,1)?")
      Ẹ              -           any? - i.e. any are neighbours/same?
           i         -   index of {WhiteCoordinates} in that (or 0)
                        -> 1 if white cells are fully connected else 0
              Ç      - call link 1
             ȧ       - logical AND
                   Ɗ - last three links as a monad - f(Grid):
                U    - {Grid} reverse each
                  Ṛ  - {Grid} reverse
                 ⁼   - equal? -> 1 if 180-degree symmetry else 0
               ȧ     - logical AND

---

Also at 33 as a lone Link (although it performs redundant checks):

,ZµŒg§’:2;U⁼ṚƊ;ŒṪḢạ§ỊẸʋƇ@ƬiƊ$;§)Ȧ

Answer 2

Python3, 562 bytes:

E=enumerate
def g(b,B):
 q=[(x,y)for x,y in B if b[x][y]=='.']
 Q=[q.pop(0)];S=[Q[0]]
 for x,y in Q:
  for X,Y in[(1,0),(-1,0),(0,-1),(0,1)]:
   u=(x+X,y+Y)
   if u in B and u not in S and'.'==b[x+X][y+Y]:Q+=[u];S+=[u]
 return not{*q}-{*S}
F=lambda x,l,c=0,k=0:k if not x else F(x[1:],l,(T:=c+(x[0]==l))*(x[0]==l),max(k,T))
def f(n,b):
 B=[(x,y)for x,r in E(b)for y,_ in E(r)]
 D=[(x,y)for x,y in B if'#'==b[x][y]]
 return all((n-x-1,n-y-1)in D for x,y in D)and g(b,B)and all(F(i,'.')>2and F(i,'#')<n for i in b)and all(F(i,'.')>2and F(i,'#')<n for i in zip(*b))

Try it online!

Answer 3

Retina 0.8.2, 186 183 bytes

\.
-
s`^(?!(.)+.?(?<-1>\1)+$(?(1)^)).+

ms`.*^#+$.*|.*(?<!-)--?(?!-).*

O$`.
$.%`
ms`.*^#+$.*|.*(?<!-)--?(?!-).*

1`-
@
+m`^((.)*)(@|-)(.*¶(?<-2>.)*(?(2)$))?(?!\3)[@-]
$1@$4@
^[¶#@]+$

Try it online! Takes input as a square array and outputs 1 for valid, 0 for invalid. Explanation:

\.
-

Change .s to -s are they're easier to match.

s`^(?!(.)+.?(?<-1>\1)+$(?(1)^)).+

Delete everything if it isn't rotationally symmetric.

ms`.*^#+$.*|.*(?<!-)--?(?!-).*

Delete everything if there is a row of #s or if there are one or two -s on their own.

O$`.
$.%`

Transpose the array.

ms`.*^#+$.*|.*(?<!-)--?(?!-).*

Check the transpose for a row of #s or one or two -s on their own.

1`-
@

Change one - to a @.

+m`^((.)*)(@|-)(.*¶(?<-2>.)*(?(2)$))?(?!\3)[@-]
$1@$4@

Flood fill -s with @s. Note that I use (?(2)$) although I used (?(1)^) above because this is a multiline match and so the final character could be at the beginning of a line.

^[¶#@]+$

Check that all of the -s were filled.

Answer 4

JavaScript (ES11), 176 bytes

Saved 1 byte thanks to @tsh

Expects a binary matrix, with 1 for white cells and 0 for black cells. Returns a Boolean value.

f=(m,i)=>m<(h=z=>m=m.map((r,y)=>r.map((v,x)=>z?/^(0*222+)+0*$/.test(r.join``)?m[x][m.length-1-y]:z:v&[-1,0,1,2].some(d=>m[y+d%2]?.[x+~-d%2]==i)?i=2:v)))()?f(m,i):h``+""==h(h``)

Attempt This Online!

How?

The same helper function h is used to process two passes:

1. We flood-fill the matrix, replacing 1's with 2's. We start at the first empty cell located on a border. If it doesn't exist, the grid is invalid anyway and will be identified as such during the next pass.

2. We rotate the matrix 3 times by 90°. We convert each resulting row to a string and make sure that it matches the following regular expression:

   /^(0*222+)+0*$/
   

   i.e. the entire string is made of groups of three or more 2's (with at least one such group) and optional groups of 0's.

   Finally, we make sure that the 3rd rotation leads to the same matrix as the 1st one to validate the 180° rotational symmetry.

Commented

f = (                        // f is a recursive function taking:
  m,                         //   m[] = input binary matrix
  i                          //   i = flag used during flood-filling,
) =>                         //       initially undefined
m < (                        // compare m[] with its updated version
  h = z =>                   // h is a helper function ...
  m =                        // ... which updates m[]
  m.map((r, y) =>            // for each row r[] at index y in m[]:
    r.map((v, x) =>          //   for each value v at index x in r[]:
      z ?                    //     if z is truthy:
        /^(0*222+)+0*$/      //       if r[], once converted to a string,
        .test(r.join``) ?    //       matches this regular expression:
          m[x]               //         apply a 90° rotation
          [m.length - 1 - y] //
        :                    //       else:
          z                  //         force the final test to fail (*)
      :                      //     else:
        v &                  //       if v = 1
        [-1, 0, 1, 2]        //       and there's some direction d
        .some(d =>           //       such that:
          m[y + d % 2]       //         the neighbor cell
          ?.[x + ~-d % 2]    //         in that direction
          == i               //         is equal to i
        ) ?                  //       then:
          i = 2              //         set i and the cell to 2
        :                    //       else:
          v                  //         leave this cell unchanged
    )                        //   end of inner map()
  )                          // end of outer map()
)() ?                        // if m[] was modified after flood-filling:
  f(m, i)                    //   try to flood-fill some more
:                            // else:
  h`` + "" == h(h``)         //   do the 1st and 3rd rotation match?

_{(*) For the 1st and 2nd rotations, z is set to [''], which is coerced to an empty string. For the 3rd rotation, it is set to the result of the 2nd rotation.}

Answer 5

Charcoal, 67 bytes

Ｆθ⊞υＳ¿⁼υＥ⮌υ⮌ι¿⬤⁺υＥθ⭆θ§λκ∧№ι.⬤⪪ι#÷⊖Ｌ벫Ｅυ⭆ι⎇⁼λ.ψλＪ⌕θ.⁰¤.¿‹ＬＫＡＬΣυ⎚«⎚¹

Try it online! Link is to verbose version of code. Takes input as a square array of strings and outputs a Charcoal boolean, i.e. - for valid, nothing if not. Explanation:

Ｆθ⊞υＳ

Input the square array.

¿⁼υＥ⮌υ⮌ι

Check that it's rotationally symmetric.

¿⬤⁺υＥθ⭆θ§λκ∧№ι.⬤⪪ι#÷⊖Ｌ벫

Concatenate the array with its transpose and check that each row contains a . but when split on #s does not contain runs of exactly 1 or 2 .s.

Ｅυ⭆ι⎇⁼λ.ψλ

Write just the #s from the array to the canvas.

Ｊ⌕θ.⁰

Jump to a position where there should be a ..

¤.

Fill the canvas with .s starting from here.

¿‹ＬＫＡＬΣυ⎚

If this didn't fill all of the original .s then just clear the canvas.

«⎚¹

If all of the .s were connected then clear the canvas and output -.

Answer 6

JavaScript (Node.js), 245 bytes

s=>new Set([...s].map(p=(c,i,a)=>c^1||[n=s.length**.5|0,(m=(s,t,v=a[t])=>v&&''+v!=s?(b=v=>v[0].at?b(v[0]):v)(s)[0]=v:s)(m(a[p=~i+~n]=[p],p-~n),p+1),+a.at(~i),a[i+~n]|a[i-~n]&a[i-~n*2],a[i-1]|a[i+1]&a[i+2]]).flat(1/0)).size<4*!s[-p]*/^1/m.test(s)

Try it online!

Input a multi line string, 1 for white cells, 0 for black cells, line break (\n) separate each rows. Output true or false.

---

JavaScript, 263 bytes

a=>new Set(a.map((r,y)=>[r.map(e=(c,x)=>!c||[(m=(s,t,v=a[t])=>v&&''+v!=s?(b=v=>v[0][1]?v:b(v[0]))(s)[0]=v:s)(m(a[p=x+[,y]]=[p],[x-1,y]),[x,y-1]),e=a.at(~y).at(~x),a[y-1]?.[x]||a[y+1]?.[x]&&a[y+2]?.[x],r[x-1]||r[x+1]&&r[x+2]]),e,a.some(r=>r[y])]).flat(1/0)).size<3

f=

a=>new Set(a.map((r,y)=>[r.map(e=(c,x)=>!c||[(m=(s,t,v=a[t])=>v&&''+v!=s?(b=v=>v[0][1]?v:b(v[0]))(s)[0]=v:s)(m(a[p=x+[,y]]=[p],[x-1,y]),[x,y-1]),e=a.at(~y).at(~x),a[y-1]?.[x]||a[y+1]?.[x]&&a[y+2]?.[x],r[x-1]||r[x+1]&&r[x+2]]),e,a.some(r=>r[y])]).flat(1/0)).size<3

const parse = (s, n = s.length ** .5) => [...Array(n)].map((_, i) => [...s.slice(i * n, (i + 1) * n)].map(v => v === '.'));
const testcases = `
......... True
##.....................## True
#..............# True
...#........#... True
...#........#... True
......................... True
##...#.............#...## True
................................................. True
........................#........................ True
....###.....##......##.....##......##.....###.... True
................................................................ True
##....####....##...........##......##...........##....####....## True
...##.......#...........##.....##.....##...........#.......##... True
#............... False
#...#......#...# False
#..##..##..##..# False
#........................ False
.......#...###...#....... False
######....#....#....#.... False
######...##...##...###### False
...#......#......#......#......#......#......#... False
.................###....#....###................. False
...#......#...............##..................... False
....#.......#.......#........######........#.......#.......#.... False
..#.........#.......#......##......#.......#.......#.........#.. False
.#......#..............................................#......#. False
...........................##......#............................ False
####............................................................ False
#......##......##......##......##......##......##......##......# False
`.trim().split('\n').map(r => [parse(r.split(' ')[0]), r.endsWith('True')])

testcases.forEach(([i, e]) => {
  console.log(f(i), e);
});

Input boolean matrix, output true or false.

a=>new Set(
  a.map((r,y)=>[
    r.map(e=(c,x)=>!c||[ // for each cell, which is either empty or
      // generate an unique symbol for its connected area
      (m=(s,t,v=a[t])=>v&&''+v!=s?(b=v=>v[0][1]?v:b(v[0]))(s)[0]=v:s)(m(a[p=x+[,y]]=[p],[x-1,y]),[x,y-1]),
      // its 180 rotated position is non-empty
      e=a.at(~y).at(~x),
      // its ^ cell is non-empty or its v and vv cells are non-empty
      a[y-1]?.[x]||a[y+1]?.[x]&&a[y+2]?.[x],
      // its < cell is non-empty or its > and >> cells are non-empty
      r[x-1]||r[x+1]&&r[x+2]
    ]),
    // at least one non-empty cell this row
    e,
    // at least one non-empty cell this column
    a.some(r=>r[y])
  ]).flat(1/0)
).size<3 // if every non-empty cell connected, they have same symbol (count as 1)
         // if all other condition holds, they will be all true (count as 1)

Transpose the matrix also costs 263 bytes, maybe someone can golf one of them a bit

m=>new Set([m,m.map((r,y)=>r.map((_,x)=>m[x][y]))].map(a=>a.map((r,y)=>[r.map(e=(c,x)=>!c||[a==m||(m=(s,t,v=a[t])=>v&&''+v!=s?(b=v=>v[0][1]?v:b(v[0]))(s)[0]=v:s)(m(a[p=x+[,y]]=[p],[x-1,y]),[x,y-1]),e=a.at(~y).at(~x),r[x-1]||r[x+1]&&r[x+2]]),e])).flat(1/0)).size<3

Answer 7

R, 196 185 184 177 176 bytes

\(x,`~`=t,`+`=sum,a=apply,e=~which(x,T),i=~~e[,1],`?`=any){while(+i<+(i=e[,a(e,2,\(y)?colSums((i-y)^2)<2)]))1
+i-+e?x-rev(x)?a(rbind(x,~x),1,\(y,z=rle(y))?!(z$v*z$l-1)%/%2&+y)}

Attempt This Online!

A function taking a square matrix of logical values and returning a single logical value. This was inspired by and works more or less the same as @JonathanAllan’s Jelly answer so be sure to upvote that one too!

Thanks to @pajonk for saving 9 bytes!

Answer 8

J, ^{95 93} 92 bytes

(2<*#])@((#;._2"1@,.&0,&,0=1&#.)@,|:)*/@,(-:|."1@|.),&,[:(]+.+./ .*)^:_~1=[:|@-/~$j./@#:I.@,

Attempt This Online!

-2 thanks to Neil's idea of catting transpose with input instead of using over

Takes input as a 0-1 matrix, where 1 means empty space.

Answer 9

05AB1E, 61 bytes

˜ƶIgôΔ2Fø0δ.ø}2Fø€ü3}*εεÅsyøÅs«à]˜0KÙgIDø«εÅγsÏ3@DgĀª}˜`IÂíQP

Input as as matrix of 1s for white squares and 0s for black squares.
Outputs a 05AB1E-truthy/falsey result, so 1 as truthy, and 0 or a positive integer as falsey.

Try it online or verify all test cases.

Explanation:

Step 1: Verify rule "All white squares must be joined in a single region.":

˜             # Flatten the (implicit) input-matrix to a single list
 ƶ            # Multiply each value by its 1-based index (so all 1s become unique)
  Igô         # Convert this list back into a matrix equal of the input-dimensions 
Δ             #  Loop until it no longer changes to flood-fill:
 2Fø0δ.ø}     #   Add a border of 0s around the matrix:
 2F     }     #    Loop 2 times:
   ø          #     Zip/transpose; swapping rows/columns
     δ        #     Map over each row:
    0 .ø      #      Add a leading/trailing 0
 2Fø€ü3}      #   Convert it into overlapping 3x3 blocks: 
 2F    }      #    Loop 2 times again:
   ø          #     Zip/transpose; swapping rows/columns
    €         #     Map over each inner list:
     ü3       #      Convert it to a list of overlapping triplets
 *            #   Multiply each 3x3 block by the value in the (implicit) input-matrix
              #   (so the 0s remain 0s)
 εεÅsyøÅs«à   #   Get the largest value from the horizontal/vertical cross of each 3x3
              #   block:
 εε           #    Nested map over each 3x3 block:
   Ås         #      Pop and push its middle row
     y        #      Push the 3x3 block again
      ø       #      Zip/transpose; swapping rows/columns
       Ås     #      Pop and push its middle rows as well (the middle column)
         «    #      Merge the middle row and column together to a single list
          à   #      Pop and push its maximum
]             #  Close the nested maps, flood-fill loop, and outer loop
 ˜            # Flatten the resulting flood-filled matrix
  0K          # Remove all 0s (the black squares)
    Ù         # Uniquify the values of each island
     g        # Pop and push its length (which is 1 if it was a single island of 1s)

Try just step 1 online for all test cases.

Step 2: Verify rules "All entries must be at least 3 squares long." and "No row/column can be completely filled with black squares.":

I             # Push the input-matrix again
 D            # Duplicate it
  ø           # Zip/transpose the copy; swapping its rows/columns
   «          # Merge the two matrices together
    ε         # Map over each inner list:
     Åγ       #  Run-length encode it; pushing a list of values and lengths
       s      #  Swap so the values are at the top
        Ï     #  Only keep the lengths for the truthy (==1) values
         3@   #  Check for each whether it's >= 3
         D    #  Duplicate this list
          g   #  Pop and push its length
           Ā  #  Check whether it's truthy (>= 0)
            ª #  Append this check to the list
    }˜        # After the map: Flatten the list of lists
      `       # Pop and dump all values to the stack
...
P             # Take the product of all values on the stack

Try just step 2 online for all test cases.

Step 3: Verify rule "They should have 180 degree rotational symmetry.":

I             # Push the input-matrix yet again
 Â            # Bifurcate it; short for Duplicate & Reverse
  í           # Also reverse each inner row
   Q          # Check if the two matrices are still the same

Try just step 3 online for all test cases.

Step 4: Combine all checks and output the result:

P             # Pop all values on the stack and push its product
              # (which is output implicitly as result)