Project

QUESTION

a) Given the two games below explain what algorithmic class can be implemented using AI software to solve the below problems.

1. A crossword puzzle.

2. Beat an opponent in drafts.

ANSWER

1. A crossword puzzle

Crossword puzzles, in addition to being a hobby of potentially millions of people around the world, are an excellent real-world example  of a constraint satisfaction problem.  A solution to a crossword puzzle, after all, is an assignment of words to a grid such that each meets a number of constraints: a semantic constraint provided by the clue, a length constraint provided by the grid, and constraints on its its letters provided by the words which it overlaps in the grid.  Similarly, the construction of a puzzle is based on similar constraints, although the application is somewhat different.  This paper describes an attempt at modeling those constraints formally and using that model to implement systems to solve and generate puzzles.

Ideally, any solution to the crossword puzzle problem would first provide a general-purpose constraint satisfaction implementation which would be applicable to other domains.  Unfortunately, to date I have been unable to achieve such a general solution, although I have had limited success with crossword-specific solutions.  This paper, therefore, describes the models I have created and

To solve a crossword puzzle you need to use Backtracking algorithm

Backtracking algorithm

Backtracking is a general algorithm for finding all (or some) solutions to some computational problems, notably constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandons each partial candidate c ("backtracks") as soon as it determines that c cannot possibly be completed to a valid solution

Backtracking can be applied only for problems which admit the concept of a "partial candidate solution" and a relatively quick test of whether it can possibly be completed to a...