What exactly are “anchors” in this scrabble algorithm?

Question

I'm trying to implement this algorithm: http://www.cs.cmu.edu/afs/cs/academic/class/15451-s06/www/lectures/scrabble.pdf but I just cannot figure out what exactly those anchor squares are (first mentioned in 3.1.2 and then in 3.3).

I know candidates for them are all empty squares adjacent to those already on the board but no idea which exactly should I choose.

Also, I don't know why all squares in left-parts have trivial cross-checks (meaning that every letter may be put there) and anchors always have nontrivial cross-checks. What about this situation:

_._._._
_._.x.A
_._._._

_ is empty square, x is anchor, A is some letter already on the board - why in this situation I need to check x for cross-checks when it obviously doesn't need it?

Answer 1

According to the rules of Scrabble, your word has to connect to -- or be anchored at -- an existing word on the board. Now when we look at one line at a time there are three types of anchors:

• Tiles to the left of a letter in the same line,
• tiles to the right of a letter in the same line,
• and tiles adjacent to a letter in the lines above or below the current line.

If we place a letter on an anchor adjacent to a letter in the line above or below, we have to form a valid word with those letters as well, thus putting an additional constraint on the letters allowed for that anchor. When using anchors adjacent to a letter in the current line (and only to those), the letters that we can place on that tile are constrained only by the word we are going to form in the current line, so no checks other than the actual word-forming-algorithm are needed.

That means, in your example there would actually by no additional constraints for letters on tile x. Just find a prefix extending from x to the left, forming a valid word (or a longer prefix) with the letter A.

You may also want to check out the Udacity Course "Design of Computer Programs", where they discuss a Scrabble-solving algorithm in Unit 6.

Answer 2

I created an algorithm based on flood fill to collect all of the tiles that are touching the ones we just dropped, one of those must then intersect the centre tile for the play to be valid.

The algorithm starts at each tile you dropped, then checks each of the surrounding squares for a tile, if the tile exists in a particular direction will then add it to a Set and recursively do the same for each tile touching this new tile, if no tile exists it will exit the function. The recursion ends when we run out of tiles in all directions from the letters we played.

    func getFilledSquare(c: Coordinate) -> Square? {
        return squares
            |> { s in filter(s) { $0.c == c && $0.tile != nil } }
            |> { s in first(s) }
    }

    func getAdjacentFilledSquares(c: Coordinate?, vertically v: Bool, horizontally h: Bool, original: Square, inout output: Set<Square>) {
        // We may hit the original square several times in different directions, so we allow it through multiple times
        if let coord = c, sq = getFilledSquare(coord) where sq == original || !output.contains(sq) {
            output.insert(sq)
            if h {
                getAdjacentFilledSquares(coord.next(.Horizontal, d: 1, b: self), vertically: v, horizontally: h, original: original, output: &output)
                getAdjacentFilledSquares(coord.next(.Horizontal, d: -1, b: self), vertically: v, horizontally: h, original: original, output: &output)
            }
            if v {
                getAdjacentFilledSquares(coord.next(.Vertical, d: 1, b: self), vertically: v, horizontally: h, original: original, output: &output)
                getAdjacentFilledSquares(coord.next(.Vertical, d: -1, b: self), vertically: v, horizontally: h, original: original, output: &output)
            }
        }
    }

It's open source and the method is called getAdjacentFilledSquares (a bit verbose I know). My repo is here: https://github.com/ChrisAU/Locution?files=1