Brute-forcing a seemingly simple number puzzle

 From StackOverflow
Something was bothering me for almost two decades. It was a pen and paper game that I learned when I was around 13. The rules are simple: on an empty 10x10 grid (100 squares in total) you put a number 1 on an arbitrary square. Starting from that square you can move horizontally or vertically jumping over two squares or diagonally jumping over one square. There you can place number 2. Your task is to reach number 100, filling all squares. You can not visit already visited squares. Here is an example of a solved game with a reduced 5x5 grid, starting at top-left corner:

 1 24 14 2 25 16 21 5 8 20 13 10 18 23 11 4 7 15 3 6 17 22 12 9 19
On the other hand, if the program makes bad choices, we might get stuck without reaching the perfect score of 25 (on a reduced 5x5 grid):

 1 8 2 9 16 13 5 17 14 10 4 7 15 3 6 19 12 18 11
Notice how we got stuck at number 19, unable to move anywhere and fill six remaining gaps. On an original 10x10 grid I never managed to reach the perfect score of 100. Countless hours wasted at school, of trial and error. Anxious and jealous, I was waiting 20 years for this moment. Two decades later I finally understood recursion and decided to brute-force the shit out of this game!

Modeling the game

The game is a simple 10x10 grid with values ranging from `1` to `100`. Therefore we could use a two-dimensional `byte[][]` array. However, due to (most likely premature) optimization, I chose one-dimensional, unrolled array:

```class Board {

private static final int SIZE = 10;
private static final int MAX = SIZE * SIZE;

private final byte[] values;

private Board(byte[] values) {
this.values = values;
}

//...

}```
Next we need to store the position of last move. Technically we could scan through `values` array and look for highest value, but that seems suboptimal:

```class Board {

private static final int SIZE = 10;
private static final int MAX = SIZE * SIZE;

private final byte[] values;
private final int x;
private final int y;

private Board(byte[] values, int x, int y) {
this.values = values;
this.x = x;
this.y = y;
}

static Board startingAt(int x, int y) {
byte[] values = new byte[MAX];
values[idx(x, y)] = 1;
return new Board(values, x, y, listeners);
}

private static int idx(int x, int y) {
return y * SIZE + x;
}
}```
Notice how we create an empty board and place number `1` in selected square in `startingAt()` factory method. The current score is simply the highest value on board:

```int score() {
return values[idx(x, y)];
}```
Before we move further, let's define possible moves. There are 8 possible directions where we can jump:

```static final int HV_OFFSET = 3;
static final int DIAG_OFFSET = 2;

enum Direction {
DOWN(0, HV_OFFSET),
DOWN_RIGHT(DIAG_OFFSET, DIAG_OFFSET),
RIGHT(HV_OFFSET, 0),
UP_RIGHT(DIAG_OFFSET, -DIAG_OFFSET),
UP(0, -HV_OFFSET),
UP_LEFT(-DIAG_OFFSET, -DIAG_OFFSET),
LEFT(-HV_OFFSET, 0),
DOWN_LEFT(-DIAG_OFFSET, DIAG_OFFSET);

final int xDelta;
final int yDelta;

Direction(int xDelta, int yDelta) {
this.xDelta = xDelta;
this.yDelta = yDelta;
}
}```
`xDelta` and `yDelta` tell how many squares we move along X and Y axis respectively. For example,  `DOWN `means no changes along X axis and adding `3` along Y axis. Having declarative definitions of each possible move we can build a method that performs all of them:

```private List<Board> nextMoves() {
List<Board> next = new ArrayList<>(Direction.values().length);
for (Direction dir : Direction.values()) {
final Board b = move(dir);
if (b != null) {
}
}
return next;
}

private Board move(Direction dir) {
final int newX = x + dir.yDelta;
final int newY = y + dir.xDelta;
if (newX < 0 || newX >= SIZE) {
return null;
}
if (newY < 0 || newY >= SIZE) {
return null;
}
if (values[idx(newX, newY)] != 0) {
return null;
}
final byte[] newValues = new byte[MAX];
System.arraycopy(values, 0, newValues, 0, MAX);
newValues[idx(newX, newY)] = (byte) (score() + 1);
return new Board(newValues, newX, newY, listeners);
}```
There's quite a bit of logic here! First of all we iterate over all possible directions and try to `move()`. The `move()` method may return `null` if:

