Lights Out (game)

Last updated
Selecting a square changes it and the surrounding squares. LightsOutIllustration.svg
Selecting a square changes it and the surrounding squares.

Lights Out is an electronic game released by Tiger Electronics in 1995. [1] The game consists of a 5 by 5 grid of lights. When the game starts, a random number or a stored pattern of these lights is switched on. Pressing any of the lights will toggle it and the adjacent lights. The goal of the puzzle is to switch all the lights off, preferably with as few button presses as possible. [1] [2]

Contents

Merlin , a similar electronic game, was released by Parker Brothers in the 1970s with similar rules on a 3 by 3 grid. Another similar game was produced by Vulcan Electronics in 1983 under the name XL-25. Tiger Toys also produced a cartridge version of Lights Out for its Game com handheld game console in 1997, shipped free with the console. A number of new puzzles similar to Lights Out have been released, such as Lights Out 2000 (5×5 with multiple colors), Lights Out Cube (six 3×3 faces with effects across edges), and Lights Out Deluxe (6×6). [1] [2]

Inventors

Lights Out was created by a group of people including Avi Olti, Gyora Benedek, Zvi Herman, Revital Bloomberg, Avi Weiner and Michael Ganor. The members of the group together and individually also invented several other games, such as Hidato, NimX, iTop and many more.

Gameplay

Lights to toggle to turn off a fully-lit 5x5 board Lights out solution.svg
Lights to toggle to turn off a fully-lit 5×5 board
Interactive Lights Out game. Lights Out SMIL.svg
Interactive Lights Out game.

The game consists of a 5 by 5 grid of lights. When the game starts, a random number or a stored pattern of these lights is switched on. Pressing any of the lights will toggle it and the four adjacent lights. The goal of the puzzle is to switch all the lights off, preferably in as few button presses as possible. [1] [4]

Mathematics

If a light is on, it must be toggled an odd number of times to be turned off. If a light is off, it must be toggled an even number of times (including none at all) for it to remain off. Several conclusions are used for the game's strategy. Firstly, the order in which the lights are pressed does not matter, as the result will be the same. [5] Secondly, in a minimal solution, each light needs to be pressed no more than once, because pressing a light twice is equivalent to not pressing it at all. [5]

In 1998, Marlow Anderson and Todd Feil used linear algebra to prove that not all configurations are solvable and also to prove that there are exactly four winning scenarios, not including redundant moves, for any solvable 5×5 problem. [6] The 5×5 grid of Lights Out can be represented as a 25x1 column vector with a 1 and 0 signifying a light in its on and off state respectively. Each entry is an element of Z2, the field of integers modulo 2. Anderson and Feil found that in order for a configuration to be solvable (deriving the null vector from the original configuration) it must be orthogonal to the two vectors N1 and N2 below (pictured as a 5×5 array but not to be confused with matrices).

In addition, they found that N1 and N2 can be used to find three additional solutions from a solution, and that these four solutions are the only four solutions (excluding redundant moves) to the starting given configuration. These four solutions are X, X + N1, X + N2, and X + N1 + N2 where X is a solution to the starting given configuration. [6] An introduction into this method was published by Robert Eisele. [7]

Light chasing

"Light chasing" is a method similar to Gaussian elimination which always solves the puzzle (if a solution exists), although with the possibility of many redundant steps. [2] [6] [8] In this approach, rows are manipulated one at a time starting with the top row. All the lights are disabled in the row by toggling the adjacent lights in the row directly below. The same method is then used on the consecutive rows up to the last one. The last row is solved separately, depending on its active lights. Corresponding lights (see table below) in the top row are toggled and the initial algorithm is run again, resulting in a solution. [8]

Bottom row isToggle on top row
□□□■■■□■■■
□□■□□■■□■■
□■□□■■■■■□
□■■■□□□■■■
■□□■□□■■■■
■□■□■□■■□■
■■□□□■■■□■

Tables and strategies for other board sizes are generated by playing Lights Out with a blank board and observing the result of bringing a particular light from the top row down to the bottom row.

Further results

Once a single solution is found, a solution with the minimum number of moves can be determined through elimination of redundant sets of button presses that have no cumulative effect. [6] [8] If the 5×5 puzzle is unsolvable under legal game creation, two leftmost lights on the bottom row will remain on when all other lights have been turned off.

Existence of solutions has been proved for a wide variety of board configurations, such as hexagonal, [9] while solutions to n-by-n boards for n≤200 have been explicitly constructed. [10]

There exists a solution for every N×N case. It is solvable on any undirected graph, where clicking on one vertex flips its value and its neighbours. More generally if the action matrix is symmetric then its diagonal is always solvable. [11]

See also

Related Research Articles

