2-dimensional data structures

[anthonyberet]

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.

 

[Carl Cerecke]

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 J. Van Arsdall]

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
(e-mail address removed)
Build and Release
MontaVista Software

 

[Larry Bates]

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

 

[Tim Chase]

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

 

[Claudio Grondi]

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

 

[Max]

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

 

[Scott David Daniels]

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
(e-mail address removed)

 

[Grant Edwards]

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.

 

[anthonyberet]

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.

 

[Kermit Rose]

From: anthonyberet
Date: 02/18/06 17:11:01
To: (e-mail address removed)
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.

 

[Diez B. Roggisch]

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]

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

 

[mensanator]

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


"""

 

[Kirk McDonald]

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

 

[Gerard Flanagan]

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