• X or Y coordinate after move would be out of range
• target square is already occupied (values different than `0`)
If given move is valid (no matter if it makes sense in the longer run), we create new `Board` after applying this move. If our current score is e.g. `17`, we place `18` on the target square. Why creating a new instance of `Board` instead of mutating it? It'll make recursion simpler and enable parallelizing work!

Now the hardest part. We can create an empty `Board` with a starting point `1` and we can generate all possible moves (boards) immediately following that first move. If we continue this process recursively (generating every possible move starting from every possible move) we will eventually explore every single path we could take. Brute force. The recursion looks as follows:

```Board explore() {
List<Board> next = nextMoves();
for (Board board : next) {
if (board.score() == MAX) {
return board;
}
}
for (Board board : next) {
Board solution = board.explore();
if (solution != null) {
return solution;
}
}
return null;
}```
First, we generate all valid moves. If any of these moves has a `score()` of `MAX` (`100`) we return a solution. Otherwise we iterate over all valid moves and recursively explore them further down. If no branch provides a solution, it means we are stuck in a dead end. Returning `null` means just that. This builds a complete game tree with every possible move. The fact that `Board` is immutable means we don't have to perform any cleanup when backtracking. What does it mean? When one of the branches is stuck in a dead end, we must slowly go back, trying to take all other possible moves. Mutating `Board` would require cleaning it up. Immutable `Board` can be simply thrown away once it's no longer needed. Also immutability enables concurrent exploration (soon to come).

How many moves do we have to examine? First, we must choose a starting point (`n<sup>2</sup>`, where `n = 10`, 100 possible squares). Then we must always examine 8 possible moves (not all of them are valid). For each move we must examine 8 further moves (so 64 in total). For each of these 64 moves we must examine 8 further moves... In general: `n28n-1`

Complexity also known as `O(insane)`. The number of boards to examine has 92 digits, billion times more than atoms in the Universe. Ouch! Let's run it anyway! Apart from what you already saw, I added a pluggable `Listeners` interface that can be used to track the progress of brute-force process:

```interface Listeners {
void onBoard(Board b);

void onSolution(Board b);

void onStuck(Board b);
}```
With a simple implementation that prints some useful statistics:

```import com.google.common.util.concurrent.RateLimiter;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import java.text.NumberFormat;
import java.time.Duration;
import java.time.Instant;
import java.util.ArrayList;
import java.util.List;
import java.util.Locale;
import java.util.concurrent.atomic.AtomicLong;

class LoggingListeners implements Listeners {

private static final Logger log = LoggerFactory.getLogger(LoggingListeners.class);

private final Instant start = Instant.now();
private final AtomicLong maxScore = new AtomicLong();
private final RateLimiter logLimiter = RateLimiter.create(0.1);

@Override
public void onBoard(Board b) {
totalExamined.increment();
if (logLimiter.tryAcquire()) {
log.info("Examined {} so far ({}K/s)", total(), throughput());
}
}

@Override
public void onSolution(Board b) {
final Duration duration = Duration.between(start, Instant.now());
log.info("Found solution in {}, examined {} ({}K/s):\n{}", duration, total(), throughput(), b);
}

@Override
public void onStuck(Board b) {
if (b.score() > maxScore.get()) {
log.info("Current max score is {} after {} examined:\n{}", b.score(), total(), b);
maxScore.set(b.score());
}
}

private int throughput() {
final Duration duration = Duration.between(start, Instant.now());
return (int) (totalExamined.longValue() / Math.max(duration.toMillis(), 1));
}

private String total() {
return NumberFormat
.getNumberInstance(Locale.US)
.format(totalExamined.longValue());
}
}```
The complete `Board` implementation looks as follows:

