Sprouts

Sprouts is a pencil-and-paper game with interesting mathematical properties. It was invented by mathematicians John Horton Conway and Michael S. Paterson at Cambridge University in 1967. A 2-spot game of Sprouts The game is played by two players, starting with a few spots drawn on a sheet of paper.

Players take turns, where each turn consists of drawing a line between two spots (or from a spot to itself) and adding a new spot somewhere along the line. The players are constrained by the following rules.

• The line may be straight or curved, but must not touch or cross itself or any other line.

• The new spot cannot be placed on top of one of the endpoints of the new line. Thus the new spot splits the line into two shorter lines.

• No spot may have more than three lines attached to it. For the purposes of this rule, a line from the spot to itself counts as two attached lines and new spots are counted as having two lines already attached to them. In so-called normal play, the player who makes the last move wins.

In misère play, the player who makes the last move loses. The diagram on the right shows a 2-spot game of normal-play Sprouts. After the fourth move, most of the spots are dead–they have three lines attached to them, so they cannot be used as endpoints for a new line.

There are two spots (shown in green) that are still alive, having fewer than three lines attached. However, it is impossible to make another move, because a line from a live spot to itself would make four attachments, and a line from one live spot to the other would cross lines. Therefore, no fifth move is possible, and the first player loses. Live spots at the end of the game are called survivors and play a key role in the analysis of Sprouts. Analysis Suppose that a game starts with n spots and lasts for exactly m moves.

Each spot starts with three lives (opportunities to connect a line) and each move reduces the total number of lives in the game by one (two lives are lost at the ends of the line, but the new spot has one life). So at the end of the game there are 3n−m remaining lives. Each surviving spot has only one life (otherwise there would be another move joining that spot to itself), so there are exactly 3n−m survivors.

There must be at least one survivor, namely the spot added in the final move. So 3n−m ≥ 1; hence a game can last no more than 3n−1 moves. By enumerating all possible moves, one can show that the first player when playing with the best possible strategy will always win in normal-play games starting with n = 3, 4, or 5 spots. The second player wins when n = 0, 1, 2, or 6. At Bell Labs in 1990, David Applegate, Guy Jacobson, and Daniel Sleator used a lot of computer power to push the analysis out to eleven spots in normal play and nine spots in misère play.

Josh Purinton and Roman Khorkov have extended this analysis to sixteen spots in misère play. Julien Lemoine and Simon Viennot have calculated normal play outcomes up to thirty-two spots, plus five more games between thirty-four and forty-seven spots.

They have also announced a result for the seventeen-spot misère game.  The normal-play results are all consistent with the pattern observed by Applegate et al. up to eleven spots and conjectured to continue indefinitely, that the first player has a winning strategy when the number of spots divided by six leaves a remainder of three, four, or five. The results for misère play do not follow as simple a pattern: up to seventeen spots, the first player wins in misère Sprouts when the remainder (mod 6) is zero, four, or five, except that the first player wins the one-spot game and loses the four-spot game.

Phutball

Phutball (short for philosopher’s football) is a two-player board game described in Elwyn Berlekamp, John Horton Conway, and Richard Guy’s Winning Ways for your Mathematical Plays.

Rules Phutball is played on the intersections of a 19×15 grid using one white stone and as many black stones as needed. In this article the two players are named Ohs (O) and Eks (X). The board is labeled A through P (omitting I) from left to right and 1 to 19 from bottom to top from Ohs’ perspective.

Rows 0 and 20 represent “off the board” beyond rows 1 and 19 respectively. Given that specialized phutball boards are hard to come by, the game is usually played on a 19×19 Go board, with a white stone representing the football and black stones representing the men.

The objective is to score goals by using the men (the black stones) to move the football (the white stone) onto or over the opponent’s goal line. Ohs tries to move the football to rows 19 or 20 and Eks to rows 1 or 0. At the start of the game the football is placed on the central point, unless one player gives the other a handicap, in which case the ball starts nearer one player’s goal. Players alternate making moves. A move is either to add a man to any vacant point on the board or to move the ball. There is no difference between men played by Ohs and those played by Eks.

