Crossword Compulsions!
GolfScript, 154 characters
:^,,{.^=46&lt;{;-1}*)}%[.^n?)/zip[0]*]{1,%{,1&gt;},}%:H&quot;AD&quot;1/]zip{~`{1$0=H{{0=}/}%.&amp;$?)\+[\]}+/}%(2/\{0=)[\~\]}$+[]{1${1=1$&amp;},.!{;1$1&lt;}*1&lt;:F~~@|@F-\1$}do;;]','*

Input has to be provided on STDIN. The examples yield the following results (check online):
1A,1D,2D,3D,4A,5A,6A,7A

1A,1D,2D,5A,4D,4A,3D,3A,7A,8A,6D,9A

1A,2D,3D,4D,5D,7A,8D,9A,10A,11A,11D,12A,13A,6D,14D,15A,16A,17A

1A,1D,2D,3D,9A,10A,4D,4A,5D,6D,7D,8D,11A,12A,13A,15A,14D,15D,16A,17A,18D,19D,20A,21D,23A,22D,24A,25D,27A,28A,26D,29A,30A,31A