```class Board {

private static final int SIZE = 10;
private static final int MAX = SIZE * SIZE;

static final int HV_OFFSET = 3;
static final int DIAG_OFFSET = 2;

private final byte[] values;
private final int x;
private final int y;
private final Listeners listeners;

private Board(byte[] values, int x, int y, Listeners listeners) {
this.values = values;
this.x = x;
this.y = y;
this.listeners = listeners;
}

int score() {
return values[idx(x, y)];
}

static Board startingAt(int x, int y, Listeners listeners) {
byte[] values = new byte[MAX];
values[idx(x, y)] = 1;
return new Board(values, x, y, listeners);
}

Board explore() {
List<Board> next = nextMoves();
for (Board board : next) {
listeners.onBoard(board);
if (board.score() == MAX) {
listeners.onSolution(board);
return board;
}
}
for (Board board : next) {
Board solution = board.explore();
if (solution != null) {
return solution;
}
}
listeners.onStuck(this);
return null;
}

private List<Board> nextMoves() {
List<Board> next = new ArrayList<>(Direction.values().length);
for (Direction dir : Direction.values()) {
final Board b = move(dir);
if (b != null) {
}
}
return next;
}

private Board move(Direction dir) {
final int newX = x + dir.yDelta;
final int newY = y + dir.xDelta;
if (newX < 0 || newX >= SIZE) {
return null;
}
if (newY < 0 || newY >= SIZE) {
return null;
}
if (values[idx(newX, newY)] != 0) {
return null;
}
final byte[] newValues = new byte[MAX];
System.arraycopy(values, 0, newValues, 0, MAX);
newValues[idx(newX, newY)] = (byte) (score() + 1);
return new Board(newValues, newX, newY, listeners);
}

private static int idx(int x, int y) {
return y * SIZE + x;
}

@Override
public String toString() {
StringBuilder sb = new StringBuilder();
for (int y = 0; y < SIZE; ++y) {
for (int x = 0; x < SIZE; ++x) {
final int value = values[idx(x, y)];
if (value < 100) {
sb.append(' ');
}
if (value < 10) {
sb.append(' ');
}
if (value == 0) {
sb.append('.');
} else {
sb.append(value);
}
if (x < SIZE - 1) {
sb.append(' ');
}
}
if (y < SIZE - 1) {
sb.append('\n');
}
}
return sb.toString();
}
}```
Enough of coding, let's run it! But first let's make sure it actually works with smaller data set:

```private static final int SIZE = 5;

final Listeners listeners = new LoggingListeners();
Board.startingAt(0, 0, listeners).explore();```
The solution to 5x5 grid (reaching 25) was found in about 100 ms:

```19:37:59.117 | Current max score is 19 after 32 examined:
1   8   .   2   9
16  13   5  17  14
.   .  10   .   .
4   7  15   3   6
19  12   .  18  11
19:37:59.122 | Current max score is 23 after 38 examined:
1   8   .   2   9
16  13   5  17  14
22  19  10  23  20
4   7  15   3   6
.  12  21  18  11
19:37:59.123 | Current max score is 24 after 75 examined:
1   8  16   2   9
23  13   5  24  14
17  20  10   .  19
4   7  15   3   6
22  12  18  21  11
19:37:59.130 | Found solution in PT0.041S, examined 1,381 (33M/s):
1  24  14   2  25
16  21   5   8  20
13  10  18  23  11
4   7  15   3   6
17  22  12   9  19```
Notice how the first top score found was `19` and the algorithm got stuck, it had to backtrack. The next best score was `23`, `24` and finally perfect `25`, filling all the squares. So it works, let's try it with the original problem of 10x10 grid:

```19:44:09.135 | Current max score is 52 after 178 examined:
1   .   .   2   .   .   3   .   .   4
.   .   .   .   .   .   .   .   .   .
.   .   .   .   .   .   .   .   .   .
.   .   .   .   .   .   .   .   .   5
.   .  51   .   .  50   .   .  49   .
32  44  17  33  45  18  34  46  19  35
11  25   .  12  26  40  13  27  39   6
.   .  52   .   .  47  20  36  48  21
31  43  16  30  42  15  29  41  14  28
10  24   .   9  23  37   8  22  38   7
19:44:09.135 | Current max score is 67 after 220 examined:
1   .   .   2   .   .   3   .   .   4
.   .   .   .   .   .   .   .   .   .
52  67   .  53  66   .  54  65   .  55
.   .   .   .   .   .   .   .   .   5
.   .  51  62  57  50  63  56  49  64
32  44  17  33  45  18  34  46  19  35
11  25   .  12  26  40  13  27  39   6
60   .   .  61  58  47  20  36  48  21
31  43  16  30  42  15  29  41  14  28
10  24  59   9  23  37   8  22  38   7
19:44:09.136 | Current max score is 86 after 255 examined:
1  82  67   2  83  68   3  84  69   4
75   .   .  76   .   .  77   .   .  78
52   .   .  53  66  85  54  65  86  55
.  81  72   .  80  71   .  79  70   5
74   .  51  62  57  50  63  56  49  64
32  44  17  33  45  18  34  46  19  35
11  25  73  12  26  40  13  27  39   6
60   .   .  61  58  47  20  36  48  21
31  43  16  30  42  15  29  41  14  28
10  24  59   9  23  37   8  22  38   7
19:44:09.136 | Current max score is 88 after 270 examined:
1   .  67   2   .  68   3   .  69   4
75  86  81  76  87  82  77  88  83  78
52   .   .  53  66   .  54  65   .  55
.   .  72  85  80  71  84  79  70   5
74   .  51  62  57  50  63  56  49  64
32  44  17  33  45  18  34  46  19  35
11  25  73  12  26  40  13  27  39   6
60   .   .  61  58  47  20  36  48  21
31  43  16  30  42  15  29  41  14  28
10  24  59   9  23  37   8  22  38   7
19:44:09.136 | Current max score is 90 after 317 examined:
1   .  67   2   .  68   3   .  69   4
75  88  81  76  87  84  77   .  85  78
52   .   .  53  66   .  54  65   .  55
82   .  72  83  80  71  86  79  70   5
74  89  51  62  57  50  63  56  49  64
32  44  17  33  45  18  34  46  19  35
11  25  73  12  26  40  13  27  39   6
60  90   .  61  58  47  20  36  48  21
31  43  16  30  42  15  29  41  14  28
10  24  59   9  23  37   8  22  38   7
19:44:09.137 | Current max score is 92 after 346 examined:
1  88  67   2  89  68   3  90  69   4
75   .  85  76   .  80  77   .  81  78
52   .   .  53  66  91  54  65  92  55
84  87  72  83  86  71  82  79  70   5
74   .  51  62  57  50  63  56  49  64
32  44  17  33  45  18  34  46  19  35
11  25  73  12  26  40  13  27  39   6
60   .   .  61  58  47  20  36  48  21
31  43  16  30  42  15  29  41  14  28
10  24  59   9  23  37   8  22  38   7
19:44:09.137 | Current max score is 94 after 379 examined:
1  90  67   2  91  68   3  92  69   4
75  84  87  76  83  80  77   .  81  78
52   .   .  53  66  93  54  65  94  55
86  89  72  85  88  71  82  79  70   5
74   .  51  62  57  50  63  56  49  64
32  44  17  33  45  18  34  46  19  35
11  25  73  12  26  40  13  27  39   6
60   .   .  61  58  47  20  36  48  21
31  43  16  30  42  15  29  41  14  28
10  24  59   9  23  37   8  22  38   7
19:44:09.138 | Current max score is 96 after 602 examined:
1  84  67   2  83  68   3  80  69   4
75  94  87  76  93  90  77   .  91  78
52   .  82  53  66  81  54  65   .  55
88  85  72  89  86  71  92  79  70   5
74  95  51  62  57  50  63  56  49  64
32  44  17  33  45  18  34  46  19  35
11  25  73  12  26  40  13  27  39   6
60  96   .  61  58  47  20  36  48  21
31  43  16  30  42  15  29  41  14  28
10  24  59   9  23  37   8  22  38   7
19:44:09.166 | Current max score is 97 after 30,829 examined:
1  89  67   2  88  68   3  87  69   4
81  95  92  80  73  76  79  72  75  78
52   .  85  53  66  86  54  65   .  55
93  90  82  94  91  71  74  77  70   5
84  96  51  62  57  50  63  56  49  64
32  44  17  33  45  18  34  46  19  35
11  25  83  12  26  40  13  27  39   6
60  97   .  61  58  47  20  36  48  21
31  43  16  30  42  15  29  41  14  28
10  24  59   9  23  37   8  22  38   7
19:44:09.683 | Current max score is 98 after 2,165,687 examined:
1  90  77   2  89  78   3  88  79   4
70  96  93  71  83  86  72  82  85  73
52   .  66  53  76  65  54  75  64  55
94  91  69  95  92  81  84  87  80   5
67  97  51  62  57  50  63  56  49  74
32  44  17  33  45  18  34  46  19  35
11  25  68  12  26  40  13  27  39   6
60  98   .  61  58  47  20  36  48  21
31  43  16  30  42  15  29  41  14  28
10  24  59   9  23  37   8  22  38   7
19:44:19.121 | Examined 64,805,972 so far (6469K/s)
19:44:20.699 | Current max score is 99 after 76,321,898 examined:
1  97  82   2  98  67   3  99  66   4
84  61  94  85  62  89  86  63  90  87
52  80  73  53  81  72  54  68  71  55
93  96  83  92  95  64  91  88  65   5
74  60  51  79  57  50  70  56  49  69
32  44  17  33  45  18  34  46  19  35
11  25  75  12  26  40  13  27  39   6
77  59   .  78  58  47  20  36  48  21
31  43  16  30  42  15  29  41  14  28
10  24  76   9  23  37   8  22  38   7
19:44:29.121 | Examined 139,819,549 so far (6985K/s)
19:44:39.120 | Examined 216,100,690 so far (7199K/s)
19:44:49.120 | Examined 287,468,941 so far (7183K/s)
19:44:59.119 | Examined 361,736,638 so far (7232K/s)
19:45:09.120 | Examined 437,409,160 so far (7288K/s)
...
20:29:29.015 | Examined 19,985,852,124 so far (7347K/s)
20:29:39.015 | Examined 20,059,067,812 so far (7347K/s)
20:29:49.015 | Examined 20,132,070,269 so far (7347K/s)
20:29:59.014 | Examined 20,202,977,476 so far (7346K/s)
20:30:09.014 | Examined 20,277,545,427 so far (7347K/s)
20:30:19.014 | Examined 20,345,749,056 so far (7345K/s)
20:30:29.013 | Examined 20,414,805,092 so far (7343K/s)```
After 45 minutes the program was stuck in local minimum. It quickly found the solution of `98` and after few more seconds `99`. However it's not capable of finding perfect `100`, despite more than 20 billion boards examined (7 million per second (!)) Turns out the starting point is extremely important. The exact same program, but starting in the middle (at `(5, 5)`) rather than in the corner finds the solution in about 3 seconds:

