JavaScript/Backtracking/KnightTour.js at master · Guduly/JavaScript · 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
// Wikipedia: https://en.wikipedia.org/wiki/Knight%27s_tour

classOpenKnightTour{
constructor(size){
this.board=newArray(size).fill(0).map(()=>newArray(size).fill(0))
this.size=size
}

getMoves([i,j]){
// helper function to get the valid moves of the knight from the current position
constmoves=[
[i+2,j-1],
[i+2,j+1],
[i-2,j-1],
[i-2,j+1],
[i+1,j-2],
[i+1,j+2],
[i-1,j-2],
[i-1,j+2]
]

returnmoves.filter(([y,x])=>y>=0&&y<this.size&&x>=0&&x<this.size)
}

isComplete(){
// helper function to check if the board is complete
return!this.board.map(row=>row.includes(0)).includes(true)
}

solve(){
// function to find the solution for the given board
for(leti=0;i<this.size;i++){
for(letj=0;j<this.size;j++){
if(this.solveHelper([i,j],0))returntrue
}
}
returnfalse
}

solveHelper([i,j],curr){
// helper function for the main computation
if(this.isComplete())returntrue

for(const[y,x]ofthis.getMoves([i,j])){
if(this.board[y][x]===0){
this.board[y][x]=curr+1
if(this.solveHelper([y,x],curr+1))returntrue
// backtracking
this.board[y][x]=0
}
}
returnfalse
}

printBoard(output=value=>console.log(value)){
// utility function to display the board
for(constrowofthis.board){
letstring=''
for(constelemofrow){
string+=elem+'\t'
}
output(string)
}
}
}

export{OpenKnightTour}
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
// Wikipedia: https://en.wikipedia.org/wiki/Knight%27s_tour

classOpenKnightTour{
constructor(size){
this.board=newArray(size).fill(0).map(()=>newArray(size).fill(0))
this.size=size
}

getMoves([i,j]){
// helper function to get the valid moves of the knight from the current position
constmoves=[
[i+2,j-1],
[i+2,j+1],
[i-2,j-1],
[i-2,j+1],
[i+1,j-2],
[i+1,j+2],
[i-1,j-2],
[i-1,j+2]
]

returnmoves.filter(([y,x])=>y>=0&&y<this.size&&x>=0&&x<this.size)
}

isComplete(){
// helper function to check if the board is complete
return!this.board.map(row=>row.includes(0)).includes(true)
}

solve(){
// function to find the solution for the given board
for(leti=0;i<this.size;i++){
for(letj=0;j<this.size;j++){
if(this.solveHelper([i,j],0))returntrue
}
}
returnfalse
}

solveHelper([i,j],curr){
// helper function for the main computation
if(this.isComplete())returntrue

for(const[y,x]ofthis.getMoves([i,j])){
if(this.board[y][x]===0){
this.board[y][x]=curr+1
if(this.solveHelper([y,x],curr+1))returntrue
// backtracking
this.board[y][x]=0
}
}
returnfalse
}

printBoard(output=value=>console.log(value)){
// utility function to display the board
for(constrowofthis.board){
letstring=''
for(constelemofrow){
string+=elem+'\t'
}
output(string)
}
}
}

export{OpenKnightTour}
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
// Wikipedia: https://en.wikipedia.org/wiki/Knight%27s_tour

classOpenKnightTour{
constructor(size){
this.board=newArray(size).fill(0).map(()=>newArray(size).fill(0))
this.size=size
}

getMoves([i,j]){
// helper function to get the valid moves of the knight from the current position
constmoves=[
[i+2,j-1],
[i+2,j+1],
[i-2,j-1],
[i-2,j+1],
[i+1,j-2],
[i+1,j+2],
[i-1,j-2],
[i-1,j+2]
]

returnmoves.filter(([y,x])=>y>=0&&y<this.size&&x>=0&&x<this.size)
}

isComplete(){
// helper function to check if the board is complete
return!this.board.map(row=>row.includes(0)).includes(true)
}

solve(){
// function to find the solution for the given board
for(leti=0;i<this.size;i++){
for(letj=0;j<this.size;j++){
if(this.solveHelper([i,j],0))returntrue
}
}
returnfalse
}

solveHelper([i,j],curr){
// helper function for the main computation
if(this.isComplete())returntrue

for(const[y,x]ofthis.getMoves([i,j])){
if(this.board[y][x]===0){
this.board[y][x]=curr+1
if(this.solveHelper([y,x],curr+1))returntrue
// backtracking
this.board[y][x]=0
}
}
returnfalse
}

printBoard(output=value=>console.log(value)){
// utility function to display the board
for(constrowofthis.board){
letstring=''
for(constelemofrow){
string+=elem+'\t'
}
output(string)
}
}
}

