Noughts and Crosses

A mathematical perspective for problem solving

Introduction:

A Paper-and-Pencil or Paper-and-Pen (P-and-P) games are type of games that is solely played by paper and pencil or other writing implements and is played usually without erasing. Noughts and Crosses is a type of P-and-P game for two players, which is commonly known as Tic-tac-toe in American English and Xs and Os/”X’y O’sies” in Ireland. It is generally played on a 3x3 grid where each player will take turns to mark the spaces in the grid with their symbol (X or O). The player who succeeds in placing three of their marks in a diagonal, horizontal, or vertical row is the winner. Thus, the row of placing is called a winning line.

a) Establish the number of winning lines of noughts and crosses on a 3 x 3 board

Problem Understanding:

The objective is to establish the number of winning lines when playing noughts and crosses on a 3x3 board. In other words, the number of possible winning line arrangements that a player can make in the game if played on a 3x3 board. The problem could you better expressed by drawing the winning lines on a 3x3 grid. The principal part of the problem is to detect the maximum number of winning lines possible to obtain from the grid. The length of the winning line is generally the number of cells in a row or column of the board. So, here the length of the grid is assumed as 3 cells, as the play-board in our problem is of size 3x3.

Problem Analysis:

The basic understanding about the problem is that the game is played between 2 players on a 3x3 board. The solution could be found by drawing the possible winning lines on a 3x3 grid and counting it. We have assumed the length of the winning line as 3 cells. As the requirement is to find the maximum possible winning lines, I can investigate the problem in a slightly different angle where a player can place all 3 symbols at a time in a way it makes a winning line. This will remove the additional complexity where the players take turns to play, which is not required for solving the requirement.

Problem Solution:

We take a 3x3 board and start drawing the winning lines horizontally, vertically, and diagonally with length of 3 cells. The vertical and horizontal lines could be counted together as a vertical winning line becomes the horizontal winning line upon rotation of the board by 90◦ or 270◦

First let us count the horizontal/Vertical lines as follows:

• From the top left corner, we can draw a horizontal winning line of 3 cells long. This makes our first winning line and is represented in Fig.1. However, when we consider rotation, the same winning line could be expressed in 4 different ways as shown in Fig.2. Hence, we can count all 4 representations as reflections of the same winning line upon rotation of the board and can count as a single winning line.

Fig.1: Winning line from top-left corner to right Fig.2: Winning line from top-left corner to right upon rotation

• If we closely analyse the second and third cells of the top row, it is unable to draw a 3 cells long winning line from both the cells along the row.
• Moving to the next row, we can draw a 3 calls long horizontal winning line from left end of the middle row to right. This is our second horizontal winning line and is represented by Fig.3. When considering the rotation, we can represent the winning line in 4 different ways as shown in Fig.4. Hence, we can count all 4 representations as reflections of the same winning line upon rotation of the board and can count as a single winning line.

Fig.3: Winning line from mid-left corner to right Fig.4: Winning line from mid-left corner to right upon rotation

• Like step 2, it is not possible to draw 3 cells long horizontal winning lines from second or third cells of the middle row as well.
• Finally, the third row reflects the top row and is already counted.

Thus, the number of horizontal/vertical winning lines after considering reflection and rotation is 2. Now let us count the diagonal winning lines as follows:

• We can draw a 3 cells long diagonal winning line from the top left corner of the board and is represented in Fig.5. Upon rotation, we can represent the same winning line in 4 different ways as shown in Fig.6 and could be counted as single winning line.

Fig.5: Winning line from top-left corner diagonally Fig.6: Winning line from -left corner to right upon rotation

• It is not possible to draw a 3 cell long diagonal winning line from any other cells in the board other than what is already covered in step 6.Hence, there is only a single unique diagonal winning line that could be drawn in a 3x3 grid.

By executing the plan, we could conclude that:

Problem Implementation

The steps required for counting the maximum number of 3 cells long winning lines, possible on a 3 x 3 grid are:

1. Declare an array (a) to save the cell combinations of successfully drawn winning lines and variable ( c) to save the count.

2. Start with the first row first cell (top-left-corner)

3. Check if a 3 cells long horizontal winning line could be drawn from the cell

4. If a winning line could be drawn from the cell

a. If the winning line is not already counted or If the cell combination is not already represented

i. Increment the variable ( c) by 1

