In my previous article, I explained the overall overview of a logic puzzle solver built with React + TypeScript. This time, I will delve deeper into the technical details of the core components of this project: Prolog engine integration and high-performance constraint satisfaction problem implementation utilizing WebAssembly.
Through developing educational tools for logic programming, I have been working on optimizing Prolog execution in browser environments. In this article, I will share the insights gained from this process and implementation techniques, including actual code examples.
Disclaimer: The implementation methods introduced in this article are based on the author's technical judgment. The selection of Prolog engines and WebAssembly integration may require different optimal approaches depending on project requirements. Please conduct thorough verification before implementation.
Prolog Engine Selection and Integration Strategy
Technical Comparison: Tau Prolog vs SWI-Prolog
For executing Prolog in browser environments, I had the following main options:
Tau Prolog Features:
- Prolog system completely implemented in JavaScript
- Browser-native execution environment
- Feature extension through module system
- High compatibility with ECMAScript compliance
SWI-Prolog + WebAssembly Features:
- High-performance production-level implementation based on C/C++
- Rich predicate library and constraint solvers
- Near-native performance through WebAssembly
- Precise control of memory usage
For this project, prioritizing educational use and browser usability, I adopted a hybrid strategy using Tau Prolog as the main engine while using the WebAssembly version of SWI-Prolog as a fallback for computationally intensive puzzles.
Design and Implementation of PrologEngine Class
Here is the implementation of the core class that abstracts the Prolog engine:
export class PrologEngine {
private module: Module | null = null
private isInitialized = false
constructor() {
this.initializeProlog()
}
private async initializeProlog() {
try {
// Dynamic loading of WebAssembly module
const Module = await import('swi-prolog-wasm')
this.module = await Module.default()
this.isInitialized = true
console.log('🧩 WASM Prolog engine initialized')
} catch (error) {
console.warn('WASM Prolog not available, using fallback')
}
}
async loadProgram(program: string): Promise<boolean> {
if (this.module && this.isInitialized) {
try {
this.module.ccall('load_program', null, ['string'], [program])
return true
} catch (error) {
console.error('Failed to load Prolog program:', error)
return false
}
}
return false
}
async query(goal: string): Promise<string[]> {
if (this.module && this.isInitialized) {
const results = this.module.ccall('query_goal', 'string', ['string'], [goal])
return JSON.parse(results)
}
return []
}
}
This design achieves a mechanism that automatically switches to JavaScript-based fallback implementation when WebAssembly is unavailable.
Prolog Implementation Patterns for Constraint Satisfaction Problems
Implementation Details of the Houses Problem
Using the basic "houses problem" among logic puzzles as an example, I will explain Prolog implementation patterns for constraint satisfaction problems.
% Alice, Bob, Charlie Houses Puzzle
solve_houses(People) :-
People = [person(alice, House1, Color1, Pet1),
person(bob, House2, Color2, Pet2),
person(charlie, House3, Color3, Pet3)],
% Domain constraint definition
permutation([1, 2, 3], [House1, House2, House3]),
permutation([red, blue, green], [Color1, Color2, Color3]),
permutation([dog, cat, bird], [Pet1, Pet2, Pet3]),
% Individual constraint conditions
( member(person(alice, _, red, _), People) ;
member(person(alice, _, blue, _), People) ),
member(person(bob, 2, _, _), People),
% Conditional constraints (Charlie's condition)
( (member(person(charlie, _, green, _), People),
member(person(charlie, _, _, dog), People)) ;
(\\+ member(person(charlie, _, green, _), People),
\\+ member(person(charlie, _, _, dog), People)) ),
% Exclusion constraints
\\+ (member(person(alice, _, red, dog), People)),
% Selection constraints
( member(person(_, _, blue, cat), People) ;
member(person(_, _, blue, bird), People) ).
The important points in this implementation are as follows:
Efficient Search through Permutation Generation: By using the permutation/2 predicate, all possible combinations are systematically generated, achieving efficient search through backtracking.
Hierarchical Constraints: Starting from basic domain constraints and gradually applying more complex conditional and exclusion constraints to achieve early pruning of the search space.
Representation of Negation and Selection: By appropriately combining Prolog's \+ (negation) and ; (selection) operators, complex logical relationships are accurately expressed.
Implementation of Backtracking Visualization
To make Prolog's reasoning process easier to understand, I implemented a mechanism that simulates each stage of backtracking on the JavaScript side for visualization.
const generateSolvingSteps = (puzzle: PuzzleProblem): PrologStep[] => {
return [
{
step: 1,
description: "Problem setup: Define variables and domains",
query: `solve_${puzzle.id}(Result)`,
result: "Setting up variables...",
facts: [
`People: [${puzzle.variables.people.join(', ')}]`,
...Object.entries(puzzle.variables.attributes).map(([key, values]) =>
`${key}: [${values.join(', ')}]`
)
]
},
{
step: 2,
description: "Apply constraints",
query: "apply_constraints(Variables)",
result: "Evaluating constraints...",
facts: puzzle.constraints.map((constraint, i) => `${i + 1}. ${constraint}`)
},
{
step: 3,
description: "Search solution with backtracking",
query: "find_solution(Result)",
result: "Solution found",
facts: [
"✅ Found solution satisfying all constraints",
"🔍 Logical reasoning process completed"
]
}
]
}
This implementation allows learners to understand Prolog's internal operation step by step.
Performance Optimization through WebAssembly Integration
Memory Management and Efficient Data Exchange
In integrating with the WebAssembly version of SWI-Prolog, the most important considerations were memory management and data exchange efficiency.
private async executeWasmQuery(goal: string): Promise<any> {
if (!this.module) return null
try {
// Buffer management considering memory efficiency
const goalBuffer = this.module._malloc(goal.length + 1)
this.module.stringToUTF8(goal, goalBuffer, goal.length + 1)
// Prolog query execution
const resultPtr = this.module.ccall(
'execute_query',
'number',
['number'],
[goalBuffer]
)
// Result retrieval and memory release
const result = this.module.UTF8ToString(resultPtr)
this.module._free(goalBuffer)
this.module._free(resultPtr)
return JSON.parse(result)
} catch (error) {
console.error('WASM query execution failed:', error)
return null
}
}
Ensuring UI Responsiveness through Asynchronous Processing
Since solving complex constraint satisfaction problems can be time-consuming, I also considered implementing asynchronous processing using Web Workers.
class PrologWorker {
private worker: Worker | null = null
constructor() {
this.worker = new Worker('/prolog-worker.js')
}
async solvePuzzle(puzzle: PuzzleProblem): Promise<any> {
return new Promise((resolve, reject) => {
if (!this.worker) {
reject(new Error('Worker not available'))
return
}
const timeoutId = setTimeout(() => {
reject(new Error('Puzzle solving timeout'))
}, 30000) // 30-second timeout
this.worker.onmessage = (event) => {
clearTimeout(timeoutId)
if (event.data.success) {
resolve(event.data.result)
} else {
reject(new Error(event.data.error))
}
}
this.worker.postMessage({
type: 'solve',
puzzle: puzzle
})
})
}
}
Sudoku Solver Implementation and Optimization
JavaScript Implementation of Backtracking Algorithm
To operate even in environments where Prolog engines are unavailable, I also prepared a pure JavaScript backtracking implementation for the Sudoku solver.
private solveSudokuRecursive(grid: number[][]): boolean {
// Search for empty cells
for (let row = 0; row < 9; row++) {
for (let col = 0; col < 9; col++) {
if (grid[row][col] === 0) {
// Try values 1-9
for (let num = 1; num <= 9; num++) {
if (this.isValidPlacement(grid, row, col, num)) {
grid[row][col] = num
// Recursively search for solution
if (this.solveSudokuRecursive(grid)) {
return true
}
// Backtrack
grid[row][col] = 0
}
}
return false // If all values are invalid
}
}
}
return true // If all cells are filled
}
private isValidPlacement(grid: number[][], row: number, col: number, num: number): boolean {
// Row constraint check
for (let x = 0; x < 9; x++) {
if (grid[row][x] === num) return false
}
// Column constraint check
for (let x = 0; x < 9; x++) {
if (grid[x][col] === num) return false
}
// 3x3 block constraint check
const startRow = row - row % 3
const startCol = col - col % 3
for (let i = 0; i < 3; i++) {
for (let j = 0; j < 3; j++) {
if (grid[i + startRow][j + startCol] === num) return false
}
}
return true
}
This implementation enables comparative learning of the differences between Prolog's logic programming approach and imperative programming approach.
Performance Measurement and Optimization Strategies
Measurement and Analysis of Reasoning Time
To quantitatively evaluate the solving performance of constraint satisfaction problems, I implemented detailed measurement functionality.
async solvePuzzleWithMetrics(puzzle: PuzzleProblem): Promise<SolveResult> {
const startTime = performance.now()
let backtracks = 0
let nodesExplored = 0
try {
const solution = await this.solvePuzzle(puzzle)
const endTime = performance.now()
return {
solution,
metrics: {
executionTime: endTime - startTime,
backtracks,
nodesExplored,
memoryUsage: this.getMemoryUsage()
}
}
} catch (error) {
return {
solution: null,
error: error.message,
metrics: {
executionTime: performance.now() - startTime,
backtracks,
nodesExplored
}
}
}
}
Search Space Reduction through Constraint Propagation
Aiming for more efficient solutions, I experimentally implemented constraint propagation using Arc Consistency algorithms.
private propagateConstraints(domains: Map<string, Set<any>>): boolean {
let changed = true
while (changed) {
changed = false
for (const [variable, domain] of domains) {
const originalSize = domain.size
// Try domain reduction for each constraint
for (const constraint of this.constraints) {
this.applyConstraint(constraint, variable, domain, domains)
}
if (domain.size < originalSize) {
changed = true
}
// Contradiction if domain becomes empty
if (domain.size === 0) {
return false
}
}
}
return true
}
Future Prospects and Technical Challenges
Integration of More Advanced Constraint Solvers
I am currently considering the integration of CHR (Constraint Handling Rules) and CLP (Constraint Logic Programming) libraries, aiming for further optimization for linear constraints and finite domain constraints.
Error Handling and Debugging Support
Since debugging Prolog programs is generally difficult, strengthening detailed analysis of constraint violations and solution existence diagnosis functions is also recognized as an important challenge.
Conclusion
In this article, I have explained in detail the integration of Prolog engines in browser environments and the implementation of high-performance constraint satisfaction problems utilizing WebAssembly. Through the hybrid utilization of Tau Prolog and SWI-Prolog, I believe I have built a system that balances educational value and practical performance.
I aim to continue developing this into a more useful tool for more learners through ongoing optimization.
Project Repository: GitHub
This article is an explanation based on the technical experience of the logic puzzle solver developer. Please consider implementation methods and optimization strategies according to individual project requirements.