```20:35:14.292 | Current max score is 67 after 218 examined:
.   .   .   .   .   .   .   .   .   .
.   .   .   .   .   .  57   .   .  58
.   .   .   .   .   .  40  47   .  41
.   .  54   .  60  55   .  59  56   .
65   .   .  64   .  38  45  42  39  46
23  52  61  24  53   1  17  48   2  18
6  35  66   7  36  43   8  37  44   9
62  25  14  63  26  15  30  27  16  31
22  51   5  21  50   4  20  49   3  19
13  34  67  12  33  28  11  32  29  10
20:35:14.292 | Current max score is 79 after 246 examined:
76   .   .  77   .   .  78   .   .  79
.  69   .   .  70   .  57  71   .  58
.   .   .   .   .   .  40  47   .  41
75   .  54  74  60  55  73  59  56  72
65  68   .  64  67  38  45  42  39  46
23  52  61  24  53   1  17  48   2  18
6  35  66   7  36  43   8  37  44   9
62  25  14  63  26  15  30  27  16  31
22  51   5  21  50   4  20  49   3  19
13  34   .  12  33  28  11  32  29  10
20:35:14.293 | Current max score is 83 after 252 examined:
76   .   .  77  82   .  78  83   .   .
.  69   .   .  70   .  57  71   .  58
.   .  81   .   .  80  40  47  79  41
75   .  54  74  60  55  73  59  56  72
65  68   .  64  67  38  45  42  39  46
23  52  61  24  53   1  17  48   2  18
6  35  66   7  36  43   8  37  44   9
62  25  14  63  26  15  30  27  16  31
22  51   5  21  50   4  20  49   3  19
13  34   .  12  33  28  11  32  29  10
20:35:14.293 | Current max score is 89 after 262 examined:
76  83   .  77  82   .  78   .   .   .
.  69  87   .  70  88  57  71  89  58
85   .  81  84   .  80  40  47  79  41
75   .  54  74  60  55  73  59  56  72
65  68  86  64  67  38  45  42  39  46
23  52  61  24  53   1  17  48   2  18
6  35  66   7  36  43   8  37  44   9
62  25  14  63  26  15  30  27  16  31
22  51   5  21  50   4  20  49   3  19
13  34   .  12  33  28  11  32  29  10
20:35:14.293 | Current max score is 90 after 266 examined:
76  83  88  77  82  89  78   .  90   .
.  69   .   .  70   .  57  71   .  58
85   .  81  84  87  80  40  47  79  41
75   .  54  74  60  55  73  59  56  72
65  68  86  64  67  38  45  42  39  46
23  52  61  24  53   1  17  48   2  18
6  35  66   7  36  43   8  37  44   9
62  25  14  63  26  15  30  27  16  31
22  51   5  21  50   4  20  49   3  19
13  34   .  12  33  28  11  32  29  10
20:35:14.293 | Current max score is 91 after 274 examined:
76  83  86  77  82   .  78   .   .   .
.  69  89   .  70  90  57  71  91  58
85   .  81  84  87  80  40  47  79  41
75   .  54  74  60  55  73  59  56  72
65  68  88  64  67  38  45  42  39  46
23  52  61  24  53   1  17  48   2  18
6  35  66   7  36  43   8  37  44   9
62  25  14  63  26  15  30  27  16  31
22  51   5  21  50   4  20  49   3  19
13  34   .  12  33  28  11  32  29  10
20:35:14.295 | Current max score is 93 after 719 examined:
76  85  88  77  84  87  80   .   .   .
.  69  91   .  70  92  57  71  93  58
89  78  83  86  79  82  40  47  81  41
75   .  54  74  60  55  73  59  56  72
65  68  90  64  67  38  45  42  39  46
23  52  61  24  53   1  17  48   2  18
6  35  66   7  36  43   8  37  44   9
62  25  14  63  26  15  30  27  16  31
22  51   5  21  50   4  20  49   3  19
13  34   .  12  33  28  11  32  29  10
20:35:14.297 | Current max score is 94 after 1,140 examined:
76  91  88  83  78  89  82  79   .   .
94  69   .  93  70   .  57  71   .  58
87  84  77  90  85  80  40  47  81  41
75  92  54  74  60  55  73  59  56  72
65  68  86  64  67  38  45  42  39  46
23  52  61  24  53   1  17  48   2  18
6  35  66   7  36  43   8  37  44   9
62  25  14  63  26  15  30  27  16  31
22  51   5  21  50   4  20  49   3  19
13  34   .  12  33  28  11  32  29  10
20:35:14.301 | Current max score is 95 after 3,454 examined:
84  92  89  75  82  90  78  81   .   .
95  69  86  94  70   .  57  71   .  58
88  76  83  91  77  80  40  47  79  41
85  93  54  74  60  55  73  59  56  72
65  68  87  64  67  38  45  42  39  46
23  52  61  24  53   1  17  48   2  18
6  35  66   7  36  43   8  37  44   9
62  25  14  63  26  15  30  27  16  31
22  51   5  21  50   4  20  49   3  19
13  34   .  12  33  28  11  32  29  10
20:35:14.304 | Current max score is 96 after 5,663 examined:
78  93  90  85  80  91  84  81   .   .
96  69  76  95  70  75  57  71   .  58
89  86  79  92  87  82  40  47  83  41
77  94  54  74  60  55  73  59  56  72
65  68  88  64  67  38  45  42  39  46
23  52  61  24  53   1  17  48   2  18
6  35  66   7  36  43   8  37  44   9
62  25  14  63  26  15  30  27  16  31
22  51   5  21  50   4  20  49   3  19
13  34   .  12  33  28  11  32  29  10
20:35:14.312 | Current max score is 97 after 13,933 examined:
86  94  91  77  84  92  80  83   .   .
97  69  88  96  70  75  57  71  74  58
90  78  85  93  79  82  40  47  81  41
87  95  54  76  60  55  73  59  56  72
65  68  89  64  67  38  45  42  39  46
23  52  61  24  53   1  17  48   2  18
6  35  66   7  36  43   8  37  44   9
62  25  14  63  26  15  30  27  16  31
22  51   5  21  50   4  20  49   3  19
13  34   .  12  33  28  11  32  29  10
20:35:14.315 | Current max score is 98 after 19,845 examined:
80  95  92  87  78  93  74  77   .  73
98  69  82  97  70  83  57  71  84  58
91  88  79  94  89  76  40  47  75  41
81  96  54  86  60  55  85  59  56  72
65  68  90  64  67  38  45  42  39  46
23  52  61  24  53   1  17  48   2  18
6  35  66   7  36  43   8  37  44   9
62  25  14  63  26  15  30  27  16  31
22  51   5  21  50   4  20  49   3  19
13  34   .  12  33  28  11  32  29  10
20:35:14.412 | Current max score is 99 after 421,749 examined:
95  69  89  94  70  88  74  71   .  75
66  85  82  67  78  81  57  77  80  58
90  93  96  87  92  72  40  47  73  41
83  68  54  84  60  55  79  59  56  76
65  86  91  64  97  38  45  42  39  46
23  52  61  24  53   1  17  48   2  18
6  35  98   7  36  43   8  37  44   9
62  25  14  63  26  15  30  27  16  31
22  51   5  21  50   4  20  49   3  19
13  34  99  12  33  28  11  32  29  10
20:35:17.731 | Found solution in PT3.468S, examined 18,392,716 (5303K/s):
94  82  98  95  81  99  77  80 100  76
85  72  67  84  73  66  57  74  65  58
69  96  93  70  97  79  40  47  78  41
62  83  54  63  60  55  64  59  56  75
86  71  68  87  92  38  45  42  39  46
23  52  61  24  53   1  17  48   2  18
6  35  91   7  36  43   8  37  44   9
89  25  14  88  26  15  30  27  16  31
22  51   5  21  50   4  20  49   3  19
13  34  90  12  33  28  11  32  29  10```