The football is moved by a series of jumps over adjacent men. Each jump is to the first vacant point in a straight line horizontally, vertically, or diagonally over one or more men. The jumped men are then removed from the board (before any subsequent jump occurs).

This process repeats for as long as there remain men available to be jumped and the player desires. Jumping is optional, there is no requirement to jump. Note that in contrast to checkers, multiple men in a row are jumped and removed as a group. The diagram on the right illustrates a jump.

• Ohs moves the football from K6-G9-G11-J11. • The men on J7, H8, G10, and H11 are removed.

• The jump from K6-G9-J9-G7 would not be legal, as that would jump the man on H8 twice.

If the football ends the move on or over the opponent’s goal line then a goal has been scored. If the football passes through your goal line, but ends up elsewhere due to further jumps, the game continues. Strategy • Carefully set up sequences of jumps can be “spoiled” by extending them at critical moments.

• A jump to the left or right edge can be blocked by leaving no vacant points.

• When you jump, it is usually bad to leave an easily used return path for your opponent to “undo” your progress. The game is sufficiently complex that checking whether there is a win in one (on an m×n board) is NP-complete. It is not known whether any player has a winning strategy or both players have a drawing strategy.

Hexapawn

Hexapawn is a deterministic two-player game invented by Martin Gardner. It is played on a rectangular board of variable size, for example on a 3×3 board or on a chessboard. On a board of size n×m, each player begins with m pawns, one for each square in the row closest to them.

The goal of each player is to advance one of their pawns to the opposite end of the board or to prevent the other player from moving.

Hexapawn on the 3×3 board is a solved game; if both players play well, the first player to move will always lose. Also it seems that any player cannot capture all enemy’s pawns. Indeed, Gardner specifically constructed it as a game with a small game tree, in order to demonstrate how it could be played by a heuristic AI implemented by a mechanical computer. A variant of this game is octapawn.

Rules As in chess, each pawn may be moved in two different ways: it may be moved one square forward, or it may capture a pawn one square diagonally ahead of it. A pawn may not be moved forward if there is a pawn in the next square.

Unlike chess, the first move of a pawn may not advance it by two spaces. A player loses if he/she has no legal moves or the other player reaches the end of the board with a pawn. Dawson’s chess Whenever a player advances a pawn to the penultimate rank (unless it is an isolated pawn) there is a threat to proceed to the final rank by capture.

The opponent’s only sensible responses are therefore either to capture the advanced pawn or to advance the threatened one, the latter only being sensible in the case that there is one threatened pawn rather than two. If one restricts 3× hexapawn with the additional rule that the capture is always compulsory, the result is the game Dawson’s chess. Dawson’s chess reduces to the impartial game denoted .137 in Conway’s notation.

This means that it is equivalent to a Nim-like game in which:

• on a turn, the player may remove one to three objects from a heap,

• removing just one object is a legal move only if the removed object is the only object in the heap, and

• when removing three objects from a heap of five or more, the player may also split the remainder into two heaps

Dots and Boxes

Dots and Boxes (also known as Boxes, Squares, Paddocks, Square-it, Dots and Dashes, Dots, Smart Dots, Dot Boxing, or, simply, the Dot Game) is a pencil and paper game for two players (or sometimes, more than two) first published in 1889 by Édouard Lucas.

Game of dots and boxes on the 2×2 board. Starting with an empty grid of dots, players take turns, adding a single horizontal or vertical line between two unjoined adjacent dots.

A player who completes the fourth side of a box earns one point and takes another turn. (The points are typically recorded by placing in the box an identifying mark of the player, such as an initial). The game ends when no more lines can be placed. The winner of the game is the player with the most points.

The board may be of any size. When short on time, 2×2 boxes (created by a square of 9 dots) is good for beginners, and 6×6 is good for experts. In games with an even number of boxes, it is conventional that if the game is tied then the win should be awarded to the second player (this offsets the advantage of going first).

The diagram on the right shows a game being played on the 2×2 board. The second player (B) plays the mirror image of the first player’s move, hoping to divide the board into two pieces and tie the game. The first player (A) makes a sacrifice at move 7; B accepts the sacrifice, getting one box. However, B must now add another line, and connects the center dot to the center-right dot, causing the remaining boxes to be joined together in a chain as shown at the end of move 8. With A’s next move, A gets them all, winning 3–1.

