Find all the solutions of NQueen

mhihasan · mhihasan · commit 5d6ef93daf8c · 2021-06-06T11:11:08.000+06:00
diff --git a/Backtracking/NQueen.js b/Backtracking/NQueen.js
@@ -1,7 +1,15 @@
+const displayBoard = (board) => {
+  console.log("\n");
+  for (const row of board) {
+    console.log(...row)
+  }
+}
+
 class NQueen {
   constructor (size) {
     this.board = new Array(size).fill('.').map(() => new Array(size).fill('.'))
     this.size = size
+    this.solutions = []
   }
 
   isValid ([row, col]) {
@@ -25,41 +33,43 @@ class NQueen {
     return true
   }
 
+  placeQueen(row, col){
+    this.board[row][col] = 'Q'
+  }
+
+  removeQueen(row, col){
+    this.board[row][col] = '.';
+  }
+
   solve (col = 0) {
-    // function to solve the board
-    if (col >= this.size) { return true }
+    if (col >= this.size) {
+      this.solutions.push(JSON.parse(JSON.stringify(this.board)));
+      return true
+    }
 
     for (let i = 0; i < this.size; i++) {
       if (this.isValid([i, col])) {
-        this.board[i][col] = 'Q'
-
-        if (this.solve(col + 1)) { return true }
-
-        // backtracking
-        this.board[i][col] = '.'
+        this.placeQueen(i, col)
+        this.solve(col + 1)
+        this.removeQueen(i, col)
       }
     }
 
     return false
   }
-
-  printBoard () {
-    // utility function to display the board
-    for (const row of this.board) {
-      console.log(...row)
-    }
-  }
 }
 
 function main () {
-  const board = new NQueen(8)
-
-  board.printBoard()
-  console.log('\n')
-
-  board.solve()
-
-  board.printBoard()
+  const nQueen = new NQueen(4)
+  displayBoard(nQueen.board)
+  nQueen.solve()
+
+  console.log("Number of solutions:", nQueen.solutions.length);
+  nQueen.solutions.forEach((solution)=> {
+    displayBoard(solution)
+  });
 }
 
-main()
+// main()
+
+export { NQueen };
diff --git a/Backtracking/test/NQueen.test.js b/Backtracking/test/NQueen.test.js
@@ -0,0 +1,16 @@
+import {NQueen} from '../NQueen';
+
+describe('NQueen', () => {
+
+  it('returns 2 solutions for 4x4 size board', ()=> {
+    const nQueen = new NQueen(4);
+    const result =  nQueen.solve();
+    expect(nQueen.solutions.length).toEqual(2);
+  })
+
+  it('returns 92 solutions for 8x8 size board', ()=> {
+    const nQueen = new NQueen(8);
+    const result =  nQueen.solve();
+    expect(nQueen.solutions.length).toEqual(92);
+  })
+})
