التحقق من صفيف 2 الأبعاد (مثل ثمانية ملكات اللغز)

Question

مشكلتي تشبه إلى حد كبير ثمانية ملكات اللغز.

لدي صفيف ثنائي الأبعاد (N X N) أنه على سبيل المثال، يبدو أن هذا:

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

أنا أتحقق أفقيا وعموديا وقطريا للحصول على حدوث 1

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

أنا أفكر في تخزين عمليات الرعايا فقط (x، y) في قائمة "1" في قائمة

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

وحلها رياضيا، تحقق من كل موقف من "1" مع آخر (x1، y1) <-> (x2، y2)،

إذا x1 == x2 أو y1 == y2 we have a collision! إن لم يكن التحقق:

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

(???)

حيث z هو +/- ذلك ( x1+z in 0..N ) and ( y1+z in 0..N ) .......

مشكلتي هي التحقق من الاصطدام القطرية، هل هناك طريقة أفضل للقيام بذلك ؟؟

Answer 1

حل واحد ممكن:

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

أي هناك تصادم إذا كانت النقطتين على نفس الصف الأفقي، نفس الصف الرأسي أو نفس القطر (المسافة الرأسية == المسافة الأفقية).

Answer 2

وصفك يبدو وكأنه مثيل لمشكلة الغطاء الدقيقة، والذي يمكن حله باستخدام مكالمات Nuth في الخوارزمية الخوارزمية X.. وبعد لقد نفذت أ Sudoku Solver في جافا سكريبت باستخدام هذه التقنية. ربما يمكنك العثور على تطبيقات في بيثون أيضا.

Answer 3

أعتقد أنه سيكون أسرع بكثير إذا لم تحلها رياضيا ولكن أولا تحقق من جميع الصفوف لتكرارات متعددة من 1S، ثم جميع الأعمدة وأخيرا جميع الخطوط القطرية.

فيما يلي بعض التعليمات البرمجية لاختبار الخطوط القطرية بطريقة بسيطة. (إنه جافا سكريبت، آسف!)

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

هذه الطريقة سيكون لها تعقيد O(n^2), ، في حين أن الشخص الذي اقترحته لديه تعقيد O(n^2 + k^2) (ك كونه عدد 1s) إذا k هو دائما صغيرة يجب أن يكون هذا مشكلة.

Answer 4

على افتراض أنك تتمتع بالفعل بمساحة N- الأبعاد، والتي ربما لا تستخدمها، يمكنك استخدام هذا الكاشف الاصطدام:

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

اجتيازها زوج من tuples مع أي arity تريد، وسيعود صحيحا إذا كذبت النقاط على أي قطري N-VIDELAL.