---
title: "Increasing Tree Search Efficiency for Constraint Satisfaction Problems"
authors:
  - "Robert M. Haralick"
  - "Gordon L. Elliott"
doi: ""
url: "https://ijcai.org/proceedings/1979/78"
pdf: "https://ijcai.org/proceedings/1979/0078.pdf"
venue: "Proceedings of the Sixth International Joint Conference on Artificial Intelligence"
year: 1979
pages: ""
track: ""
keywords:
---

# Increasing Tree Search Efficiency for Constraint Satisfaction Problems

Robert M. Haralick, Gordon L. Elliott

*Proceedings of the Sixth International Joint Conference on Artificial Intelligence*.

## Abstract

In this paper we explore the number of consistency checks made by a tree sear c h in o rder t o solve binary constraint satisfaction problems. l~e show analytically and experimentally that the two principles of first trying the pla c es most likely to fail and remembering wh a t ha s be en done to avoid repeating the same mistake twice improve the standard backtrac k ing sear c h. We experimentally show that a lookahead pro c edure called forward c hecking (to remember the future) which employs the most likely to fail principle performs better than standard b ac ktracking, Ullman's, Waltz's, Mackworth's, and Haralick's discrete relaxation in all c ases t e sted, and better than Gaschnigs backmarking in the larger problems.