Many problems in artificial intelligence are intractable owing to the exponential growth of the solution space with problem size. Often these problems can benefit from heuristic search or forward-checking techniques, which attempt to prune the search space down to a manageable size before or during the actual search procedure. Many interesting search problems can be formulated as consistent labeling problems in which the initial problem information is given in the form of a set of binary constraints, for which Boolean matrices are a natural data representation. In this paper optical implementations of Boolean matrix operations are proposed for manipulating the constraint matrices to perform forward checking and thereby increase the search efficiency. The high degree of parallelism afforded by using optical techniques and the relatively low accuracy requirements of Boolean matrix operations suggest that optical techniques are well matched to this problem.