Spaces:

Rithikadroid
/

nqueensproblemvisualizer-com

Running

App Files Files Community

nqueensproblemvisualizer-com / index.html

Rithikadroid

make nxn chessboard which can change (1-8)

07aa1d4 verified 12 months ago

Raw

History Blame Contribute Delete

16.5 kB

	<!DOCTYPE html>
	<html lang="en">
	<head>
	<meta charset="UTF-8">
	<meta name="viewport" content="width=device-width, initial-scale=1.0">
	<title>N-Queens Problem Visualizer</title>
	<script src="https://cdn.tailwindcss.com"></script>
	<link href="https://unpkg.com/aos@2.3.1/dist/aos.css" rel="stylesheet">
	<script src="https://unpkg.com/aos@2.3.1/dist/aos.js"></script>
	<script src="https://cdn.jsdelivr.net/npm/feather-icons/dist/feather.min.js"></script>
	<script src="https://unpkg.com/feather-icons"></script>
	<style>
	.chess-board {
	display: grid;
	aspect-ratio: 1/1;
	border: 2px solid #333;
	}

	.chess-cell {
	display: flex;
	justify-content: center;
	align-items: center;
	position: relative;
	}

	.queen {
	color: #dc2626;
	font-size: 80%;
	}

	.conflict {
	background-color: rgba(239, 68, 68, 0.3) !important;
	}

	.solution-node {
	transition: all 0.3s ease;
	cursor: pointer;
	}

	.solution-node:hover {
	transform: scale(1.05);
	}

	.tree-container {
	max-height: 60vh;
	overflow-y: auto;
	}

	.active-solution {
	border: 2px solid #3b82f6;
	box-shadow: 0 0 10px rgba(59, 130, 246, 0.5);
	}
	</style>
	</head>
	<body class="bg-gray-50 min-h-screen">
	<div class="container mx-auto px-4 py-8">
	<header class="text-center mb-8" data-aos="fade-down">
	<h1 class="text-3xl md:text-4xl font-bold text-gray-800 mb-2">N-Queens Problem Visualizer</h1>
	<p class="text-gray-600">Place N queens on an N×N chessboard so that no two queens threaten each other</p>
	</header>

	<div class="grid grid-cols-1 lg:grid-cols-2 gap-8">
	<!-- Left Column: Controls and Chessboard -->
	<div class="space-y-6">
	<div class="bg-white rounded-lg shadow-md p-6" data-aos="fade-right">
	<h2 class="text-xl font-semibold mb-4 flex items-center">
	<i data-feather="sliders" class="mr-2"></i> Configuration
	</h2>

	<div class="mb-4">
	<label class="block text-sm font-medium text-gray-700 mb-2">Board Size (N)</label>
	<div class="flex items-center space-x-4">
	<input type="range" min="1" max="8" value="4" class="w-full" id="boardSizeSlider">
	<span class="text-lg font-medium w-8 text-center" id="boardSizeValue">4</span>
	</div>
	</div>

	<div class="flex space-x-3">
	<button id="solveBtn" class="flex-1 bg-blue-600 hover:bg-blue-700 text-white py-2 px-4 rounded-md flex items-center justify-center">
	<i data-feather="play" class="mr-2"></i> Solve
	</button>
	<button id="resetBtn" class="flex-1 bg-gray-200 hover:bg-gray-300 text-gray-800 py-2 px-4 rounded-md flex items-center justify-center">
	<i data-feather="refresh-cw" class="mr-2"></i> Reset
	</button>
	</div>
	</div>

	<div class="bg-white rounded-lg shadow-md p-6" data-aos="fade-right" data-aos-delay="100">
	<h2 class="text-xl font-semibold mb-4 flex items-center">
	<i data-feather="grid" class="mr-2"></i> Chessboard
	</h2>

	<div class="flex justify-center">
	<div id="chessboardContainer" class="w-full max-w-md"></div>
	</div>
	</div>
	</div>

	<!-- Right Column: Solutions and Space Tree -->
	<div class="space-y-6">
	<div class="bg-white rounded-lg shadow-md p-6" data-aos="fade-left">
	<h2 class="text-xl font-semibold mb-4 flex items-center">
	<i data-feather="list" class="mr-2"></i> Solutions
	<span id="solutionsCount" class="ml-2 bg-blue-100 text-blue-800 text-xs font-medium px-2.5 py-0.5 rounded">0 found</span>
	</h2>

	<div id="solutionsContainer" class="grid grid-cols-2 sm:grid-cols-3 gap-3 max-h-60 overflow-y-auto"></div>
	</div>

	<div class="bg-white rounded-lg shadow-md p-6" data-aos="fade-left" data-aos-delay="100">
	<h2 class="text-xl font-semibold mb-4 flex items-center">
	<i data-feather="git-branch" class="mr-2"></i> Search Space Tree
	</h2>

	<div id="treeContainer" class="tree-container bg-gray-100 p-4 rounded-md">
	<div id="treeVisualization" class="relative"></div>
	</div>
	</div>
	</div>
	</div>
	</div>

	<script>
	// Initialize libraries
	document.addEventListener('DOMContentLoaded', function() {
	AOS.init();
	feather.replace();

	// Initialize the chessboard
	const boardSizeSlider = document.getElementById('boardSizeSlider');
	const boardSizeValue = document.getElementById('boardSizeValue');
	const chessboardContainer = document.getElementById('chessboardContainer');
	const solutionsContainer = document.getElementById('solutionsContainer');
	const solutionsCount = document.getElementById('solutionsCount');
	const treeVisualization = document.getElementById('treeVisualization');
	const solveBtn = document.getElementById('solveBtn');
	const resetBtn = document.getElementById('resetBtn');

	let currentSize = 4;
	let solutions = [];
	let currentSolutionIndex = -1;

	// Create the initial chessboard
	createChessboard(currentSize);

	// Event listeners
	boardSizeSlider.addEventListener('input', function() {
	currentSize = parseInt(this.value);
	boardSizeValue.textContent = currentSize;
	createChessboard(currentSize);
	clearSolutions();
	});

	solveBtn.addEventListener('click', function() {
	solveNQueens(currentSize);
	});

	resetBtn.addEventListener('click', function() {
	createChessboard(currentSize);
	clearSolutions();
	});

	function createChessboard(size) {
	chessboardContainer.innerHTML = '';
	const board = document.createElement('div');
	board.className = 'chess-board';
	board.style.gridTemplateColumns = `repeat(${size}, 1fr)`;
	board.style.gridTemplateRows = `repeat(${size}, 1fr)`;

	for (let row = 0; row < size; row++) {
	for (let col = 0; col < size; col++) {
	const cell = document.createElement('div');
	cell.className = `chess-cell ${(row + col) % 2 === 0 ? 'bg-gray-100' : 'bg-gray-300'}`;
	cell.dataset.row = row;
	cell.dataset.col = col;
	board.appendChild(cell);
	}
	}

	chessboardContainer.appendChild(board);
	}

	function solveNQueens(n) {
	solutions = [];
	currentSolutionIndex = -1;
	clearSolutions();

	// Solve using backtracking
	const board = Array(n).fill().map(() => Array(n).fill(0));
	solveNQueensUtil(board, 0, n);

	// Display solutions count
	solutionsCount.textContent = `${solutions.length} found`;

	// Display solutions
	if (solutions.length > 0) {
	displaySolutions();
	displaySearchTree(n);
	showSolution(0); // Show first solution by default
	} else {
	solutionsContainer.innerHTML = '<p class="text-gray-500 text-center col-span-full">No solutions found</p>';
	treeVisualization.innerHTML = '<p class="text-gray-500 text-center">No search tree to display</p>';
	}
	}

	function solveNQueensUtil(board, col, n) {
	if (col >= n) {
	// Found a solution
	const solution = [];
	for (let i = 0; i < n; i++) {
	for (let j = 0; j < n; j++) {
	if (board[i][j] === 1) {
	solution.push(j);
	}
	}
	}
	solutions.push(solution);
	return;
	}

	for (let i = 0; i < n; i++) {
	if (isSafe(board, i, col, n)) {
	board[i][col] = 1;
	solveNQueensUtil(board, col + 1, n);
	board[i][col] = 0; // backtrack
	}
	}
	}

	function isSafe(board, row, col, n) {
	// Check row on left side
	for (let i = 0; i < col; i++) {
	if (board[row][i] === 1) return false;
	}

	// Check upper diagonal on left side
	for (let i = row, j = col; i >= 0 && j >= 0; i--, j--) {
	if (board[i][j] === 1) return false;
	}

	// Check lower diagonal on left side
	for (let i = row, j = col; i < n && j >= 0; i++, j--) {
	if (board[i][j] === 1) return false;
	}

	return true;
	}

	function displaySolutions() {
	solutionsContainer.innerHTML = '';

	solutions.forEach((solution, index) => {
	const solutionElement = document.createElement('div');
	solutionElement.className = 'solution-node bg-white border rounded-md p-2 text-center cursor-pointer';
	solutionElement.innerHTML = `
	<div class="text-sm font-medium">Solution ${index + 1}</div>
	<div class="text-xs text-gray-500">[${solution.join(', ')}]</div>
	`;

	solutionElement.addEventListener('click', () => {
	showSolution(index);
	});

	solutionsContainer.appendChild(solutionElement);
	});
	}

	function showSolution(index) {
	// Remove active class from all solutions
	document.querySelectorAll('.solution-node').forEach(node => {
	node.classList.remove('active-solution', 'bg-blue-50');
	});

	// Add active class to selected solution
	document.querySelectorAll('.solution-node')[index].classList.add('active-solution', 'bg-blue-50');

	currentSolutionIndex = index;
	renderBoardWithSolution(solutions[index]);
	}

	function renderBoardWithSolution(solution) {
	const cells = document.querySelectorAll('.chess-cell');
	const n = solution.length;

	// Clear the board
	cells.forEach(cell => {
	cell.innerHTML = '';
	cell.classList.remove('conflict');
	});

	// Place queens
	for (let col = 0; col < n; col++) {
	const row = solution[col];
	const cellIndex = row * n + col;
	if (cells[cellIndex]) {
	cells[cellIndex].innerHTML = '<i data-feather="circle" class="queen"></i>';
	}
	}

	feather.replace();
	}

	function displaySearchTree(n) {
	treeVisualization.innerHTML = '';

	// Create a simplified visualization of the search space
	const treeContainer = document.createElement('div');
	treeContainer.className = 'space-y-4';

	// Add title
	const title = document.createElement('div');
	title.className = 'text-sm font-medium text-gray-700';
	title.textContent = `Search space for ${n}-queens problem`;
	treeContainer.appendChild(title);

	// Add info about the search
	const info = document.createElement('div');
	info.className = 'text-xs text-gray-500';
	info.innerHTML = `
	<p>• The algorithm uses backtracking to explore possible queen placements</p>
	<p>• Each level represents a column where a queen is being placed</p>
	<p>• Valid placements continue to the next level (column)</p>
	<p>• Invalid placements cause backtracking to previous levels</p>
	`;
	treeContainer.appendChild(info);

	// Add visualization of the search process
	const visual = document.createElement('div');
	visual.className = 'bg-blue-50 p-3 rounded-md mt-2';

	const visualContent = document.createElement('div');
	visualContent.className = 'text-xs';

	if (n <= 4) {
	visualContent.innerHTML = `
	<p class="font-medium mb-1">Search Process:</p>
	<p>1. Start with column 0, try all rows</p>
	<p>2. For each valid placement, move to next column</p>
	<p>3. When a solution is found, record it and backtrack</p>
	<p>4. Continue until all possibilities are explored</p>
	`;
	} else {
	visualContent.innerHTML = `
	<p class="font-medium mb-1">Search Process (simplified):</p>
	<p>The search tree for ${n}-queens is too large to display in detail.</p>
	<p>The algorithm explored ${Math.pow(n, n)} possible placements</p>
	<p>but used constraints to prune invalid branches early.</p>
	`;
	}

	visual.appendChild(visualContent);
	treeContainer.appendChild(visual);

	treeVisualization.appendChild(treeContainer);
	}

	function clearSolutions() {
	solutions = [];
	currentSolutionIndex = -1;
	solutionsContainer.innerHTML = '';
	solutionsCount.textContent = '0 found';
	treeVisualization.innerHTML = '<p class="text-gray-500 text-center">Solve to see search tree</p>';

	// Clear any queens from the board
	const cells = document.querySelectorAll('.chess-cell');
	cells.forEach(cell => {
	cell.innerHTML = '';
	cell.classList.remove('conflict');
	});
	}
	});
	</script>
	</body>
	</html>