CODEWITHSUNDEEP
algorithmoptimizationlanguage-agnosticpseudocodecrossword
Munahil
Munahil

Reputation: 2419

Efficient algorithm to generate crosswords (NYtime's style)

I want to find an efficient way to generate Crosswords. I have read solutions mentioned here. This generates an easy crossword, where as I am looking for an efficient and optimised way to generate crosswords like in New York times. i.e, when you rotate the puzzle 180 degrees, it looks the same (black squares remain in the same position). Here, we can assume that grid is initially generated, and we can use any more than three letter word.

What is the best approach to do so? What search algorithm can we use to lessen the number of iterations and make it less time consuming?

Upvotes: 4

Views: 2368

Answers (1)

Robbie Dee
Robbie Dee

Reputation: 1977

I approached the problem from a different angle for another (unfinished) word game. In my design, boards were selected if they could be mirrored across the X or Y axis (or both).

Taking a square of size N, I built up all the possible grids using a bit mask taking 2^cell count -1 as the maximum value. So for a grid 2x2 (4 cells), go from 0...15.

0 - empty grid

1 - black block in top left

2 - black block in top right

3 - black blocks in the top row

.

.

.

15 - grid full of black blocks

Clearly this yields many non-suitable candidates. We can drop:

  • Patterns where the rows don't match either side of the half-way point (and so on outwards) for Y-axis mirroring
  • Patterns where the columns don't match either side of the half-way point (and so on outwards) for the X-axis mirroring
  • Grids full of black blocks
  • Patterns where the extents of the grid (first row, last row, first column, last column) have no white blocks
  • Patterns where white blocks are isolated (*)

I think I ran this up to about 7x7 and it finished in a reasonable length of time. What I didn't get to was selecting the words. However, once you have crunched the numbers, you can simply store all the candidate values for each grid size and then just create new crosswords each time.

(*) - for the game I was writing, this was important but I'm not 100% sure this is a requirement for a crossword. Having 2 or more distinct patterns of white squares on various sections of the board (however this is configured) could I suppose be perfectly valid.

Upvotes: 0

Related Questions