Scrabble Island detection

Keywords: flood fill algorithm, board state, validity check, tile, program, simple, empty, trivial, generate, valid, part. Powered by TextRank.

there is a game app called “kelimelik” which is a Turkish version of scrabble that I’ve been playing for a while now which is quite fun. So I thought it might be a nice way to waste a couple of hours trying to write a program that would give the highest scoring word given a board state. Most of the program is quite trivial in that it just has to generate permutations of the given letters and place them in all possible combinations on the board and then check if the board is valid. E.g that all the words on the board are in a dictionary and all the tiles are connected. The second part of the validity check is interesting. The first thing that popped to my mind was using a flood-fill algorithm starting from the tile nearest to the top-left corner. After the fill if there are any tiles on the board that are unmarked then there is more than 1 island on the board and the board is invalid. So how does a flood-fill algorithm work? Quite simple actually. You mark the current tile you are on at (x,y) and recurse to the neighbors if they are not empty, or have not been marked. Here is a simple bit code that does this:

private boolean connectedCheck(int i, int j, String[][] board) {
    board[i][j] = "!";
    boolean resh = true;
    boolean resv = true;
    boolean resh2 = true;
    boolean resv2 = true;
    if (i < 14 && !board[i + 1][j].equals("*") && !board[i + 1][j].equals("!")) {
        connectedCheck(i + 1, j, board);
    }
    if (i > 0 && !board[i - 1][j].equals("*") && !board[i - 1][j].equals("!")) {
        connectedCheck(i - 1, j, board);
    }
    if (j < 14 && !board[i][j + 1].equals("*") && !board[i][j + 1].equals("!")) {
        connectedCheck(i, j + 1, board);
    }
    if (j > 0 && !board[i][j - 1].equals("*") && !board[i][j - 1].equals("!")) {
        connectedCheck(i, j - 1, board);
    }
}

empty squares are noted as “*”, tiles with the letter and marked tiles with “!”. Here is a 3×3 board array for reference:

|   |   |   |
|---|---|---|
|*  | * | * |
|A  | * | * |
|B  | C | * |

Scrabble Island detection

Metadata

Similar posts