RevDijkstra

Reverse Dijkstra's algorithm and The Crossword Filling Problem

How does Dijkstra's algorithm apply to puzzle Crossword manufacture?
Dijkstra's algorithm is a way to find the shortest path between two points
ie if you are in Sydney city in Australia and want to travel to Paramatta
by train do you via Hornsby or Strathfield? yeah no worries just pull out your
GPS and let it do the walking :)
Ah but your GPS phone connection has broken down  and you only
have the calculator working while waiting at the lights in Sydney's terrible
motor traffic.

You usually go about this problem in distance travelling by checking the
length of these points by measuring the kilometers between them and finding
the shortest path.

Reverse Dijkstra

But crosswords are a different problem in crosswords you want to go the
LONGEST path because you want to fill the crosswords with the longest and
as many words as possible ( so you can make it tough and interesting
and you can print the xword on smaller piece of paper)
um so ........... how to go about it?

You must have lists of crosswords already compiled for this program
once you have your sorted lists by word size you can use the program
to insert them given the word length as a value ie if you start at
the top left and go to the bottom right of the xword then take as many
jumps to get there as you can and give each jump a value given by the
words length so example pseudo-code follows

Say we have 2 series of words that go trough part of the xword puzzle
the first will get to the same place as the second but the
first uses
10-20-16-21 will be higher then a series of words like
8-13-20-9   so choose the first group in the 4 then go to the next
position in the xword and choose another group to test until you get
to the bottom of the xword do this 10 times and compare each version
to get the final product (comparing more than 10 will produce higher
values but will start to take  N infinity) time.

Ok so onto pseudo ..........

look at position of cursor will we get closer to finish point by
taking a this jump in this direction?

yes forward no check another direction down or across

check length of words so we can find the longest that
goes in that direction to fill the x word.

next check to see if we can go in any direction or do we have to
abandon this length of string (4 linked words) and return to
original cursor position to fill the requirements
create/find another 4 words to get us forward.

are we at the finish point if not have we made enough to continue
by jumping to the finish point and working backwards? (some groups
may be favorable to others even if they don't finish as they have
such high scores we may keep them anyway.
 

Some problems in code construction.

1.

What positions to take? would it be better to give the algo the first
top left and the bottom right and let it rip? or do it in piecemeal
jumps say for the top 3 lines of the xword and then check?

I will try the piecemeal version first as it is more natural for me
to test algo's when they are created first and as they
progress. Hey i just got a idea for
my xword it's Jason and the AlgoNauts :)

2.

Um but i digress ah.... yes another problem is remembering previous
groups if i have tested some groups before i don't need the processor
time to check that group again. So for this i probably need some
construction like a stringList to keep my previous lists of words
(stringlist is a Delphi programming construct to keep lists) word lists
are good for xwords checking too, this makes sure you don't ask the
same question in the one xword twice.

another group problem... what if groups have the same value? hmm
for now i think that if a group has the same value and ends up further
away it should be seleced (ultimately we want to STAY AWAY from
 destination as much as possible (while still finishing)
note on staying away see previous chapter in point 2.

3

How to make snakes?
hmm i think each word should attach to the tail or head that way it
can be easier in code for now but should check every char of word
that way it would find more permutaions and higher result number.


Main Page and Crossword page
Comments