algorithms

# WoShi Power

I estimate, that currently at least 1000 scheduling computer programs exists in the wild. Marketing people attached to nearly every one of them, will tell you two things.

First, you can’t schedule entirely automatically, it is a NP hard problem.

Second, their software does it the best possible way.

As Aristotle already knew, marketing people are liars.

So, I have devised a little test: Can your software, tweaked if need be, “schedule” a small 3D crossword? 5 times 5 times 5, thus of 125 letters, with no black fields, in such a way that every North-South, every Est-West and every up-down word inside this cube, is a valid English word, according to some real life dictionary?

In other words, 25 N-S, 25 E-W and 25 u-d words in a legit 3D (cubical) crossword. Or 15 classical 2D crosswords (with no black fields) interwoven in a cube.

As far as I know, it hasn’t been done before. Perhaps it was just too difficult for humans and for programs. Here is one of many WoShi’s results:

asses
salat
slave
eaten
stert

latah
agami
tabor
amove
hirer

alate
labor
ibota
tomes
erase

amove
tomes
evert
resty

arend
rarer
erase
nests
dress

A five slices cube, you can rotate it if you wish, to get the other two orientations.

Standard

## 4 thoughts on “WoShi Power”

1. msjr says:

Can there be a 5×5 square without repeating any word in it?

• Sure. The number of repetitions hasn’t been specified here yet, but it’s possible to set them to 1. Every word once at the most.

Or to freeze a certain word and so on. With adding some black fields, the edge could be bigger.

(5x5x5, from the current dictionary of 11000+ words, there is about 10^113 possible different configurations. A tinny fraction of them are consistent. Perhaps 1 in 10^70. What gives us 10^40 or so puzzles.)

But beyond the testing of an algorithm, what do you think, would it be an interesting puzzle for solving? I wonder how to display it to a crosswords loving user?

2. msjr says:

A small daily crossword would be nice. The system could be just like puzzles (crossword has the same functionallity as sudoku) on http://www.logicgamesonline.com/

• Now, I have some Slovenian language cubuses also. Even though the dictionary I have is 3 times smaller than the English one. Which is 3500 against 11500 words 5 letters long.