-<BODY BGCOLOR="#FFFFFF">

+<?xml version="1.0" encoding="utf-8"?>

+ html PUBLIC "-//W3C//DTD XHTML 1.1//EN"

+ "http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd">

+<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en-US">

+<title>Mathematical Analysis of the Toggle Squares Game</title>

+<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />

+<meta name="Author" content="Shlomi Fish" />

+<meta name="Keywords" content="Shlomi Fish, Toggle Squares, Ken Housley, Linear Algebra, Mathematics" />

+body { background-color : white; }

-Most of this page is in ASCII, because I sent it to myself from home as an

-email message and some diagrams are less complicated to write in ASCII than

-in HTML. However, I will try to emphasize some stuff in the text with HTML

+<h1>Mathematical Analysis of the Toggle Squares Game</h1>

-I hope everything is clear to you. If you want clarification on something,

-send a message to <A HREF="mailto:shlomi@slink.co.il">shlomi@slink.co.il</A>

-and I'll place the clarification on this page.<P>

- Shlomi Fish<P>

+<p>Most of this page is in ASCII, because I sent it to myself from

+home as an email message and some diagrams are less complicated to

+write in ASCII than in HTML. However, I will try to emphasize some

+stuff in the text with HTML formatting.</p>

+<p>I hope everything is clear to you. If you want clarification on

+something, send a message to <a href=

+"mailto:shlomif@iglu.org.il">shlomif@iglu.org.il</a> and I'll place

+the clarification on this page.</p>

-<B><U>Recent Note:</U></B> I managed to prove that the two-way algorithm works

-for 3k and 3k+1 square boards. It was added as theorems 4 and 5.<P>

-<B><U>More Recent Note:</U></B> Added section about the dimension

-of solutions space in 3k+2 boards and a note about the efficiency of the algorithms.

+<p> Shlomi Fish</p>

+<p><b>Recent Note:</b> I managed to prove that the two-way

+algorithm works for 3k and 3k+1 square boards. It was added as

-<H3>Table of Contents</H3>

-<A HREF="#1Dboard">Analysis of a 1-D Toggle-board</A><BR>

-<A HREF="#lemma1">Lemma 1: 1D is always solveable if vector 100..00 can be formed.</A><BR>

-<A HREF="#lemma2">Lemma 2: 1D is always solveable only for N=3k and 3k+1</A><BR>

-<A HREF="#2Dboard">Main (2-D) Theorems</A><BR>

-<A HREF="#theorem1">Theorem 1: (3k+2)^2 boards are not solveable for every state.</A><BR>

-<A HREF="#theorem2">Theorem 2: 3k and 3k+1 2-D boards are solveable for every state.</A><BR>

-<A HREF="#theorem3">Theorem 3: Solveable 3k+2 boards can be solved by the one way algorithm.</a><BR>

-<A HREF="#theorem4">Theorem 4: Solving 3k boards.</A><BR>

-<A HREF="#theorem5">Theorem 5: Solving 3k+1 boards.</A><BR>

+<p><b>More Recent Note:</b> Added section about the

+dimension of solutions space in 3k+2 boards and a note about the

+efficiency of the algorithms.

-<A HREF="#dim_press_span">The Dimension of the Presses Span of 3k+2 boards</A><BR>

-<A HREF="#efficiency">A Note about Efficiency</A><BR>

+<h2>Table of Contents</h2>

+<a href="#One_Dimensional_Board">Analysis of a 1-D Toggle-board</a><br />

+<a href="#lemma1">Lemma 1: 1D is always solveable if vector 100..00 can be

+<a href="#lemma2">Lemma 2: 1D is always solveable only for N=3k and

+<a href="#Two-Dimensional-Board">Main (2-D) Theorems</a><br />

+<li><a href="#theorem1">Theorem 1:

+(3k+2)^2 boards are not solveable for every state.</a>

+<a href="#theorem2">Theorem 2: 3k and 3k+1 2-D boards are solveable

+<a href="#theorem3">Theorem 3: Solveable 3k+2 boards can be solved

+by the one way algorithm.</a>

+<a href="#theorem4">Theorem 4: Solving 3k boards.</a>

+<a href="#theorem5">Theorem 5: Solving 3k+1 boards.</a>

+<a href="#dim_press_span">The Dimension of the Presses Span of 3k+2

+<a href="#efficiency">A Note about Efficiency</a><br />

+<h2 id="One_Dimensional_Board">Analysis of a 1-D Toggle-board</h2>

