# Jumpsaround

## Solving The Knight's Tour Problem in 7+ programming languages

Years ago I discussed with a friend how to solve The Knight's Tour Problem with a program. Over time I started to implement a backtracking logic to solve the problem in different programming languages. In the following text I describe my adventures and insights during the development in different programming languages.

The Knight's Tour Problem searches for solutions in which a knight moves over a chessboard in a way that it jumps on every field exactly once. If the Knight can reach its starting point, when it moves to the last empty square, this is called a closed solution. (German: geschlossene Touren)

For more information on the Knight's tour problem see Wikipedia (German: Springerproblem)

Progressing in the development, I focused on finding all closed solutions only. The programs also count all solutions, but this is not an exhaustive list, because the algorithm I used only starts in the upper left corner.

Since I don't want to wait too long for the calculation of the solutions for a regular 8 x 8 chess board during development, I use a board of size 6 x 5 by default. In this case there are 4542 solutions and 16 roundtripps.

Because the Knight kind of jumps over the board, I call the project and programs jumpsaround or short jumper.

To compute the solutions I use the backtracking algorithm. No algorithmic optimizations are used.

I did this just for fun, to compare programming languages in syntax, design and performance, with a relatively simple, but non-trivial algorithm. The following code is ordered in the sequence I developed it.

## Pseudo Code

A high level description of the logic I will use in the following lineup:

• Function "Jump on field" with a new position
• Store the current position on the board
• Check if all fields have been jumped to,
• If YES
• Add 1 to solutions
• Check if Knight can reach its start position, if YES
• Add 1 to roundtripp
• print the board
• If NO - not all fields have been jumped to
• Iterate over all 8 possible moves of the knight; for each move:
• Call function "Jump on field" with the new position (recursion)
• Remove the position from the board
• End the function "Jump on field"

In the following you find code excerpts from parts which are discussed. Additionally there are always links to view and download the sources.

At the end is an overview of all the performance results.

## C

C was the third programming language I learned after BASIC on home computers and Turbo Pascal 3.0 under CPM.

The C version ist the first implementation I made. I used the GCC compiler.

Let's talk about the implementation.

There is a Robustness principle also known as "Postel's law" for designing interfaces. Jon Postel was and RFC Editor, Protocol Guru. As functions are has an interface you can - or should - also apply this rule here.

"Be liberal in what you accept and
conservative in what you send"

In other words, when you call a function make sure all parameters are within the expected value range. When you write a function, make sure that the function can handle unexpected values.

Implementing both rules in such a simple program would be overkill. I have weighted the first part of the rule a bit more. So in the first version of the implementation, the `jumpto` function validates if it was called with valid values for the board position.

Source of jumpsaround_0.c: view, download

```   40 void jumpto(signed char x, signed char y, int iter, char arity) {
41
42     // check if position is on the board
43     if ( x<0 || x>(SIZEX-1) || y<0 || y>(SIZEY-1) ) return;
44
45     // check if field on board is still empty
46     if ( board[x][y] != 0 ) return;
47
48     // ok - store position
49     board[x][y] = iter;
50     iters[iter] = arity + '0';
51
52     // finished?
53     if (iter >= SIZEX*SIZEY ) {
54
55         // check for jumper roundtrips
56         signed int round = 0;
57         for (int i = 0; i < 8; i++) {
58             signed char nx = x + jump[i][0];
59             signed char ny = y + jump[i][1];
60             // check if position is on the board
61             if ( nx<0 || nx>(SIZEX-1) || ny<0 || ny>(SIZEY-1) ) continue;
62             // detect roundtrip
63             if ( board[nx][ny] == 1 ) { round = 1; roundtrips++; break; } // True
64         }
65         solutions++;
66         printboard(round);
67
68         // end this iteration
69         board[x][y] = 0;
70         iters[iter] = 0;
71         return;
72     }
73
74     // try next jump
75     for (int i = 0; i < 8; i++) {
76         signed char nx = x + jump[i][0];
77         signed char ny = y + jump[i][1];
78         jumpto(nx, ny, iter + 1, i);
79     }
80
81     // this iteration is done
82     board[x][y] = 0;
83     iters[iter] = 0;
84
85 }

```

This obviously resulted in many function calls to board positions which are already used or are off the board. To check the impact of unnecessary calls I changed the implementation to validate the destination coordinates before the function is called. So here I followed the second part of the Robustness principle. (Remember, you should do both!)

"Be liberal in what you accept and
conservative in what you send"

This second version reduced the time needed by about 30%.

I know that it takes time to push parameters onto the stack and reserve memory for the called function, but this is more then I expected.

Source of jumpsaround_1.c: view, download

```   42 void jumpto(signed char x, signed char y, int iter, char arity) {
43
44     // ok - store position
45     board[x][y] = iter;
46     iters[iter] = arity + '0';
47
48     // finished?
49     if (iter >= SIZEX*SIZEY ) {
50
51         // check for jumper roundtrips
52         signed int round = 0;
53         for (int i = 0; i < 8; i++) {
54             signed char nx = x + jump[i][0];
55             signed char ny = y + jump[i][1];
56             // check if position is on the board
57             if ( nx<0 || nx>(SIZEX-1) || ny<0 || ny>(SIZEY-1) ) continue;
58             // detect roundtrip
59             if ( board[nx][ny] == 1 ) { round = 1; roundtrips++; break; } // True
60         }
61
62         solutions++;
63         printboard(round);
64
65         board[x][y] = 0;
66         iters[iter] = 0;
67         return;
68     }
69
70     // try next jump
71     for (int i = 0; i < 8; i++) {
72
73         // new position
74         signed char nx = x + jump[i][0];
75         signed char ny = y + jump[i][1];
76
77         // check if new position is on the board
78         if ( nx<0 || nx>(SIZEX-1) || ny<0 || ny>(SIZEY-1) ) continue;
79
80         //  check if new field position is still empty
81         if ( board[nx][ny] != 0 ) continue;
82
83         jumpto(nx, ny, iter + 1, i);
84     }
85
86     // this iteration is done
87     board[x][y] = 0;
88     iters[iter] = 0;
89
90 }

```

This C program became the basic version for the following programs.

In my opinion C is still a pragmatic and consistent programming language, but it lacks some modern features and secure memory access and easy multithreading. C would not be my first choice for new programs, but is still good if it is used in existing projects.

### Gcc Compiler Optimizations

With creating the initial version of this website I tried the gcc compiler option `-O2`. Later I checked all "regular" `-On` compiler options in an separate test. (There are options to activate each optimization individually.) Here are the results.

Execution time in seconds:

Optimizer Flagnone-O1-O2-O3
jumpsaround_0.c7.64.13.83.8
jumpsaround_1.c5.52.43.21.8

As expected usually each higher optimization level speeds up the program execution time. But looking at version 1 and the optimizer flags `-O1` and `-O2` you can see that the higher optimization level made the code slower. That's strange.

But note that the results cannot be generalized. The values are only valid for this example program. Other logics may result in different optimizer results.

Version 1 is always significant faster than version 0. So I deduct, that the compiler does not reorder code like I did manually.

I also took a look at the times needed to compile jumpsaround_x.c with the different optimizer flags.

Compile time in seconds:

Optimizer Flagnone-O1-O2-O3
jumpsaround_0.c0.050.070.080.10
jumpsaround_1.c0.060.070.090.11

As documented each higher optimization level needs more compile time. But the program is too small to make significant statements about the times.

Here you can find more about the Gcc optimizer options.

## Go

GO is a relatively new, modern, compiled language. It is straightforward in structure and easy to learn. The compiler is very fast and the standard library is extensive.

I use Go for a small personal project: Another static web-site generator.

In the first version I simply used "type inference" to let the compiler determine the datatype, or used `int` if needed. This program version is already faster than the C version.

Source of jumpsaround_1.go: view, download

```   18 var board boardt
19 var jump = [8][2]int{{-1, -2}, {1, -2}, {-2, -1}, {2, -1}, {-2, 1}, {2, 1}, {-1, 2}, {1, 2}}
20 var solutions = 0
21 var roundtrips = 0
22
23 func main() {
24     fmt.Println("Hello, Jumper!")
25
26     jumpto(0, 0, 1)
27
28     fmt.Println("I am done.")
29 }
30
31 func jumpto(x, y, iter int) {
32
33     // ok - store position
34     board[x][y] = iter
35
36     // finished?
37     if iter >= SIZEX*SIZEY {
38
39         // check for jumper roundtrips
40         round := false
41         for _, d := range jump {
42             nx := x + d[0]
43             ny := y + d[1]
44             // check if position is on the board
45             if nx < 0 || nx > (SIZEX-1) || ny < 0 || ny > (SIZEY-1) {
46                 continue
47             }
48             // detect roundtrip
49             if board[nx][ny] == 1 {
50                 round = true
51                 roundtrips++
52                 break
53             } // True
54         }
55
56         solutions++
57         if round == true {
58             printboard(round)
59         }
60         board[x][y] = 0
61         return
62     }
63
64     // try next jump
65     for _, d := range jump {
66         nx := x + d[0]
67         ny := y + d[1]
68
69         // check if position is on the board
70         if nx < 0 || nx > (SIZEX-1) || ny < 0 || ny > (SIZEY-1) {
71             continue
72         }
73
74         //  check if new field position is still empty
75         if board[nx][ny] != 0 {
76             continue
77         } // True
78
79         jumpto(nx, ny, iter+1)
80     }
81
82     // this iteration is done
83     board[x][y] = 0
84
85 }

```

By type inference and the normal `int` a 64-bit integer is used. But 64-bit ints are not needed, so I used 32-bit integers in the second version. This made the code about 7% faster.

Source of jumpsaround_2.go: view, download

```   15 type boardt [SIZEX][SIZEY]int32
16 var board boardt
17 var jump = [8][2]int32{{-1,-2}, {1,-2}, {-2,-1}, {2,-1}, {-2,1}, {2,1}, {-1,2}, {1,2}}
18 var solutions int32  = 0
19 var roundtrips int32 = 0

```

```   31 func jumpto(x, y, iter int32) {
32

```

Go is also known for its easy multithreading and should handle thousands of threads well. I tried this with version 3. The `jumpto` function is simply always called with a `go` in a single thread. The board must now be passed as a copy.

An atomic addition is also used for the summation of solutions and round trips.

The number of threads is kept in a WaitGroup and waits until all threads are finished.

Source of jumpsaround_3.go: view, download

```   26 func main() {
27     fmt.Println("Hello, Jumper!")
28     var board boardt // [SIZEX][SIZEY]int
29     wg.Add(1)                                                             // <<--
30     jumpto(board, 0, 0, 1)
31     wg.Wait() // waiting for waitgroup processes                          // <<--
32     fmt.Println("===== Solution #", solutions," (Roundtripps:", roundtrips, ") ====== ")
33     fmt.Println("I am done.")
34 }
35
36
37 func jumpto(board boardt, x, y, iter int32) {
38
39     defer wg.Done()                                                       // <<--
40
41     // ok - store position
42     board[x][y] = iter
43
44     // finished ?
45     if iter >= SIZEX*SIZEY {
46
47         // check for jumper roundtrips
48         round := false
49         for _, d := range jump {
50             nx := x + d[0]
51             ny := y + d[1]
52             // check if position is on the board
53             if nx<0 || nx>(SIZEX-1) || ny<0 || ny>(SIZEY-1) { continue }
54             // detect roundtrip
55             if board[nx][ny] == 1 { round = true; atomic.AddInt32(&roundtrips,1); break } // True
56         }
57
58         atomic.AddInt32(&solutions, 1)                                    // <<--
59
60         printboard(board, round)
61
62         return
63     }
64
65     // try next jump
66     for _, d := range jump {
67         nx := x + d[0]
68         ny := y + d[1]
69
70         // check if position is on the board
71         if nx<0 || nx>(SIZEX-1) || ny<0 || ny>(SIZEY-1) { continue }
72
73         //  check if new field position is still empty
74         if board[nx][ny] != 0 { continue } // True
75
76         wg.Add(1)                                                         // <<--
77         go jumpto(board, nx, ny, iter + 1);                               // <<--
78     }
79
80     // this iteration is done
81     board[x][y] = 0;
82
83 }

```

As already expected, it is not a good idea to open thousands of threads without any reason. The program now needs 5 times longer to find the solution. But despite the fact that this version is slower, I'm amazed at how well Go handles so many threads.

That's why I chose a slightly smarter solution. Now a new thread is started only in the second iteration:

The output of the board has also been synchronized, so that no two boards are simultaneously printed by two threads to avoid a mess.

Here now follows the fastest solution so far, which needs only one third of the time of the C program.

Source of jumpsaround_4.go: view, download

```   69     // try next jump
70     for _, d := range jump {
71         nx := x + d[0]
72         ny := y + d[1]
73
74         // check if position is on the board
75         if nx<0 || nx>(SIZEX-1) || ny<0 || ny>(SIZEY-1) { continue }
76
77         //  check if new field position is still empty
78         if board[nx][ny] != 0 { continue } // True
79
80         if iter == SPAWN {  // SPAWN = 2                                  // <<--
81             wg.Add(1)
82             go jumpto(board, nx, ny, iter + 1);                           // <<--
83         } else {
84             jumpto(board, nx, ny, iter + 1);                              // <<--
85         }
86     }
87
88     // this iteration is done
89     board[x][y] = 0;
90
91 }
92
93
94 func printboard(board boardt, round bool) {
95     mutex.Lock()                                                          // <<--
96     if round == true { fmt.Println(" *** Roundtrip #", roundtrips, "*** ")

```

All in all, parallel programming in Go is quite easy.

Go is just fun to use. The easy to learn language, the fast turnaround cycles for code — compile — test is amazing. In my opinion it stands up to Python, in its clarity and simplicity. However, Go is by magnitudes faster than Python, as we will see later.

Go is current my favorite goto language for most programming tasks.

There is a nice, german introduction to Go on Heise: Ein Einstieg in die Programmier­sprache Go

## Racket Scheme

Racket is a Scheme. Scheme is a Lisp dialect. And I really wanted to try out Scheme as a functional program.

Of course you will notice the typical Lisp brackets in Racket.

Source of jumpsaround.rkt: view, download