At the start of a game, play is more or less random, the only strategy is to avoid adding the third side to any box. This continues until all the remaining (potential) boxes are joined together into chains – groups of one or more adjacent boxes in which any move gives all the boxes in the chain to the opponent.

A novice player faced with a situation like position 1 in the diagram on the left, in which some boxes can be captured, takes all the boxes in the chain, resulting in position 2. But with their last move, they have to open the next (and larger) chain, and the novice loses the game, An experienced player faced with position 1 instead plays the double-cross strategy, taking all but 2 of the boxes in the chain, leaving position 3. This leaves the last two boxes in the chain for their opponent, but then the opponent has to open the next chain. By moving to position 3, player A wins.

The double-cross strategy applies however many long chains there are. Take all but two of the boxes in each chain, but take all the boxes in the last chain. If the chains are long enough then the player will certainly win.

Therefore, when played by experts, Dots and Boxes becomes a battle for control: An expert player tries to force their opponent to start the first long chain. Against a player who doesn’t understand the concept of a sacrifice, the expert simply has to make the correct number of sacrifices to encourage the opponent to hand him the first chain long enough to ensure a win. If the other player also knows to offer sacrifices, the expert also has to manipulate the number of available sacrifices through earlier play. There is never any reason not to accept a sacrifice, as if it is refused, the player who offered it can always take it without penalty.

Thus, the impact of refusing a sacrifice need not be considered in your strategy. Experienced players can avoid the chaining phenomenon by making early moves to split the board. A board split into 4×4 squares is ideal. Dividing limits the size of chains- in the case of 4×4 squares, the longest possible chain is four, filling the larger square.

A board with an even number of spaces will end in a draw (as the number of 4×4 squares will be equal for each player); an odd numbered board will lead to the winner winning by one square (the 4×4 squares and 2×1 half-squares will fall evenly, with one box not incorporated into the pattern falling to the winner). A common alternate ruleset is to require all available boxes be claimed on your turn.

This eliminates the double cross strategy, forcing even the experienced player to take all the boxes, and give his opponent the win. In combinatorial game theory dots and boxes is very close to being an impartial game and many positions can be analyzed using Sprague–Grundy theory. Dots and boxes need not be played on a rectangular grid. It can be played on a triangular grid or a hexagonal grid. Investigations on a triangular variation of the game have even been carried out by Raffles Institution students. There is also a variant in Bolivia when it is played in a Chakana or Inca Cross grid, which adds more complications to the game. Dots-and-boxes has a dual form called “strings-and-coins”.

This game is played on a network of coins (vertices) joined by strings (edges). Players take turns to cut a string. When a cut leaves a coin with no strings, the player pockets the coin and takes another turn. The winner is the player who pockets the most coins. Strings-and-coins can be played on an arbitrary graph. A variant played in Poland allows a player to claim a region of several squares as soon as its boundary is completed.

Polyform

In recreational mathematics, a polyform is a plane figure constructed by joining together identical basic polygons.

The basic polygon is often (but not necessarily) a convex plane-filling polygon, such as a square or a triangle. More specific names have been given to polyforms resulting from specific basic polygons, as detailed in the table below. For example, a square basic polygon results in the well-known polyominoes.

Construction rules The rules for joining the polygons together may vary, and must therefore be stated for each distinct type of polyform. Generally, however, the following rules apply:

1. Two basic polygons may be joined only along a common edge.

2. No two basic polygons may overlap.

3. A polyform must be connected (that is, all one piece; see connected graph, connected space). Configurations of disconnected basic polygons do not qualify as polyforms.

4. The mirror image of an asymmetric polyform is not considered a distinct polyform (polyforms are “double sided”).

Generalizations Polyforms can also be considered in higher dimensions. In 3-dimensional space, basic polyhedra can be joined along congruent faces. Joining cubes in this way produces the polycubes. One can allow more than one basic polygon.

The possibilities are so numerous that the exercise seems pointless, unless extra requirements are brought in. For example, the Penrose tiles define extra rules for joining edges, resulting in interesting polyforms with a kind of pentagonal symmetry. When the base form is a polygon that tiles the plane, rule 1 may be broken.

