2-dimensional data structures

[anthonyberet]

Hello again - rather a newbie here...

I want to work on a sudoku brute-forcer, just for fun.

I am considering different strategies, but first I need to decide on the
data-structure to use for the progress/solution grid.

This being a square, I would have used a 9x9 2-dimensional array in my
teenage years back in the 80's, using BASIC.

What is the equivalent way to store data in python? - It isn't obvious
to me how to do it with lists.

'scuse me for being thick - but give me a little pointer and I will do
the rest.

[Carl J. Van Arsdall]

anthonyberet wrote:

Hello again - rather a newbie here...

I want to work on a sudoku brute-forcer, just for fun.

I am considering different strategies, but first I need to decide on the
data-structure to use for the progress/solution grid.

This being a square, I would have used a 9x9 2-dimensional array in my
teenage years back in the 80's, using BASIC.

What is the equivalent way to store data in python? - It isn't obvious
to me how to do it with lists.]
Well, you could do a list of lists, or a tuple of tuples, or a
combination thereof.

For example:
val = matrix[indexA][indexB]

-carl 'scuse me for being thick - but give me a little pointer and I will do
the rest.

--

Carl J. Van Arsdall
cv*********@mvi sta.com
Build and Release
MontaVista Software

[Carl Cerecke]

anthonyberet wrote:

Hello again - rather a newbie here...

I want to work on a sudoku brute-forcer, just for fun.
I know what you mean. I wrote one just for fun too.
I am considering different strategies, but first I need to decide on the
data-structure to use for the progress/solution grid.

This being a square, I would have used a 9x9 2-dimensional array in my
teenage years back in the 80's, using BASIC.

What is the equivalent way to store data in python? - It isn't obvious
to me how to do it with lists.

List of lists.
One list with nine elements, each of which is a list with nine numbers.
[[5,2,7,3,9,8,1,4 ,6],
[3,1,4,....],
....
]

Cheers,
Carl.

[Larry Bates]

anthonyberet wrote:

Hello again - rather a newbie here...

I want to work on a sudoku brute-forcer, just for fun.

I am considering different strategies, but first I need to decide on the
data-structure to use for the progress/solution grid.

This being a square, I would have used a 9x9 2-dimensional array in my
teenage years back in the 80's, using BASIC.

What is the equivalent way to store data in python? - It isn't obvious
to me how to do it with lists.

'scuse me for being thick - but give me a little pointer and I will do
the rest.

Probably the numeric module:

http://numeric.scipy.org/

But you can also do nested lists.

Larry Bates

[Tim Chase]

> I want to work on a sudoku brute-forcer, just for fun.

Well, as everybody seems to be doing these (self included...),
the sudoku solver may become the "hello world" of the new world :)

What is the equivalent way to store data in python? - It isn't obvious
to me how to do it with lists.

Several other answers have crossed the list. I've done it using
a dictionary of tuples:

grid = {}
for row in range(1,10):
for col in range(1,10):
grid[(row,col)] = value

item = grid[(3,2)]

etc.

Seemed fairly quick and worked for me.

-tkc

[Claudio Grondi]

anthonyberet wrote:

Hello again - rather a newbie here...

I want to work on a sudoku brute-forcer, just for fun.

I am considering different strategies, but first I need to decide on the
data-structure to use for the progress/solution grid.

This being a square, I would have used a 9x9 2-dimensional array in my
teenage years back in the 80's, using BASIC.

What is the equivalent way to store data in python? - It isn't obvious
to me how to do it with lists.

'scuse me for being thick - but give me a little pointer and I will do
the rest.

Another approach as already proposed could be, that you define your grid
as a dictionary in a following way:
grid = {}
for column in range(1,10):
for row in range(1,10):
grid[(column, row)] = None
# then you can refer to the cells of the 'array' like:
colNo=5; rowNo=4
valueInCellOfGr id = grid[(colNo, rowNo)]
# and set them like:
grid[(colNo, rowNo)] = 9
print valueInCellOfGr id
print grid[(colNo, rowNo)]

I haven't checked it out, but I can imagine, that this approach could
even have a speed advantage over a list of lists what can become
important in a 'brute-forcer' approach.

Best way is probably to use one of available numeric libraries with
array support, but this is another story.

Claudio

Claudio

[Max]

Claudio Grondi wrote:

Another approach as already proposed could be, that you define your grid
as a dictionary in a following way:
grid = {}
for column in range(1,10):
for row in range(1,10):
grid[(column, row)] = None
# then you can refer to the cells of the 'array' like:
colNo=5; rowNo=4
valueInCellOfGr id = grid[(colNo, rowNo)]
# and set them like:
grid[(colNo, rowNo)] = 9
print valueInCellOfGr id
print grid[(colNo, rowNo)]

FWIW, if you leave out the parentheses, it looks more like a genuine 2D
array, which can be nice (actually I think it's the main advantage over
lists of lists):

print grid[colNo, rowNo]

Claudio

--Max

[Scott David Daniels]

Claudio Grondi wrote:

anthonyberet wrote:

Hello again - rather a newbie here...
I am considering different strategies, but first I need to decide on
the data-structure to use for the progress/solution grid.

... define your grid as a dictionary in a following way:
grid = {}
for column in range(1,10):
for row in range(1,10):
grid[(column, row)] = None
# then you can refer to the cells of the 'array' like:
colNo=5; rowNo=4
valueInCellOfGr id = grid[(colNo, rowNo)]
# and set them like:
grid[(colNo, rowNo)] = 9
print valueInCellOfGr id
print grid[(colNo, rowNo)]

Though a couple of people have suggested a dictionary, nobody has
yet pointed out that a[i, j] is the same as a[(i, j)] (and looks
less ugly). So, I'd go with dictionaries, and index them as
grid = {}
for column in range(1,10):
for row in range(1,10):
grid[column, row] = None
...
valueInCellOfGr id = grid[col, row]
grid[col, row] = 9
...

--Scott David Daniels
sc***********@a cm.org

[Grant Edwards]

On 2006-01-26, Larry Bates <la*********@we bsafe.com> wrote:

I want to work on a sudoku brute-forcer, just for fun.

I am considering different strategies, but first I need to decide on the
data-structure to use for the progress/solution grid.

This being a square, I would have used a 9x9 2-dimensional array in my
teenage years back in the 80's, using BASIC.

What is the equivalent way to store data in python? - It isn't obvious
to me how to do it with lists.

'scuse me for being thick - but give me a little pointer and I will do
the rest.

Probably the numeric module:

http://numeric.scipy.org/

I'd use numeric or numarray. They have built-in notation for
grabbing a row or column.

--
Grant Edwards grante Yow! I appoint you
at ambassador to Fantasy
visi.com Island!!!

[anthonyberet]

Tim Chase wrote:

I want to work on a sudoku brute-forcer, just for fun.

Well, as everybody seems to be doing these (self included...), the
sudoku solver may become the "hello world" of the new world :)

What is the equivalent way to store data in python? - It isn't obvious
to me how to do it with lists.

Several other answers have crossed the list. I've done it using a
dictionary of tuples:

grid = {}
for row in range(1,10):
for col in range(1,10):
grid[(row,col)] = value

item = grid[(3,2)]

etc.

Seemed fairly quick and worked for me.

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.