Conclusion

I was hoping to use this simple game as a fun exercise in concurrency (`ForkJoinPool` in particular). Unfortunately, the single core performance seems sufficient... But at least I know this game can be beaten. Well, there are actually much easier ways to prove that...

PS: optimizations

I mentioned that the usage of `byte` array instead of `int` was most likely a premature optimization. But the following trick definitely wasn't. Did you notice this clumsy, old-school loop?

```private List<Board> nextMoves() {
List<Board> next = new ArrayList<>(Direction.values().length);
for (Direction dir : Direction.values()) {
final Board b = move(dir);
if (b != null) {
}
}
return next;
}```
It sure is ugly, compared to shiny functional stream:

```return Arrays
.stream(Direction.values())
.map(this::move)
.filter(Objects::nonNull)
.collect(toList());```
Why? Because it's twice as slow in this particular program. In general, you should prefer streams.

1. Note: I am only a hack programmer (in the bad sense, not the good sense!)

Question: Wouldn't it have made more sense to pre-define every possible move from each square up front rather then keep doing it over and over? Each square on the board would have an array of 8 valid moves (some of which would be null). Then you simply loop through the array for the current square and there is no need to determine direction and calculate which is the next square, you just go to the next memory address.

Looks like an interesting problem for me to try in Python.

