สังเกตว่าสิ่งที่เราสนใจจริง ๆ ไม่ใช่สถานะเริ่มต้นหรือสถานะสิ้นสุดของหลอดไฟ แต่เป็นการเปลี่ยนแปลงสถานะของหลอดไฟ ดังนั้น เพื่อความสะดวก จะนิยามให้ $A_{i,j}$ สื่อถึงการเปลี่ยนแปลงสถานะของหลอดไฟในแถวที่ $i$ หลักที่ $j$ (สำหรับ $0 \leq i, j < N$) โดยถ้าต้องมีการเปลี่ยนสถานะจากปิดเป็นเปิดหรือจากเปิดเป็นปิด จะได้ $A_{i,j}=1$ มิเช่นนั้นจะได้ $A_{i,j}=0$

สำหรับแต่ละปุ่ม เมื่อกดปุ่มมากกว่า 1 ครั้ง ผลที่เกิดต่อหลอดไฟดวงนั้นและหลอดไฟดวงข้าง ๆ จะเทียบเท่ากับการไม่กดปุ่มเลย (ถ้ากดเป็นจำนวนคู่ครั้ง) หรือการกดปุ่มเพียง 1 ครั้ง (ถ้ากดเป็นจำนวนคี่ครั้ง) ดังนั้น เราจะพิจารณากดปุ่มแต่ละปุ่มแค่ 0 หรือ 1 ครั้งเท่านั้น เพื่อความสะดวก นิยามให้ $x_{i,j}=0$ เมื่อเลือกไม่กดปุ่มในแถวที่ $i$ หลักที่ $j$ และ $x_{i,j}=1$ เมื่อเลือกกดปุ่ม

สังเกตว่าการเปลี่ยนแปลงสถานะของหลอดไฟแถวที่ $i$ หลักที่ $j$ เกิดจากจำนวนครั้งที่ปุ่มของหลอดไฟนั้นหรือปุ่มข้าง ๆ ถูกกด โดยถ้าถูกกดเป็นจำนวนคี่ครั้งจะมีการเปลี่ยนแปลงสถานะเกิดขึ้น แต่ถ้าถูกกดเป็นจำนวนคู่ครั้งจะไม่มีการเปลี่ยนแปลง

เช่น หากพิจารณา $i=2$, $j=3$ จะได้ความสัมพันธ์เป็น $A_{2,3} \equiv x_{2,3}+x_{1,3}+x_{2,2}+x_{2,4}+x_{3,3} \mod 2$

หากเราพิจารณาความสัมพันธ์ของการเปลี่ยนแปลงสถานะกับการกดปุ่มสำหรับหลอดไฟทุกดวง จะได้สมการเชิงเส้นทั้งหมด $N \times N$ สมการ เนื่องจากโจทย์กำหนดค่า $A_{i,j}$ ให้อยู่แล้ว เราสามารถแก้สมการหาค่า $x_{i,j}$ ต่าง ๆ ใน modulo 2 ได้ แล้วตอบทุก $(i, j)$ ที่ทำให้ $x_{i,j}=1$

เราสามารถแก้สมการเชิงเส้นได้ด้วย Gauss–Jordan elimination โดยเพื่อความสะดวกในการสร้างเมทริกซ์สัมประสิทธิ์และเวกเตอร์คำตอบ ให้แปลงพิกัด $(i,j)$ ให้กลายเป็นเลข $i \cdot N+j$ เช่น หาก $N=5$ พิกัด $(2,3)$ จะถือว่าเป็นตัวแปรลำดับที่ $2 \cdot 5 + 3 = 13$

เนื่องจากเรามีทั้งหมด $N \cdot N$ สมการ และมีสัมประสิทธิ์และค่าคำตอบ รวม $N \cdot N + 1$ ตัวต่อสมการ ดังนั้น หากใช้ Gauss–Jordan elimination จะต้องใช้เวลาในการทำงานทั้งหมด $O((N \cdot N)^3) = O(N^6)$ และพื้นที่ทั้งหมด $O(N^2)$

Implementation

ในภาษา C++:

#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 20;

int n;
int A[N * N][N * N];
int B[N];

int calc(int x, int y) {
  return (x < 0 || x >= n || y < 0 || y >= n ? -1 : (x)*n + (y));
}

void swapRow(int x, int y) {
  for (int j = 0; j <= n * n; ++j) {
    swap(A[x][j], A[y][j]);
  }
}

void addRow(int from, int to) {
  for (int j = 0; j <= n * n; ++j) {
    A[to][j] = (A[to][j] + A[from][j]) % 2;
  }
}

int main() {
  scanf("%d", &n);
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      int u = calc(i, j);
      scanf("%d", &A[u][n * n]);
    }
  }
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      int x;
      scanf("%d", &x);
      int u = calc(i, j);
      A[u][n * n] = (A[u][n * n] + x) % 2;
    }
  }

  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      int u = calc(i, j);
      int v[] = {u, calc(i - 1, j), calc(i + 1, j), calc(i, j - 1),
                 calc(i, j + 1)};
      for (int k = 0; k < 5; ++k) {
        if (v[k] == -1)
          v[k] = u;
        A[v[k]][u] = 1;
      }
    }
  }

  for (int i = 0; i < n * n; ++i) {
    for (int j = i; j < n * n; ++j) {
      if (A[j][i] == 1) {
        swapRow(i, j);
        break;
      }
    }
    for (int j = 0; j < n * n; ++j) {
      if (j == i)
        continue;
      if (A[j][i] == 1)
        addRow(i, j);
    }
  }

  int cnt = 0;
  for (int i = 0; i < n * n; ++i) {
    if (A[i][n * n] == 1)
      ++cnt;
  }

  printf("%d\n", cnt);
  for (int i = 0; i < n * n; ++i) {
    if (A[i][n * n] == 1) {
      printf("%d %d\n", i / n + 1, i % n + 1);
    }
  }

  return 0;
}