Red Ed wrote:One thing you could do is, after placing digits 1-5, represent each entry in the (by now very short) list of possible digit "templates" as a 32-bit int. This means the arithmetic in the inner loop (i.e. digits 6-9) will be very quick. It may also pay to do a 81->64 bit compression right at the start (i.e. given the top left box fill and the placement of the 1s) so as to make the work for digits 2-4 reasonably quick as well.
I wrote the program in C/C++. I store the boards as integer arrays of length 9, each entry corresponding to a box, encoded as a number from 1 to 2^9. (Is this called bitmasking?) I did it this way to make the first stage a lot easier, since permutations of rows and columns are simple bitwise operations. I have a 617KB .txt file containing the arrays for the fillings of the digits 2-8 that are compatible with my unique choice of filling of 1's. This file is needed to run the brute-force search.
I read your comment, Red Ed, and converted the boards from integer arrays of length 9 to integer arrays of length 2, keeping only the required 2*32 = 64 bits (335KB .txt file). I reprogrammed the brute-force search and was able to find over 1,000,000 solutions per minute (increase by factor of ~2.5).
I'm not sure what you mean by the first sentence, however. As it stands now, I don't look for overcounting (the "12 above a 21" symmetries). There are just way too many combinations (or maybe not?). The number of ways to partially fill the board in with 2's is 2097; with 2's and 3's is 1,593,270; and with 2's, 3's and 4's is 501,651,862. How many of these are repeats? None of the 2's, I previously guessed maybe an 1/8 of the 2's and 3's. It seems too big to store the partially-filled boards.
I am going to try it on a faster computer tomorrow. If this dramatically increases the speed I can try to pretty-up the code and post it here. I'm sure there are ways to make it faster. But it still may not match Bertram's program (I wasn't able to get that to work on my computer here; hopefully I will be able to race the two programs tomorrow).
Brian
