Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commite2ef460

Browse files
committed
Add N-Queens.
1 parentf8222ed commite2ef460

File tree

6 files changed

+281
-5
lines changed

6 files changed

+281
-5
lines changed

‎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-
##Usefullinks
145+
##UsefulInformation
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|
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+
exportdefaultclassQueenPosition{
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+
getleftDiagonal(){
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+
returnthis.rowIndex-this.columnIndex;
23+
}
24+
25+
/**
26+
*@return {number}
27+
*/
28+
getrightDiagonal(){
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+
returnthis.rowIndex+this.columnIndex;
34+
}
35+
36+
toString(){
37+
return`${this.rowIndex},${this.columnIndex}`;
38+
}
39+
}
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)
Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,16 @@
1+
importQueenPositionfrom'../QueenPosition';
2+
3+
describe('QueenPosition',()=>{
4+
it('should store queen position on chessboard',()=>{
5+
constposition1=newQueenPosition(0,0);
6+
constposition2=newQueenPosition(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+
});
Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
importnQueensfrom'../nQueens';
2+
3+
describe('nQueens',()=>{
4+
it('should not hae solution for 3 queens',()=>{
5+
constsolutions=nQueens(3);
6+
expect(solutions.length).toBe(0);
7+
});
8+
9+
it('should solve n-queens problem for 4 queens',()=>{
10+
constsolutions=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+
constsolutions=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+
});
Lines changed: 103 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,103 @@
1+
importQueenPositionfrom'./QueenPosition';
2+
3+
/**
4+
*@param {QueenPosition[]} queensPositions
5+
*@param {number} rowIndex
6+
*@param {number} columnIndex
7+
*@return {boolean}
8+
*/
9+
functionisSafe(queensPositions,rowIndex,columnIndex){
10+
// New position to which the Queen is going to be placed.
11+
constnewQueenPosition=newQueenPosition(rowIndex,columnIndex);
12+
13+
// Check if new queen position conflicts with any other queens.
14+
for(letqueenIndex=0;queenIndex<queensPositions.length;queenIndex+=1){
15+
constcurrentQueenPosition=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+
returnfalse;
34+
}
35+
}
36+
37+
// Looks like we're safe.
38+
returntrue;
39+
}
40+
41+
/**
42+
*@param {QueenPosition[][]} solutions
43+
*@param {QueenPosition[]} previousQueensPositions
44+
*@param {number} queensCount
45+
*@param {number} rowIndex
46+
*@return {boolean}
47+
*/
48+
functionnQueensRecursive(solutions,previousQueensPositions,queensCount,rowIndex){
49+
// Clone positions array.
50+
constqueensPositions=[...previousQueensPositions].map((queenPosition)=>{
51+
return!queenPosition ?queenPosition :newQueenPosition(
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+
returntrue;
64+
}
65+
66+
// Let's try to put queen at row rowIndex into its safe column position.
67+
for(letcolumnIndex=0;columnIndex<queensCount;columnIndex+=1){
68+
if(isSafe(queensPositions,rowIndex,columnIndex)){
69+
// Place current queen to its current position.
70+
queensPositions[rowIndex]=newQueenPosition(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+
returnfalse;
81+
}
82+
83+
84+
/**
85+
*@param {number} queensCount
86+
*@return {QueenPosition[][]}
87+
*/
88+
exportdefaultfunctionnQueens(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+
constqueensPositions=Array(queensCount).fill(null);
95+
96+
/**@var {QueenPosition[][]} solutions */
97+
constsolutions=[];
98+
99+
// Solve problem recursively.
100+
nQueensRecursive(solutions,queensPositions,queensCount,0);
101+
102+
returnsolutions;
103+
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp