Jumpsaround

Solving The Knight's Tour Problem in 7 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)

Years ago I discussed with a friend how to solve the Knights tour problem with a program. Over time I started to implement the logic in different programming languages. In the following text I describe my adventures during developing in the different programming languages.

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:

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. Screenshot of the DrRacket IDE.

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 just played a little around with it.

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 }

Even if Javascript is a scripting language it's compiled wherever possible. The compiled code is extremely fast. We can see that during the browser wars millions of dollars where put into developing fast javascript engines. In this case here the Node.js version just takes 30% more time than the C version. For a basically compiled 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 >= 1, 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*
C (gcc)10.1.0jumpsaround_0.cjump dest. checked at beginning of func.627,62s
C (gcc)10.1.0jumpsaround_1.cjump dest. checked before recursive call625,52s
C (gcc -O2)10.2.0jumpsaround_1.coptimizer activated (same code as before)621,67s
Go1.15jumosaround_1.gosingle thread, using type inference/int664,24s
Go1.15jumosaround_2.gosingle thread, using int32523,97s
Go1.15jumosaround_3.gospawn each recursion in new thread - bad idea5921,45s
Go1.15jumosaround_4.gospawn new thread in 2nd iteration681,87s
Racket (Scheme)7.8jumpsaround.rktcompiled5928,18s
Racket (Scheme)7.8jumpsaround.rktinteractive DrRacket592m 20,90s
Guile (Scheme)2.2.6jumpsaround.scm592m 6,00s
V (dev=own compiler)0.129jumpsaround_2.vno globals allowed, whole context as param.6011,96s
V (prod=cross comp. to C)0.129jumpsaround_2.vno globals allowed, whole context as param.603,75s
Forth (Gforth)0.7.9jumpsaround_1.4th6151,32s
Forth (Gforth)0.7.9jumpsaround_2.4thslightly more modularized7053,62s
Python3.8.5jumpsaround.py533m 0,89s
Python (cython3 -3)0.29.21jumpsaround.pyxkeine Cython type annotation, gcc533m 40.93s
Python (cython3 -3)0.29.21jumpsaround.pyxkeine Cython type annotation, gcc -O2531m 18,85s
Python (PyPy)7.3.3jumpsaround.py5322,02s
Javascript (Node.js)14.8.0jumpsaround_1.js577,18s

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

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 6x7 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. ;)


More Resources

Honorable Mentions

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-02-11
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.



Creative Commons License
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.