1. Indeed, that sounds like a valid optimization!

2. You're working to hard. Let the computer do the work. Its not like it has better things to do...

3. Well you really don't have to do the work, you could use the computer to pre-define it...

4. This comment has been removed by the author.

2. This may get out of the realm of "brute forcing," but what if you divide the grid into four 5x5 boards, and, since the moves are valid in any orientation, solve for starting in the top left corner, and solving 5x5 such that move #25 ends in a position from which it can jump to the first row, sixth column (the starting point of the top right 5x5). Then solve for 5x5 where move #25 ends on the sixth row, fifth column (top right of the next square). Then use that same solutions, but rotated 90% to solve the bottom right quadrant, ending in position to jump to the bottom right of the bottom left quadrant and then use the same solution (rotated again) to solve the bottom left. Assuming there is a solution for those two boards, you are reducing the complexity from (100^2) * (8^100) to something slightly higher than 2 * (25^2) * (8^25). (Higher because of the constraint on the endpoint)

1. Oops. I just saw that my suggestion was also provided in the linked stackexchange problem.

2. Why not start at the third row and first column, solve it such that you end in the center square and then repeat this for all four quadrants? But not sure there exists such solution :)

3. This sounds a lot like the Knight's Tour problem. I wonder if you could apply the same heuristic that helps brute force solutions there...

