2

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?

2 Answers 2

3

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.

3
  • Ok, that helps a bit but I still have some questions. Paragraph 3.3.1 says: "...Furthermore, the anchor squares are exactly those with nontrivial cross-checks...". The part I put in bold suggets (IMO) that anchors are only those that require cross-checking (thus those adjacent to tiles in the lines above or below the current line). What you wrote in your post however makes me think anchors are those squares which only sometimes require said checking. Where am I wrong and which one is true? --- Also, why do I never need to cross-check the squares in left parts?
    – NPS
    Sep 8, 2012 at 14:25
  • I think, the usage of the term cross check is a bit inconsistent here. I understand 3.3.1 in the way that the part to the left of an anchor never touches another letter. (It is either made up of existing letters, or extends to at most the next anchor to the left, otherwise the word would belong to that other anchor.) Thus, the left part can be any prefix (from your set of known prefixes), and only when the prefix reaches the anchor it is checked whether it fits to the existing letters on the board.
    – tobias_k
    Sep 8, 2012 at 15:11
  • 1
    I marked your post as an answer although it was rather kind of another clue that finally made me realise what is what than an actual answer. Still I'm very greatful. Both your post and the link you provided helped. Btw. I'd like to clarify some things for other people reading it: ANCHORS ARE ALL SQUARES ADJACENT IN ANY WAY (VERTICALLY OR HORIZONTALLY) TO ANY TILE ALREADY ON THE BOARD. I really wish someone had just said so anywhere. :P Also, anchors sometimes (but not always) need to be cross-checked, no more, no less.
    – NPS
    Sep 8, 2012 at 15:28
0

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

3
  • Improved my answer, I'll also get onto adding an MD file soon. The function fulfills the anchor definition posted above.
    – cjnevin
    Jun 7, 2015 at 13:42
  • While this link may answer the question, it is better to include the essential parts of the answer here and provide the link for reference. Link-only answers can become invalid if the linked page changes. Jun 7, 2015 at 15:57
  • Thanks for the tip, didn't think about that but it makes sense. I'll update my answer.
    – cjnevin
    Jun 7, 2015 at 15:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.