2-dimensional data structures

[Kermit Rose]

From: anthonyberet

Date: 02/18/06 17:11:01

To: python-list at 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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-list/attachments/20060218/c01d5e03/attachment.html>