2-dimensional data structures

[Kirk McDonald]

anthonyberet wrote:
> Thanks for the advice (to everyone in the thread).
> I think I will go with nested lists.
> However, I am running into a conceptual problem.
> My approach will be firstly to remove all the impossible digits for a 
> square by searching the row and column for other occurances.
> 
> However, I wondering how to approach the search of the nine regions of 
> the grid. I am thinking of producing another nested list, again 9x9 to 
> store the contents of each region, and to update this after each pass 
> through -and update of- the main grid (row and column).
> 
> I am not sure how to most efficiently identify which region any given 
> square on the grid is actually in - any thoughts, for those that have 
> done this? - I don't want a massive list of IF conditionals if I can 
> avoid it.
> 

When I wrote my Sudoku solver (a terribly inefficient and naive 
recursive algorithm that I originally wrote in C++ and was the first 
thing I ever wrote in Python), I used numarray. It allows 
two-dimensional slicing:

def inBlock(x, y, val):
     blockX = x/size * size
     blockY = y/size * size

     return val in sudoku[blockX:blockX+size, blockY:blockY+size]

'size' in this example is a global variable equal to the size of the 
puzzle, so 3 for a normal puzzle. 'sudoku' is a global two-dimensional 
array simply holding the values in the puzzle.

(There are any number of things in this can be improved, such as using 
the // floor division operator rather than /, not using global 
variables, and so on. What can I say? It was a straight conversion from 
C++. I hardly knew what "Pythonic" meant.)

-Kirk McDonald