# 2-dimensional data structures

Discussion in 'Python' started by anthonyberet, Jan 26, 2006.

1. ### anthonyberetGuest

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.

anthonyberet, Jan 26, 2006

2. ### Carl CereckeGuest

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 Cerecke, Jan 26, 2006

3. ### Carl J. Van ArsdallGuest

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

Build and Release
MontaVista Software

Carl J. Van Arsdall, Jan 26, 2006
4. ### Larry BatesGuest

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

Larry Bates, Jan 26, 2006
5. ### Tim ChaseGuest

> 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

Tim Chase, Jan 26, 2006
6. ### Claudio GrondiGuest

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

Claudio Grondi, Jan 26, 2006
7. ### MaxGuest

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

Max, Jan 27, 2006
8. ### Scott David DanielsGuest

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

Scott David Daniels, Jan 27, 2006
9. ### Grant EdwardsGuest

On 2006-01-26, Larry Bates <> 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!!!

Grant Edwards, Jan 27, 2006
10. ### anthonyberetGuest

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.

anthonyberet, Feb 18, 2006
11. ### Kermit RoseGuest

From: anthonyberet
Date: 02/18/06 17:11:01
To:
Subject: Re: 2-dimensional data structures

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.

Kermit says:

There is a MUCH more efficient way to do this!

If you are doing a 9 by 9 soduku,

Each row and column has exactly the digits 1 through 9

Think of your data as being in a list 81 cells long that is accessed 3
different ways.

As a 9 by 9, row wise,

As a 9 by 9 column wise

As a 3 by 3 by 9 where the first two subscripts identify the region, and
the last identify one of
the 9 values within the region.

And , most important,

To search for a value not yet in a row, column, or region,

Define holding list of length 9.

Suppose a row has 4,2,8 in it,

and the corresponding column has 2,3,1 in it

and the correspond region has 2, 7, 6 in it.

Then you initialize your hold vector to -1,

and set

hold(4) = 4
hold(2) = 1
hold(8) = 1
hold(2) = 1
hold (3) = 1
hold(1) = 1
hold(2) = 1
hold(7) = 1
hold(6) = 1

Then by scaning only the nine elements of hold, you see that

hold(5) = -1, , and hold(9) = -1 are the only values not reset, and

only 5 and 9 are possible choices for the target cell.

Kermit Rose, Feb 18, 2006
12. ### Diez B. RoggischGuest

> 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.

The question is not so much which region a give square is in, but more
which square contains which fields. If we assume that you number your
squares row-wise (top-left zero, top-right 3, bottom-right 9), this
function computes the field indices that a given square is composed of:

def scoords(n):
square_row = n / 3
square_col = n % 3
start_row = square_row * 3 # ( this is _not_ n!!)
start_column = square_col * 3
for x in xrange(start_column, start_column + 3):
for y in xrange(start_row, start_row + 3):
yield (x,y)

print list(coords(4))

Regards,

Diez

Diez B. Roggisch, Feb 18, 2006
13. ### Diez B. RoggischGuest

Diez B. Roggisch schrieb:
> The question is not so much which region a give square is in, but more
> which square contains which fields. If we assume that you number your
> squares row-wise (top-left zero, top-right 3, bottom-right 9), this
> function computes the field indices that a given square is composed of:

I'm confusing squares with fields here. What I meant by a square here is
the 3x3 region, of which 9 exist. Each has 3x3=9 cells.

Diez

Diez B. Roggisch, Feb 18, 2006
14. ### Guest

anthonyberet wrote:
> 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.

Here's another way:

def region_map():
for row in range(9):
for col in range(9):
region = (row/3,col/3)
print region,
print

def identify_region(cell):
return (cell[0]/3,cell[1]/3)

def create_regions():
regions = {}
for row in range(9):
for col in range(9):
rowcol = (row,col)
reg = (row/3,col/3)
if regions.has_key(reg):
regions[reg].append(rowcol)
else:
regions[reg] = [rowcol]
return regions

