views:

1088

answers:

4

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???

+12  A: 

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).

dF
I wish I had votes. This is a really good answer! However, wouldn't you want to find abs(dx) and abs(dy) instead?
strager
Thanks for VERY GOOD ANSWER! I haven't thought it would be so simple ;) Stupid me... I've managed to write a simple brute force checker using your collision function. Now I'm looking forward to check Algoritm X mentioned in another answer.
Murzyn1
Now I feel stupid for writing a loop to do this. Very nice!
int3
A: 

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.

Georg
"My problem is checking for diagonal collision, is there a better way to do it???" -- He's not trying to solve the Eight Queens problem. He's simply checking for collision. @dF's method is O(1).
strager
My understanding is, that he checks if there is at least one collision, not if point (x,y) has a collision. dF's method is O(1), but only if you assume that the number of comparisons is static.
Georg
Isn't k = N? So O(n^2+k^2) = O(2n^2) = O(n^2)? Certainly, in the 8 Queens problem, k = N.
Jonathan Leffler
No, k is the number of positions having a 1 in the array and n is the length of one side of the array.
Georg
+2  A: 

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.

Greg Hewgill
+1 . that's what i thought about first. but wasn't sure about it and haven't done anything with it so waited for a knowledgeable guy to vote him up. now found him :p
Johannes Schaub - litb
Made a simple brute force check, using collision function. Now, checking your method (looks complicated though)... Thanks!
Murzyn1
A: 

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.

recursive