 | This article has multiple issues. Please help improve it or discuss these issues on the talk page . (Learn how and when to remove these template messages)
|
Board puzzles with algebra of binary variables ask players to locate the hidden objects based on a set of clue cells and their neighbors marked as variables (unknowns). A variable with value of 1 corresponds to a cell with an object. Conversely, a variable with value of 0 corresponds to an empty cell—no hidden object.
These puzzles are based on algebra with binary variables taking a pair of values, for example, (no, yes), (false, true), (not exists, exists), (0, 1). It invites the player quickly establish some equations, and inequalities for the solution. The partitioning can be used to reduce the complexity of the problem. Moreover, if the puzzle is prepared in a way that there exists a unique solution only, this fact can be used to eliminate some variables without calculation.
The problem can be modeled as binary integer linear programming which is a special case of integer linear programming. [1]
Minesweeper, along with its variants, is the most notable example of this type of puzzle.
Below the letters in the mathematical statements are used as variables where each can take the value either 0 or 1 only. A simple example of an equation with binary variables is given below:
Here there are two variables a and b but one equation. The solution is constrained by the fact that a and b can take only values 0 or 1. There is only one solution here, both a= 0, and b= 0. Another simple example is given below:
The solution is straightforward: a and b must be 1 to make a+b equal to 2.
Another interesting case is shown below:
Here, the first statement is an equation and the second statement is an inequality indicating the three possible cases:
The last case causes a contradiction on c by forcing c= 2, which is not possible. Therefore, either first or second case is correct. This leads to the fact that c must be 1.
The modification of a large equation into smaller form is not difficult. However, an equation set with binary variables cannot be always solved by applying linear algebra. The following is an example for applying the subtraction of two equations:
The first statement has four variables whereas the second statement has only two variables. The latter one means that the sum of c and d is 1. Using this fact on the first statement, the equations above can be reduced to
A game based on the algebra with binary variables can be visualized in many different ways. One generic way is to represent the right side of an equation as a clue in a cell (clue cell), and the neighbors of a clue cell as variables. A simple case is shown in Figure 1. The neighbors can be assumed to be the up/down, left/right, and corner cells that are sharing an edge or a corner. The white cells may contain a hidden object or nothing. In other words, they are the binary variables. They take place on the left side of the equations. Each clue cell, a cell with blue background in Figure 1, contains a positive number corresponding to the number of its neighbors that have hidden objects. The total number of the objects on the board can be given as an additional clue. The same board with variables marked is shown in Figure 2.
The main equation is written by using the total number of the hidden objects given. From the first figure this corresponds to the following equation
The other equations are composed one by one for each clue cells:
Although there are several ways to solve the equations above, the following explicit way can be applied:
 |  |  |
