Initialize game board in matrix is to populate one digit number into a MxN matrix. The digit can be generated randomly. However, no 3 adjacent cells shall be the same, horizontal, vertical, diagonal and L shape. If you find invalid digit, replace with a different one in that cell.
Matrix is 2D array, which reflects the game in real world. The popular game board questions such as tic tac toe, sudoku, or chess board, all use matrix. Note the cells at the edge has no adjacent cells. So the index should be offset 1 from the edge.
Question:
Initialize a M X N board with integer 0, 10, in which no 3 adjacent cells are the same.
The 3 adjacent cells are might be in horizontal line, vertical line, diagonal line, or L shapes.
Java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 | import java.util.ArrayList; import java.util.List; public class InitializeGameBoard { public static int randomInt(int m) { return (int) (Math.random() * m); } public static int[][] initialize(int n, int m) { int[][] result = new int[n][n]; for (int i = 0; i < n; i++) for (int j = 0; j < n;j++) result[i][j] = randomInt (m); return result; } public static int randomNotIn(int m, int n ) { // K is sorted List<Integer> uSet = new ArrayList<Integer>(); for (int i = 0; i < m;i++) { uSet.add(i); } uSet.remove(uSet.indexOf(n)); int un = randomInt(uSet.size()); return uSet.get(un); } static void validateBoard (int[][] a, int m) { for (int i =1;i<a.length-1; i++) for (int j=1; j<a.length-1; j++) { //left and right if (a[i][j] == a[i][j-1] && a[i][j] == a[i][j+1]) { System.out.println("found horizontal conjuction:"+a[i][j]); a[i][j] = randomNotIn (m, a[i][j]); } //upper and below if (a[i][j] == a[i-1][j] && a[i][j] == a[i+1][j] ) { System.out.println("found vertical conjuction:"+a[i][j]); a[i][j] = randomNotIn (m, a[i][j]); } //Diagonal if (a[i][j] == a[i-1][j-1] && a[i][j] == a[i+1][j+1] ){ System.out.println("found left diagonal conjuction:"+a[i][j]); a[i][j] = randomNotIn (m, a[i][j]); } //Diagonal if (a[i][j] == a[i-1][j+1] && a[i][j] == a[i+1][j-1] ){ System.out.println("found right diagonal conjuction:"+ a[i][j]); a[i][j] = randomNotIn (m, a[i][j]); } // left and upper if (a[i][j] == a[i][j-1] && a[i][j] == a[i-1][j] ){ System.out.println("found L sharps face left conjuction:" + a[i][j]); a[i][j] = randomNotIn (m, a[i][j]); } //right and upper if (a[i][j] == a[i][j+1] && a[i][j] == a[i-1][j] ) { System.out.println("found L sharps conjuction:"+ a[i][j]); a[i][j] = randomNotIn (m, a[i][j]); } //left and lower if (a[i][j] == a[i][j-1] && a[i][j] == a[i+1][j] ){ System.out.println("found L sharps face left down conjuction:"+ a[i][j]); a[i][j] = randomNotIn (m, a[i][j]); } //right and lower if (a[i][j] == a[i][j+1] && a[i][j] == a[i+1][j] ){ System.out.println("found L sharps face down conjuction:"+ a[i][j]); a[i][j] = randomNotIn (m, a[i][j]); } } } private static void showBoard(int[][] a) { for (int i = 0; i < a.length; i++) { for (int j = 0;j <a.length; j++) System.out.print(a[i][j]+" "); System.out.println(); } } public static void main(String[] args) { int size = 8; int range = 10; int[][] result = initialize(size, range); showBoard(result); System.out.println(); validateBoard (result, range); System.out.println(); showBoard(result); } } } |
Output (one example):
2 1 3 3 0 9 9 1
6 4 7 6 0 4 6 4
9 8 4 0 0 6 0 4
7 7 4 2 6 4 6 0
1 5 7 7 9 2 7 8
8 7 4 0 0 4 8 0
1 0 8 7 6 8 5 8
8 3 7 7 1 8 1 0
found vertical conjuction:0
found right diagonal conjuction:6
found right diagonal conjuction:8
found L sharps face left conjuction:7
2 1 3 3 0 9 9 1
6 4 7 6 1 4 6 4
9 8 4 0 0 1 0 4
7 7 4 2 6 4 6 0
1 5 7 7 9 2 7 8
8 7 4 0 0 4 2 0
1 0 8 7 6 8 5 8
8 3 7 8 1 8 1 0
O Notation:
Time complexity: O(n^2)
Space complexity: O(n^2)
Download InitializeGameBoard.java
TicTacToe (GitHub)
(1) Create a mxn matrix (2) write a function to generate random numbers (3) fill the matrix cells with the random numbers (4) write a function to validate whether the values in each cell follow the rules (4) adjust the invalid cells.