FazBrowse GitHub Viewer | Trending |
URL:
| Home
Tools: [Download Repo ZIP]   [Original HTTPS Page]

Add N-Queens. · stormnode/javascript-algorithms@e2ef460 · GitHub

/ javascript-algorithms Public
forked from trekhleb/javascript-algorithms

Commit e2ef460

Browse files
trekhleb
committed
Add N-Queens.
1 parent f8222ed commit e2ef460

6 files changed

Lines changed: 281 additions & 5 deletions

File tree

‎README.md‎

Lines changed: 12 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -78,6 +78,7 @@
7878
* [Strongly Connected Components](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/graph/strongly-connected-components) - Kosaraju's algorithm
7979
* **Uncategorized**
8080
* [Tower of Hanoi](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/uncategorized/hanoi-tower)
81+
* [N-Queens Problem](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/uncategorized/n-queens)
8182
* Union-Find
8283
* Maze
8384
* Sudoku
@@ -110,9 +111,15 @@
110111
* [Maximum Subarray](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sets/maximum-subarray)
111112
* [Bellman-Ford Algorithm](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/graph/bellman-ford) - finding shortest path to all graph vertices
112113
* **Backtracking**
114+
* [N-Queens Problem](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/uncategorized/n-queens)
113115
* **Branch & Bound**
114116

115-
## Running Tests
117+
## How to use this repository
118+
119+
**Install all dependencies**
120+
```
121+
npm i
122+
```
116123

117124
**Run all tests**
118125
```
@@ -135,11 +142,11 @@ Then just simply run the following command to test if your playground code works
135142
npm test -- -t 'playground'
136143
```
137144

138-
## Useful links
145+
## Useful Information
139146

