Velocity Reviews > 2-dimensional data structures

# 2-dimensional data structures

anthonyberet
Guest
Posts: n/a

 01-26-2006
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 Cerecke
Guest
Posts: n/a

 01-26-2006
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.

Carl J. Van Arsdall
Guest
Posts: n/a

 01-26-2006
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
http://www.velocityreviews.com/forums/(E-Mail Removed)
Build and Release
MontaVista Software

Larry Bates
Guest
Posts: n/a

 01-26-2006
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
Guest
Posts: n/a

 01-26-2006
> 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
Guest
Posts: n/a

 01-26-2006
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
valueInCellOfGrid = grid[(colNo, rowNo)]
# and set them like:
grid[(colNo, rowNo)] = 9
print valueInCellOfGrid
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
Guest
Posts: n/a

 01-27-2006
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
> valueInCellOfGrid = grid[(colNo, rowNo)]
> # and set them like:
> grid[(colNo, rowNo)] = 9
> print valueInCellOfGrid
> 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
Guest
Posts: n/a

 01-27-2006
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
> valueInCellOfGrid = grid[(colNo, rowNo)]
> # and set them like:
> grid[(colNo, rowNo)] = 9
> print valueInCellOfGrid
> 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
...
valueInCellOfGrid = grid[col, row]
grid[col, row] = 9
...

--Scott David Daniels
(E-Mail Removed)

Grant Edwards
Guest
Posts: n/a

 01-27-2006
On 2006-01-26, Larry Bates <(E-Mail Removed)> 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
visi.com Island!!!

anthonyberet
Guest
Posts: n/a

 02-18-2006
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.
>

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.