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