In mathematics, the determinant is a scalar value that is a function of the entries of a square matrix. The determinant of a matrix A is commonly denoted det(A), det A, or |A|. Its value characterizes some properties of the matrix and the linear map represented, on a given basis, by the matrix. In particular, the determinant is nonzero if and only if the matrix is invertible and the corresponding linear map is an isomorphism. The determinant of a product of matrices is the product of their determinants.

<span class="mw-page-title-main">Matrix multiplication</span> Mathematical operation in linear algebra

In mathematics, particularly in linear algebra, matrix multiplication is a binary operation that produces a matrix from two matrices. For matrix multiplication, the number of columns in the first matrix must be equal to the number of rows in the second matrix. The resulting matrix, known as the matrix product, has the number of rows of the first and the number of columns of the second matrix. The product of matrices A and B is denoted as AB.

<span class="mw-page-title-main">Scalar multiplication</span> Algebraic operation

In mathematics, scalar multiplication is one of the basic operations defining a vector space in linear algebra. In common geometrical contexts, scalar multiplication of a real Euclidean vector by a positive real number multiplies the magnitude of the vector without changing its direction. Scalar multiplication is the multiplication of a vector by a scalar, and is to be distinguished from inner product of two vectors.

<span class="mw-page-title-main">Nonogram</span> Logic puzzle forming a picture in a grid

Nonograms, also known as Hanjie, Paint by Numbers, Picross, Griddlers, and Pic-a-Pix are picture logic puzzles in which cells in a grid must be colored or left blank according to numbers at the edges of the grid to reveal a hidden picture. In this puzzle, the numbers are a form of discrete tomography that measures how many unbroken lines of filled-in squares there are in any given row or column. For example, a clue of "4 8 3" would mean there are sets of four, eight, and three filled squares, in that order, with at least one blank square between successive sets.

In mathematics, and more specifically in abstract algebra, a *-algebra is a mathematical structure consisting of two involutive ringsR and A, where R is commutative and A has the structure of an associative algebra over R. Involutive algebras generalize the idea of a number system equipped with conjugation, for example the complex numbers and complex conjugation, matrices over the complex numbers and conjugate transpose, and linear operators over a Hilbert space and Hermitian adjoints. However, it may happen that an algebra admits no involution.

<span class="mw-page-title-main">Connect Four</span> Childrens board game

Connect Four is a game in which the players choose a color and then take turns dropping colored tokens into a six-row, seven-column vertically suspended grid. The pieces fall straight down, occupying the lowest available space within the column. The objective of the game is to be the first to form a horizontal, vertical, or diagonal line of four of one's own tokens. It is therefore a type of M,n,k-game with restricted piece placement. Connect Four is a solved game. The first player can always win by playing the right moves.

In mathematics, and in particular linear algebra, the Moore–Penrose inverse of a matrix is the most widely known generalization of the inverse matrix. It was independently described by E. H. Moore in 1920, Arne Bjerhammar in 1951, and Roger Penrose in 1955. Earlier, Erik Ivar Fredholm had introduced the concept of a pseudoinverse of integral operators in 1903. When referring to a matrix, the term pseudoinverse, without further specification, is often used to indicate the Moore–Penrose inverse. The term generalized inverse is sometimes used as a synonym for pseudoinverse.

<span class="mw-page-title-main">Sparse matrix</span> Matrix in which most of the elements are zero

In numerical analysis and scientific computing, a sparse matrix or sparse array is a matrix in which most of the elements are zero. There is no strict definition regarding the proportion of zero-value elements for a matrix to qualify as sparse but a common criterion is that the number of non-zero elements is roughly equal to the number of rows or columns. By contrast, if most of the elements are non-zero, the matrix is considered dense. The number of zero-valued elements divided by the total number of elements is sometimes referred to as the sparsity of the matrix.

<span class="mw-page-title-main">15 Puzzle</span> Sliding puzzle with fifteen pieces and one space

The 15 Puzzle is a sliding puzzle. It has 15 square tiles numbered 1 to 15 in a frame that is 4 tile positions high and 4 tile positions wide, with one unoccupied position. Tiles in the same row or column of the open position can be moved by sliding them horizontally or vertically, respectively. The goal of the puzzle is to place the tiles in numerical order.

In linear algebra, a generalized eigenvector of an matrix is a vector which satisfies certain criteria which are more relaxed than those for an (ordinary) eigenvector.

<span class="mw-page-title-main">Sudoku</span> Logic-based number-placement puzzle

Sudoku is a logic-based, combinatorial number-placement puzzle. In classic Sudoku, the objective is to fill a 9 × 9 grid with digits so that each column, each row, and each of the nine 3 × 3 subgrids that compose the grid contains all of the digits from 1 to 9. The puzzle setter provides a partially completed grid, which for a well-posed puzzle has a single solution.