Create another 10x10 board. Each cell is then pre-filled with the number of "potential" moves reachable from that square. So for example, the corners have 3 escapes, while central squares have a full 8.

Each time you visit a node, set its value to 0, and also update each potential (unvisited) hop from here, by decrementing the value in that cell. Then, recurse, but try your next hop in order of the lowest potential first.

The goal here is to avoid creating unreachable cells, by ensuring that each one is visited in order of "least able to be reached" and getting those out of the way first.

Added bonus: see if you can do a "perfect tour" by landing your final square within one hop of your initial square (a complete cycle).

1. I couldn't help it - I found some free time and had to try it.

Turns out, if you use this heuristic, there is no need to recurse at all. The algorithm never reaches a dead end. You can see my solution (in Perl) here:

https://github.com/greg-kennedy/100Hops

Thanks for the puzzle, fun to play with on an otherwise boring day.

4. You can easily construct Hamilton paths without any structure by hand. You just need to know one trick. If you have a path a-b-c-d-e-f and c is connected to f, then a-b-c-f-e-d is also a path. You can use this operation to move the end points of your path until they neighbour unfilled vertices and you can increase the length of your path. Just choose an operation which gets the end closer to unfilled vertex and if there are no such operation, just wander randomly. I constructed countless knight tours using this approach while I couldn't construct a single one before I discovered this trick.

5. Really enjoyed this post! So much I made my own version of it.
I did manage to find a solution by starting 1 in the corner:

+-----------------------+
| 1 49 22 2 17 23 3 9 24 4 |
| 88 46 19 32 40 13 26 6 14 27 |
| 21 34 42 48 35 8 16 29 37 10 |
| 44 50 89 45 18 31 39 12 25 5 |
| 87 47 20 33 41 67 36 7 15 28 |
| 96 91 43 51 90 82 52 30 38 11 |
| 77 72 94 78 75 60 79 68 61 58 |
| 86 100 97 83 55 66 63 56 53 64 |
| 95 92 76 71 93 81 70 59 80 69 |
| 98 73 85 99 74 84 54 65 62 57 |
+-----------------------+

Nathan's approach was used, where all the possible moves from the current cell were being tested recursively.

Its made in processing, to more easily visualize the results. code:
https://github.com/TomRoozendaal/processing-projects/tree/master/gridPuzzle

6. would you try deep learning to slove this problem?