Checking 2-dimensional array (like eight queens puzzle)

Question

My problem is very similar to eight queens puzzle.

I've got 2-dimensional array (N x N) that for example, looks like this:

0,0,0,0,1 y
0,0,0,0,0 |
0,0,0,0,0 V
0,0,0,1,0
0,0,0,0,0
x->

I'm checking horizontally, vertically and diagonally for occurrences of 1

\,0,|,0,/
0,\,|,/,0
-,-,1,-,-
0,/,|,\,0
/,0,|,0,\

I'm thinking about storing only the (x,y) postions of "1"'s in a list

[[4,0],[3,3]]

and solving it mathematically, check every position of "1" with another (x1,y1)<->(x2,y2),

if x1 == x2 or y1 == y2 we have a collision! if not check:

x2 == x1 + z;
y2 == y1 + z;
x2 == x1 - z;
y2 == y1 - z;

(???)

where z is +/- that ( x1+z in 0..N ) and ( y1+z in 0..N ) .......

My problem is checking for diagonal collision, is there a better way to do it???

Answer 1

One possible solution:

def collision(x1, y1, x2, y2):
    return x1 == x2 or y1 == y2 or abs(x1-x2) == abs(y1-y2)

i.e. there is a collision if the two points are on the same horizontal row, same vertical row or same diagonal (vertical distance == horizontal distance).

Answer 2

Your description sounds like an instance of an exact cover problem, which can be solved using an algorithm Knuth calls Algorithm X. I have implemented a Sudoku solver in Javascript using this technique. You can probably find implementations in Python, too.

Answer 3

I think it would be much faster if you didn't solve it mathematically but first check all rows for multiple occurrences of 1s, then all columns and finally all diagonal lines.

Here is some code to test the diagonal lines in a simple way. (It's JavaScript, sorry!)

var count = 0;
for (column = -n; column < n; column++) {
    for (row = 0; row < n; row++) {
            // conditions for which there are no valid coordinates.
            if (column + row > 6) {
                break;
            }
            if (column < 0) {
                continue;

            if (field[row][column] == 1) {
                count++;
                if (count == 2)
                    break; // collision
            }
    }
}

This method would have a complexity of O(n^2), whereas the one you suggested has a complexity of O(n^2 + k^2) (k being the number of 1s) If k is always small this should be no problem.

Answer 4

Assuming you actually do have an N-dimensional space, which you probably don't, you can use this collision detector:

def collision(t1, t2):
    return len(set([abs(a-b) for a,b in zip(t1, t2)] + [0])) <= 2

Pass it a pair of tuples with whatever arity you like, and it will return true if the two points lie on any N-dimensional diagonal.