<span class="mw-page-title-main">Light Up (puzzle)</span> Logic puzzle

Light Up, also called Akari is a binary-determination logic puzzle published by Nikoli. As of 2011, three books consisting entirely of Light Up puzzles have been published by Nikoli.

<span class="mw-page-title-main">Mathematics of Sudoku</span> Mathematical investigation of Sudoku

Mathematics can be used to study Sudoku puzzles to answer questions such as "How many filled Sudoku grids are there?", "What is the minimal number of clues in a valid puzzle?" and "In what ways can Sudoku grids be symmetric?" through the use of combinatorics and group theory.

<span class="mw-page-title-main">Glossary of Sudoku</span>

This is a glossary of Sudoku terms and jargon. It is organized thematically, with links to references and example usage provided as ([1]). Sudoku with a 9×9 grid is assumed, unless otherwise noted.

In numerical linear algebra, the Jacobi method is an iterative algorithm for determining the solutions of a strictly diagonally dominant system of linear equations. Each diagonal element is solved for, and an approximate value is plugged in. The process is then iterated until it converges. This algorithm is a stripped-down version of the Jacobi transformation method of matrix diagonalization. The method is named after Carl Gustav Jacob Jacobi.

In numerical analysis and linear algebra, lower–upper (LU) decomposition or factorization factors a matrix as the product of a lower triangular matrix and an upper triangular matrix. The product sometimes includes a permutation matrix as well. LU decomposition can be viewed as the matrix form of Gaussian elimination. Computers usually solve square systems of linear equations using LU decomposition, and it is also a key step when inverting a matrix or computing the determinant of a matrix. The LU decomposition was introduced by the Polish astronomer Tadeusz Banachiewicz in 1938. To quote: "It appears that Gauss and Doolittle applied the method [of elimination] only to symmetric equations. More recent authors, for example, Aitken, Banachiewicz, Dwyer, and Crout … have emphasized the use of the method, or variations of it, in connection with non-symmetric problems … Banachiewicz … saw the point … that the basic problem is really one of matrix factorization, or “decomposition” as he called it." It is also sometimes referred to as LR decomposition.

<span class="mw-page-title-main">Sense switch</span> A switch on the console of a computer that can be read by software

A sense switch, or program switch, is a switch on the front panel of a computer whose state can be tested by conditional branch instructions in software. Most early computers had several sense switches. They were typically used by the operator to set program options.

An algebraic Riccati equation is a type of nonlinear equation that arises in the context of infinite-horizon optimal control problems in continuous time or discrete time.

In the mathematical discipline of numerical linear algebra, a matrix splitting is an expression which represents a given matrix as a sum or difference of matrices. Many iterative methods depend upon the direct solution of matrix equations involving matrices more general than tridiagonal matrices. These matrix equations can often be solved directly and efficiently when written as a matrix splitting. The technique was devised by Richard S. Varga in 1960.

Birkhoff's algorithm is an algorithm for decomposing a bistochastic matrix into a convex combination of permutation matrices. It was published by Garrett Birkhoff in 1946. It has many applications. One such application is for the problem of fair random assignment: given a randomized allocation of items, Birkhoff's algorithm can decompose it into a lottery on deterministic allocations.

References

  1. 1 2 3 4 'Beyond Tetris' - Lights Out, Tony Delgado, GameSetWatch, January 29, 2007. Accessed on line October 18, 2007.
  2. 1 2 3 Lights Out, Jaap's Puzzle Page. Accessed on line October 18, 2007.
  3. ↑ "Programming Puzzle: Lights Toggle". 13 December 2020.
  4. ↑ "Archive of Interesting Code". www.keithschwarz.com. Retrieved 2020-06-12.
  5. 1 2 Weisstein, Eric W. "Lights Out Puzzle". MathWorld .
  6. 1 2 3 4 Marlow Anderson, Todd Feil (1998). "Turning Lights Out with Linear Algebra" (PDF). Mathematics Magazine . 71 (4): 300–303. doi:10.1080/0025570X.1998.11996658. Archived from the original (PDF) on 15 August 2014.
  7. ↑ Eisele, Robert (2018-07-30). "LightsOut Solution using Linear Algebra" . Retrieved 2024-03-20.
  8. 1 2 3 Solving Lights Out, Matthew Baker.
  9. ↑ unknown (20 Nov 2010). "Lights out game on hexagonal grid" . Retrieved 30 November 2010.
  10. ↑ Jim Fowler (21 July 2008). "Solutions to Lights Out". Jim Fowler blog. Retrieved 30 November 2010.
  11. ↑ Igor Minevich (2012). "Symmetric Matrices over F_2 and the Lights Out Problem". arXiv: 1206.2973 [math.RA].
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.