Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Python > 2-dimensional data structures

Reply
Thread Tools

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.
 
Reply With Quote
 
 
 
 
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.
 
Reply With Quote
 
 
 
 
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

 
Reply With Quote
 
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
 
Reply With Quote
 
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






 
Reply With Quote
 
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
 
Reply With Quote
 
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
 
Reply With Quote
 
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)
 
Reply With Quote
 
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
at ambassador to Fantasy
visi.com Island!!!
 
Reply With Quote
 
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.
>

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.


 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
structures, structures and more structures (questions about nestedstructures) Alfonso Morra C Programming 11 09-24-2005 07:42 PM
Type Casting IPv4 and IPv6 structures to Generic Structures tweak C Programming 14 06-11-2004 02:43 PM
data structures in java reference learningjava Java 3 10-16-2003 07:31 AM
Data Structures help MIke Beam Java 5 10-14-2003 09:53 AM
sharing complex data structures between threads in mod_perl2 Dennis Gavrilov Perl 1 07-24-2003 07:22 AM



Advertisments