[Tutor] Sudoku puzzle implementation
Chinook
chinook.nr at tds.net
Mon Jul 4 03:18:33 CEST 2005
Liam,
I couldn't get "into" your approach at the moment, but I was wondering
if you have looked at the following:
First, the Reverse Puzzle section of:
http://cs.gettysburg.edu/~tneller/resources/ai-search/uninformed-java/
and secondly more generally:
http://www.gamedev.net/reference/articles/article1374.asp
http://www.gamedev.net/reference/articles/article1433.asp
http://www.gamedev.net/reference/articles/article2041.asp
Just some references I've used for puzzle problems,
Lee C
Liam Clarke wrote:
> 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.'
>
>
> ------------------------------------------------------------------------
>
> _______________________________________________
> Tutor maillist - Tutor at python.org
> http://mail.python.org/mailman/listinfo/tutor
More information about the Tutor
mailing list