[Tutor] Sudoku puzzle implementation
Liam Clarke
cyresse at gmail.com
Mon Jul 4 01:39:37 CEST 2005
Hi all,
If you aren't aware of Sudoku, this is it - http://www.sudoku.com/
Big craze at my office, and I've just been wracking my brains to try and
think of how to model it in Python (in order to solve.)
What I'm not sure of is how to implement it.
Basic rundown of a Sudoku puzzle is -
Generally composed of 9 x 9 squares, with the box divided further into nine
3 x 3 mini-squares. Certain numbers are given at the start.
Sudoku puzzles follow these rules -
Each column, row and mini-square must contain the complete set of numbers 1
- 9.
The numbers do not have to be sequential.
Each column, row, and mini-square can only contain each number once
So that's it. So, to implement...
I was thinking, a list of lists of lists....
[grid[0], grid[1], grid[2],
grid[3], grid[4], grid[5],
grid[6], grid[7], grid[8] ]
[
[
[a,b,c],
[d,e,f,],
[g,h,i]
],
[
[j,k,l],
[m,n,o],
[p,q,r]....
So forth. This approach gets a little confusing in terms of array arithmetic
but it's livable.
Now each variable can be [1-9]....
Variable a (grid[0][0][0]) can be 1 unless
grid - any member of grid[0] is 1
row - any member of grid[1][0] or grid[2][0] is 1
column - grid[3][x][0] or grid[6][x][0] is 1 (where x is an index of 0 to 2)
My current approach is to start with each variable as a list of numbers
[1-9] and to pop numbers based on the above rules,
but I got thinking about sets and what not, and wondered if they would work
better, unions and intersections and whatnot.
Problem is, I don't know the first thing about set mathematics.
Any pointers in the right direction would be gratefully appreciated.
Regards,
Liam Clarke
--
'There is only one basic human right, and that is to do as you damn well
please.
And with it comes the only basic human duty, to take the consequences.'
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mail.python.org/pipermail/tutor/attachments/20050704/1e7afdb6/attachment.htm
More information about the Tutor
mailing list