Scrabble Word Block Solver

Problem Statement

Develop an algorithm that generates a valid n x n Scrabble word block. Given a square block of letters, the program output should only include valid words (horizontal and vertical), as determined by the scrabble dictionary. The solution to the problem should can be in any language or event pseudocode. The applicant should provide comments and explanations for their problem solving process.

Examples

5X5

S C A M P
A A L I I
B R I N E
E L V E R
D E E D S

6X6

U P P E R S
M E A N I E
B A R G E D
E N D I V E
R U I N E R
S T E E R S

Goals

The goals of this test are to evaluate the applicant's ability to:

• Design and implement an algorithm that solves a complex problem, communicate their problem solving process, and demonstrate their ability to implement strategies that meet requirements while taking into consideration the constraints.
• Optimize the algorithm for performance and memory efficiency
• Write clean and well-documented (pseudo)code
• Clearly explain their thought process and proposed solution

Constraints

• The program must adhere to valid Scrabble rules, including the use of the official Scrabble dictionary for validating words.
• The program must generate valid word blocks for square boards of size n x n, where n is between 3 and at least 6.
• Each word must be unique and can only be used once in a block solution

Requirements

• The program must output the generated Scrabble block and all valid words within it.
• The program's code must be self-documented with a detailed explanation of the algorithm and data structures used.
• The solution should take memory and execution time into account. As a rough guide, reasonable solutions for 6x6 blocks running on an average laptop should be in the 5 seconds or less range. Even when implemented in an interpreted language such as Ruby.
• The algorithm and solution must be thoroughly explained, with clear and detailed comments.
• The author should explain alternative approaches considered and justify why their proposed solution is the best option given the constraints and requirements.
• The explanation should discuss alternative approaches and provide any additional notes or comments that the author feels would be helpful in evaluating their solution.

Instructions for Submission

• The applicant must submit their solution in a document or text file, along with any instructions or notes needed to run the program (if applicable).
• Please send your submission to bacote@aps.org as a zip, .tar, or .tar.gz file.

Bonus Points

• Include examples of the largest blocks you created that contains valid words in the dictionary

Good luck!