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**

## 1 comment:

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

Post a Comment