: Go to
blog home : Go to
M-Space home
As I blogged yesterday, I tried a while ago to write a computer program to generate sudoku squares by randomly filling in the grid, but swiftly concluded that my algorithm was hideously ineffecient and gave up on it. After that, I didn't really think much at all about the problem of sudoku generation until a random conversation at a party last week brought it back to mind. I now have a new strategy for generating sudoku squares and I have developed some of the mathematical tools necessary to show that it will work.
My plan this time is to start with a known sudoku square and then use a series of transformations that preserve the sudoku conditions (i.e. the uniqueness of each digit within any given row, column or block) to convert it into a new square. It is easy to see that swapping arbitrary squares, or rows, columns or blocks can swiftly break the conditions. However, if you restrict yourself to swapping rows or columns without crossing block boundaries, or swapping whole rows (or columns) of blocks, the conditions are preserved. Also, all instances of one digit can be swapped for all instances of another digit (e.g. swap all 1's with 7's) or all columns and rows can be interchanged (viewing the grid as a matrix, you're taking its transpose) without breaking the conditions.
Using fairly elementary mathematics, it is quite straightforward to prove that all those operations preserve the well-formedness of a sudoku square, although to do so it would be necessary to be slightly more rigorous with definitions and notation. Thus we get a set of tools that can be applied at random to any valid sudoku square to get another one. It should be fairly straightforward to implement this as a computer program, and I intend to give it a try soon (probably using Python again). This will effectively be a way of recycling sudokus by converting them into new ones.
However, as usually happens in mathematical (or any other?) research, when you answer a question you find it leads to several questions. While I have established that you can transform one sudoku into another with these tools, it is not clear whether you can generate all sudokus in this way from a given starting point (although, all these tools are reversible so it would be sufficient to show that an arbitrary sudoku can be reduced to some standard form). Also, it is possible that some of the tools could be duplicated using some of the others, so there might be a certain amount of redundancy within the toolset (even if that is the case, it may still be convenient to retain them all - consider the analogous case of logic gates, where all gates can be build from a combination of nand gates; this renders all other gates technically superfluous, but in practice it is much easier to allow and, or, not and others separately as well).
Additionally, there remains the problem of taking a complete sudoku square and converting it into an interesting yet soluble problem. This also raises a stack of questions: how many squares can you delete and still guarantee being able to find a solution? how many can you delete before it becomes impossible to solve? (hopefully no fewer than for the previous question!), is it just a matter of how many, or is the distribution (numerical or physical) important as well?
I suspect that all these questions will be somewhat harder to answer than the previous one (in case you didn't spot the implicit question it was "can I find a set of transformations that will enable me to turn one sudoku square into another one?") so don't expect any results from me anytime soon. Of course, if you have any clever insights into how to solve them, please drop me a line.
: Go to
blog home : Go to
M-Space home