export{OpenKnightTour}
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
// Wikipedia: https://en.wikipedia.org/wiki/Knight%27s_tour

classOpenKnightTour{
constructor(size){
this.board=newArray(size).fill(0).map(()=>newArray(size).fill(0))
this.size=size
}

getMoves([i,j]){
// helper function to get the valid moves of the knight from the current position
constmoves=[
[i+2,j-1],
[i+2,j+1],
[i-2,j-1],
[i-2,j+1],
[i+1,j-2],
[i+1,j+2],
[i-1,j-2],
[i-1,j+2]
]

returnmoves.filter(([y,x])=>y>=0&&y<this.size&&x>=0&&x<this.size)
}

isComplete(){
// helper function to check if the board is complete
return!this.board.map(row=>row.includes(0)).includes(true)
}

solve(){
// function to find the solution for the given board
for(leti=0;i<this.size;i++){
for(letj=0;j<this.size;j++){
if(this.solveHelper([i,j],0))returntrue
}
}
returnfalse
}

solveHelper([i,j],curr){
// helper function for the main computation
if(this.isComplete())returntrue

for(const[y,x]ofthis.getMoves([i,j])){
if(this.board[y][x]===0){
this.board[y][x]=curr+1
if(this.solveHelper([y,x],curr+1))returntrue
// backtracking
this.board[y][x]=0
}
}
returnfalse
}

printBoard(output=value=>console.log(value)){
// utility function to display the board
for(constrowofthis.board){
letstring=''
for(constelemofrow){
string+=elem+'\t'
}
output(string)
}
}
}

export{OpenKnightTour}
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
// Wikipedia: https://en.wikipedia.org/wiki/Knight%27s_tour

classOpenKnightTour{
constructor(size){
this.board=newArray(size).fill(0).map(()=>newArray(size).fill(0))
this.size=size
}

getMoves([i,j]){
// helper function to get the valid moves of the knight from the current position
constmoves=[
[i+2,j-1],
[i+2,j+1],
[i-2,j-1],
[i-2,j+1],
[i+1,j-2],
[i+1,j+2],
[i-1,j-2],
[i-1,j+2]
]

returnmoves.filter(([y,x])=>y>=0&&y<this.size&&x>=0&&x<this.size)
}

isComplete(){
// helper function to check if the board is complete
return!this.board.map(row=>row.includes(0)).includes(true)
}

solve(){
// function to find the solution for the given board
for(leti=0;i<this.size;i++){
for(letj=0;j<this.size;j++){
if(this.solveHelper([i,j],0))returntrue
}
}
returnfalse
}

solveHelper([i,j],curr){
// helper function for the main computation
if(this.isComplete())returntrue

for(const[y,x]ofthis.getMoves([i,j])){
if(this.board[y][x]===0){
this.board[y][x]=curr+1
if(this.solveHelper([y,x],curr+1))returntrue
// backtracking
this.board[y][x]=0
}
}
returnfalse
}

printBoard(output=value=>console.log(value)){
// utility function to display the board
for(constrowofthis.board){
letstring=''
for(constelemofrow){
string+=elem+'\t'
}
output(string)
}
}
}

export{OpenKnightTour}
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
// Wikipedia: https://en.wikipedia.org/wiki/Knight%27s_tour