140-
[▶ Data Structures and Algorithms on YouTube](https://www.youtube.com/playlist?list=PLLXdhg_r2hKA7DPDsunoDZ-Z769jWn4R8)
147+
### References
141148

142-
## Useful Information
149+
[▶ Data Structures and Algorithms on YouTube](https://www.youtube.com/playlist?list=PLLXdhg_r2hKA7DPDsunoDZ-Z769jWn4R8)
143150

144151
### Big O Notation
145152

@@ -185,4 +192,4 @@ Below is the list of some of the most used Big O notations and their performance
185192
| **Heap sort** | n log(n) | n log(n) | n log(n) | 1 | No |
186193
| **Merge sort** | n log(n) | n log(n) | n log(n) | n | Yes |
187194
| **Quick sort** | n log(n) | n log(n) | n^2 | log(n) | No |
188-
| **Shell sort** | n log(n) | depends on gap sequence | n (log(n))^2 | 1 | No |
195+
| **Shell sort** | n log(n) | depends on gap sequence | n (log(n))^2 | 1 | No |

‎src/algorithms/uncategorized/n-queens/QueenPosition.js‎

Lines changed: 39 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,39 @@
1+
/**
2+
* Class that represents queen position on the chessboard.
3+
*/
4+
export default class QueenPosition {
5+
/**
6+
* @param {number} rowIndex
7+
* @param {number} columnIndex
8+
*/
9+
constructor(rowIndex, columnIndex) {
10+
this.rowIndex = rowIndex;
11+
this.columnIndex = columnIndex;
12+
}
13+
14+
/**
15+
* @return {number}
16+
*/
17+
get leftDiagonal() {
18+
// Each position on the same left (\) diagonal has the same difference of
19+
// rowIndex and columnIndex. This fact may be used to quickly check if two
20+
// positions (queens) are on the same left diagonal.
21+
// @see https://youtu.be/xouin83ebxE?t=1m59s
22+
return this.rowIndex - this.columnIndex;
23+
}
24+
25+
/**
26+
* @return {number}
27+
*/
28+
get rightDiagonal() {
29+
// Each position on the same right diagonal (/) has the same
30+
// sum of rowIndex and columnIndex. This fact may be used to quickly
31+
// check if two positions (queens) are on the same right diagonal.
32+
// @see https://youtu.be/xouin83ebxE?t=1m59s
33+
return this.rowIndex + this.columnIndex;
34+
}
35+
36+
toString() {
37+
return `${this.rowIndex},${this.columnIndex}`;
38+
}
39+
}

‎src/algorithms/uncategorized/n-queens/README.md‎

Lines changed: 73 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,73 @@
1+
# N-Queens Problem
2+
3+
The **eight queens puzzle** is the problem of placing eight chess queens
4+
on an `8×8` chessboard so that no two queens threaten each other.
5+
Thus, a solution requires that no two queens share the same row,
6+
column, or diagonal. The eight queens puzzle is an example of the
7+
more general *n queens problem* of placing n non-attacking queens
8+
on an `n×n` chessboard, for which solutions exist for all natural
9+
numbers `n` with the exception of `n=2` and `n=3`.
10+
11+
For example, following is a solution for 4 Queen problem.
12+
13+
![N Queens](https://cdncontribute.geeksforgeeks.org/wp-content/uploads/N_Queen_Problem.jpg)
14+
15+
The expected output is a binary matrix which has 1s for the blocks
16+
where queens are placed. For example following is the output matrix
17+
for above 4 queen solution.
18+
19+
```
20+
{ 0, 1, 0, 0}
21+
{ 0, 0, 0, 1}
22+
{ 1, 0, 0, 0}
23+
{ 0, 0, 1, 0}
24+
```
25+
26+
## Naive Algorithm
27+
28+
Generate all possible configurations of queens on board and print a
29+
configuration that satisfies the given constraints.
30+
31+
```
32+
while there are untried conflagrations
33+
{
34+
generate the next configuration
35+
if queens don't attack in this configuration then
36+
{
37+
print this configuration;
38+
}
39+
}
40+
```
41+
42+
## Backtracking Algorithm
43+
44+
The idea is to place queens one by one in different columns,
45+
starting from the leftmost column. When we place a queen in a
46+
column, we check for clashes with already placed queens. In
47+
the current column, if we find a row for which there is no
48+
clash, we mark this row and column as part of the solution.
49+
If we do not find such a row due to clashes then we backtrack
50+
and return false.
51+
52+
```
53+
1) Start in the leftmost column
54+
2) If all queens are placed
55+
return true
56+
3) Try all rows in the current column. Do following for every tried row.
57+
a) If the queen can be placed safely in this row then mark this [row,
58+
column] as part of the solution and recursively check if placing
59+
queen here leads to a solution.
60+
b) If placing queen in [row, column] leads to a solution then return
61+
true.
62+
c) If placing queen doesn't lead to a solution then umark this [row,
63+
column] (Backtrack) and go to step (a) to try other rows.
64+
3) If all rows have been tried and nothing worked, return false to trigger
65+
backtracking.
66+
```
67+
68+
## References
69+
70+
- [Wikipedia](https://en.wikipedia.org/wiki/Eight_queens_puzzle)
71+
- [GeeksForGeeks](https://www.geeksforgeeks.org/backtracking-set-3-n-queen-problem/)
72+
- [On YouTube by Abdul Bari](https://www.youtube.com/watch?v=xFv_Hl4B83A)
73+
- [On YouTube by Tushar Roy](https://www.youtube.com/watch?v=xouin83ebxE)

‎src/algorithms/uncategorized/n-queens/__test__/QueensPosition.test.js‎

Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,16 @@
1+
import QueenPosition from '../QueenPosition';
2+
3+
describe('QueenPosition', () => {
4+
it('should store queen position on chessboard', () => {
5+
const position1 = new QueenPosition(0, 0);
6+
const position2 = new QueenPosition(2, 1);
7+
8+
expect(position2.columnIndex).toBe(1);
9+
expect(position2.rowIndex).toBe(2);
10+
expect(position1.leftDiagonal).toBe(0);
11+
expect(position1.rightDiagonal).toBe(0);
12+
expect(position2.leftDiagonal).toBe(1);
13+
expect(position2.rightDiagonal).toBe(3);
14+
expect(position2.toString()).toBe('2,1');
15+
});
16+
});

‎src/algorithms/uncategorized/n-queens/__test__/nQueens.test.js‎

Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
import nQueens from '../nQueens';
2+
3+
describe('nQueens', () => {
4+
it('should not hae solution for 3 queens', () => {
5+
const solutions = nQueens(3);
6+
expect(solutions.length).toBe(0);
7+
});
8+
9+
it('should solve n-queens problem for 4 queens', () => {
10+
const solutions = nQueens(4);
11+
expect(solutions.length).toBe(2);
12+
13+
// First solution.
14+
expect(solutions[0][0].toString()).toBe('0,1');
15+
expect(solutions[0][1].toString()).toBe('1,3');
16+
expect(solutions[0][2].toString()).toBe('2,0');
17+
expect(solutions[0][3].toString()).toBe('3,2');
18+
19+
// Second solution (mirrored).
20+
expect(solutions[1][0].toString()).toBe('0,2');
21+
expect(solutions[1][1].toString()).toBe('1,0');
22+
expect(solutions[1][2].toString()).toBe('2,3');
23+
expect(solutions[1][3].toString()).toBe('3,1');
24+
});
25+
26+
it('should solve n-queens problem for 6 queens', () => {
27+
const solutions = nQueens(6);
28+
expect(solutions.length).toBe(4);
29+
30+
// First solution.
31+
expect(solutions[0][0].toString()).toBe('0,1');
32+
expect(solutions[0][1].toString()).toBe('1,3');
33+
expect(solutions[0][2].toString()).toBe('2,5');
34+
expect(solutions[0][3].toString()).toBe('3,0');
35+
expect(solutions[0][4].toString()).toBe('4,2');
36+
expect(solutions[0][5].toString()).toBe('5,4');
37+
});
38+
});

‎src/algorithms/uncategorized/n-queens/nQueens.js‎

Lines changed: 103 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,103 @@
1+
import QueenPosition from './QueenPosition';
2+
3+
/**
4+
* @param {QueenPosition[]} queensPositions
5+
* @param {number} rowIndex
6+
* @param {number} columnIndex
7+
* @return {boolean}
8+
*/
9+
function isSafe(queensPositions, rowIndex, columnIndex) {
10+
// New position to which the Queen is going to be placed.
11+
const newQueenPosition = new QueenPosition(rowIndex, columnIndex);
12+
13+
// Check if new queen position conflicts with any other queens.
14+
for (let queenIndex = 0; queenIndex < queensPositions.length; queenIndex += 1) {
15+
const currentQueenPosition = queensPositions[queenIndex];
16+
17+
if (
18+
// Check if queen has been already placed.
19+
currentQueenPosition &&
20+
(
21+
// Check if there are any queen on the same column.
22+
newQueenPosition.columnIndex === currentQueenPosition.columnIndex ||
23+
// Check if there are any queen on the same row.
24+
newQueenPosition.rowIndex === currentQueenPosition.rowIndex ||
25+
// Check if there are any queen on the same left diagonal.
26+
newQueenPosition.leftDiagonal === currentQueenPosition.leftDiagonal ||
27+
// Check if there are any queen on the same right diagonal.
28+
newQueenPosition.rightDiagonal === currentQueenPosition.rightDiagonal
29+
)
30+
) {
31+
// Can't place queen into current position since there are other queens that
32+
// are threatening it.
33+
return false;
34+
}
35+
}
36+
37+
// Looks like we're safe.
38+
return true;
39+
}
40+
41+
/**
42+
* @param {QueenPosition[][]} solutions
43+
* @param {QueenPosition[]} previousQueensPositions
44+
* @param {number} queensCount
45+
* @param {number} rowIndex
46+
* @return {boolean}
47+
*/
48+
function nQueensRecursive(solutions, previousQueensPositions, queensCount, rowIndex) {
49+
// Clone positions array.
50+
const queensPositions = [...previousQueensPositions].map((queenPosition) => {
51+
return !queenPosition ? queenPosition : new QueenPosition(
52+
queenPosition.rowIndex,
53+
queenPosition.columnIndex,
54+
);
55+
});
56+
57+
if (rowIndex === queensCount) {
58+
// We've successfully reached the end of the board.
59+
// Store solution to the list of solutions.
60+
solutions.push(queensPositions);
61+
62+
// Solution found.
63+
return true;
64+
}
65+
66+
// Let's try to put queen at row rowIndex into its safe column position.
67+
for (let columnIndex = 0; columnIndex < queensCount; columnIndex += 1) {
68+
if (isSafe(queensPositions, rowIndex, columnIndex)) {
69+
// Place current queen to its current position.
70+
queensPositions[rowIndex] = new QueenPosition(rowIndex, columnIndex);
71+
72+
// Try to place all other queens as well.
73+
nQueensRecursive(solutions, queensPositions, queensCount, rowIndex + 1);
74+
75+
// Remove the queen from the row to avoid isSafe() returning false.
76+
queensPositions[rowIndex] = null;
77+
}
78+
}
79+
80+
return false;
81+
}
82+
83+
84+
/**
85+
* @param {number} queensCount
86+
* @return {QueenPosition[][]}
87+
*/
88+
export default function nQueens(queensCount) {
89+
// Init NxN chessboard with zeros.
90+
// const chessboard = Array(queensCount).fill(null).map(() => Array(queensCount).fill(0));
91+
92+
// This array will hold positions or coordinates of each of
93+
// N queens in form of [rowIndex, columnIndex].
94+
const queensPositions = Array(queensCount).fill(null);
95+
96+
/** @var {QueenPosition[][]} solutions */
97+
const solutions = [];
98+
99+
// Solve problem recursively.
100+
nQueensRecursive(solutions, queensPositions, queensCount, 0);
101+
102+
return solutions;
103+
}

0 commit comments

Comments
 (0)
Back | FazBrowse Home | New Git URL