Description

Introduction

Given an 𝑛 × 𝑛 square board, the no-three-in-line problem is to put as many pieces to the board as possible so that no three pieces can appear in a straight line, where “straight line” means a line along the horizontal －, vertical ｜, or diagonal ＼／ directions. You will write a program to put pieces to the board one by one until no more possible positions can be found. Figure 1 shows an example 12 × 12 board configuration. In the figure, ‘@’ denotes a piece, ‘.’ denotes an empty square, and ‘=’ denotes an empty square that cannot have a piece on it anymore. For example, in row 4, there are two pieces on the two ends, thus the remaining squares along the row are all ‘=’ as we cannot have a third piece on this row anymore.

A B C D E F G H I J K L

0 = = = @ @ = = = = = = =  1 = . . = . . . . . . . .

• . = = . . . . . . . . .
• . = @ . . . . . . . . .
• @ = = = = = = = = = = @ 5 . . . . = . . . . . . .
• . . . . . = . . . . . .
• . . . . . . @ . . . . .
• . . . . . . . = . . . .
• . . . . . . . . = . . .
• . . . . . . . . . = . .
• . . . . . . . . . . = .

Figure 1: An Example 𝟏𝟐×𝟏𝟐 Board Configuration

Program Specification

This section describes the board representation, program flow, and some special requirements.

Board Representation

The board will be represented by a two-dimensional array of char. The array elements should be either ‘@’ (a piece), ‘.’ (empty), or ‘=’ (empty but cannot be put).

const int SIZE = 12;    // Global named constant

…

char board[SIZE][SIZE];    // Local 2-D array

When SIZE = 12, the array elements board[0][0], board[0][SIZE-1], board[SIZE-1][0], and board[SIZE-1][SIZE-1] denote the four corner squares A0, L0, A11, and L11 respectively.

Program Flow

1. The program starts with a completely empty board.
2. Then the program prompts the user to enter an input position to put a piece, which is always a letter followed by an integer. (E.g., F 4 means putting a piece at position F4.)
3. A user input is invalid if: (a) the row and column are outside of the board, or (b) the input position is not empty ‘.’ In case the user makes an invalid input, display a warning message and go back to Step 2. Note that lowercase column letters are considered invalid.
4. Update the board by putting a piece to the input position.
5. After putting a piece, for each of the four directions －｜＼／ of the input square, if there are already two pieces along that direction (that is, no pieces can be put in this line in the future), mark the remaining empty squares in that line as ‘=’.
6. Repeat Steps 2–5 until the board contains no empty squares. That is, only ‘@’ and ‘=’ remain.
7. At the end, print the total number of pieces on the board.

Special Requirements

• You are not allowed to use any global variables in your program. (That is, do not declare any variables outside functions.) Nonetheless, const ones (e.g., SIZE) do not count.
• Your program should be decomposed into at least four functions (including main()). At least two functions should have array parameter(s).
• Your program should be scalable to other values for the named constant SIZE. That is, your program should still work normally for board size other than 12. When grading, we may modify your program by changing SIZE to other values (may be 1–26) for testing.

Program Output

The following shows some sample output of the program. The blue text is user input and the other text is the program output. You can try the provided sample program for other input. Your program output should be exactly the same as the sample program (i.e., same text, same symbols, same letter case, same number of spaces, etc.). Otherwise, it will be considered as wrong, even if you have computed the correct result.

A B C D E F G H I J K L  0 . . . . . . . . . . . .

• . . . . . . . . . . . .
• . . . . . . . . . . . .
• . . . . . . . . . . . .
• . . . . . . . . . . . .
• . . . . . . . . . . . .
• . . . . . . . . . . . .
• . . . . . . . . . . . .
• . . . . . . . . . . . .
• . . . . . . . . . . . .
• . . . . . . . . . . . .
• . . . . . . . . . . . .

Put a piece (col row): H 1↵

 

A B C D E F G H I J K L  0 . . . . . . . . . . . .

