Combus

Crosswords are perhaps my biggest hobby. I have published many puzzles in top Romanian crossword magazines, such as Rebus Flacara, and on my own crossword site Rebus Online.

In my spare time, I program a grid composer called Combus, which is used both as a research tool, to experiment with new ideas, and as a practical tool, to generate puzzles for the free online crossword server Rebus Online.

Research-wise, Combus achieves stronger results than all previous work reported in the AI literature that I'm aware of. Combus has been used as a tool for a detailed study of crossword puzzles as a constraint problem. Part of the study and of the Combus' architecture are described in an article available for download in the "Publications" section.

On the practical side, Combus is used to compose puzzles for the Rebus Online site. Some of the puzzles generated with Combus are next to impossible to create by hand. Some interesting grids that Combus is capable to build include:
  • 13x13 triangle with no blocked cells. When using an "official" dictionary, this is the largest triangle in Romanian.
  • 13x13 diamond with no blocked cells. As before, this is the maximal size for which solutions exist.
  • 9x9 square grids with 2 blocked cells.
  • 11x11 square grids with 6 blocked cells.
  • 13x13 square grids with 12 blocked cells.
  • 15x15 square grids with 17 blocked cells.
  • Grids where all words are a restricted class of anagrams called "100% anagrams". Compared to 100% anagrams puzzles composed by human experts, Combus' grids have features such as:
    • Longer words.
    • Fewer blocked cells.
    • The blocked cells are arranged symmetrically.
  • Grids where all words placed horizontally belong to a theme (e.g., given names). The advantages mentioned in the case of 100% anagrams are present in this class of puzzles as well.

My dream is to win the National Grid Composition Contest, a highly prestigious event organized yearly by the Romanian magazine Rebus Flacara. So far, only humans have entered this competition. At this time, Combus is not prepared to compete, as the problems in the competition differ from regular crossword puzzles in two fundamental aspects:
  • The initial state contains no blocked cells. These will be added dynamically as the composition process evolves. I believe that this requires major changes to a solver because a constraint propagation approach, which is successful in regular puzzles, might have to be replaced by a heuristic search approach.
  • There is a scoring function to distinguish between solutions. Therefore, even after finding one or several solutions, one should continue searching for a better solution.