For instance, squares may be joined orthogonally at vertices, as well as at edges, to form polyplets or polykings.

Types and applications Polyforms are a rich source of problems, puzzles and games. The basic combinatorial problem is counting the number of different polyforms, given the basic polygon and the construction rules, as a function of n, the number of basic polygons in the polyform. Well-known puzzles include the pentomino puzzle and the Soma cube

TetraVex

TetraVex is a puzzle computer game, available for Windows and Linux systems.

TetraVex is an edge-matching puzzle. The player is presented with a grid (by default, 3×3) and nine square tiles, each with a number on each edge. The objective of the game is to place the tiles in the grid in the proper position as fast as possible. Two tiles can only be placed next to each other if the numbers on adjacent faces match.

TetraVex was originally available for Windows in Windows Entertainment Pack 3. It was later re-released as part of the Best of Windows Entertainment Pack. It is also available as an open source game on the GNOME desktop.

Origins The original version of TetraVex (for the Windows Entertainment Pack 3) was written (and named) by Scott Ferguson who was also the Development Lead and an architect of the first version of Visual Basic .

TetraVex was inspired by “the problem of tiling the plane” as described by Donald Knuth on page 382 of Volume 1: Fundamental Algorithms, the first book in his The Art of Computer Programming series. In the TetraVex version for Windows, the Microsoft Blibbet logo is displayed if the player solves a 6 by 6 puzzle.

The tiles are also known as McMahon Squares, named for Percy McMahon who explored their possibilities in the 1920s. Counting the possible number of TetraVex Since the game is simple in its definition, it is easy to count how many possible TetraVex are for each grid of size . For instance, if , there are possible squares with a number from zero to nine on each edge. Therefore for there are possible TetraVex puzzles.

There are possible TetraVex in a grid of size . Proof sketch: For this is true. We can proceed with mathematical induction. Take a grid of . The first rows and the first columns form a grid of and by the hypothesis of induction, there are possible TetraVex on that subgrid. Now, for each possible TetraVex on the subgrid, we can choose squares to be placed in the position of the grid (first row, last column), because only one side is determined.

Once this square is chosen, there are squares available to be placed in the position , and fixing that square we have possibilities for the square on position . We can go on until the square on position is fixed. The same is true for the last row: there are possibilities for the square on the first column and last row, and for all the other. This gives us . Then the proposition is proven by induction. It is easy to see that if the edges of the squares are allowed to take possible numbers, then there are possible TetraVex puzzles.

Mathematics of Sudoku

The class of Sudoku puzzles consists of a partially completed row-column grid of cells partitioned into N regions each of size N cells, to be filled in using a prescribed set of N distinct symbols (typically the numbers {1, …, N}), so that each row, column and region contains exactly one of each element of the set. The puzzle can be investigated using mathematics.

The mathematical analysis of Sudoku falls into two main areas: analyzing the properties of a) completed grids and b) puzzles. Grid analysis has largely focused on counting (enumerating) possible solutions for different variants. Puzzle analysis centers on the initial given values.

The techniques used in either are largely the same: combinatoric and permutation group theory, augmented by the dexterous application of programming tools. There are many Sudoku variants, (partially) characterized by the size (N) and shape of their regions.

For classic Sudoku, N=9 and the regions are 3×3 squares (blocks). A rectangular Sudoku uses rectangular regions of row-column dimension R×C. For R×1 (and 1×C), i.e. where the region is a row or column, Sudoku becomes a Latin square. Other Sudoku variants also exist, such as those with irregularly-shaped regions or with additional constraints or different constraint types. See Sudoku – Variants for a discussion of variants and Sudoku terms and jargon for an expanded listing.

The mathematics of Sudoku is a relatively new area of exploration, mirroring the popularity of Sudoku itself. NP-completeness was documented late 2002 , enumeration results began appearing in May 2005 . In contrast with the two main mathematical approaches of Sudoku mentioned above, an approach resting on mathematical logic and dealing with the resolution of the puzzles from the viewpoint of a player has recently been proposed in Denis Berthier’s book “The Hidden Logic of Sudoku”. This formalizes certain mathematical symmetries.

