Nondeterministic Algorithms

1 October 1967

journal article
Published by Association for Computing Machinery (ACM) in Journal of the ACM

Vol. 14 (4) , 636-644
https://doi.org/10.1145/321420.321422

Abstract

Programs to solve combinatorial search problems may often be simply written by using multiple-valued functions. Such programs, although impossible to execute directly on conventional computers, may be converted in a mechanical way into conventional backtracking programs. The process is illustrated with algorithms to find all solutions to the eight queens problem on the chessboard, and to find all simple cycles in a network.

Keywords

MULTIPLE-VALUED FUNCTION
NONDETERMINISTIC ALGORITHMS
SIMPLE CYCLE
CONVENTIONAL BACKTRACKING PROGRAM
QUEENS PROBLEM
CONVENTIONAL COMPUTER
COMBINATORIAL SEARCH PROBLEM

This publication has 2 references indexed in Scilit:

Backtrack Programming
Journal of the ACM, 1965
A syntax directed compiler for ALGOL 60
Communications of the ACM, 1961