• . . . . . . . @ . . . .
• . . . . . . . . . . . .
• . . . . . . . . . . . .
• . . . . . . . . . . . .
• . . . . . . . . . . . .
• . . . . . . . . . . . .
• . . . . . . . . . . . .
• . . . . . . . . . . . .
• . . . . . . . . . . . .
• . . . . . . . . . . . .
• . . . . . . . . . . . .

Put a piece (col row): M 1↵

Invalid. Try again!

Put a piece (col row): E -3↵

Invalid. Try again!

Put a piece (col row): a 4↵

Invalid. Try again!

Put a piece (col row): A 4↵

A B C D E F G H I J K L  0 . . . . . . . . . . . .

• . . . . . . . @ . . . .
• . . . . . . . . . . . .
• . . . . . . . . . . . .
• @ . . . . . . . . . . .
• . . . . . . . . . . . .
• . . . . . . . . . . . .
• . . . . . . . . . . . .
• . . . . . . . . . . . .
• . . . . . . . . . . . .
• . . . . . . . . . . . .
• . . . . . . . . . . . .

Put a piece (col row): H 1↵

Invalid. Try again!

Put a piece (col row): E 9↵

A B C D E F G H I J K L  0 . . . . . . . . . . . .

• . . . . . . . @ . . . .
• . . . . . . . . . . . .
• . . . . . . . . . . . .
• @ . . . . . . . . . . .
• . . . . . . . . . . . .
• . . . . . . . . . . . .
• . . . . . . . . . . . .
• . . . . . . . . . . . .
• . . . . @ . . . . . . .
• . . . . . . . . . . . .
• . . . . . . . . . . . .

Put a piece (col row): I 8↵

 

A B C D E F G H I J K L  0 . . . . . . . . . . . . 1   . . . . . . . @ . . . . 2   . . . . . . . . . . . . 3   . . . . . . . . . . . . 4   @ . . . . . . . . . . . 5   . . . . . . . . . . . . 6   . . . . . . . . . . . . 7   . . . . . . . . . . . . 8   . . . . . . . . @ . . . 9   . . . . @ . . . . . . . 10  . . . . . . . . . . . . 11  . . . . . . . . . . . . Put a piece (col row): E 2↵ A B C D E F G H I J K L  0 . . . . = . . . . . . . 1   . . . . = . . @ . . . . 2   . . . . @ . . . . . . . 3   . . . . = . . . . . . . 4   @ . . . = . . . . . . . 5   . . . . = . . . . . . . 6   . . . . = . . . . . . . 7   . . . . = . . . . . . . 8   . . . . = . . . @ . . . 9   . . . . @ . . . . . . . 10  . . . . = . . . . . . . 11  . . . . = . . . . . . . Put a piece (col row): E 5↵ Invalid. Try again!   ⋮    (Some moves are skipped to save space. See Blackboard for full version.)   A B C D E F G H I J K L 0        = @ = = = = = = = @ = = 1        = = = = = = @ @ = = = = 2        = = = @ @ = = = = = = = 3        = @ = = = = = = @ = = =  4 @ = = = = = = = = = . . 5   = = @ = = @ = = = = = = 6   @ = = @ = = = = = = = = 7   = = = = = = @ = = @ = = 8   = = = = = = = @ @ = = = 9   = = @ = @ = = = = = = = 10  = = = = = . = = = = = = 11  = = = = = = = = = = = = Put a piece (col row): L 4↵

 

A B C D E F G H I J K L

• = @ = = = = = = = @ = =
• = = = = = = @ @ = = = =
• = = = @ @ = = = = = = =
• = @ = = = = = = @ = = =
• @ = = = = = = = = = = @
• = = @ = = @ = = = = = =
• @ = = @ = = = = = = = =
• = = = = = = @ = = @ = =
• = = = = = = = @ @ = = =
• = = @ = @ = = = = = = =
• = = = = = = = = = = = =
• = = = = = = = = = = = =

Num of pieces: 20