Spreadsheet Interface for Tabular Constraint Programming

In this project we are developing a generalization of the spreadsheet paradigm, called Knowledgesheet, for solving a class of constraint satisfaction problems. The traditional spreadsheet paradigm is based on attaching expression to individual cells and then evaluating them; the Knowledgesheet interface instead allows finite domain constraints to be attached to individual cells that are then solved to obtain a solution. This extension provides an easy-to-use interface for solving a large class of constraint satisfaction problems---those whose specification and solution conforms to a 2-dimensional structure, e.g., scheduling problems, time-tabling problems, etc. A prototype for the Knowledgesheet has been developed and applied to solve many different types of problems. This prototype includes the spreadsheet-like interface as well as the protocol between the interface and the back-end constraint-solving engine. The constraint solving engine is based on a finite domain constraint logic programming system (CLP(FD)). The protocol maps the constraints attached to the various cells of the Knowledgesheet to a CLP(FD) program. The auto-generated program is executed by the back-end CLP(FD) engine and the computed results communicated to the Knowledgesheet interface for display. A major advantage of Knowledgesheet is that novice users can solve certain types of practical constraint satisfaction problems without being an expert in constraint logic programming or constraint solving. Participants: S. Akhter (now at Intel), Larry King.

Papers