# ASP DSL Template Library
**7 Pre-Built Problem Templates**
## Overview
Templates provide pre-built ASP programs for common problem patterns. Simply provide parameters and get a complete, optimized ASP program.
## Template System Architecture
### Template Interface
```typescript
interface ProblemTemplate {
name: string;
description: string;
category: string;
parameters: TemplateParameter[];
generate(params: Record<string, any>): string;
validate(params: Record<string, any>): ValidationResult;
examples: TemplateExample[];
}
```
## Template Library
### 1. Graph Coloring Template
**Description:** Color graph vertices such that adjacent vertices have different colors.
**Parameters:**
- `vertices` (number[] | number): List of vertices or count (1..n)
- `edges` ([number, number][]): List of edges
- `numColors` (number): Number of colors to use
- `directed` (boolean, optional): Is graph directed? Default: false
**Generated Program:**
```asp
% Vertices
vertex(${vertices}).
% Edges
${edges.map(([u,v]) => `edge(${u}, ${v}).`).join('\n')}
% Colors
color(1..${numColors}).
% Assignment: each vertex one color
1 {assign(X, C) : color(C)} 1 :- vertex(X).
% Constraint: adjacent vertices different colors
:- assign(X, C), assign(Y, C), edge(X, Y).
% Output
#show assign/2.
```
**Usage Example:**
```typescript
const program = templates.apply('graph_coloring', {
vertices: [1, 2, 3, 4, 5],
edges: [[1,2], [2,3], [3,4], [4,5], [5,1]],
numColors: 3
});
```
**Optimization Variant:**
```typescript
// Minimize colors used
const program = templates.apply('graph_coloring', {
vertices: 5,
edges: [[1,2], [2,3], [3,4], [4,5], [5,1]],
numColors: 5, // Upper bound
minimize: true
});
```
Adds:
```asp
color_used(C) :- assign(X, C).
#minimize {1, C : color_used(C)}.
```
---
### 2. Hamiltonian Path Template
**Description:** Find path visiting each vertex exactly once.
**Parameters:**
- `vertices` (number[]): List of vertices
- `edges` ([number, number][]): List of edges
- `start` (number, optional): Starting vertex
- `end` (number, optional): Ending vertex
- `cycle` (boolean, optional): Find cycle instead of path
**Generated Program:**
```asp
% Vertices
vertex(${vertices.join('; ')}).
% Edges (make undirected)
${edges.map(([u,v]) => `edge(${u}, ${v}).`).join('\n')}
edge(X, Y) :- edge(Y, X).
${start ? `start(${start}).` : ''}
${end ? `end(${end}).` : ''}
% Select path edges
{in_path(X, Y)} :- edge(X, Y).
${!cycle ? `
% Each vertex (except start) has exactly one incoming
1 {in_path(Y, X) : edge(Y, X)} 1 :- vertex(X), not start(X).
% Each vertex has at most one outgoing
{in_path(X, Y) : edge(X, Y)} 1 :- vertex(X).
% Start has exactly one outgoing
1 {in_path(X, Y) : edge(X, Y)} 1 :- start(X).
% No incoming to start
:- in_path(Y, X), start(X).
` : `
% Each vertex has exactly one incoming and outgoing (cycle)
1 {in_path(X, Y) : edge(X, Y)} 1 :- vertex(X).
1 {in_path(Y, X) : edge(Y, X)} 1 :- vertex(X).
`}
% Reachability
reach(X) :- start(X).
reach(Y) :- reach(X), in_path(X, Y).
:- vertex(V), not reach(V).
#show in_path/2.
```
---
### 3. N-Queens Template
**Description:** Place N queens on NxN board with no attacks.
**Parameters:**
- `n` (number): Board size
- `symmetryBreaking` (boolean, optional): Add symmetry breaking constraints
**Generated Program:**
```asp
% Board
row(1..${n}). col(1..${n}).
% One queen per row
1 {queen(R, C) : col(C)} 1 :- row(R).
% No column conflicts
:- queen(R1, C), queen(R2, C), R1 != R2.
% No diagonal conflicts
:- queen(R1, C1), queen(R2, C2), R1 != R2, |C1 - R1| = |C2 - R2|.
:- queen(R1, C1), queen(R2, C2), R1 != R2, C1 + R1 = C2 + R2.
${symmetryBreaking ? `
% Symmetry breaking: queen in row 1 is in first half
:- queen(1, C), C > ${Math.ceil(n/2)}.
` : ''}
#show queen/2.
```
**Variants:**
- `n_queens_all`: Find all solutions
- `n_queens_one`: Find one solution (faster)
- `n_queens_count`: Count solutions only
---
### 4. Scheduling Template
**Description:** Schedule tasks/people to time slots/shifts with constraints.
**Parameters:**
- `entities` (string[]): People, tasks, etc.
- `slots` (string[]): Shifts, time slots, etc.
- `minPerSlot` (number): Minimum entities per slot
- `maxPerSlot` (number): Maximum entities per slot
- `entitiesPerSlot` (number, optional): Exact number if min=max
- `unavailable` ([string, string][], optional): Unavailability constraints
- `conflicts` ([string, string][], optional): Entity pairs that can't share slot
- `required` ([string, string][], optional): Entity must be in specific slot
**Generated Program:**
```asp
% Entities
entity(${entities.map(e => `'${e}'`).join('; ')}).
% Slots
slot(${slots.map(s => `'${s}'`).join('; ')}).
% Assignment: each entity to exactly one slot
1 {assign(E, S) : slot(S)} 1 :- entity(E).
% Slot capacity
${minPerSlot} {assign(E, S) : entity(E)} ${maxPerSlot} :- slot(S).
${unavailable?.map(([e, s]) =>
`:- assign('${e}', '${s}').`
).join('\n')}
${conflicts?.map(([e1, e2]) =>
`:- assign('${e1}', S), assign('${e2}', S).`
).join('\n')}
${required?.map(([e, s]) =>
`assign('${e}', '${s}').`
).join('\n')}
#show assign/2.
```
**Usage Example:**
```typescript
const program = templates.apply('scheduling', {
entities: ['alice', 'bob', 'carol', 'dave'],
slots: ['morning', 'afternoon', 'evening'],
minPerSlot: 1,
maxPerSlot: 2,
unavailable: [['alice', 'morning']],
conflicts: [['bob', 'carol']]
});
```
---
### 5. Sudoku Template
**Description:** Solve Sudoku puzzles of size NxN.
**Parameters:**
- `size` (number): Grid size (4, 9, 16)
- `boxSize` (number, optional): Box size (default: sqrt(size))
- `given` ([number, number, number][], optional): Initial clues [row, col, num]
**Generated Program:**
```asp
% Grid
cell(1..${size}, 1..${size}).
num(1..${size}).
% Each cell one number
1 {sudoku(R, C, N) : num(N)} 1 :- cell(R, C).
% Row constraint
:- sudoku(R, C1, N), sudoku(R, C2, N), C1 != C2.
% Column constraint
:- sudoku(R1, C, N), sudoku(R2, C, N), R1 != R2.
% Box constraint
box(R, C, (R-1)/${boxSize}, (C-1)/${boxSize}) :- cell(R, C).
:- sudoku(R1, C1, N), sudoku(R2, C2, N),
box(R1, C1, BR, BC), box(R2, C2, BR, BC),
R1 != R2, C1 != C2.
% Given clues
${given?.map(([r, c, n]) => `sudoku(${r}, ${c}, ${n}).`).join('\n')}
#show sudoku/3.
```
**Variants:**
- `sudoku_4x4`: 4x4 Sudoku
- `sudoku_9x9`: Standard 9x9 Sudoku
- `sudoku_16x16`: 16x16 Sudoku
---
### 6. Knapsack Template
**Description:** 0-1 knapsack optimization problem.
**Parameters:**
- `items` (string[]): Item names
- `weights` (Record<string, number>): Item weights
- `values` (Record<string, number>): Item values
- `capacity` (number): Knapsack capacity
- `mustInclude` (string[], optional): Items that must be selected
- `mustExclude` (string[], optional): Items that must not be selected
**Generated Program:**
```asp
% Items
item(${items.map(i => `'${i}'`).join('; ')}).
% Weights and values
${items.map(i => `weight('${i}', ${weights[i]}).`).join('\n')}
${items.map(i => `value('${i}', ${values[i]}).`).join('\n')}
% Capacity
capacity(${capacity}).
% Selection
{selected(I) : item(I)}.
% Capacity constraint
:- #sum{W, I : selected(I), weight(I, W)} > C, capacity(C).
${mustInclude?.map(i => `selected('${i}').`).join('\n')}
${mustExclude?.map(i => `:- selected('${i}').`).join('\n')}
% Maximize value
#maximize {V, I : selected(I), value(I, V)}.
#show selected/1.
```
**Variants:**
- `knapsack_bounded`: Bounded knapsack (multiple copies)
- `knapsack_multidimensional`: Multiple constraints (weight, volume, etc.)
---
### 7. Configuration Template
**Description:** Valid system configuration with dependencies and conflicts.
**Parameters:**
- `components` (Record<string, string[]>): Component options
- `dependencies` ([string, string][], optional): A requires B
- `conflicts` ([string, string][], optional): A conflicts with B
- `constraints` (string[], optional): Additional constraints
- `optimize` ('cost' | 'quality' | 'performance', optional): Optimization goal
**Generated Program:**
```asp
% Component types and options
${Object.entries(components).map(([type, options]) => `
${type}(${options.map(o => `'${o}'`).join('; ')}).
1 {select_${type}(X) : ${type}(X)} 1.
`).join('\n')}
% Dependencies
${dependencies?.map(([a, b]) =>
`:- select_component('${a}'), not select_component('${b}').`
).join('\n')}
% Conflicts
${conflicts?.map(([a, b]) =>
`:- select_component('${a}'), select_component('${b}').`
).join('\n')}
% Additional constraints
${constraints?.join('\n')}
${optimize ? `
% Optimization (costs/scores defined elsewhere)
#${optimize === 'cost' ? 'minimize' : 'maximize'} {
Score : select_component(C), ${optimize}_score(C, Score)
}.
` : ''}
#show select_cpu/1.
#show select_gpu/1.
% ... show all component selections
```
**Usage Example:**
```typescript
const program = templates.apply('configuration', {
components: {
cpu: ['intel', 'amd'],
gpu: ['nvidia', 'amd'],
ram: ['8gb', '16gb', '32gb']
},
dependencies: [
['intel', '16gb'], // Intel needs 16GB+
],
conflicts: [
['amd_cpu', 'amd_gpu'] // No AMD+AMD
],
optimize: 'cost'
});
```
---
## Template Engine Implementation
### Template Registry
```typescript
class TemplateRegistry {
private templates = new Map<string, ProblemTemplate>();
register(template: ProblemTemplate): void {
this.templates.set(template.name, template);
}
get(name: string): ProblemTemplate | undefined {
return this.templates.get(name);
}
list(): ProblemTemplate[] {
return Array.from(this.templates.values());
}
findByCategory(category: string): ProblemTemplate[] {
return this.list().filter(t => t.category === category);
}
}
```
### Template Application
```typescript
class TemplateEngine {
apply(
templateName: string,
params: Record<string, any>
): string {
const template = this.registry.get(templateName);
if (!template) {
throw new Error(`Template not found: ${templateName}`);
}
// Validate parameters
const validation = template.validate(params);
if (!validation.valid) {
throw new Error(`Invalid parameters: ${validation.errors.join(', ')}`);
}
// Generate program
return template.generate(params);
}
}
```
## Template Categories
### Graph Problems
- `graph_coloring`
- `hamiltonian_path`
- `hamiltonian_cycle`
- `max_independent_set`
- `max_clique`
### Scheduling
- `scheduling`
- `meeting_scheduler`
- `course_timetabling`
- `job_shop`
### Puzzles
- `n_queens`
- `sudoku_4x4`
- `sudoku_9x9`
- `knights_tour`
### Optimization
- `knapsack`
- `bin_packing`
- `tsp`
- `vehicle_routing`
### Configuration
- `configuration`
- `package_dependencies`
- `resource_allocation`
### Planning
- `blocks_world`
- `route_planning`
- `task_planning`
## Adding Custom Templates
### Create Template
```typescript
const myTemplate: ProblemTemplate = {
name: 'my_problem',
description: 'Description of problem',
category: 'optimization',
parameters: [
{
name: 'param1',
type: 'number',
required: true,
description: 'Description'
}
],
generate(params) {
return `
% Generated ASP program
% ...
`;
},
validate(params) {
if (!params.param1) {
return { valid: false, errors: ['param1 required'] };
}
return { valid: true };
},
examples: [
{
description: 'Example usage',
parameters: { param1: 42 },
expectedOutput: '...'
}
]
};
```
### Register Template
```typescript
const registry = new TemplateRegistry();
registry.register(myTemplate);
```
## Best Practices
1. **Parameter Validation**: Always validate parameters before generation
2. **Clear Documentation**: Provide examples for each template
3. **Optimization Hints**: Include comments about grounding size
4. **Default Values**: Provide sensible defaults for optional parameters
5. **Error Messages**: Clear error messages when validation fails
## Performance Considerations
### Grounding Size
Templates should warn about large groundings:
```typescript
validate(params) {
const estimatedGrounding = params.vertices.length ** 2;
if (estimatedGrounding > 100000) {
return {
valid: true,
warnings: ['Large grounding expected, may be slow']
};
}
return { valid: true };
}
```
### Optimization
Templates can include optimization tips:
```asp
% Optimization: Use X < Y instead of X != Y to halve grounding
edge(X, Y) :- vertex(X), vertex(Y), X < Y.
```
---
**Total: 7 templates covering major problem categories!**