ii. Save all the possible cell combinations of the winning line and combinations of all the alternate representations of the winning line in the array (a)

b. Else Continue

5. Check if a 3 cells long diagonal winning line could be drawn from the cell

6. Step 4

7. Move to the second cell of the row and perform steps 3 and 4

8. Move to the third cell of the row and perform steps 3 and 4

9. Move to the second row first cell and repeat steps 3 to 8

10. Move to the third row first cell and repeat steps 3 to 8

Critical Evaluation:

While carrying out the proposed solution for the problem, it is observed that:

1. Since we have assumed that the winning line’s length is 3 cells in the grid, there can exist only a single horizontal or vertical winning line is each row or column.

2. A vertical winning line becomes a horizontal winning line upon rotation of the board by 90◦ or 270◦

3. The rotation of the board is considered while counting the winning lines as the direction of the winning lines is not a factor in the game

4. Also, all the possible arrangements of a winning line, upon rotation is counted as a single winning line as the direction is not relevant to the scenario

5. The reflection of the winning lines is also handled as the rotation of the board is considered.

b) Establish the number of winning lines of noughts and crosses on a m x n board

Problem Understanding:

The objective is to establish the number of winning lines when playing noughts and crosses on a m x n board, where m and n are positive whole numbers, and the length of winning line is given as p units long. The problem could be better expressed by drawing grids of various m x n value combinations and counting the possible winning lines. The principal part of the problem is to identify how the count of winning lines vary based on the size of the two-dimensional grid. So, let us assume that the game is always played in a square board or m = n. Another unknown factor in the problem is how to determine the value of p (length of winning line) for various grids of different m or n values. So, let us assume that p is the length of the longest straight line that could be drawn in each grid.

Problem Analysis:

The basic understanding about the problem is that the game is played between 2 players on a m x n board. The solution could be found by simplifying the problem and solving for smaller values of m or n. We have assumed that m = n and the length of the winning line as the length of the longest line that could be drawn from the grid.

Problem Solution:

Let us investigate smaller grids starting from 0 and count the possible winning lines. For the ease of representation, the winning lines are represented as colored columns in the grid. Horizontal/Vertical winning lines are represented in red and diagonal winning lines are represented as green. If 2 winning lines meets on a cell, then the cell is colored as blue.

Here we can mathematically conclude that the maximum number of winning lines of a square grid (m=n) as:

Finally, we can generate the function for finding the maximum number of winning lines of a grid of size m x n and winning line of length p units where p being the longest line that could be drawn in the grid is given by:

Problem Implementation

The steps required for counting the maximum number of winning lines of p units long, possible on a m x n grid are:

1. Determine the size of the grid and assign to variables (m) and (n)
2. Assign the length of longest line that could be drawn in the grid to a variable (p)
3. Declare an array (a) to save the cell combinations of successfully drawn winning lines
4. Initialize a variable ( c) to save the count of successfully drawn winning lines
5. Start with the first row first cell (top-left-corner)
6. Check if p units long horizontal winning line could be drawn from the cell
7. If a winning line of length p could be drawn from the cell
   a. If the winning line is not already counted or If the cell combination is not already represented
   i. Increment the variable ( c) by 1
   ii. Save all the possible cell combinations of the winning line and combinations of all the alternate representations of the winning line in the array (a)
   b. Else Continue
8. Move to the subsequent cells of the row and perform steps 6 and 7
9. Move to the subsequent rows and repeat steps 6 to 8
10. Step 5
11. Check if a diagonal winning line of given length could be drawn from the cell
12. Step 7
13. Move to the subsequent cells of the row and perform steps 11 and 12
14. Move to the subsequent rows and repeat steps 11 to 13

Critical Evaluation

Let us investigate a sample game for a critical evaluation of the game.

Stage 1: Empty Grid

At this stage, both players choose their symbols and decides on who to start playing.

Stage 2: First move of first player

The first player starts to fill the chosen symbol (say X).

Stage 3: First move of second player

Now the second player makes the move and places the symbol (since first player chose X, the symbol of second player is O).

Stage 4: Follow-up moves

Hereafter the players make alternate moves to create a winning line with their corresponding symbols. Let us see an example as follows:

In this example game, the player with symbol X won the match as the player successfully made the first winning line using the symbol.