The general problem of solving Sudoku puzzles on n2 × n2 boards of n × n blocks is known to be NP-complete . For n=3 (classical Sudoku), however, this result is of little relevance: algorithms such as Dancing Links can solve puzzles in fractions of a second. Solving Sudoku puzzles can be expressed as a graph coloring problem. Consider the 9 × 9 = 32 × 32 case. The aim of the puzzle in its standard form is to construct a proper 9-coloring of a particular graph, given a partial 9-coloring.

The graph in question has 81 vertices, one vertex for each cell of the grid. The vertices can be labeled with the ordered pairs (x, y), where x and y are integers between 1 and 9. In this case, two distinct vertices labeled by (x, y) and (x′, y′) are joined by an edge if and only if: • x = x′ (same column) or, • y = y′ (same row) or, • ⌈ x/3 ⌉ = ⌈ x′/3 ⌉ and ⌈ y/3 ⌉ = ⌈ y′/3 ⌉ (same 3 × 3 cell) The puzzle is then completed by assigning an integer between 1 and 9 to each vertex, in such a way that vertices that are joined by an edge do not have the same integer assigned to them. A valid Sudoku solution grid is also a Latin square.

There are significantly fewer valid Sudoku solution grids than Latin squares because Sudoku imposes the additional regional constraint. Nonetheless, the number of valid Sudoku solution grids for the standard 9×9 grid was calculated by Bertram Felgenhauer and Frazer Jarvis in 2005 to be 6,670,903,752,021,072,936,960 (sequence A107739 [12] in OEIS). This number is equal to 9! × 722 × 27 × 27,704,267,971, the last factor of which is prime. The result was derived through logic and brute force computation. Russell and Jarvis also showed that when symmetries were taken into account, there were 5,472,730,538 solutions (sequence A109741 in OEIS).

The number of valid Sudoku solution grids for the 16×16 derivation is not known. The maximum number of givens that can be provided while still not rendering the solution unique, regardless of variation, is four short of a full grid; if two instances of two numbers each are missing and the cells they are to occupy are the corners of an orthogonal rectangle, and exactly two of these cells are within one region, there are two ways the numbers can be added.

The inverse of this—the fewest givens that render a solution unique—is an unsolved problem, although the lowest number yet found for the standard variation without a symmetry constraint is 17, a number of which have been found by Japanese puzzle enthusiasts , and 18 with the givens in rotation symmetric cells. Sudoku from group tables As in the case of Latin squares the (addition- or) multiplication tables (Cayley tables) of finite groups can be used to construct Sudoku and related tables of numbers. Namely, one has to take subgroups and quotient groups into account: Take for example the group of pairs, adding each component separately modulo some . By omitting one of the components, we suddenly find ourselves in (and this mapping is obviously compatible with the respective additions, i.e. it is a group). One also says that the latter is a quotient group of the former, because some once different elements become equal in the new group. However, it is also a subgroup, because we can simply fill the missing component with to get back to .

Latin square

Sets of Latin squares that are orthogonal to each other have found an application as error correcting codes in situations where communication is disturbed by more types of noise than simple white noise, such as when attempting to transmit broadband Internet over power lines.

Firstly, the message is sent by using several frequencies, or channels, a common method that makes the signal less vulnerable to noise at any one specific frequency. A letter in the message to be sent is encoded by sending a series of signals at different frequencies at successive time intervals. In the example below, the letters A to L are encoded by sending signals at four different frequencies, in four time slots. The letter C for instance, is encoded by first sending at frequency 3, then 4, 1 and 2.

The encoding of the twelve letters are formed from three Latin squares that are orthogonal to each other. Now imagine that there’s added noise in channels 1 and 2 during the whole transmission. The letter A would then be picked up as:

In other words, in the first slot we receive signals from both frequency 1 and frequency 2; while the third slot has signals from frequencies 1, 2 and 3. Because of the noise, we can no longer tell if the first two slots were 1,1 or 1,2 or 2,1 or 2,2. But the 1,2 case is the only one that yields a sequence matching a letter in the above table, the letter A. Similarly, we may imagine a burst of static over all frequencies in the third slot:

