7
$\begingroup$

I was staring at my crossword this morning when I had this question: How many possible arrangement of grid squares are there in an $N\times N$ crossword, provided we impose certain constraints? I take the following standard constraints present in leading dailies.

A) Only four-letter words or more are permissible. B) Every alternate letter of every word must be check-able, i.e., must have an intersecting word. For example, for a five-letter word, letters $1$, $3$ and $5$ must intersect with other words, or letters $2$ and $4$ must do so.

I took up the example of $N=4$. I obtained 4 possible grid-fills. If $A=[a_{ij}]$ is the grid matrix, I shaded the following sets of elements in the $4$ solutions:

1) $a_{22},\ a_{24},\ a_{42},\ a_{44}$
2) $a_{11},\ a_{13},\ a_{31},\ a_{33}$
3) $a_{21},\ a_{23},\ a_{41},\ a_{43}$
4) $a_{12},\ a_{14},\ a_{32},\ a_{34}$

Is it possible to apply combinatoric theory to derive a general solution for arbitrary $N$?

  • 0
    In an NxN crossword, will you only allow 4 letter words, og N letter words?2012-03-03
  • 0
    I meant words with 4 letters or more. The maximum is obviously $N$, unless it is a phrase etc, which may not affect this problem.2012-03-03
  • 0
    Can you give me an example of a solution for a 5x5 grid then?2012-03-03
  • 0
    So that would be a [British-style](http://en.wikipedia.org/wiki/Crossword#Types_of_grid) crossword grid?2012-03-03
  • 0
    Yes, British-style grid it is. It is the standard in India as well.2012-03-03
  • 0
    @utdiscant: One example would be to blacken $a_{22},a_{24},a_{42},a_{44}$. The crossword will have 3 across clues and 3 down clues.2012-03-03
  • 0
    If you type *crossword* into the search window at http://oeis.org/ you will be supplied with several sequences and much information about them. I don't know whether any of the sequences matches your specs exactly, but even if not the references may get you started on the road to a solution.2012-03-04
  • 0
    just thinking out loud.... What about a Sparse/Dense Matrix approach ?2013-03-02
  • 0
    The trivial puzzle (all-blacked-in grid) seems to satisfy your conditions.2015-01-23
  • 0
    The British crosswords I've seen have the across words in odd rows, the down words in odd columns, and each row and column has at least one word. This seems more restrictive, but probably easier to solve.2015-01-23

0 Answers 0