```    1 #lang racket
2
3 ; jumpsaround - jumper game
4 ; (c) 2020 Alexander Kulbartsch
5
6 (define SIZEX 6)  ;6
7 (define SIZEY 5)  ;5
8
9 (define JUMP '{{-1 -2} {1 -2} {-2 -1} {2 -1} {-2 1} {2 1} {-1 2} {1 2}} )
10
11 (define board (make-vector (* SIZEX SIZEY) 0))
12 (define solutions 0)
13 (define roundtrips 0)
14
15 (define (board-ref x y)
16   (vector-ref board (+ x (* y SIZEX))))
17
18 (define (board-set! x y v)
19   (vector-set! board (+ x (* y SIZEX)) v))
20
21 (define (printboard rt)
22   (printf "===== Solution # ~a - Roundtripps: ~a ====== \n" solutions roundtrips)
23   (if rt  (printf " *** Roundtrip *** ")  #f)
24   (for ([i SIZEY])
25     (for ([j SIZEX])
26       (printf "~a:" (board-ref j i)))
27     (printf "\n"))
28   (printf "\n"))
29
30
31 (define (jumpto x y iter)
32   (board-set! x y iter)
33   ;check if finished
34   (if (>= iter (* SIZEX SIZEY))
35       (begin ;check for roundtrips
36           (let ([round #f])
37             (map (lambda (d)
38               (let ([nx (+ x (car  d))]
39                     [ny (+ y (cadr d))])
40                 (if (and (not round)
41                          (>= nx 0) (< nx SIZEX)
42                          (>= ny 0) (< ny SIZEY))
43                    (if (= (board-ref nx ny) 1)
44                        (begin
45                          (set! roundtrips (+ roundtrips 1))
46                          (set! round #t))
47                        #f )
48                    #f )))
49            JUMP)
50           (set! solutions (+ solutions 1))
51           (printboard round)))
52       ; else try next
53       (map (lambda (d)
54              (let ([nx (+ x (car  d))]
55                    [ny (+ y (cadr d))])
56                (if (and (>= nx 0) (< nx SIZEX)
57                         (>= ny 0) (< ny SIZEY))
58                    (if (= (board-ref nx ny) 0)
59                        (begin
60                          ; (display nx)
61                          (jumpto nx ny (add1 iter)) )
62                        #f)
63                    #f)))
64            JUMP))
65
66   (board-set! x y 0)
67 )
68
69 (define (start)
70    (printf "Hello Jumper!\n")
71    ;(display board)
72    (jumpto 0 0 1)
73    (printf "I am done.\n"))
74
75 (let ([start-sec (current-inexact-milliseconds)])
76   (start)
77   (printf "Duration: ~a seconds.\n" (/ (- (current-inexact-milliseconds) start-sec) 1000)))
78
79 ; EOF

```

Idiomatic Scheme would separate code into smaller functions. Here it just reproduces the base version logic with a to big function.

Racket can be interpreted or compiled. The interpreted version needed 25 times more time than the C version, the Compiled version still needed 5 times longer.

But Racket is not just only a Scheme, it's also possible to define you own language with it. For example Typed Racket which adds statically type checking or Pollen which is a publishing system.

I like the Lisp and Scheme functional languages for their precise syntax `(function parameters...)`. There is no difference between statements and (own) functions. Even data is structured the same way. This and the possibility to extend it with the powerful macro system according to your needs to a domain specific language (DSL).

Racket also comes with a nice IDE which has an integrated REPL.

But if you are used to ALGOL-like structured languages like C or Java you have to change your thinking to grasp the functional programming concepts.

### Guile

Guile is another implementation of Scheme. It was recommended to me to try this out as well.

I had to change some function calls, where Racket offers some more first-time user friendly variants. But generally it's the same.

Source of jumpsaround.scm: view, download

The compiled Guile version needed 4 times as much time compared to the compiled Racket version. I am a little disappointed.

## V

The V Programming Language is a relatively new language. It aims to be as simple (or simpler) as Go and as secure as Rust. The compiler is extremely fast, but for faster production builds it transpiles V to C and let the C compiler do the optimizations. V has an easy multithreading option like Go and gains to have a cross platform batteries included library with web, GUI, ORM and graphics features. Fascinating ist, that V is primarily a one person project. But there is already a growing community around it.

To gain the security of Rust V does not have global variables. So you have to pass the whole state. For the first version I put the Knights jump definitions into a not-mutable variable into the function. But this allocates memory on the heap whenever the function is called. This memory is (in the current version 0.1.29) not freed on the end of the function, which resulted in a memory exhaustion during run. In the next iteration I used constants, which are only allowed on module level. This worked well.

Source of jumpsaround_2.v: view, download

```    7 const (
8     // {{-1,-2}, {1,-2}, {-2,-1}, {2,-1}, {-2,1}, {2,1}, {-1,2}, {1,2}}
9     jumpx = [-1,  1, -2,  2, -2,  2, -1,  1]
10     jumpy = [-2, -2, -1, -1,  1,  1,  2,  2]
11 )
12
13 // Main
14 fn main() {
15     println('Hello, Jumper!')
16
17     sizex := 6
18     sizey := 5
19
20     mut board := [0].repeat(sizex * sizey)
21
22     solutions, roundtrips := jumpto(mut board, sizex, sizey, 0, 0, 1, 0, 0)
23
24     println('===== Solutions:\$solutions - Roundtripps:\$roundtrips ====== ')
25     println('I am done.')
26 }
27
28
29 // Jump to a new postion
30 fn jumpto(mut board []int, sizex int, sizey int, x int, y int, iter_in int, solutions_in int, roundtrips_in int) (int, int) {
31
32     mut solutions  := solutions_in
33     mut roundtrips := roundtrips_in
34     mut iter       := iter_in
35
36     // store position
37     // board_set(mut board, sizex, sizey, x, y, iter)
38     board[x + y * sizex] = iter
39
40     // check if finished
41     mut round := false
42     if  iter == sizex * sizey {
43         for i, jx in jumpx {
44             nx := x + jx
45             ny := y + jumpy[i]
46
47             // new position still on board
48             if nx<0 || nx>(sizex-1) || ny<0 || ny>(sizey-1) { continue }
49
50             // check for roundtrips
51             if board[nx + ny * sizex] == 1 {
52                 round = true
53                 roundtrips++
54                 print_board(board, sizex, sizey, round, iter, solutions, roundtrips)
55                 break
56             }
57         }
58
59         board[x + y * sizex] = 0
60         return solutions + 1, roundtrips
61     }
62
63     // try next jump
64     iter++
65     for i, jx in jumpx {
66         nx := x + jx
67         ny := y + jumpy[i]
68
69         // new position still on board
70         if nx<0 || nx>(sizex-1) || ny<0 || ny>(sizey-1) { continue }
71
72         // check if new position is empty and jump to it
73         if board[nx + ny * sizex] == 0 {
74             solutions, roundtrips = jumpto(mut board, sizex, sizey, nx, ny, iter, solutions, roundtrips)
75         }
76     }
77
78     board[x + y * sizex] = 0
79     return solutions, roundtrips
80 }

```