In the example above (Figure 2), the variables a, b, c, and e are the neighbors of the clue cell 1 and they are not neighbors of any other cell. It is obvious that the followings are possible solutions:
However, if the puzzle is prepared so that we should have one only one (unique) solution, we can set that all these variables a, b, c, and e must be 0. Otherwise there become more than one solutions.
Some puzzle configurations may allow the player to use partitioning [2] for complexity reduction. An example is given in Figure 5. Each partition corresponds to a number of the objects hidden. The sum of the hidden objects in the partitions must be equal to the total number of objects hidden on the board. One possible way to determine a partitioning is to choose the lead clue cells which have no common neighbors. The cells outside of the red transparent zones in Figure 5 must be empty. In other words, there are no hidden objects in the all-white cells. Since there must be a hidden object within the upper partition zone, the third row from top shouldn't contain a hidden object. This leads to the fact that the two variable cells on the bottom row around the clue cell must have hidden objects. The rest of the solution is straightforward.
At some cases, the player can set a variable cell as 1 and check if any inconsistency occurs. The example in Figure 6 shows an inconsistency check. The cell marked with an hidden object Δ is under the test. Its marking leads to the set all the variables (grayed cells) to be 0. This follows the inconsistency. The clue cell marked red with value 1 does not have any remaining neighbor that can include a hidden object. Therefore, the cell under the test must not include a hidden object. In algebraic form we have two equations:
Here a, b, c, and d correspond to the top four grayed cells in Figure 6. The cell with Δ is represented by the variable f, and the other two grayed cells are marked as e and g. If we set f= 1, then a= 0, b= 0, c= 0, d= 0, e= 0, g= 0. The first equation above will have the left hand side equal to 0 while the right hand side has 1. A contradiction.
Try-and-check may need to be applied consequently in more than one step on some puzzles in order to reach a conclusion. This is equivalent to binary search algorithm [3] to eliminate possible paths which lead to inconsistency.
Because of binary variables, the equation set for the solution does not possess linearity property. In other words, the rank of the equation matrix may not always address the right complexity.
The complexity of this class of puzzles can be adjusted in several ways. One of the simplest method is to set a ratio of the number of the clue cells to the total number of the cells on the board. However, this may result a largely varying complexity range for a fixed ratio. Another method is to reduce clue cells based on some problem solving strategies step by step. The complex strategies may be enabled for high complexity levels such as subtracting an equation with another one, or the higher depth of try-and-check steps. When the board size increases, the range of the problem cases increases. The ratio of the number of hidden objects to the total number of cells affects the complexity of the puzzle too.
In mathematics, analytic geometry, also known as coordinate geometry or Cartesian geometry, is the study of geometry using a coordinate system. This contrasts with synthetic geometry.
In computer science, an abstract data type (ADT) is a mathematical model for data types, defined by its behavior (semantics) from the point of view of a user of the data, specifically in terms of possible values, possible operations on data of this type, and the behavior of these operations. This mathematical model contrasts with data structures, which are concrete representations of data, and are the point of view of an implementer, not a user. For example, a stack has push/pop operations that follow a Last-In-First-Out rule, and can be concretely implemented using either a list or an array. Another example is a set which stores values, without any particular order, and no repeated values. Values themselves are not retrieved from sets; rather, one tests a value for membership to obtain a Boolean "in" or "not in".
In mathematics, an equation is a mathematical formula that expresses the equality of two expressions, by connecting them with the equals sign =. The word equation and its cognates in other languages may have subtly different meanings; for example, in French an équation is defined as containing one or more variables, while in English, any well-formed formula consisting of two expressions related with an equals sign is an equation.
Elementary algebra, also known as college algebra, encompasses the basic concepts of algebra. It is often contrasted with arithmetic: arithmetic deals with specified numbers, whilst algebra introduces variables.
In mathematics, the Euclidean algorithm, or Euclid's algorithm, is an efficient method for computing the greatest common divisor (GCD) of two integers (numbers), the largest number that divides them both without a remainder. It is named after the ancient Greek mathematician Euclid, who first described it in his Elements . It is an example of an algorithm, a step-by-step procedure for performing a calculation according to well-defined rules, and is one of the oldest algorithms in common use. It can be used to reduce fractions to their simplest form, and is a part of many other number-theoretic and cryptographic calculations.
In mathematics, a system of linear equations is a collection of two or more linear equations involving the same variables. For example,
In mathematics and science, a nonlinear system is a system in which the change of the output is not proportional to the change of the input. Nonlinear problems are of interest to engineers, biologists, physicists, mathematicians, and many other scientists since most systems are inherently nonlinear in nature. Nonlinear dynamical systems, describing changes in variables over time, may appear chaotic, unpredictable, or counterintuitive, contrasting with much simpler linear systems.
Constraint satisfaction problems (CSPs) are mathematical questions defined as a set of objects whose state must satisfy a number of constraints or limitations. CSPs represent the entities in a problem as a homogeneous collection of finite constraints over variables, which is solved by constraint satisfaction methods. CSPs are the subject of research in both artificial intelligence and operations research, since the regularity in their formulation provides a common basis to analyze and solve problems of many seemingly unrelated families. CSPs often exhibit high complexity, requiring a combination of heuristics and combinatorial search methods to be solved in a reasonable time. Constraint programming (CP) is the field of research that specifically focuses on tackling these kinds of problems. Additionally, the Boolean satisfiability problem (SAT), satisfiability modulo theories (SMT), mixed integer programming (MIP) and answer set programming (ASP) are all fields of research focusing on the resolution of particular forms of the constraint satisfaction problem.
In mathematics, a quadratic form is a polynomial with terms all of degree two. For example,
In mathematics, a quadratic irrational number is an irrational number that is the solution to some quadratic equation with rational coefficients which is irreducible over the rational numbers. Since fractions in the coefficients of a quadratic equation can be cleared by multiplying both sides by their least common denominator, a quadratic irrational is an irrational root of some quadratic equation with integer coefficients. The quadratic irrational numbers, a subset of the complex numbers, are algebraic numbers of degree 2, and can therefore be expressed as
In mathematical optimization, Dantzig's simplex algorithm is a popular algorithm for linear programming.
An integer programming problem is a mathematical optimization or feasibility program in which some or all of the variables are restricted to be integers. In many settings the term refers to integer linear programming (ILP), in which the objective function and the constraints are linear.
In computer science, 2-satisfiability, 2-SAT or just 2SAT is a computational problem of assigning values to variables, each of which has two possible values, in order to satisfy a system of constraints on pairs of variables. It is a special case of the general Boolean satisfiability problem, which can involve constraints on more than two variables, and of constraint satisfaction problems, which can allow more than two choices for the value of each variable. But in contrast to those more general problems, which are NP-complete, 2-satisfiability can be solved in polynomial time.
In mathematics, a variable is a symbol that represents a mathematical object. A variable may represent a number, a vector, a matrix, a function, the argument of a function, a set, or an element of a set.
The complexity of constraint satisfaction is the application of computational complexity theory to constraint satisfaction. It has mainly been studied for discriminating between tractable and intractable classes of constraint satisfaction problems on finite domains.
Boolean algebra is a mathematically rich branch of abstract algebra. Stanford Encyclopaedia of Philosophy defines Boolean algebra as 'the algebra of two-valued logic with only sentential connectives, or equivalently of algebras of sets under union and complementation.' Just as group theory deals with groups, and linear algebra with vector spaces, Boolean algebras are models of the equational theory of the two values 0 and 1. Common to Boolean algebras, groups, and vector spaces is the notion of an algebraic structure, a set closed under some operations satisfying certain equations.
The Karnaugh map is a method of simplifying Boolean algebra expressions. Maurice Karnaugh introduced it in 1953 as a refinement of Edward W. Veitch's 1952 Veitch chart, which itself was a rediscovery of Allan Marquand's 1881 logical diagram aka Marquand diagram but now with a focus set on its utility for switching circuits. Veitch charts are also known as Marquand–Veitch diagrams, Svoboda charts -(albeit only rarely)- and even Karnaugh maps as Karnaugh–Veitch maps.
Zhegalkinpolynomials, also known as algebraic normal form, are a representation of functions in Boolean algebra. Introduced by the Russian mathematician Ivan Ivanovich Zhegalkin in 1927, they are the polynomial ring over the integers modulo 2. The resulting degeneracies of modular arithmetic result in Zhegalkin polynomials being simpler than ordinary polynomials, requiring neither coefficients nor exponents. Coefficients are redundant because 1 is the only nonzero coefficient. Exponents are redundant because in arithmetic mod 2, x2 = x. Hence a polynomial such as 3x2y5z is congruent to, and can therefore be rewritten as, xyz.
Algebra is the branch of mathematics that studies algebraic structures and the manipulation of statements within those structures. It is a generalization of arithmetic that introduces variables and algebraic operations other than the standard arithmetic operations such as addition and multiplication.
In mathematics and mathematical logic, Boolean algebra is a branch of algebra. It differs from elementary algebra in two ways. First, the values of the variables are the truth values true and false, usually denoted 1 and 0, whereas in elementary algebra the values of the variables are numbers. Second, Boolean algebra uses logical operators such as conjunction (and) denoted as ∧, disjunction (or) denoted as ∨, and negation (not) denoted as ¬. Elementary algebra, on the other hand, uses arithmetic operators such as addition, multiplication, subtraction, and division. Boolean algebra is therefore a formal way of describing logical operations in the same way that elementary algebra describes numerical operations.
