Bits of Learning

Learning sometimes happens in big jumps, but mostly in little tiny steps. I share my baby steps of learning here, mostly on topics around programming, programming languages, software engineering, and computing in general. But occasionally, even on other disciplines of engineering or even science. I mostly learn through examples and doing. And this place is a logbook of my experiences in learning something. You may find several things interesting here: little cute snippets of (hopefully useful) code, a bit of backing theory, and a lot of gyan on how learning can be so much fun.

Monday, May 13, 2013

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).

1 comment:

Aditya said...

Sudoku puzzles usually have a unique solution. You could adapt some of the suggestions on this thread to ensure uniqueness:
http://stackoverflow.com/questions/6924216/how-to-generate-sudoku-boards-with-unique-solutions