|
Date: 02/18/06 17:11:01
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.
| 