For this project I just used the V native compilation (development build) and the trans-compilation to C (production build). The native compilation takes about double the time of the C version. The C based binary is as fast as the native C program.

Would I use it? When V becomes a little more mature, the answer is a veritable "Yes". The downside is, that it is currently not nearly as popular as Go or Rust.

Here is a short german article about V on Heise: V eine neue Programmier­sprache betritt die Open Source Bühne

## Forth

Around 1983 when I was a teenager I heard rumors about Forth and that it should be faster than assembler. Of course I knew that can't be possible but I was curious. So I bought a tape with an Forth implementation for Sharp MZ-700. But I only played around with it a little bit.

Now and then Forth pops up and stood on my mind. On the Open Rhein Ruhr 2019 I visited a booth where they used Forth to program microcontrollers. And during DIVOC - Hidden Service 2020 was an introduction talk to Forth I saw.

So I thought it will popup anyway in my live and I just have to give it a try. I decided to use Gforth.

This project was like a puzzle game to me. You have to remember a lot and fiddle out how it works together.

Forth has a REPL where you can use it interactively, but you define something new it will be immediately compiled. A disgusting thing was, that the word `char` does only work interactive, not compiled. For compilation `[char]` has to be used.

Forth uses a stack to hand over parameters to functions (called words in Forth). So far this is the way most programming languages work. But instead of using this parameters as variables you directly modify the stack. The same is true for returning parameters. So you have to take care to consume all parameters from the stack and to give back the exact returning values under any condition of your word. In other languages your function might ignore parameters in certain conditions, in Forth you have to handle with this.

Forth's stack uses native CPU words. This are 8 bytes on an 64bit machine. In the Go version I made a change to use smaller number types which increased performance. This I didn't try in Forth and which might gain performance increase as well.

Sorry, no syntax highlighting here. A `/` is a comment to the end of the line. A `( ... )` is a block comment, mostly used to describe the expected stack input and after two dashes `--` the output.

Source of jumpsaround_1.4th: view, download

```    4 6 constant SIZEX
5 5 constant SIZEY
6
7 \ init the possible 8 moves for a night
8 : init-jump ( n7..n0 a -- ) 8 0 ?do dup rot swap i cells + ! loop drop ;
9 variable jumpx 8 cells allot
10  1 -1  2 -2  2 -2  1 -1  jumpx init-jump
11 variable jumpy 8 cells allot
12  2  2  1  1 -1 -1 -2 -2  jumpy init-jump
13 \ display jumpto coordinates, only for needed testing
14 : jump-show ( -- ) 8 0 ?do ." {" jumpx i cells + @ . ." ," jumpy i cells + @ . ." }" loop cr ;
15
16 \ define and init more variables
17 variable board SIZEX SIZEY * cells allot   board SIZEX SIZEY * cells erase
18 variable iters SIZEX SIZEY * cells allot   iters SIZEX SIZEY * cells 0 fill
19 variable solutions                         0 solutions !
20 variable roundtrips                        0 roundtrips !
21 variable isroundtrip                       false isroundtrip !
22
23 : board-get ( x y -- n ) SIZEX * + cells board + @ ;
24 : board-set ( n x y -- ) SIZEX * + cells board + ! ;
25
26 \ print board
27 : printboard ( -- )
28   ." ===== Solution #" solutions @ . ." - Roundtripps:" roundtrips @ . ." ====== "
29   isroundtrip @ if ." *** Roundtrip ***" endif cr
30   SIZEY 0 ?do
31     SIZEX 0 ?do
32       i j board-get dup 10 < if space endif . [char] : emit
33     loop cr
34   loop cr ;
35
36 \ jump to
37 : jumpto ( nx ny ni -- )
38     dup 2over board-set                 \ store position ( nx ny ni )
39     \ finished?
40     dup SIZEX SIZEY * >= if             \ finished ?
41         8 0 ?do
42             jumpx i cells + @ 3 pick +    \ ( nx ny ni nx2 )
43             jumpy i cells + @ 3 pick +    \ ( nx ny ni nx2 ny2)
44             \ check if the new position is on the board
45             dup  0 >=  over sizey < and
46             2 pick
47             dup  0 >=  swap sizex < and   and if
48                 \ detect roundtrip
49                 board-get 1 = if 1 roundtrips +! true isroundtrip ! leave  then  \ ( nx ny ni b )
50             else 2drop
51             then \ btw "then" and "endif" are the same ;)
52         loop
53         1 solutions +!
54         printboard                      \ ( nx ny )
55     else \ try next jump
56         8 0 ?do
57             jumpx i cells + @ 3 pick +    \ ( nx ny ni nx2 )
58             jumpy i cells + @ 3 pick +    \ ( nx ny ni nx2 ny2)
59             \ ." i=" i . .s cr  \ test
60             \ check if the new position is on the board
61             dup  0 >=  over sizey < and
62             2 pick
63             dup  0 >=  swap sizex < and   and if
64                 \ check if new field position is still empty
65                 2dup board-get 0 =
66                 if   2 pick 1+
67                      recurse
68                 else 2drop
69                 then \ ( nx ny ni )
70             else 2drop
71             then \ btw "then" and "endif" are the same ;)
72         loop
73     then
74     drop                            \ ( nx ny ni -- nx ny )
75     0 -rot board-set ;              \ ( nx ny -- )
76
77 \ main
78 cr
79 ." Hello, Jumper!" cr
80  0 0 1 jumpto
81 ." I am done" cr
82 bye

```

