Acm Solution: Turn All the Lights Off

Eshita is a very ecologically conscious person. She works late and every night before going home she makes sure that all the lights are turned off at her workplace to conserve electricity. The workplace is represented as a 2-dimensional grid. Each square in the grid has 4 neighbors in up, down, left and right directions. The electrical wiring is such that the sides of the grid wrap around i.e., the leftmost and the rightmost columns are neighbors. Similarly, the top and bottom rows are neighbors. This ensures that each of the squares in the grid has 4 neighbors.

To standardize our notation, assume that the upper left-most square of the board is position \((0,0)\). Rows run horizontally and the top row is row 0. Columns are vertical and column 0 is the left-most column. Any reference to a square is by row then column; this square \((4,6)\) means row 4, column 6.

So, in the figure below, the grid has 4 columns and 4 rows (all the grids will have same number of rows and columns). The shaded square is denoted as \((2,3)\). The four neighbors of the square \((2,3)\) are squares \((1,3), (3,3), (2,2)\) and \((2,0)\). Similarly, the four neighbors of the square \((0,0)\) are squares \((3,0), (1,0), (0,1)\) and \((0,3)\).

Eshita is told that each square of the grid is a switch and a light. When a switch in some square is pushed, the light in that square and it's neighboring squares toggle their ON/OFF state. The next figure shows a sequence where, starting from a grid with all the lights OFF, switches \((1,1)\), and \((0,0)\) have been pushed. The ON lights are shown as shaded.

Given a grid with some of the lights ON, Eshita needs to say whether it is possible to turn all the lights OFF by pushing some sequence of button pushes. For example the first configuration of the 3x3 grid in the next figure, all the lights can be turned of by pushing switches \((0,0), (1,1)\) and \((2,2)\) (some other lights may be turned ON in the intermediate stages, but at the end of this sequence all the lights will be turned off). But in the second configuration, it is not possible to turn all the lights off by pushing any sequence of switches.

Your task is to write a program, which given some arbitrary configuration of a grid will determine whether all the lights can be turned off or not.

Input

The input file contains the description of several grids. Each grid starts with a line containing an integer size, specifying the number of rows and columns in the grid. Next line has a single integer \(n\), specifying the number of lights that are turned on. The following \(n\) lines contain two integers each, namely the row and column of each of ON light.

Output

For each of the grids output "Yes" or "No" on a line of its own. The output will be "Yes" if all the lights in the configuration can be turned off and "No" if it is not possible.

Sample Input

5
11
0 0
0 1
0 2
0 4
1 4
2 1
2 2
2 3
3 2
4 2
4 4
3
3
0 1
0 2
1 0

Sample Output

Yes
Now

Solution

I spend quite some time on this problem to find an optimal solution and finally implemented LightsOut, including a solver. The principle of the game LightsOut is so simple that the state of the playing field can be represented by a vector of size \(n^2\) and the rules of play can be coded in a matrix of dimension \(n^2 \times n^2 \). The goal then is to solve the linear system in \(\mathbb{Z}_2 \) for the target vector \(\mathbf{0} \) using the matrix inverse, as described in the more detailed article about the derivation of LightsOut solution.

For this problem, we only need to check if the game is solvable. But lets start with the unspectacular surrounding:

const fs = require('fs');

fs.readFile('input.txt', (err, data) => {
  if (err) throw err;
  let lines = data.toString().trim().split("\n");

  do {
    let s = lines.shift() | 0;
    let n = lines.shift() | 0;

    // Create augmented matrix A in Z2
    let A = new Matrix(s * s, s * s + 1, Matrix.FIELDS.Z(2));
    for (let i = 0; i < n; i++) {
      let [r, c] = lines.shift().split(" ").map(Number);

      // Add board to last colum of A
      A.set(r * s + c, s * s, 1);
    }

    // Check if the board is solvable
    console.log(solvable(A) ? "Yes" : "No");
  } while (lines.length > 0);
});