When we closely observe the above game moves, the player X has won by creating a situation where a winning line arrangement can be made irrespective of the last move of the player O. This scenario or condition in the game is sometimes referred as a multi-win situation, however, this is not an official term. Having a symbol on the center position of the grid helps the player to generate this scenario. So, the objectives of each player of the game can be noted as:

1. Create a winning line arrangement

2. Block the other player from creating a winning line arrangement

3. Block the other player from creating the multi-win situation

c) Establish the number of winning lines of noughts and crosses on a k x l x m board

Problem Understanding:

The objective is to establish the number of winning lines when playing noughts and crosses on a k x l x m board, where k, l and m are positive whole numbers, and the length of winning line is given as n units long. The k x l x m board is a cube structure. The problem needs to be simplified further for counting the possible winning lines. The principal part of the problem is to identify how the count of winning lines vary based on the size of the three-dimensional grid. So, let us assume that the game is played on a cube or k = l = m and the winning lines are drawn, or the game is played only on the faces of the cube.

Another unknown factors in the problem to determine the value of p (length of winning line) for various cubes of different k, l or m values. So, let us also assume that n is the length of the longest straight line that could be drawn on the cube.

Problem Analysis:

The basic understanding about the problem is that the game is played between 2 players (X and O) on a k x l x m board. As we have assumed that the game is played only on the faces of the board, the cube structure could be opened and simplified as 6 two dimensional boards. Hence sum of winning lines drawn in all the faces will be the maximum number of winning lines that could be drawn in the given shape. We have also assumed the length of the winning line as the length of the longest line that could be drawn on all faces.

Problem Solution:

When all three dimensions of a cube are same, then the cube opens into 6 uniform squares. Hence from the solution obtained for two-dimensional square boards, the solution could be derived as:

1. Determine the dimensions of the cube and assign to variables (k), (l) and (m)
2. Assign the length of longest line that could be drawn in the grid to a variable (n)
3. Declare an array (a) to save the cell combinations of successfully drawn winning lines
4. Initialize a variable ( c) to save the count of successfully drawn winning lines
5. Start with the first row first cell (top-left-corner) of one face of the cube.
6. Check if p units long horizontal winning line could be drawn from the cell
7. If a winning line of length p could be drawn from the cell
   a. If the winning line is not already counted or If the cell combination is not already represented
   i. Increment the variable ( c) by 1
   i. Save all the possible cell combinations of the winning line and combinations of all the alternate representations of the winning line in the array (a)
   b. Else Continue
8. Move to the subsequent cells of the row and perform steps 6 and 7
9. Move to the subsequent rows and repeat steps 6 to 8
10. Step 5
11. Check if a diagonal winning line of given length could be drawn from the cell
12. Step 7
13. Move to the subsequent cells of the row and perform steps 11 and 12
14. Move to the subsequent rows and repeat steps 11 to 13
15. Multiply the variable ( c)by 6 to get the maximum number of winning lines on the given grid

Critical Evaluation

Let us consider an example of 1 x 2 x 3 board (k != l != m):

From this example we could see that when we expanded a 1 x 2 x 3 board, we got 2 (1 x 2) boards, 2 (1 x 3) boards and 2 (2 x 3) boards. On a critical analysis we could understand that:

• A k x l x m board expands into 2 k x l boards, 2 k x m boards and 2 l x m boards when k != l != m
• The additional orientations of sizes can be ignored as a k x l board becomes l x k board on rotation
• Under the assumption that the length of the longest line drawn in all the faces of the cube is the length of winning line, the winning lines could be drawn only on k x m and l x m boards, if k < l < m. So, total number of winning lines drawn in a k x l x m board is given as:
  (2 * Number of Winning Lines of k x m board) + (2 * Number of Winning Lines of l x m board)

Let us consider another example of 1 x 2 x 2 board (k != l = m):

Here we got 4 (1 x 2) boards and 2 (2 x 2) boards, when a 1 x 2 x 2 board is expanded. On a critical analysis we could infer:

• A k x l x m board expands into 4 (k x l or k x m) boards and 2 l x m boards when k != l = m
• The additional orientations of sizes can be ignored as a k x l board becomes l x k board on rotation
• Under the assumption that the length of the longest line drawn in all the faces of the cube is the length of winning line, the winning lines could be counted as:
  (4 * Number of Winning Lines of (k x l or k x m board) + (2 * Number of Winning Lines of l x m board)