The first Forth version of jumpsaround is also a more or less 1:1 translation from the C version. In this case the `jumpto` word has many lines. In Forth it is more idiomatic to split up the code in to words just having just a few lines. That way it is much easier to debug code an get the stack right.

For the second version I refactored some parts into smaller words. This has just a minor performance impact.

Source of jumpsaround_2.4th: view, download

```   36 : roundtrip? ( nx ny -- )
37     board-get 1 =
38     if   1 roundtrips +! true isroundtrip !
39     then ;
40
41 : position-on-board?    ( nx ny -- nx ny b )
42     dup  0 >=           ( nx ny b )
43     over sizey <        ( nx ny b b )
44     and                 ( nx ny b   )
45     2 pick              ( nx ny b nx )
46     dup  0 >=           ( nx ny b nx b )
47     swap sizex <        ( nx ny b b b )
48     and  and ;          ( nx ny b )
49
50 \ jump to
51 : jumpto ( nx ny ni -- )
52     dup 2over board-set                 \ store position ( nx ny ni )
53     \ finished?
54     dup SIZEX SIZEY * >= if             \ finished?
55         false isroundtrip !
56         8 0 ?do
57             jumpx i cells + @ 3 pick +    \ ( nx ny ni nx2 )
58             jumpy i cells + @ 3 pick +    \ ( nx ny ni nx2 ny2)
59             \ check if the new position is on the board
60             position-on-board?
61             if   roundtrip?  isroundtrip @  if leave  endif
62             else 2drop
63             then \ btw "then" and "endif" are the same ;)
64         loop
65         1 solutions +!
66         printboard                      \ ( nx ny )
67     else \ try next jump

```

Forth is a very low level programming language like C where directly manipulate pointers for memory access. So it is easy to shoot yourself in the foot.

Would I use Forth for future projects? I don't think I would do so for larger projects. Maybe just for fun or for programming micro controllers like an Adruino.

About the speed. At least for gforth I can tell that it is around 10 times slower than the basic C version. So I am a little disappointed with the speed of this language. I think that the reason for this, that every word is looked up in a directory, because you can (re)define words during runtime. In "normal" compiled languages the address of the function is known and can be called immediately.

After I finished my work on Forth heise online published a (german) article about Forth: Forth – die ewig junge Programmier­sprache

## Python

Everybody loves Python!? At least it is very popular. So let's take a look.

Python is an interpreted language. It claims to be very easy. I think it is easy, but there are other languages - like Go - which are also that "easy".

Source of jumpsaround.py: view, download

```    8 jump = ((-1,-2), (1,-2), (-2,-1), (2,-1), (-2,1), (2,1), (-1,2), (1,2))
9
10 # init board
11 board = []
12 for i in range(SIZEX):
13     col = []
14     for i in range(SIZEY):
15         col.append(0)
16     board.append(col)
17
18 solutions = 0
19 roundtrips = 0
20
21 def jumpto(x, y, iter):
22     global solutions
23     global roundtrips
24     global board
25
26     board[x][y] = iter
27
28     # finished?
29     if iter >= SIZEX * SIZEY:
30         # check for roundtrips
31         round = 0
32         for np in jump:
33             nx = x + np[0]
34             ny = y + np[1]
35             # check if position is on the board
36             if nx < 0 or nx > (SIZEX-1) or ny < 0 or ny > (SIZEY-1):
37                 continue
38             # detect roundtrip
39             if board[nx][ny] == 1:
40                 round = True
41                 roundtrips += 1
42                 break
43         solutions += 1
44         printboard(round)
45         board[x][y] = 0
46         return
47
48     # try next jump
49     for np in jump:
50         nx = x + np[0]
51         ny = y + np[1]
52         # check if position is on the board
53         if nx < 0 or nx > (SIZEX-1) or ny < 0 or ny > (SIZEY-1):
54             continue
55         # check if new field position is still empty
56         if board[nx][ny] != 0:
57             continue
58         jumpto(nx, ny, iter + 1)
59     board[x][y] = 0

```

What is noticeable is that there are no parentheses or begin-end blocks to structure code. Blocks such as loop bodies or conditional executions are only structured using indentation. This gives a novice programmer practice in formatting code cleanly and looks nice. But this has also the disadvantage that when moving code to another structural level you have to manually correct your indentation. For many other languages, that use brackets for structuring code, you have formatter available which can fix this for you.

