Quatrainment: A game in a 4 X 4 grid

The game of Quatrainment is played on two 4 x 4 grids. One grid, called the initial grid has some of its cells marked (state 1) and some unmarked (state 0). The second grid, called the target grid has similar property, and the objective of the game is to transform the initial gird to the target grid. The player moves by choosing a cell of the initial grid and this reverses the state of some of the cells in it, depending on the cell chosen. After a finite sequence of moves, the initial grid is transformed to the target grid.With the use of Linear Algebra, particularly the concepts of basis and linear combination, the minimum number of moves necessary to transform the initial grid to the final grid is determined. Matrices with entries 0's and 1's form a vector space over the field with two elements 0 and 1. Addition and multiplication are based on modulo 2. Thus, the matrices are called Boolean matrices. The standard basis for this vector space has 16 elements, each of which is a matrix with exactly one entry equal to 1.This study shows how to select a set of cells which will alter exactly one chosen cell of the initial grid. The concept of linear combination of vectors is used here. This solution is then used to find a minimum algorithm for arriving at the target grid. It is shown that at most 16 moves are necessary to transform any initial grid to any specified target grid.The thesis also includes the design of a Turbo Pascal program to implement the game in a computer.