grid = [[0,0,6,0,7,0,0,0,0], \
[0,3,5,4,0,0,0,9,0], \
[0,0,0,0,0,6,1,2,0], \
[0,0,0,0,0,3,2,0,8], \
[0,0,0,0,6,0,0,0,0], \
[4,0,7,2,0,0,0,0,0], \
[0,5,2,1,0,0,0,0,0], \
[0,7,0,0,0,5,9,1,0], \
[0,0,0,0,4,0,3,0,0]]

print 'the grid:'
for g in grid: print g
print

print 'the region ids:'
region_map()
print

# create the region dictionary
regions = create_regions()

# pick an arbitrary cell
cell = (5,5)
reg_id = identify_region(cell)

print 'cell:',cell,'is in region:',reg_id
print

print 'region',reg_id,'contains:'

reg_data = regions[reg_id]
for c in reg_data:
print grid[c[0]][c[1]],

"""

the grid:
[0, 0, 6, 0, 7, 0, 0, 0, 0]
[0, 3, 5, 4, 0, 0, 0, 9, 0]
[0, 0, 0, 0, 0, 6, 1, 2, 0]
[0, 0, 0, 0, 0, 3, 2, 0, 8]
[0, 0, 0, 0, 6, 0, 0, 0, 0]
[4, 0, 7, 2, 0, 0, 0, 0, 0]
[0, 5, 2, 1, 0, 0, 0, 0, 0]
[0, 7, 0, 0, 0, 5, 9, 1, 0]
[0, 0, 0, 0, 4, 0, 3, 0, 0]

the region ids:
(0, 0) (0, 0) (0, 0) (0, 1) (0, 1) (0, 1) (0, 2) (0, 2) (0, 2)
(0, 0) (0, 0) (0, 0) (0, 1) (0, 1) (0, 1) (0, 2) (0, 2) (0, 2)
(0, 0) (0, 0) (0, 0) (0, 1) (0, 1) (0, 1) (0, 2) (0, 2) (0, 2)
(1, 0) (1, 0) (1, 0) (1, 1) (1, 1) (1, 1) (1, 2) (1, 2) (1, 2)
(1, 0) (1, 0) (1, 0) (1, 1) (1, 1) (1, 1) (1, 2) (1, 2) (1, 2)
(1, 0) (1, 0) (1, 0) (1, 1) (1, 1) (1, 1) (1, 2) (1, 2) (1, 2)
(2, 0) (2, 0) (2, 0) (2, 1) (2, 1) (2, 1) (2, 2) (2, 2) (2, 2)
(2, 0) (2, 0) (2, 0) (2, 1) (2, 1) (2, 1) (2, 2) (2, 2) (2, 2)
(2, 0) (2, 0) (2, 0) (2, 1) (2, 1) (2, 1) (2, 2) (2, 2) (2, 2)

cell: (5, 5) is in region: (1, 1)

region (1, 1) contains:
0 0 3 0 6 0 2 0 0

"""

, Feb 18, 2006
15. ### Kirk McDonaldGuest

anthonyberet wrote:
> 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

Kirk McDonald, Feb 19, 2006
16. ### Gerard FlanaganGuest

anthonyberet wrote:
> I want to work on a sudoku brute-forcer, just for fun.
>...
> 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.

Some 'UselessPython' :

import math

def SudokuOrder( length ):
block_length = int(math.sqrt(length))
for block in range(length):
row_offset = block_length * ( block // block_length )
col_offset = block_length * ( block % block_length )
for i in range( block_length ):
for j in range( block_length ):
yield i+row_offset, j+col_offset

grid = list(SudokuOrder(9))

BLOCK1 = grid[:9]
BLOCK2 = grid[9:18]
BLOCK9 = grid[72:81]

print
print 'BLOCK1 ->', BLOCK1
print
print 'BLOCK2 ->', BLOCK2
print
print 'BLOCK9 ->', BLOCK9

BLOCK1 -> [(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0), (2,
1), (2, 2)]

BLOCK2 -> [(0, 3), (0, 4), (0, 5), (1, 3), (1, 4), (1, 5), (2, 3), (2,
4), (2, 5)]

BLOCK9 -> [(6, 6), (6, 7), (6, 8), (7, 6), (7, 7), (7, 8), (8, 6), (8,
7), (8, 8)]

Gerard

Gerard Flanagan, Feb 19, 2006