hkociemba wrote:Good progress concerning generation of a valid grid. Generation of 100x100 took 15 min though I did not try any optimization yet. For 225x255 though I do not think it will finish in a reasonable time yet.
The algorithm yet is extremely simple:
1. Fill all rows with numbers from 1..N in random order.
2. Select a random row r and in this row two random cells (r,c1) and (r,c2).
3. Count the number n1 of "wrong" numbers in the two columns c1 and c2 and in the two blocks b1 and b2 the (r,c1) and (r,c2) are in.
4. Swap the content of (r,c1) and (r,c2).
5. Count again. If the number n2 of "wrong" numbers is now greater, swap back.
6. Goto 2 and repeat until the grid is valid. Validity can be computed by the initial value I for the number of wrong numbers and always updating this value: I <-- I - n1 + n2.
Surprisingly the algorithm does not seem to get stuck in a local minimum (most of the time?) and this greedy algorithm works. For a standard 9x9 creation time is only about 30 ms on average, for a 49x49 20 s to 30 s.
m_b_metcalf wrote:Good to know that your algorithm works up to higher sizes. You prompted me to make some new timings on ancient code, the result being:
- Code: Select all
box
size number time average time
---- ------ ---- ------------
3 1,000,000 28s 28µs
4 1,000 0.41s 0.41ms
5 1,000 6.28s 6.28ms
6 10 19.70s 1.97s
7 3 12.55s 4.18s
8 1 stalls
On an i5, with no output.
For x-sudokus my method works only for 9x9 and 16x16. For larger sizes I offer a solver a pseudo puzzle, empty but with the diagonals already in place, and take the first solution it finds. That works for up to 36x36.
hkociemba wrote:For small blocksizes you algorithm works much faster than mine. For XSudoku mine does not seem to work at all. I have some idea how to manage this. I implemented a complete generator set of symmetry operations for non-XSudokus into my program now (permute_band, permute_stack, permute_bands, permute_stacks, reflect_diagonal,,relabel_nums). Only the last two also are symmetries of XSudoku too. So by applying the first 4 I will try to fix the XSudoku diagonals without destroying the Sudoku grid. But this will have to wait until next week. Btw., my program is written generally and works also for rectangular blocksizes. But I think XSudoku works best for quadradic blocksizes and I will restrict XSudoku to this kind of blocks.
I'm making a new thread for this topic.
Please note that all those permutations do not create what are regarded as essentially different grids. You can see more on this topic in this Mathematics thread, and more particularly in this paper. One of the authors, known as RedEd on that forum, had a way of determining biases in the grids. I submitted him a set of mine and it came off fairly well. Also, I submitted a large number of permutations of the Most Canonical grid and he discovered immediately that it was all the same basic grid (see here).
See also here, here, and here (all light reading for a mathematician!).
Regards,
Mike Metcalf
