Scrabble island detection

stuff about computer science and programming
Post Reply
User avatar
dendiz
Site Admin
Posts: 114
Joined: Wed Oct 10, 2018 3:48 am

Scrabble island detection

Post by dendiz » Thu Oct 11, 2018 12:58 am

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 into 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:

Code: Select all

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);
    }
}

User avatar
dendiz
Site Admin
Posts: 114
Joined: Wed Oct 10, 2018 3:48 am

Re: Scrabble island detection

Post by dendiz » Thu Oct 11, 2018 12:59 am

I had already talked about a mutable version of this algorithm for flood filling island detection here. This time I went immutable with Clojure The algorithm is a bit different, this we will not have a variable in the outer scope but pass a new instance of a board (which is efficiently managed by Clojure) to the function for each iteration/recursion.

The full source is at this repo

there a few helper functions

first-char-on-board scans the board to find the first tile that is not empty split this will split a string such as "abc" into a vector as ["a" "b" "c"]

the basic idea is to keep a list of next slots to visit on the board as we visit slots. the next-frontier function will return a list of next slots. This is basically BFS search on a graph.

Code: Select all

(defn flood-fill
  "flood fill the board starting from the first non empty slot.
   the flooded slots will contain '!' empty slots '.'. If there
   are islands they will contain letters.
  "
  [board]
  (let [[y x] (first-char-on-board board)
        board (mapv split board)
        ]
    (loop [board board
           frontier [[x y]]]
      (if (-> frontier count zero?)
        board
        (let [front (first frontier)
              x (first front)
              y (second front)]
          (recur
           (assoc-in board [y x] "!")
           (concat (next frontier) (next-frontier board [x y]))))))))
the next-frontier code is also worth mentioning

Code: Select all

(defn next-frontier
  "return the coordinates of candidate neighbors for flood filling"
  [board [x y]]
  (for [i [(dec y) y (inc y)]
        j [(dec x) x (inc x)]
        :when (and (>= i 0)
                   (>= j 0)
                   (< i 15)
                   (< j 15)
                   (or (= x j) (= y i))
                   (not (and (= x j) (= y i)))
                   (not= "!" (get-in board [i j]))
                   (not= "." (get-in board [i j])))]
    [j i]))
flood-fill will mark visited slots with ! and next-frontier will return a list of the candidate slot from the 8 neighbors of the current slot. if the neighbor is visited or empty it's not included in the list.

if the starting board was like this

Code: Select all

...a...
...bc..
..de...
the flood would start with a and the next-frontier would return only "b" from the neighbors and mark "a" as "!". "b" would return "c" and "e" and "d". "a" would be marked as "!" so it would not be included. After the fill, the board would be like

Code: Select all

...!...
...!!..
..!!...
this algorithm is useful when detecting if the scrabble board is connected.

Post Reply