Connect Four Game Coding Puzzle Algorithm in Java

Puzzle Description:

Connect Four (also known as Plot Four, Find Four, Four in a Row, and Four Up) is a two-player game where players select a color, then take turns dropping their colored discs from the top into a vertically suspended grid. The pieces fall straight down, occupying the next available space within the column. The object of the game is to get four of the same colored discs next to each other vertically, horizontally, or diagonally before one’s opponent can do so. You can find more details about the game from Wikipedia.

Write a program that takes an input as a single argument on the command line. This argument must be a file name, which contains the state of a Four in a Line game. The program must determine if the game has ended and if one of the two players has won. Note that the game ends if either side wins or if the board has no empty slots left, which is a draw.

Input specifications

Your submission will be tested against an input file that contains ASCII characters. Each row of text is terminated by a single new-line character. Each row contains a comma separated list of numbers. Each row will have the same length and all the rows together will describe the grid.

An example of the input file can be:

0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0
0,0,0,0,1,0,0,0
0,2,1,2,1,2,0,1
2,1,1,2,1,2,1,1
1,2,2,1,1,2,2,2

Where each cell is associated to a number:

  • 0 means that the cell is still empty
  • 1 means that the cell contains a disk put by player 1
  • 2 means that the cell contains a disk put by player 2

Output specifications

The expected output must be one of the following strings, terminated by a new line character:

  • 1 if the game ended and player 1 won
  • 2 if the game ended and player 2 won
  • draw if the game ended with no winner
  • play if the game did not ended yet

Expected output based on the example above:

1

[hr]
Algorithm :

  • Make 2D array representing the Connect Four Grid
  • Initial Array with values 1,0,-1 (using -1 for player 2)
  • If at least one ‘0’ in array then return ‘play’ else return ‘draw’
  • We start checking from Bottom to speed up the code
  • Check row,columns,diagonals by adding the values
  • If sum is ‘4’ then Player1 wins and if ‘-4’ then Player2 wins
Source: (Note: There may be more optimised /simple code available)
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;

public class fourinaline {
	static int ROWS;
	static int COLUMNS;
	public static void main(String args[]) throws IOException {

		String filename = args[0];
		FileReader fr = new FileReader(filename);
		BufferedReader bfr = new BufferedReader(fr);

		int count = 0;
		String str;
		str = bfr.readLine();
		String[] temp = str.split(",");
		COLUMNS = temp.length;
		bfr.close();
		FileReader fr1 = new FileReader(filename);
		BufferedReader bfr1 = new BufferedReader(fr1);

		while ((str = bfr1.readLine()) != null) {
			if (str.length() > 3) { // To remove rows with characters like \n
				count++;
			}
		}

		ROWS = count;
		// Array
		int[][] Array = new int[ROWS][COLUMNS];
		FileReader fr2 = new FileReader(filename);
		BufferedReader bfr2 = new BufferedReader(fr2);

		// Initializing Array
		int rx = 0;
		while (rx < ROWS) {
			str = bfr2.readLine();
			String[] temp1 = str.split(",");
			for (int j = 0; j < COLUMNS; j++) {
				if (temp1[j].equals("0")) {
					Array[rx][j] = 0;
				}
				if (temp1[j].equals("1")) {
					Array[rx][j] = 1;
				}
				if (temp1[j].equals("2")) {
					Array[rx][j] = -1;
				}
			}
			rx++;
		}
		int f = checkBoard(Array);
		if (f != 0) {
			System.out.println(f);
			System.exit(1);
		}
		System.out.println(checkDraw(Array));
	}

	private static String checkDraw(int[][] array) {
		for (int j = 0; j < COLUMNS; j++) {
			if (array[0][j] == 0) {
				return "play";
			}
		}
		return "draw";
	}

	private static int checkBoard(int[][] Array) {
		// Row Wise
		for (int r = ROWS - 1; r >= 0; r--) {
			int total;
			for (int c = 0; c < COLUMNS - 3; c++) {
				total = Array[r][c] + Array[r][c + 1] + Array[r][c + 2]
						+ Array[r][c + 3];
				if (total == 4) {
					return 1;
				}
				if (total == -4) {
					return 2;
				}
			}
		}
		// Column Wise

		for (int c = 0; c < COLUMNS - 1; c++) {
			int total;
			for (int r = ROWS - 1 - 3; r >= 0; r--) {
				total = Array[r][c] + Array[r + 1][c] + Array[r + 2][c]
						+ Array[r + 3][c];
				if (total == 4) {
					return 1;
				}
				if (total == -4) {
					return 2;
				}
			}
		}
		// Diagonals
		for (int r = ROWS - 1 - 3; r >= 3; r--) {
			int total;
			for (int c = 0; c < COLUMNS - 1 - 3; c++) {
				total = Array[r][c] + Array[r + 1][c + 1] + Array[r + 2][c + 2]
						+ Array[r + 3][c + 3];
				if (total == 4) {
					return 1;
				}
				if (total == -4) {
					return 2;
				}
			}
		}
		for (int r = ROWS - 1 - 3; r >= 3; r--) {
			int total;
			for (int c = 3; c < COLUMNS - 1; c++) {
				total = Array[r][c] + Array[r - 1][c - 1] + Array[r - 2][c - 2]
						+ Array[r - 3][c - 3];
				if (total == 4) {
					return 1;
				}
				if (total == -4) {
					return 2;
				}
			}
		}
		for (int r = ROWS - 1 - 3; r >= 3; r--) {
			int total;
			for (int c = 0; c < COLUMNS - 3; c++) {
				total = Array[r][c] + Array[r - 1][c + 1] + Array[r - 2][c + 2]
						+ Array[r - 3][c + 3];
				if (total == 4) {
					return 1;
				}
				if (total == -4) {
					return 2;
				}
			}
		}
		for (int r = ROWS - 1 - 3; r >= 3; r--) {
			int total;
			for (int c = 3; c < COLUMNS - 3; c++) {
				total = Array[r][c] + Array[r + 1][c - 1] + Array[r + 2][c - 2]
						+ Array[r + 3][c - 3];
				if (total == 4) {
					return 1;
				}
				if (total == -4) {
					return 2;
				}
			}
		}
		return 0;
	}
}

 

Download Test Cases,Source code

One thought on “Connect Four Game Coding Puzzle Algorithm in Java”

Leave a Reply

Your email address will not be published. Required fields are marked *