CODEWITHSUNDEEP
algorithm
user63898
user63898

Reputation: 30923

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 algorithms should i learn ?

Upvotes: 2

Views: 899

Answers (4)

Ahmad
Ahmad

Reputation: 9668

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

Upvotes: 1

Lazer
Lazer

Reputation: 94950

  • 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.

Upvotes: 0

Master Yoda
Master Yoda

Reputation: 587

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 :)

Upvotes: 0

Yuval F
Yuval F

Reputation: 20621

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.

Upvotes: 4

Related Questions