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.

[Kermit Rose]

From: anthonyberet
Date: 02/18/06 17:11:01
To: py*********@pyt hon.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.

[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_co lumn, start_column + 3):
for y in xrange(start_ro w, start_row + 3):
yield (x,y)

print list(coords(4))

Regards,

Diez

[Diez B. Roggisch]

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

[mensanator]

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,'i s 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]

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+s ize, blockY:blockY+s ize]

'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]

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(l ength))
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(SudokuOrde r(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