classOpenKnightTour{
constructor(size){
this.board=newArray(size).fill(0).map(()=>newArray(size).fill(0))
this.size=size
}

getMoves([i,j]){
// helper function to get the valid moves of the knight from the current position
constmoves=[
[i+2,j-1],
[i+2,j+1],
[i-2,j-1],
[i-2,j+1],
[i+1,j-2],
[i+1,j+2],
[i-1,j-2],
[i-1,j+2]
]

returnmoves.filter(([y,x])=>y>=0&&y<this.size&&x>=0&&x<this.size)
}

isComplete(){
// helper function to check if the board is complete
return!this.board.map(row=>row.includes(0)).includes(true)
}

solve(){
// function to find the solution for the given board
for(leti=0;i<this.size;i++){
for(letj=0;j<this.size;j++){
if(this.solveHelper([i,j],0))returntrue
}
}
returnfalse
}

solveHelper([i,j],curr){
// helper function for the main computation
if(this.isComplete())returntrue

for(const[y,x]ofthis.getMoves([i,j])){
if(this.board[y][x]===0){
this.board[y][x]=curr+1
if(this.solveHelper([y,x],curr+1))returntrue
// backtracking
this.board[y][x]=0
}
}
returnfalse
}

printBoard(output=value=>console.log(value)){
// utility function to display the board
for(constrowofthis.board){
letstring=''
for(constelemofrow){
string+=elem+'\t'
}
output(string)
}
}
}

export{OpenKnightTour}
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
// Wikipedia: https://en.wikipedia.org/wiki/Knight%27s_tour

classOpenKnightTour{
constructor(size){
this.board=newArray(size).fill(0).map(()=>newArray(size).fill(0))
this.size=size
}

getMoves([i,j]){
// helper function to get the valid moves of the knight from the current position
constmoves=[
[i+2,j-1],
[i+2,j+1],
[i-2,j-1],
[i-2,j+1],
[i+1,j-2],
[i+1,j+2],
[i-1,j-2],
[i-1,j+2]
]

returnmoves.filter(([y,x])=>y>=0&&y<this.size&&x>=0&&x<this.size)
}

isComplete(){
// helper function to check if the board is complete
return!this.board.map(row=>row.includes(0)).includes(true)
}

solve(){
// function to find the solution for the given board
for(leti=0;i<this.size;i++){
for(letj=0;j<this.size;j++){
if(this.solveHelper([i,j],0))returntrue
}
}
returnfalse
}

solveHelper([i,j],curr){
// helper function for the main computation
if(this.isComplete())returntrue

for(const[y,x]ofthis.getMoves([i,j])){
if(this.board[y][x]===0){
this.board[y][x]=curr+1
if(this.solveHelper([y,x],curr+1))returntrue
// backtracking
this.board[y][x]=0
}
}
returnfalse
}

printBoard(output=value=>console.log(value)){
// utility function to display the board
for(constrowofthis.board){
letstring=''
for(constelemofrow){
string+=elem+'\t'
}
output(string)
}
}
}

export{OpenKnightTour}
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
// Wikipedia: https://en.wikipedia.org/wiki/Knight%27s_tour

classOpenKnightTour{
constructor(size){
this.board=newArray(size).fill(0).map(()=>newArray(size).fill(0))
this.size=size
}

getMoves([i,j]){
// helper function to get the valid moves of the knight from the current position
constmoves=[
[i+2,j-1],
[i+2,j+1],
[i-2,j-1],
[i-2,j+1],
[i+1,j-2],
[i+1,j+2],
[i-1,j-2],
[i-1,j+2]
]

returnmoves.filter(([y,x])=>y>=0&&y<this.size&&x>=0&&x<this.size)
}

isComplete(){
// helper function to check if the board is complete
return!this.board.map(row=>row.includes(0)).includes(true)
}

solve(){
// function to find the solution for the given board
for(leti=0;i<this.size;i++){
for(letj=0;j<this.size;j++){
if(this.solveHelper([i,j],0))returntrue
}
}
returnfalse
}

solveHelper([i,j],curr){
// helper function for the main computation
if(this.isComplete())returntrue

for(const[y,x]ofthis.getMoves([i,j])){
if(this.board[y][x]===0){
this.board[y][x]=curr+1
if(this.solveHelper([y,x],curr+1))returntrue
// backtracking
this.board[y][x]=0
}
}
returnfalse
}

printBoard(output=value=>console.log(value)){
// utility function to display the board
for(constrowofthis.board){
letstring=''
for(constelemofrow){
string+=elem+'\t'
}
output(string)
}
}
}

export{OpenKnightTour}