The Python solution is 34 times slower than C and nearly 100 times slower than the parallel Go version.

If there is no need to use Python, I would prefer Go.

### Speeding up Python

There are ways to speed up Python. I checked out two of the popular options.

First I tried Cython. Cython transpiles Python code to C which you have to compile with gcc. This can be run independently or be used as C-modules in a regular Python program like numpy. Even if it is compiled it still interprets the code. You can add static types to your Python code, this might speed up your program but then it's not Python anymore. I didn't try this. The performance of the cython version, with gcc compiled with the `-O2` optimizer flag, needed less than half the time of the native Python version. Nice. Without the `-O2` flag it was even slower than the native Python version.

The second option I tried was PyPy. PyPy is a just in time compiler. Jumpsaround runs with pypy3 8 times faster than the native Python version. That's an impressive speedup. But PyPy has the disadvantage that including of C modules does not work or incurs some overhead. Source Wikipedia on PyPy.

## Javascript

Javascript is a must to be looked at. Starting as a way to create active web sites it's now everywhere. With Node.js its powering servers and with Electron javascript now is used for frontend development as well.

For my program I use Node.js as the runtime. Node.js uses the V8 JavaScript engine which is also used in the Chrome browser.

The syntax is like C. if you remove type definitions and replace it with "var" or "function" when appropriate your mostly done. (Of course C library functions are not the same.)

Source of jumpsaround_1.js: view, download

```    7 const jump = [[-1, -2], [1, -2], [-2, -1], [2, -1], [-2, 1], [2, 1], [-1, 2], [1, 2]];
8
9 let board = new Array;
10 let solutions = 0;
11 let roundtrips = 0;
12
13
14 function main() {
15     console.log("Hello, Jumper!\n");
16
17     // init
18     for (i = 0; i < SIZEX; i++) {
19         board[i] = [];  // same as "new Array"
20         for (j = 0; j < SIZEY; j++) {
21             board[i][j] = 0;
22         }
23     }
24     jumpto(0, 0, 1, 0);
25     console.log("I am done.");
26     return 0;
27 }
28
29
30 function jumpto(x, y, iter) {
31
32     // ok - store position
33     board[x][y] = iter;
34
35     // finished ?
36     if (iter >= SIZEX*SIZEY ) {
37         // check for jumper roundtrips
38         var round = false;
39         for (var i = 0; i < 8; i++) {
40             nx = x + jump[i][0];
41             ny = y + jump[i][1];
42             // check if position is on the board
43             if ( nx<0 || nx>(SIZEX-1) || ny<0 || ny>(SIZEY-1) ) continue;
44             // detect roundtrip
45             if ( board[nx][ny] == 1 ) { round = true; roundtrips++; break; } // True
46         }
47         solutions++;
48         if(round) printboard(round);
49         board[x][y] = 0;
50         return;
51     }
52
53     // try next jump
54     for (i = 0; i < 8; i++) {
55         // new position
56         nx = x + jump[i][0];
57         ny = y + jump[i][1];
58         // check if new position is on the board
59         if ( nx<0 || nx>(SIZEX-1) || ny<0 || ny>(SIZEY-1) ) continue;
60         //  check if new field position is still empty
61         if ( board[nx][ny] != 0 ) continue;
62         jumpto(nx, ny, iter + 1, i);
63     }
64
65     // this iteration is done
66     board[x][y] = 0;
67 }

```

Javascript is fascinating fast. Even if Javascript is a scripting language it's compiled wherever possible. The compiled code is extremely fast. jumpsaround can be optimised very well. We can see that during the browser wars Millons of \$ have bee pured into the development of fast javascript engines. In this case here the Node.js version just takes 30% more time than the C version. For a basically interpreted language, this is an impressive result.

With javascript you get the ease of a scripting language and the power of a compiled language.

What I dislike is that the language is not type save and uses implicit type conversion. For example you have three variables `a = 3; b = 2; c = 1;` and compare them with `a >= b >= c` - which is valid code - the result ist true. Good, isn't it? Now change the values of the variables to `a = 4; b = 3; c = 2;`. in this case the result is false. Why? The explanation is, that first `4 >= 3` will evaluate to true. In the comparison of `true >= 2`, true will be automatically be converted to a number. true becomes 1. So the second part of the comparison is `1 >= 2`. This was ok for our first test.

Libraries often use objects as parameters. If you misspelled an attribute the language won't warn you and it's sometimes hard to find the problem. Here an example. You define a person Object `p = { name: "Peter", birth: 1990 }`. And later you want to know if the person is born before 2000 with `p.born < 2000` this will evaluate to true. There is no error that `p.born` was not declared. Ouch!

There are many more of this pitfalls in Javascript, you wont recognize when you start programming with javascript, but you probably will unexpected behavior. That's a pain!

But today there are languages like TypeScript or Dart (and several more) which transcompiles to javascript and compensate those issues. Transcompiling (or shorter transpiling), on the other hand, gives you another layer of complexity that introduces new problems.

If possible, I would try to avoid Javascript and stick with Go. 😉

## Performance results

Performance was measured by just running `time \$Program`.

