2-dimensional data structures

mensanator at aol.com mensanator at aol.com
Sat Feb 18 18:38:38 EST 2006


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

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


"""




More information about the Python-list mailing list