chakravyuha

If you have not heard of Sudoku in the past year, you have probably been living under a rock. For those not in the know, Sudoku is like a crossword puzzle but with numbers. Most of the ones I have seen, are in a 9×9 grid. The grid is populated with numbers ranging from 0 to 9. The objective of the game is simple. Fill in the grid in such a way that each row and each column has all the digits from 0 to 9. Bookstores are full of Sudoku puzzle books with titles such as “The Essential Book of Sudoku”, “Sudoku for beginners”, “Still more Sudoku”, “Sudoku while luching”, “Sudoku for the loo”. Ok I made the last few up. But there are hundreds of these puzzle books out there, each with pages full of puzzles. One of these that I own, has the whole book divided into 5 sections. The difficulty level of the puzzles increase as you go from 1 to 5, with the puzzles in section 1 being the easiest (I take about 9 minutes for each of these) while those in section 5 the hardest (the only one I tried here took me an hour or so!).

What is interesting is the question “How are these puzzles created and assigned a difficulty level?” Firstly, since there are 81 squares (it is a 9×9 grid) simple permutation dictates that there are 1.966270504e+77 (9^81) possible puzzles. That is a huge number so we can rule out the possibility of anybody feeling like they have seen one before. A possible method to generate one could work like this. Start with a fully populated grid. You can write a computer program to generate a fully populated grid, a solved Sudoku if you will. Numbers are then stripped from the grid at random till there are only X number of them (let’s call them seed numbers) left, enough to enable a person to solve the puzzle to reach a particular solution. None of these puzzles in the puzzle book has more than one possible solution. That is the intriguing part. How many and in what way do you put these seed numbers that will guarantee a unique solution to a puzzle? Intuitively, a 9×9 grid with just, say, 1 seed number would have more than one solution (and would make for a very poor puzzle). So there has to be a way to determine a minimum number of seed numbers to guarantee a unique solution. The other question is setting the difficulty level. How can you make a puzzle more difficult than the other? This might not be a hard thing to do. My guess is that once you have determined the minimum number of seed numbers, you just add more to the puzzle to decrease the difficulty level. But I am not exactly sure whether that is how it is done. Any maths wizs out there?