LanguageVersionProgramFeatureLoCX250*X250*
C (gcc)10.1.0jumpsaround_0.cjump dest. checked at beginning of func.627,62s7,62s
C (gcc)10.1.0jumpsaround_1.cjump dest. checked before recursive call625,52s5,52s
C (gcc -O2)10.2.0jumpsaround_1.coptimizer activated (same code as before)621,67s1,67s
Go1.15jumosaround_1.gosingle thread, using type inference/int664,24s4,24s
Go1.15jumosaround_2.gosingle thread, using int32523,97s3,97s
Go1.15jumosaround_3.gospawn each recursion in new thread - bad idea5921,45s21,45s
Go1.15jumosaround_4.gospawn new thread in 2nd iteration681,87s1,87s
Racket (comp.)7.8jumpsaround.rkt(Scheme) compiled5928,18s28,18s
Racket (intera.)7.8jumpsaround.rktinteractive DrRacket592m 20,90s140,90s
Guile (Scheme)2.2.6jumpsaround.scm592m 6,00s126,00s
V (dev=own comp.)0.129jumpsaround_2.vno globals allowed, whole context as param.6011,96s11,96s
V (prod=via C)0.129jumpsaround_2.vno globals allowed, whole context as param.603,75s3,75s
Forth (Gforth)0.7.9jumpsaround_1.4th6151,32s51,32s
Forth (Gforth)0.7.9jumpsaround_2.4thslightly more modularized7053,62s53,62s
Python3.8.5jumpsaround.py533m 0,89s180,89s
Python (cython3 -3)0.29.21jumpsaround.pyxkeine Cython type annotation, gcc533m 40.93s220,93s
Python (cython3 -3)0.29.21jumpsaround.pyxkeine Cython type annotation, gcc -O2531m 18,85s78,85s
Python (PyPy)7.3.3jumpsaround.py5322,02s22,02s
Javascript (Node.js)14.8.0jumpsaround_1.js577,18s7,18s
Ruby2.7.2jumpsaround_1.rb2m 6,69s126,69s
Crystal1.0.0jumpsaround_1.crbuild time 1,7s47,09s47,09s
Crystal (release)1.0.0jumpsaround_1.cr(crystal build --release) build time 16,58s (LLVM 10.0.0)4,16s4,16s

* The X250 has an Intel i5-5300U (2 cores/4 threads) 2.90GHz CPU.

Language
Sec
shorter is better
C (gcc)
8
C (gcc)
6
C (gcc -O2)
2
Go
4
Go
4
Go
21
Go
2
Racket (comp.)
28
Racket (intera.)
141
Guile (Scheme)
126
V (dev=own comp.)
12
V (prod=via C)
4
Forth (Gforth)
51
Forth (Gforth)
54
Python
181
Python (cython3 -3)
221
Python (cython3 -3)
79
Python (PyPy)
22
Javascript (Node.js)
7
Ruby
127
Crystal
47
Crystal (release)
4

Keep in mind, this timings are only valid for this type of algorithm. For other situations, the performance of the languages will differ.

LoC = Lines of Code. There is noc significant difference. The number of code-lines are more dependent of writing, like writing a simple clause in same line as the condition.

### Timings of different Board sizes

In the beginning I mentioned, that I use a 6x5 sized board for the tests. What time would it take on slightly larger boards? Here are some results calculated with the jumosaround_4.go version on a faster machine with an Intel Core i7-8700T (6 cores/12 threads) 4GHz CPU.

Sizeh:mm:ss.sFactorRoundtrips
6x500:00.5116
6x601:45.021019724
6x76:11:55.044.630m(

I didn't try a larger board. No need to burn several days long energy for this. ;)

## Honorable Mentions

• Rust is an imperative and functional language. It's unique selling point is it's memory safety, without using garbage collection. Rust can be used critical software, even for system programming tasks. The compiled code is fast, but the compiler, which does all the memory checking in advance, needs a fair amount of time for this job. Of course it also supports multithreading. Rust on Wikipedia
• Smalltalk is the Godfather of object-oriented programming languages. One cool and actively maintained Smalltalk implementation is Pharo. It comes with an powerful graphical environment which is like an IDE and OS rolled into one.
• Dart is a nice language and it's able to crosscompile to many platforms, including mobile, desktop and servers. It's good to build cross-platform applications with the corresponding Flutter toolkit to natively compile applications for mobile, web, and desktop from a single codebase.

Maybe I'll do the implementation of Jumpsaround in one of those languages as well.

## This Website

This website can be found at kulbartsch.de/jumper

The last update of this page: 2021-07-02
Release: Version 1.2

Write me an email if you have any comments to: a-jumper àt alice-and-bob·de

Many thanks to all the people who supported me and gave me feedback for this website and the corresponding presentation.

This Website has been hand crafted with aswsg, my static website generator.

All source code on this page is licensed under the GPLv3 - GNU GENERAL PUBLIC LICENSE Version 3.

Syntax highlighting is done with highlight.

The design of this website and the logo on the top of the page follows the design of the 2020s remote Chaos experience (rC3) - as an homage to this online congress and for fun. The logo was made with the help of the rC3 logo generator from bleeptrack.

Here you'll find my homepage kulbartsch.de.

Jumpsaround - Solving The Knight's Tour problem in 7 programming languages by Alexander Kulbartsch is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.