Start: My DAWG. * I started with your dawgutils, applied the packing a la Liang, reduced letters to numbers 1..29 (german takes 3 umlaut letters more). In the packing procedure I add to each node the leaf 0, which is the bit pattern of present letters in that node. So when you have two node pointers from across and down, you may check possible intersections with ((*across)&(*down))!=0. Fast, I think. A side effect is that you don't need to put letters in the other leaves of the node because you checked before that this is your pointer. So: leaves==pure indices into the dawg, no flags, no letters, no masking. Next: Paths. What's the best sequence of fields in our square to find squares? The best way might be adaptive (recalculating probabilities... but way too slow). So fixed paths. Hardcoded in the program. So only constant indices into fields, rarifying address calculation. I decided to take this one in the unsymmetrical case. Fields are numbered in order of execution: 1 2 4 7 11 3 5 8 12 6 9 13 10 14 15 etc. Zigzagging. So that I have a mix of long and short fragments all the time, not always short and not always long. And I can check everytime that a continuation across exists! (use bits mask in dawg). No analyses made about paths, but that one worked. For the symmetrical case I do not work with the below left half, so the path is 0 1 3 6 * 2 4 7 * * 5 8 * * * 9 etc. The code for one field is built like this: (the third field on the top row, the 4th in the path, labelled '3' above). m3: // I come here from below. feld[].mask holds the bit mask of still possible // letters. If it is empty, this field is done and we return to previous field. if((mask=feld[2].mask)==0) goto m2; // erase the lowest bit in feld[].mask (Kill that letter) feld[2].mask=maske=mask&(mask-1); // maske= lowest bit just killed maske^=mask; // get log of that, use the code you like for that. log=0; if(maske&0xffff0000) { log=64;maske>>=16;} if(maske&0xff00) { log+=32; maske>>=8;} log+=logtab[maske]; // prepare the next square across (wnode=its across node) // It is the dawg pointer + the leaf for the calculated letter in the current across node mask=*(unsigned int *)(feld[3].wnode=rdawg+PTR(*(NODE *)(feld[2].wnode+log))); // I cannot take my letter if it doesn't match with the down node (snode) of // the next field. So check. if((feld[3].omask=(*(unsigned int *)(feld[3].snode))&mask)==0) { goto m3; } // Now prepare the down node of the square below mask=*(unsigned int *)(feld[11].snode=rdawg+PTR(*(NODE *)(feld[2].snode+log))); // with the mask remembered make cross-check if((mask=(*(unsigned int *)(feld[11].wnode))&mask)==0) { goto m3; } // Just that anded mask is the beginning mask for the square below! feld[11].mask=mask; // Next square, please Some operations are not necessary on the borders, some are not on the diagonal. My Perl script takes account of that. I hope that are relatively few cycles per field. But the algorithm is still dumb, and I cannot figure out another one. I will append the perl script with another log determiner commented out. So you can generate C-files. I hope that I find all include-files as well. They will come zipped and uuencoded in a separate mail. I will gladly run other programs here on my wordlists. If others can cope with the German alphabet, they can use my wordlist, but on a tight nondisclosure agreement, for the sake of magic squares! In the zip file, often.c and aoften.c are essentially the same, often is for UTF-8 in/output. You could replace all often.c's with aoften.c's if you like. dawg.c is a comment-stripped and otherwise tweaked version of your brilliant dawg code. (Hash table size 500009, adjust!) repack2 sth. along your packing code. One should sort the list, dawg it (usage: dawg list all9) and repack it (usage: repack2 all9). run the script below: mgs 9 >msq9s.c Then, msq9s should run. I cannot beautify and test all that, because I am seriously ill currently and have a limited time up. At least there is hope it will work. Greetings, Martin. ------------------------------------------------------------------- Jean-Charles Meyrignac wrote: Attached, an optimized version of Martin Läuter's code generator for MSQ. I already sent him this version, and he suggested that you archive it. The new version outputs a standalone C source, instead of C++ with includes, and has several optimizations added: 1) relocation of the DAWG 2) save/restore (if you break the program then rerun it, it will restart where the computation stopped !) 3) skipping some square symmetries 4) the output files are updated when a new solution is found (under Windows, a file cannot be opened until the end of the program). 5) several small optimizations in the doform() routine JC [JC's other contributions are in ../jean-charles ]