A PUZZLE MADE OF EVEN AND ODD
Every lantern carries a number, and every number burns a flame for each prime it holds an odd number of times. Light lanterns together and matching flames put each other out. When every flame is out, the numbers you lit multiply to a perfect square.
Light a lantern to begin.
A number is a perfect square when every prime in it appears an even number of times: 900 = 2² · 3² · 5². Multiplying numbers adds their exponents, so only even and odd matter. Write a 1 for odd and a 0 for even and each lantern becomes a row of bits; lighting two lanterns adds their rows, and in this arithmetic adding is XOR. A set of rows that adds up to all zeros is a set of numbers whose product is a square.
The line under the lanterns is the square split, product = r² + rem, with r the whole-number square root. The remainder is zero exactly when you have won.
One row for each lantern, one column for each prime, a dot where the exponent is odd. The solver strips columns that only one lantern burns (that lantern can never be part of a square), then takes the lightest column, picks its lightest row as a pivot and adds it into the others. A row that empties out is a square.
Thirteen lanterns can be solved by hand. Here is a street of several hundred. Type a word; it names a large number N, and the street is every number near √N whose square, less N, breaks into small primes. Structured elimination thins the matrix until it grows dense, then hands what is left to block Lanczos, which works on thirty-two candidate answers at once. At the end: hundreds of numbers whose product is one enormous perfect square.
The Square Lanterns · by Lars Rocha · the solver is gf2.js: sets for rows and columns, singleton stripping, lightest-column pivots, and Montgomery's block Lanczos over GF(2).