バックトラッキング
処理を高速化するための一般的なヒューリスティクスがいくつか知られている。変数の処理の順番は決まっていないので、最も制約がきつい変数(つまり、値の範囲が狭いもの)から探索を始めるのが効率的であり、それによって探索木を早く刈り取ることができる(早期の選択の影響を最大限有効利用できる)。
設定する値を選ぶとき、多くの実装ではなるべく他の値を制限しない値を選ぶ。そのような選択をする背景には a) 解の発見に結びつく可能性が高いこと、b) 未解決の制約がなくなったときに解が見つかっていること、がある。
洗練されたバックトラッキングの実装では、束縛関数をしばしば使用する。それにより、現在の部分解で解を得られるかどうかをチェックする。従って、解に結びつかない部分解を検出する束縛関数によって検索効率を改善することができる。束縛関数は頻繁に動作するため、その計算コストはなるべく小さいのが望ましい。さもなくば、アルゴリズムの全体としての効率は改善されない。効率的な束縛関数は他のヒューリスティック関数を作るのと同様の方法で作成される。