which algorithms i need to learn to write crossword weaver?

i like to learn a bit about algorithms especially one that can help me to build crossword weaver (simple one )

which alg开发者_JAVA百科orithms should i learn ?

I would start with the following:

1. Dictionary Data Structures.
2. Strings.
3. Planning.
4. A star search.

Start small, using say a word list of 100 and a 2 by 2 crossword.

The main category of your problem is CSP (Constraint Satisfaction Problems) which is mainly solved by backtracking algorithms

Try backtracking which is similar to DFS. So learn DFS then learn backtracking.

A* is also good but you need good heuristic. A prefix tree with A* search might work. But first start the easy backtracking version.

By the way one advantage of learning backtracking is that, you can solve many other puzzle also using it, like sudoku, 15 queen, rate in a maze and zig-saw puzzle :)

• Have you decided what programming language you are going to use? When dealing with characters and strings, some languages are really better than others, for example Java and C++ have considerably better character/string handling capabilities.

• Apart from what Yuval and Atul mentioned, I think you will need to know about Longest Common Substring algorithms.

• Also check answers on this SO thread. There some algorithmic steps are discussed to create a crossword weaver. You should have an efficient algorithm of implementing each step that you follow.