Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$?

share|improve this question
    
In an NxN crossword, will you only allow 4 letter words, og N letter words? –  utdiscant Mar 3 '12 at 18:49
    
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. –  Bravo Mar 3 '12 at 18:54
    
Can you give me an example of a solution for a 5x5 grid then? –  utdiscant Mar 3 '12 at 18:56
    
So that would be a British-style crossword grid? –  Henning Makholm Mar 3 '12 at 19:08
    
Yes, British-style grid it is. It is the standard in India as well. –  Bravo Mar 3 '12 at 19:11
show 3 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.