8000 add n-knights · Koki131/backtrack-visualizer@9912386 · GitHub
[go: up one dir, main page]
Skip to content

Commit 9912386

Browse files
Koki131Koki131
committed
add n-knights
1 parent dfc61af commit 9912386

File tree

4 files changed

+342
-4
lines changed

4 files changed

+342
-4
lines changed

‎dist/index.html

Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -13,6 +13,7 @@
1313
<select name="select-problem" id="select-problem">
1414
<option value="Sudoku">Sudoku Solver</option>
1515
<option value="N-Queens">N-Queens</option>
16+
<option value="N-Knights">N-Knights</option>
1617
</select>
1718
</div>
1819

@@ -64,6 +65,28 @@ <h2 id="current-status"></h2>
6465

6566
</div>
6667
</div>
68+
<div class="n-knights-container" style="display: none;">
69+
<div id="picker-and-board">
70+
<div id="number-picker" style="margin-top: 1em;">
71+
<p id="knight-number-value">Value: 4</p>
72+
<input id="no-of-knights" type="range" min="1" max="9" value="4" step="1">
73+
<button id="submit-knight-range">Solve</button>
74+
<button id="stop-knight-execution">Stop</button>
75+
<select name="knight-speed" id="knight-speed">
76+
<option value="Slow">Slow</option>
77+
<option value="Medium">Medium</option>
78+
<option value="Fast">Fast</option>
79+
</select>
80+
</div>
81+
<div id="knight-result"><h3>Total: </h3></div>
82+
<div id="knight-board">
83+
84+
</div>
85+
</div>
86+
<div id="knight-solved-boards">
87+
88+
</div>
89+
</div>
6790

6891
</div>
6992
</body>

‎src/index.js

Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,10 +1,12 @@
11
import "./style.css";
22
import nQueens from "./nQueens";
33
import solveSudoku from "./sudokuSolver";
4+
import nKnights from "./nKnights";
45

56

67

78
const nQueensContainer = document.querySelector(".n-queens-container");
9+
const nKnightsContainer = document.querySelector(".n-knights-container");
810
const sudokuContainer = document.querySelector(".sudoku-container");
911
const selectProblem = document.querySelector("#select-problem");
1012