First, I'll prove some analogous statements about a one-dimensional

toggle-squares board, i.e: conjectures that apply to the set of rows of size

1*n and in which the presses are:

space (or vector field) {0,1}^n where the operations in the set {0,1} are

XOR for '+' and AND for '*'.

-A 1-D toggle field is solveable for every state if (and only if) the vector

-100...000 can be formed as combination of the presses.

+<h3 id="lemma1">Lemma 1</h3>

+A 1-D toggle field is solveable for every state if (and only if)

+the vector 100...000 can be formed as combination of the

If 1000000 can be solved then along with the press 110000...00 than

010000000 can be solved too. Furthermore:

and one 1, are solveable. Since this is a basis of {1,0}^N then every state

is solveable. (i.e contained in Sp{Presses} )

-A 1-D toggle field of size N is solveable for every state if N = 3k or

-N = 3k+1 and isn't if N = 3k+2 for some non-negative integer k.

+<h3 id="lemma2">Lemma 2</h3>

+A 1-D toggle field of size N is solveable for every state if N = 3k

+or N = 3k+1 and isn't if N = 3k+2 for some non-negative integer

One way to show it is by inspecting the matrixes of the presses set:

and calculate their determinants (according to the boolean operations).

After calculating the determinants of the first three by hand: 1, 0 and 1

-respectively, we can show that the determinant of every matrix where N ~~>~~ 3 is:

+respectively, we can show that the determinant of every matrix where N > 3 is:

based on the first row: det (Presses Matrix (N-1)) XOR - det(Matrix that

contains 1 at the top-left cell and below a Presses Matrix of size N-2) =

-Now for the actual proofs:<BR>

+<h2 id="Two-Dimensional-Board">Analysis of 2-D Boards</h2>

+Now for the actual proofs:

+<h3 id="theorem1">Theorem 1</h3>

2-D (3k+2) * (3k+2) boards are not solveable for every state.

If we take a look at the topmost row - it is affected only by the presses

on the two topmost rows. The effective portions of all the presses on that

presses on the block, much less the entire board can be solved for every

+<h3 id="theorem2">Theorem 2</h3>

2-D boards of size 3k * 3k or (3k+1) * (3k+1) are solveable for

If we restrict ourselves to the presses on cells of one column, then we get

an array of rectangular vectors with a fixed horizontal postion and width

110000 , 111000 , 011100 , 001110 , 000111 , 000011

+<h3 id="theorem3">Theorem 3</h3>

Solveable states of 3k+2 boards can be solved by the one-way

The one way algorithm is described as follows:

Scan every row from top to bottom. For every row, scan every cell from right

to left, and for every filled cell, click the cell to the bottom-left of it.

filled because it's a column-wise contradiction of Lemma 1. Therefore, it

-A 2-D board of size (3k) * (3k) can be solved by using the two-way -

+<h3 id="theorem4">Theorem 4:</h3>

+A 2-D board of size (3k) * (3k) can be solved by using the two-way

The two way algorithm is described as follows:

Scan the rows from top to bottom. For every row, scan the cells from right

of the leftmost filled square, one gets to the 0...11 state, which is

-A 2-D board of size (3k+1)*(3k+1) can be cleared by an down-(edge)-up

-iteration of left-(edge)-right row clearing scheme.

+<h3 id="theorem5">Theorem 5:</h3>

+A 2-D board of size (3k+1)*(3k+1) can be cleared by an

+down-(edge)-up iteration of left-(edge)-right row clearing

This algorithm is similiar to the two-way algorithm, except that if a at the

end of the left iteration, there is a single filled cell, one has to press

-<A NAME="dim_press_span">

-<B>The Dimension of the Presses Span in 3k+2 boards</B>

+<h2 id="dim_press_span">The Dimension of the Presses Span in 3k+2 boards</h2>

(3k+2)*(3k+2) boards are not solveable for every state. The solveable

states form a vector field which is formed by the spanning all the

presses. Since, in this case it does not include all the states, I

vectors. In conclusion, there cannot be less than (3k+1)^2 vectors that

span the space of the solveable states of (3k+2) boards.

-<B>A Note about Efficiency</B>

+<h2 id="efficiency">A Note about Efficiency</h2>

I believe the previous section showed that the 1w-1w algorithm for

clearing (3k+2) boards is as efficient as it could be, i.e. requires

the minimal number of presses.

(yet) regarding "CPU" requirement and growing complexity, and has the

advantage that it can be utilized without the aid of a computer.