Algo-Visualizer/src/algorithms/Recursion/NQueens.js at d81801fd2f5d21d4ee11392c16e2754050564e5d · indrasuthar07/Algo-Visualizer · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
export function nQueensVisualizerSteps(N) {
  const steps = [];
  const board = Array.from({ length: N }, () => Array(N).fill(0));
  const solutions = [];
  const cols = Array(N).fill(false);
  const diag1 = Array(2 * N).fill(false);
  const diag2 = Array(2 * N).fill(false);
  const stack = [];

  function cloneBoard(b) {
    return b.map(r => [...r]);
  }

  function solve(row) {
    if (row === N) {
      steps.push({
        type: "solution",
        board: cloneBoard(board),
        message: `Found valid solution!`,
        stack: [...stack],
        safe: true,
        solutionCount: solutions.length + 1
      });
      solutions.push(cloneBoard(board));
      return;
    }

    for (let col = 0; col < N; col++) {
      steps.push({
        type: "try",
        board: cloneBoard(board),
        row,
        col,
        message: `Trying to place Queen at (${row}, ${col})`,
        safe: null,
        stack: [...stack]
      });

      if (!cols[col] && !diag1[row - col + N] && !diag2[row + col]) {
        steps.push({
          type: "check",
          board: cloneBoard(board),
          row,
          col,
          safe: true,
          message: `Position (${row}, ${col}) is safe.`,
          stack: [...stack]
        });

        board[row][col] = 1;
        cols[col] = diag1[row - col + N] = diag2[row + col] = true;
        stack.push({ row, col });

        steps.push({
          type: "place",
          board: cloneBoard(board),
          row,
          col,
          message: `Placed Queen at (${row}, ${col}). Moving to next row.`,
          safe: true,
          stack: [...stack]
        });

        solve(row + 1);

        board[row][col] = 0;
        cols[col] = diag1[row - col + N] = diag2[row + col] = false;
        stack.pop();

        steps.push({
          type: "remove",
          board: cloneBoard(board),
          row,
          col,
          message: `Backtracking: Removed Queen from (${row}, ${col}).`,
          safe: false,
          stack: [...stack]
        });
      } else {
        steps.push({
          type: "check",
          board: cloneBoard(board),
          row,
          col,
          safe: false,
          message: `Conflict at (${row}, ${col}). Cannot place Queen here.`,
          stack: [...stack]
        });
      }
    }
  }

  solve(0);

  return {
    steps,
    solutions,
    solutionCount: solutions.length,
    solvable: solutions.length > 0,
  };
}