/**
* Simple Towers of Hanoi Solver with Move Validator
*/
class TowersOfHanoi {
constructor(numDisks) {
this.numDisks = numDisks;
this.reset();
}
reset() {
// Initialize towers: A has all disks, B and C are empty
this.towers = {
A: Array.from({length: this.numDisks}, (_, i) => this.numDisks - i),
B: [],
C: []
};
this.moveCount = 0;
this.moves = [];
}
/**
* Check if a move is valid
* @param {string} from - Source tower ('A', 'B', or 'C')
* @param {string} to - Destination tower ('A', 'B', or 'C')
* @returns {Object} - {valid, reason, disk}
*/
isValidMove(from, to) {
// Check if towers exist
if (!this.towers[from] || !this.towers[to]) {
return {valid: false, reason: "Invalid tower name", disk: null};
}
// Check if source tower has disks
if (this.towers[from].length === 0) {
return {valid: false, reason: "Source tower is empty", disk: null};
}
const sourceDisk = this.towers[from][this.towers[from].length - 1];
const destTop = this.towers[to].length > 0 ? this.towers[to][this.towers[to].length - 1] : Infinity;
// Check if disk can be placed (smaller on larger)
if (sourceDisk > destTop) {
return {valid: false, reason: "Cannot place larger disk on smaller disk", disk: sourceDisk};
}
return {valid: true, reason: "Valid move", disk: sourceDisk};
}
/**
* Execute a move if valid
* @param {string} from - Source tower
* @param {string} to - Destination tower
* @returns {Object} - {success, validation, state}
*/
makeMove(from, to) {
const validation = this.isValidMove(from, to);
if (validation.valid) {
const disk = this.towers[from].pop();
this.towers[to].push(disk);
this.moveCount++;
this.moves.push({from, to, disk, moveNumber: this.moveCount});
}
return {
success: validation.valid,
validation: validation,
state: this.getState()
};
}
/**
* Get current state of towers
*/
getState() {
return {
towers: JSON.parse(JSON.stringify(this.towers)),
moveCount: this.moveCount,
isSolved: this.towers.C.length === this.numDisks
};
}
/**
* Solve using iterative approach
* Uses the pattern: alternate between smallest disk and other moves
*/
solve() {
this.reset();
const solution = [];
// Determine direction based on number of disks
// Odd: A->C, Even: A->B
const isOdd = this.numDisks % 2 === 1;
const smallestDiskPath = isOdd ? ['A', 'C', 'B'] : ['A', 'B', 'C'];
let smallestDiskPos = 0; // Position in the path
const totalMoves = Math.pow(2, this.numDisks) - 1;
for (let moveNum = 1; moveNum <= totalMoves; moveNum++) {
let result;
if (moveNum % 2 === 1) {
// Odd moves: move smallest disk
const from = smallestDiskPath[smallestDiskPos];
const to = smallestDiskPath[(smallestDiskPos + 1) % 3];
result = this.makeMove(from, to);
smallestDiskPos = (smallestDiskPos + 1) % 3;
} else {
// Even moves: make the only legal move not involving smallest disk
const towers = ['A', 'B', 'C'];
const smallestTower = smallestDiskPath[smallestDiskPos];
const otherTowers = towers.filter(t => t !== smallestTower);
// Try both directions between the two non-smallest towers
let found = false;
for (let from of otherTowers) {
for (let to of otherTowers) {
if (from !== to && this.isValidMove(from, to).valid) {
result = this.makeMove(from, to);
found = true;
break;
}
}
if (found) break;
}
}
solution.push({
moveNumber: moveNum,
move: result,
state: this.getState()
});
}
return solution;
}
/**
* Validate a sequence of moves
* @param {Array} moves - Array of {from, to} objects
* @returns {Object} - Validation result with details
*/
validateMoveSequence(moves) {
this.reset();
const results = [];
let allValid = true;
for (let i = 0; i < moves.length; i++) {
const move = moves[i];
const result = this.makeMove(move.from, move.to);
results.push({
moveNumber: i + 1,
move: move,
result: result,
state: this.getState()
});
if (!result.success) {
allValid = false;
}
}
return {
valid: allValid,
isSolved: this.towers.C.length === this.numDisks,
totalMoves: moves.length,
optimalMoves: Math.pow(2, this.numDisks) - 1,
results: results
};
}
}
// Example usage and testing
console.log("=== Towers of Hanoi Solver ===\n");
// Test with 3 disks
console.log("Solving 3-disk Towers of Hanoi:");
const hanoi3 = new TowersOfHanoi(3);
console.log("Initial state:", hanoi3.getState());
const solution3 = hanoi3.solve();
console.log(`\nSolution found in ${solution3.length} moves:`);
solution3.forEach(step => {
const move = step.move.validation;
console.log(`Move ${step.moveNumber}: ${step.move.move?.from || 'N/A'} → ${step.move.move?.to || 'N/A'} (disk ${move.disk})`);
});
console.log("Final state:", hanoi3.getState());
// Test move validation
console.log("\n=== Move Validation Tests ===");
const hanoiTest = new TowersOfHanoi(3);
console.log("\nTesting valid moves:");
console.log("A → C:", hanoiTest.makeMove('A', 'C'));
console.log("A → B:", hanoiTest.makeMove('A', 'B'));
console.log("\nTesting invalid moves:");
console.log("C → B (larger on smaller):", hanoiTest.makeMove('C', 'B'));
console.log("C → A (empty tower):", hanoiTest.makeMove('C', 'A'));
// Test sequence validation
console.log("\n=== Sequence Validation Test ===");
const testMoves = [
{from: 'A', to: 'C'},
{from: 'A', to: 'B'},
{from: 'C', to: 'B'},
{from: 'A', to: 'C'},
{from: 'B', to: 'A'},
{from: 'B', to: 'C'},
{from: 'A', to: 'C'}
];
const validationResult = new TowersOfHanoi(3).validateMoveSequence(testMoves);
console.log("Sequence validation:", {
valid: validationResult.valid,
solved: validationResult.isSolved,
moves: validationResult.totalMoves,
optimal: validationResult.optimalMoves
});
// Test with different disk counts
console.log("\n=== Solutions for Different Disk Counts ===");
for (let n = 1; n <= 4; n++) {
const hanoi = new TowersOfHanoi(n);
const solution = hanoi.solve();
console.log(`${n} disks: ${solution.length} moves (optimal: ${Math.pow(2, n) - 1})`);
}