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

Commit476c0ac

Browse files
committed
Add Knight's tour.
1 parentd2c6d14 commit476c0ac

File tree

4 files changed

+190
-0
lines changed

4 files changed

+190
-0
lines changed

‎README.md

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -80,6 +80,7 @@
8080
***Uncategorized**
8181
*[Tower of Hanoi](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/uncategorized/hanoi-tower)
8282
*[N-Queens Problem](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/uncategorized/n-queens)
83+
*[Knight's Tour](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/uncategorized/knight-tour)
8384
* Union-Find
8485
* Maze
8586
* Sudoku
@@ -114,6 +115,7 @@
114115
***Backtracking**
115116
*[Hamiltonian Cycle](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/graph/hamiltonian-cycle) - Visit every vertex exactly once
116117
*[N-Queens Problem](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/uncategorized/n-queens)
118+
*[Knight's Tour](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/uncategorized/knight-tour)
117119
***Branch & Bound**
118120

119121
##How to use this repository
Lines changed: 33 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,33 @@
1+
#Knight's Tour
2+
3+
A**knight's tour** is a sequence of moves of a knight on a chessboard
4+
such that the knight visits every square only once. If the knight
5+
ends on a square that is one knight's move from the beginning
6+
square (so that it could tour the board again immediately,
7+
following the same path), the tour is**closed**, otherwise it
8+
is**open**.
9+
10+
The**knight's tour problem** is the mathematical problem of
11+
finding a knight's tour. Creating a program to find a knight's
12+
tour is a common problem given to computer science students.
13+
Variations of the knight's tour problem involve chessboards of
14+
different sizes than the usual`8×8`, as well as irregular
15+
(non-rectangular) boards.
16+
17+
The knight's tour problem is an instance of the more
18+
general**Hamiltonian path problem** in graph theory. The problem of finding
19+
a closed knight's tour is similarly an instance of the Hamiltonian
20+
cycle problem.
21+
22+
![Knight's Tour](https://upload.wikimedia.org/wikipedia/commons/d/da/Knight%27s_tour_anim_2.gif)
23+
24+
An open knight's tour of a chessboard.
25+
26+
![Knight's Tour](https://upload.wikimedia.org/wikipedia/commons/c/ca/Knights-Tour-Animation.gif)
27+
28+
An animation of an open knight's tour on a 5 by 5 board.
29+
30+
##References
31+
32+
-[Wikipedia](https://en.wikipedia.org/wiki/Knight%27s_tour)
33+
-[GeeksForGeeks](https://www.geeksforgeeks.org/backtracking-set-1-the-knights-tour-problem/)
Lines changed: 43 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,43 @@
1+
importknightTourfrom'../knightTour';
2+
3+
describe('knightTour',()=>{
4+
it('should not find solution on 3x3 board',()=>{
5+
constmoves=knightTour(3);
6+
7+
expect(moves.length).toBe(0);
8+
});
9+
10+
it('should find one solution to do knight tour on 5x5 board',()=>{
11+
constmoves=knightTour(5);
12+
13+
expect(moves.length).toBe(25);
14+
15+
expect(moves).toEqual([
16+
[0,0],
17+
[1,2],
18+
[2,0],
19+
[0,1],
20+
[1,3],
21+
[3,4],
22+
[2,2],
23+
[4,1],
24+
[3,3],
25+
[1,4],
26+
[0,2],
27+
[1,0],
28+
[3,1],
29+
[4,3],
30+
[2,4],
31+
[0,3],
32+
[1,1],
33+
[3,0],
34+
[4,2],
35+
[2,1],
36+
[4,0],
37+
[3,2],
38+
[4,4],
39+
[2,3],
40+
[0,4],
41+
]);
42+
});
43+
});
Lines changed: 112 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,112 @@
1+
/**
2+
*@param {number[][]} chessboard
3+
*@param {number[]} position
4+
*@return {number[][]}
5+
*/
6+
functiongetPossibleMoves(chessboard,position){
7+
// Generate all knight moves (event those that goes beyond the board).
8+
constpossibleMoves=[
9+
[position[0]-1,position[1]-2],
10+
[position[0]-2,position[1]-1],
11+
[position[0]+1,position[1]-2],
12+
[position[0]+2,position[1]-1],
13+
[position[0]-2,position[1]+1],
14+
[position[0]-1,position[1]+2],
15+
[position[0]+1,position[1]+2],
16+
[position[0]+2,position[1]+1],
17+
];
18+
19+
// Filter out all moves that go beyond the board.
20+
returnpossibleMoves.filter((move)=>{
21+
constboardSize=chessboard.length;
22+
returnmove[0]>=0&&move[1]>=0&&move[0]<boardSize&&move[1]<boardSize;
23+
});
24+
}
25+
26+
/**
27+
*@param {number[][]} chessboard
28+
*@param {number[]} move
29+
*@return {boolean}
30+
*/
31+
functionisMoveAllowed(chessboard,move){
32+
returnchessboard[move[0]][move[1]]!==1;
33+
}
34+
35+
/**
36+
*@param {number[][]} chessboard
37+
*@param {number[][]} moves
38+
*@return {boolean}
39+
*/
40+
functionisBoardCompletelyVisited(chessboard,moves){
41+
consttotalPossibleMovesCount=chessboard.length**2;
42+
constexistingMovesCount=moves.length;
43+
44+
returntotalPossibleMovesCount===existingMovesCount;
45+
}
46+
47+
/**
48+
*@param {number[][]} chessboard
49+
*@param {number[][]} moves
50+
*@return {boolean}
51+
*/
52+
functionknightTourRecursive(chessboard,moves){
53+
constcurrentChessboard=chessboard;
54+
55+
// If board has been completely visited then we've found a solution.
56+
if(isBoardCompletelyVisited(currentChessboard,moves)){
57+
returntrue;
58+
}
59+
60+
// Get next possible knight moves.
61+
constlastMove=moves[moves.length-1];
62+
constpossibleMoves=getPossibleMoves(currentChessboard,lastMove);
63+
64+
// Try to do next possible moves.
65+
for(letmoveIndex=0;moveIndex<possibleMoves.length;moveIndex+=1){
66+
constcurrentMove=possibleMoves[moveIndex];
67+
68+
// Check if current move is allowed. We aren't allowed to go to
69+
// the same cells twice.
70+
if(isMoveAllowed(currentChessboard,currentMove)){
71+
// Actually do the move.
72+
moves.push(currentMove);
73+
currentChessboard[currentMove[0]][currentMove[1]]=1;
74+
75+
// If further moves starting from current are successful then
76+
// return true meaning the solution is found.
77+
if(knightTourRecursive(currentChessboard,moves)){
78+
returntrue;
79+
}
80+
81+
// BACKTRACKING.
82+
// If current move was unsuccessful then step back and try to do another move.
83+
moves.pop();
84+
currentChessboard[currentMove[0]][currentMove[1]]=0;
85+
}
86+
}
87+
88+
// Return false if we haven't found solution.
89+
returnfalse;
90+
}
91+
92+
/**
93+
*@param {number} chessboardSize
94+
*@return {number[][]}
95+
*/
96+
exportdefaultfunctionknightTour(chessboardSize){
97+
// Init chessboard.
98+
constchessboard=Array(chessboardSize).fill(null).map(()=>Array(chessboardSize).fill(0));
99+
100+
// Init moves array.
101+
constmoves=[];
102+
103+
// Do first move and place the knight to the 0x0 cell.
104+
constfirstMove=[0,0];
105+
moves.push(firstMove);
106+
chessboard[firstMove[0]][firstMove[0]]=1;
107+
108+
// Recursively try to do the next move.
109+
constsolutionWasFound=knightTourRecursive(chessboard,moves);
110+
111+
returnsolutionWasFound ?moves :[];
112+
}

0 commit comments

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