2-dimensional data structures
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. -- http://mail.python.org/mailman/listinfo/python-list
Re: 2-dimensional data structures
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 [EMAIL PROTECTED] Build and Release MontaVista Software -- http://mail.python.org/mailman/listinfo/python-list
Re: 2-dimensional data structures
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. -- http://mail.python.org/mailman/listinfo/python-list
Re: 2-dimensional data structures
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 -- http://mail.python.org/mailman/listinfo/python-list
Re: 2-dimensional data structures
> 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
--
http://mail.python.org/mailman/listinfo/python-list
Re: 2-dimensional data structures
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
--
http://mail.python.org/mailman/listinfo/python-list
Re: 2-dimensional data structures
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
--
http://mail.python.org/mailman/listinfo/python-list
Re: 2-dimensional data structures
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
[EMAIL PROTECTED]
--
http://mail.python.org/mailman/listinfo/python-list
Re: 2-dimensional data structures
On 2006-01-26, Larry Bates <[EMAIL PROTECTED]> 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.comIsland!!! -- http://mail.python.org/mailman/listinfo/python-list
Re: 2-dimensional data structures
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.
--
http://mail.python.org/mailman/listinfo/python-list
Re: 2-dimensional data structures
From: anthonyberet Date: 02/18/06 17:11:01 To: python-list@python.org 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. -- http://mail.python.org/mailman/listinfo/python-list
Re: 2-dimensional data structures
> 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 -- http://mail.python.org/mailman/listinfo/python-list
Re: 2-dimensional data structures
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 -- http://mail.python.org/mailman/listinfo/python-list
Re: 2-dimensional data structures
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
"""
--
http://mail.python.org/mailman/listinfo/python-list
Re: 2-dimensional data structures
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 -- http://mail.python.org/mailman/listinfo/python-list
Re: 2-dimensional data structures
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 -- http://mail.python.org/mailman/listinfo/python-list
