An Automated Sudoku Generator

In a recent post, I presented an automated sudoku player. Given a sudoku puzzle, this little program gives you its solution in a matter of seconds (mostly fractions of a second).

Here's an addition to it: An automated Sudoku Generator.

In the earlier one, I had gone into gory details of the algorithm because the beauty lay in the depth first branch and bound design of the algorithm. Here, I don't go into any details, simply because there aren't any! And that's the beauty of the whole thing. It's ridiculously simple.

And it succeeds to completely build on the sudoku solver. Well, almost. I have modified the sudoku solver just slightly to make it randomised. That means that for the same input, two separate runs may (and most probably will) give out two distinct solutions. This was necessary to prevent our sudoku generator from throwing the same puzzle at us every time. Now, every 9 by 9 sudoku puzzle that can be has an equal probability of getting generated by our program!

The trick is simple: Give sudoku solver a completely empty sudoku puzzle and let it come back with a valid solved puzzle. Now, just mask away some of the cells in this grid with blanks. That's your new sudoku puzzle!
Here's the code:

#!/usr/bin/python
from sudoku import *

def mask(sudoku):
 def generateRandomList(num, lst):
  index = random.randint(0, len(lst) - 1)
  result = [lst.pop(index)]
  if(num > 1):
   result.extend(generateRandomList(num - 1, lst))
  return result

 for rowNum in range(9):
  row = sudoku[rowNum]
  offset = random.randint(0, 1)
  maskIndices = generateRandomList(5 + offset, range(9))
  for i in maskIndices:
   row[i] = 0
 return sudoku

In the above almost trivial piece of code, probably the function generateRandomList is the only part which merits a second glance. This function takes a list lst and returns a sublist of num randomly chosen elements of it. Again, don't you agree that implementing it recursively has made it simpler to read?

All the outer mask function does is to call generateRandomList for each of its rows.

If you wish to test the above, here's the main function:

if __name__ == '__main__':
 sudoku = [[0] * 9] * 9
 print 'solution:'
 solution = solve(sudoku)
 printSudoku(solution)
 print 'masked:'
 printSudoku(mask(solution))

That's all!

Follows the downloadable file:
sudoku_maker.py

Download it at the same place where you have placed your sudoku.py. And make sure to make the sudoku_maker.py an executable:
chmod +x sudoku_maker.py

Or run it as follows:

python sudoku_maker.py

Acknowledgement:

Thanks Prahlad for asking me to write the above (or something of this sort).