Again, we are able to infer from the table of encoding that it must have been the letter A being transmitted. The number of errors this code can spot is one less than the number of time slots. It has also been proved that if the number of frequencies is a prime or a power of a prime, the orthogonal Latin squares produce error detecting codes that are as efficient as possible.

Eternity puzzle

The eternity puzzle was a geometric puzzle with a million-pound prize, created by Christopher Monckton, who put up half the money himself, the other half being put up by underwriters in the London insurance market. The puzzle was distributed by the Ertl Company.

The puzzle consisted of filling a large almost regular dodecagon with 209 irregularly shaped smaller polygons. All the polygons had the same color and had between seven and eleven sides.

It was launched in June 1999, by Ertl Toys, marketed to amateur puzzle solvers and 500,000 copies were sold worldwide, with the game becoming a craze at one point. Eternity was the best-selling puzzle or game in the UK at its price-point of £35 in its launch month. It was voted Puzzle of the Year in Australia. Before marketing the puzzle, Monckton had thought that it would take at least 3 years before anyone could crack the puzzle.

One estimate made at the time stated that the puzzle had 10500 possible attempts at a solution, and it would take longer than the lifetime of the Universe to calculate all of them even if you had a million computers.

According to Eternity’s rules, possible solutions to the puzzle would be received by mail on September 21, 2000. If no correct solutions were opened, the mail for the next year would be kept until September 30, 2001, the process being repeated every year until 2003, after which no entries would be accepted.

Solution
The puzzle was solved on May 15, 2000, before the first deadline by two Cambridge mathematicians, Alex Selby and Oliver Riordan, who had used an ingenious technique to vastly accelerate their solution.

They realised that it was trivial to fill the board almost completely, to an “end-game position” where an irregularly-shaped void had to be filled with only a few pieces, at which point the pieces left would be the “wrong shapes” to fill the remaining space. The hope of solving the end-game depended vitally on having pieces that were easy to tile together in a variety of shapes. They started a computer search to find which pieces tiled well or badly, and then used these data to alter their otherwise-standard backtracking search program to use the bad pieces first, in the hope of being left with only good pieces in the hard final part of the search.

This heuristic approach paid off rapidly, with a complete solution being obtained within seven months of brute-force search on two domestic PCs. The puzzle’s inventor falsely claimed in 2000 that the earlier-than-expected discovery had forced him to sell his 67-room house to pay the prize.

In 2006 he revealed by his own will that the claim had been a PR stunt to boost sales over Christmas, that the house’s sale was unrelated, and that he was going to sell it anyway.

River crossing puzzle

A river crossing puzzle is a type of transport puzzle in which the object is to carry items from one river bank to another.

The difficulty of the puzzle may arise from restrictions on which or how many items can be transported at the same time, or from which or how many items may be safely left together. The setting may vary cosmetically, for example, by replacing the river by a bridge.

The earliest known river-crossing problems occur in the manuscript Propositiones ad Acuendos Juvenes (English: Problems to sharpen the young), traditionally said to be written by Alcuin. The earliest copies of this manuscript date from the 9th century; it contains three river-crossing problems, including the fox, goose and bag of beans puzzle and the jealous husbands problem.

Well-known river-crossing puzzles include:

• The fox, goose and bag of beans puzzle, in which a farmer must transport a fox, goose and bag of beans from one side of a river to another using a boat which can only hold one item in addition to the farmer, subject to the constraints that the fox cannot be left alone with the goose, and the goose cannot be left alone with the beans.

• The jealous husbands problem, in which three married couples must cross a river using a boat which can hold at most two people, subject to the constraint that no woman can be in the presence of another man unless her husband is also present. This is equivalent to the missionaries and cannibals problem, in which three missionaries and three cannibals must cross the river, with the constraint that at any time when both missionaries and cannibals are standing on either bank, the cannibals on that bank may not outnumber the missionaries.

• The bridge and torch problem.

• Propositio de viro et muliere ponderantibus plaustrum.

In this problem, also occurring in Propositiones ad Acuendos Juvenes, a man and a woman of equal weight, together with two children, each of half their weight, wish to cross a river using a boat which can only carry the weight of one adult.

These problems may be analyzed using graph-theoretic methods, programming.