@@ -16,10 +18,17 @@ selectProblem.addEventListener("change", function(event) {
1618
case "N-Queens":
1719
sudokuContainer.style.display = "none";
1820
nQueensContainer.style = "display: grid; grid-template: 1fr / 10fr 3fr; align-items: center; justify-items: center;";
21+
nKnightsContainer.style.display = "none";
1922
break;
2023
case "Sudoku":
2124
sudokuContainer.style.display = "flex";
2225
nQueensContainer.style.display = "none";
26+
nKnightsContainer.style.display = "none";
27+
break;
28+
case "N-Knights":
29+
nKnightsContainer.style = "display: grid; grid-template: 1fr / 10fr 3fr; align-items: center; justify-items: center;"
30+
nQueensContainer.style.display = "none";
31+
sudokuContainer.style.display = "none";
2332
break;
2433
}
2534

‎src/nKnights.js

Lines changed: 306 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,306 @@
1+
2+
const knightBoard = document.querySelector("#knight-board");
3+
const solvedBoards = document.querySelector("#knight-solved-boards");
4+
const submitNum = document.querySelector("#submit-knight-range");
5+
const noOfKnights = document.querySelector("#no-of-knights");
6+
const stopExecution = document.querySelector("#stop-knight-execution");
7+
const result = document.querySelector("#knight-result h3");
8+
const solveSpeed = document.querySelector("#knight-speed");
9+
10+
11+
let stopEx = false;
12+
let combinations = 0;
13+
let count = 0;
14+
15+
let board;
16+
17+
let isSolving = false;
18+
19+
submitNum.addEventListener("click", async function() {
20+
result.textContent = "Total: ";
21+
combinations = 0;
22+
isSolving = true;
23+
solvedBoards.textContent = "";
24+
submitNum.disabled = true;
25+
26+
await nKnights();
27+
28+
submitNum.disabled = false;
29+
stopEx = false;
30+
isSolving = false;
31+
});
32+
33+
stopExecution.addEventListener("click", function() {
34+
35+
stopEx = true;
36+
37+
});
38+
39+
40+
if (!isSolving) {
41+
createDefaultBoard();
42+
createBoard();
43+
}
44+
45+
let value1 = 200;
46+
let value2 = 500;
47+
48+
solveSpeed.addEventListener("change", function(event) {
49+
50+
switch(event.target.value) {
51+
case "Slow":
52+
value1 = 500;
53+
value2 = 1000;
54+
break;
55+
case "Medium":
56+
value1 = 100;
57+
value2 = 200;
58+
break;
59+
case "Fast":
60+
value1 = 0;
61+
value2 = 0;
62+
break;
63+
}
64+
65+
})
66+
67+
68+
export default async function nKnights() {
69+
70+
if (board.length > 0) {
71+
72+
if (count == 0) {
73+
74+
count = 1;
75+
76+
await solveForNKnights(board, 0, 0, board.length);
77+
78+
count = 0;
79+
}
80+
81+
}
82+
83+
}
84+
85+
function createDefaultBoard() {
86+
const newBoard = [];
87+
88+
for (let i = 0; i < 4; i++) {
89+
90+
newBoard[i] = [];
91+
92+
for (let j = 0; j < 4; j++) {
93+
94+
const div = document.createElement("div");
95+
newBoard[i][j] = div;
96+
knightBoard.append(div);
97+
98+
}
99+
}
100+
knightBoard.style = `display: grid; grid-template: repeat(4, 1fr) / repeat(4, 1fr)`;
101+
board = newBoard;
102+
}
103+
104+
async function createKnightBoard(value) {
105+
106+
return new Promise((resolve) => {
107+
108+
const newBoard = [];
109+
knightBoard.textContent = "";
110+
111+
for (let i = 0; i < value; i++) {
112+
113+
newBoard[i] = [];
114+
115+
for (let j = 0; j < value; j++) {
116+
117+
const div = document.createElement("div");
118+
newBoard[i][j] = div;
119+
knightBoard.append(div);
120+
121+
}
122+
}
123+
124+
knightBoard.style = `display: grid; grid-template: repeat(${value}, 1fr) / repeat(${value}, 1fr)`;
125+
126+
board = newBoard; // Update the global board variable
127+
128+
resolve(board);
129+
130+
});
131+
132+
}
133+
134+
function createBoard() {
135+
136+
const pickerValue = document.querySelector("#knight-number-value");
137+
138+
noOfKnights.addEventListener("change", async function (event) {
139+
140+
141+
if (!isSolving) {
142+
143+
const value = event.target.value;
144+
pickerValue.textContent = "Value: " + value;
145+
if (board) {
146+
// Remove the previous board before creating a new one
147+
knightBoard.textContent = "";
148+
}
149+
150+
board = await createKnightBoard(value);
151+
152+
}
153+
154+
});
155+
156+
}
157+
158+
function sleep(ms) {
159+
return new Promise(resolve => setTimeout(resolve, ms));
160+
}
161+
162+
async function solveForNKnights(board, row, col, target) {
163+
164+
if (!stopEx) {
165+
if (target == 0) {
166+
appendBoard(board);
167+
combinations += 1;
168+
169+
result.textContent = "Total: " + combinations;
170+
171+
return;
172+
}
173+
174+
if (row == board.length-1 && col == board.length) {
175+
return;
176+
}
177+
178+
if (row == board.length) {
179+
return;
180+
}
181+
182+
if (col == board[row].length) {
183+
await solveForNKnights(board, row + 1, 0, target);
184+
return;
185+
}
186+
187+
await sleep(value1);
188+
189+
board[row][col].textContent = "\u265E";
190+
board[row][col].style.color = "red";
191+
192+
await sleep(value2);
193+
board[row][col].textContent = "";
194+
195+
if (isSafe(board, row, col)) {
196+
197+
board[row][col].style.color = "green";
198+
board[row][col].textContent = "\u265E";
199+
200+
await sleep(value1);
201+
202+
await solveForNKnights(board, row, col + 1, target - 1);
203+
204+
await sleep(value2);
205+
206+
board[row][col].textContent = "";
207+
}
208+
209+
210+
211+
await solveForNKnights(board, row, col + 1, target);
212+
213+
214+
}
215+
216+
217+
218+
}
219+
220+
function appendBoard(board) {
221+
222+
const solvedBoards = document.querySelector("#knight-solved-boards");
223+
const boardDiv = document.createElement("div");
224+
boardDiv.id = "solved-board-div";
225+
226+
for (let i = 0; i < board.length; i++) {
227+
228+
229+
for (let j = 0; j < board[i].length; j++) {
230+
231+
const div = document.createElement("div");
232+
233+
234+
if (board[i][j].textContent == "\u265E") {
235+
div.textContent = "\u265E";
236+
} else {
237+
div.textContent = "";
238+
}
239+
boardDiv.append(div);
240+
}
241+
}
242+
boardDiv.style = `display: grid; grid-template: repeat(${board.length}, 1fr) / repeat(${board[0].length}, 1fr); margin-top: 1em`;
243+
244+
solvedBoards.append(boardDiv);
245+
246+
247+
}
248+
249+
function isValid(board, row, col) {
250+
251+
if (row >= 0 && row <= board.length-1 && col >= 0 && col <= board[row].length-1) {
252+
return true;
253+
}
254+
return false;
255+
256+
}
257+
258+
function isSafe(board, row, col) {
259+
260+
if (isValid(board, row - 2, col - 1)) {
261+
if (board[row - 2][col - 1].textContent == "\u265E") {
262+
return false;
263+
}
264+
}
265+
if (isValid(board, row - 1, col - 2)) {
266+
if (board[row - 1][col - 2].textContent == "\u265E") {
267+
return false;
268+
}
269+
}
270+
if (isValid(board, row - 2, col + 1)) {
271+
if (board[row - 2][col + 1].textContent == "\u265E") {
272+
return false;
273+
}
274+
}
275+
if (isValid(board, row - 1, col + 2)) {
276+
if (board[row - 1][col + 2].textContent == "\u265E") {
277+
return false;
278+
}
279+
}
280+
if (isValid(board, row + 2, col - 1)) {
281+
if (board[row + 2][col - 1].textContent == "\u265E") {
282+
return false;
283+
}
284+
}
285+
if (isValid(board, row + 1, col - 2)) {
286+
if (board[row + 1][col - 2].textContent == "\u265E") {
287+
return false;
288+
}
289+
}
290+
if (isValid(board, row + 2, col + 1)) {
291+
if (board[row + 2][col + 1].textContent == "\u265E") {
292+
return false;
293+
}
294+
}
295+
if (isValid(board, row + 1, col + 2)) {
296+
if (board[row + 1][col + 2].textContent == "\u265E") {
297+
return false;
298+
}
299+
}
300+
301+
302+
303+
return true;
304+
305+
306+
}

0 commit comments

Comments
 (0)
0