mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Puzzles (https://www.mersenneforum.org/forumdisplay.php?f=18)

 Bobby Jacobs 2021-02-06 02:47

Crosswords

Crosswords usually obey the following 3 rules.

1. The grid is symmetrical, the same upside-down.
2. The grid is connected.
3. Every word has at least 3 letters.

What is the most words that can fit in a 15*15 crossword puzzle?

 xilman 2021-02-06 11:39

[QUOTE=Bobby Jacobs;570965]Crosswords usually obey the following 3 rules.

1. The grid is symmetrical, the same upside-down.
2. The grid is connected.
3. Every word has at least 3 letters.

What is the most words that can fit in a 15*15 crossword puzzle?[/QUOTE]Blocks or bars?

 retina 2021-02-06 11:44

[QUOTE=Bobby Jacobs;570965]Crosswords usually obey the following 3 rules.

1. The grid is symmetrical, the same upside-down.
2. The grid is connected.
3. Every word has at least 3 letters.

What is the most words that can fit in a 15*15 crossword puzzle?[/QUOTE]Does the answer have to follow those usual rules? Or are those three usual rules just for informational purposes?

 Dr Sardonicus 2021-02-06 13:04

Assuming each word is within a single row or column, and is at least three letters, there can't be more than 5 words in any row or column. So there can't be more than 75 "across" words or 75 "down" words. No more than 150 words all told.

Assuming further that the beginning and end of each word is at either an edge or a blacked-in square (a general crossword rule which I cheerfully ignored in the above) will knock down the number of possible words. Trivially the number of "across" and "down" words drops to at most 60 each, and the total to at most 120.

The number of "across" and "down" clues in most daily (15x15) crosswords I've worked have each generally been in the mid to upper thirties IIRC (it's been a while) so in practice there are probably between 70 and 80 words in a 15x15 crossword puzzle.

For printed puzzles, the number of words is also limited by the amount of space available.

 Uncwilly 2021-02-06 16:48

[QUOTE=xilman;570972]Blocks or bars?[/QUOTE]
Absent word from the OP, assume blocks. That is the norm on-line and much of the word. It adds to the challenge.
[QUOTE=retina;570974]Does the answer have to follow those usual rules? Or are those three usual rules just for informational purposes?[/QUOTE]
Those 3 are the recognized rules for a typical CW. A Sunday one might have a larger grid. One done for your local Hūsker Dū? club with members names likely won't fulfill the symmetric rule, nor filling the square.

 xilman 2021-02-06 17:56

[QUOTE=Uncwilly;571002]Absent word from the OP, assume blocks. That is the norm on-line and much of the word. It adds to the challenge.[/QUOTE]This challenge, perhaps. I have not tried to solve it.

The most challenging regularly published crossword is generally held to be [I][URL="https://listenercrossword.com/"]The Listener[/URL][/I] which almost always uses bars. I have solved one of their puzzles fewer than ten times in about 30 years of trying (though I haven't tried every one of them) and won precisely once, about 25 years ago.

 slandrum 2021-02-07 00:37

[QUOTE=Dr Sardonicus;570978]Assuming each word is within a single row or column, and is at least three letters, there can't be more than 5 words in any row or column. So there can't be more than 75 "across" words or 75 "down" words. No more than 150 words all told.

Assuming further that the beginning and end of each word is at either an edge or a blacked-in square (a general crossword rule which I cheerfully ignored in the above) will knock down the number of possible words. Trivially the number of "across" and "down" words drops to at most 60 each, and the total to at most 120.[/QUOTE]

If there are 60 across words, then there are blocks completely filling 3 columns and no other blocks on the grid, so the number of down words would be 12 words (of 15 letters apiece) which would lead to a total of only 72 words. If the grid is sub-sectioned into 3x3 grids then you have 48 across and 48 down for a total of 96 words. This though violates another rule - the grid is not connected.

 retina 2021-02-07 00:53

If you completely fill the grid with 15 letter words, then counting all embedded words will give the maximum possible.

15 + 15 = 30 x 15-letters
15x2 + 15x2 = 60 x 14-letters
...
15x14 + 15x14 = 420 x 2-letters
15x15 + 15x15 = 450 x 1-letter
[code]~ echo 30*{1..15}+ 0|bc
[b]3600[/b][/code]:showoff:

 0scar 2021-02-08 04:24

nice puzzle; not sure about minimality of my candidates.

"bars" version, fixing 150-word near-solution by Dr Sardonicus.
5 words and 4 bars per row/column;
150 words, 120 bars placed along 8 lines, 25 disconnected 3x3 squares;
symmetry holds, restore grid connection by removing 24 bars;
any bar removal merges two words, so 150 - 24 = 126 words?

[SPOILER]Example with both upside-down and left-right symmetry:
label rows and columns from 1 to 15;
remove all bars from row 8 and from columns 2,5,8,11,14.[/SPOILER]

"block" version, fixing 96-word near-solution by slandrum.
3 rows and 3 columns containing blocks only;
4 words and 3 blocks per remaining row/column;
96 words, 81 blocks placed along 6 lines, 16 disconnected 3x3 squares;
symmetry holds, restore grid connection by removing 15 blocks;
so 96-15 = 81 words?

[SPOILER]We can connect 4 squares by removing 3 contiguous blocks:
two pairs of 3-letter words are merged into two 7-letter words, a new 3-letter word is built.
So 96-5 = 91 words?
Example with both upside-down and left-right symmetry (0=letter, 1=block):
000100010001000
000100010001000
000100010001000
110001111100011
000100010001000
000100010001000
000100010001000
111111000111111
000100010001000
000100010001000
000100010001000
110001111100011
000100010001000
000100010001000
000100010001000[/SPOILER]

 Bobby Jacobs 2021-02-11 23:54

I am talking about blocked crosswords. By the way, your blocked crossword contains some 1-letter words (unchecked letters). Every letter must be part of a word going across and a word going down.

 SmartMersenne 2021-02-12 02:18

I think the problem is not very clear to everyone. You may help by providing some small cases to clarify all your points.

All times are UTC. The time now is 22:45.