2-dimensional data structures

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

  1. anthonyberet

    anthonyberet Guest

    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
    #1
    1. Advertising

  2. anthonyberet

    Carl Cerecke Guest

    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
    #2
    1. Advertising

  3. 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
    #3
  4. anthonyberet

    Larry Bates Guest

    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
    #4
  5. anthonyberet

    Tim Chase Guest

    > 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
    #5
  6. 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
    #6
  7. anthonyberet

    Max Guest

    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
    #7
  8. 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
    #8
  9. 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
    at ambassador to Fantasy
    visi.com Island!!!
     
    Grant Edwards, Jan 27, 2006
    #9
  10. anthonyberet

    anthonyberet Guest

    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.
     
    anthonyberet, Feb 18, 2006
    #10
  11. anthonyberet

    Kermit Rose Guest

    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
    #11
  12. > 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
    #12
  13. 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
    #13
  14. anthonyberet

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

    > 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


    """
     
    , Feb 18, 2006
    #14
  15. anthonyberet wrote:
    > 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.
    >


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



    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
    #16
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Alf P. Steinbach
    Replies:
    0
    Views:
    436
    Alf P. Steinbach
    Aug 18, 2003
  2. John Harrison
    Replies:
    4
    Views:
    6,927
    Default User
    Aug 19, 2003
  3. Icosahedron
    Replies:
    8
    Views:
    656
    Vivek
    Aug 21, 2003
  4. Alfonso Morra
    Replies:
    11
    Views:
    721
    Emmanuel Delahaye
    Sep 24, 2005
  5. Konstantinos

    Multi-dimensional Data Structures

    Konstantinos, Dec 9, 2003, in forum: Perl Misc
    Replies:
    8
    Views:
    142
    Eric J. Roode
    Dec 10, 2003
Loading...

Share This Page