Definitions for backtrackingback·track·ing

WikipediaRate this definition:0.0 / 0 votes

1. Backtracking

Backtracking is a class of algorithms for finding solutions to some computational problems, notably constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandons a candidate ("backtracks") as soon as it determines that the candidate cannot possibly be completed to a valid solution.The classic textbook example of the use of backtracking is the eight queens puzzle, that asks for all arrangements of eight chess queens on a standard chessboard so that no queen attacks any other. In the common backtracking approach, the partial candidates are arrangements of k queens in the first k rows of the board, all in different rows and columns. Any partial solution that contains two mutually attacking queens can be abandoned. 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 valid solution. It is useless, for example, for locating a given value in an unordered table. When it is applicable, however, backtracking is often much faster than brute-force enumeration of all complete candidates, since it can eliminate many candidates with a single test. Backtracking is an important tool for solving constraint satisfaction problems, such as crosswords, verbal arithmetic, Sudoku, and many other puzzles. It is often the most convenient technique for parsing, for the knapsack problem and other combinatorial optimization problems. It is also the basis of the so-called logic programming languages such as Icon, Planner and Prolog. Backtracking depends on user-given "black box procedures" that define the problem to be solved, the nature of the partial candidates, and how they are extended into complete candidates. It is therefore a metaheuristic rather than a specific algorithm – although, unlike many other meta-heuristics, it is guaranteed to find all solutions to a finite problem in a bounded amount of time. The term "backtrack" was coined by American mathematician D. H. Lehmer in the 1950s. The pioneer string-processing language SNOBOL (1962) may have been the first to provide a built-in general backtracking facility.

FreebaseRate this definition:0.0 / 0 votes

1. Backtracking

Backtracking is a general algorithm for finding all solutions to some computational problem, that incrementally builds candidates to the solutions, and abandons each partial candidate c as soon as it determines that c cannot possibly be completed to a valid solution. The classic textbook example of the use of backtracking is the eight queens puzzle, that asks for all arrangements of eight chess queens on a standard chessboard so that no queen attacks any other. In the common backtracking approach, the partial candidates are arrangements of k queens in the first k rows of the board, all in different rows and columns. Any partial solution that contains two mutually attacking queens can be abandoned, since it 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 valid solution. It is useless, for example, for locating a given value in an unordered table. When it is applicable, however, backtracking is often much faster than brute force enumeration of all complete candidates, since it can eliminate a large number of candidates with a single test.

Numerology

1. Chaldean Numerology

The numerical value of backtracking in Chaldean Numerology is: 2

2. Pythagorean Numerology

The numerical value of backtracking in Pythagorean Numerology is: 1

Examples of backtracking in a Sentence

1. The U.S. side has given many labels recently, 'backtracking,' 'betraying,' etc. ... China sets great store on trustworthiness and keeps its promises, and this has never changed.

2. I think from an investor's point of view, this u-turn is hugely positive. The push-back by the market, part of the ANC and citizens forced this backtracking by Zuma.

3. Discord and backtracking over refugees and migration could end up fragmenting EU cohesion, taking away the political oxygen to deal with other challenges in the economy or Ukraine.

4. Talking and pledging is very easy but governing is slightly more difficult, the policy reforms that we've implemented have worked, and backtracking would be a blunder. When I see that, with the help of Podemos, the Socialists wants to change everything we've done, I just think it's bad for Spain.

5. I don’t like [backtracking], it gets in my head, but … you get over it.

Popularity rank by frequency of use

backtracking#10000#55257#100000

Translations for backtracking

• Backtracking
• retroceso
• バックトラッキング

Translation

Find a translation for the backtracking definition in other languages:

Select another language:

• - Select -
• 简体中文 (Chinese - Simplified)
• Español (Spanish)
• Esperanto (Esperanto)
• 日本語 (Japanese)
• Português (Portuguese)
• Deutsch (German)
• العربية (Arabic)
• Français (French)
• Русский (Russian)
• 한국어 (Korean)
• עברית (Hebrew)
• Gaeilge (Irish)
• Українська (Ukrainian)
• اردو (Urdu)
• Magyar (Hungarian)
• मानक हिन्दी (Hindi)
• Indonesia (Indonesian)
• Italiano (Italian)
• தமிழ் (Tamil)
• Türkçe (Turkish)
• తెలుగు (Telugu)
• ภาษาไทย (Thai)
• Tiếng Việt (Vietnamese)
• Čeština (Czech)
• Polski (Polish)
• Bahasa Indonesia (Indonesian)
• Românește (Romanian)
• Nederlands (Dutch)
• Ελληνικά (Greek)
• Latinum (Latin)
• Svenska (Swedish)
• Dansk (Danish)
• Suomi (Finnish)
• فارسی (Persian)
• ייִדיש (Yiddish)
• հայերեն (Armenian)
• Norsk (Norwegian)
• English (English)

Citation

Style:MLAChicagoAPA

"backtracking." Definitions.net. STANDS4 LLC, 2023. Web. 24 Mar. 2023. <https://www.definitions.net/definition/backtracking>.

Are we missing a good definition for backtracking? Don't keep it to yourself...

Credit »

Browse Definitions.net

Free, no signup required:

Get instant definitions for any word that hits you anywhere on the web!

Free, no signup required:

Get instant definitions for any word that hits you anywhere on the web!

Quiz

Are you a words master?

»
a custom among some peoples whereby the husband of a pregnant wife is put to bed at the time of bearing the child
• A. macron
• B. callathump