A King's Hamiltonian Tours

Question

a) Place the numbers 1 to 25 in the cells of a 5 x 5 board in such a way that consecutive numbers occur in adjacent cells either vertically, horizontally, or diagonally, and so do cells with numbers 1 and 25. Numbers in the nine cells belonging to the board's two diagonals should all be prime.

b) Can such a placement be also achieved with numbers 2 to 37 in the cells of a 6 x 6 board? Again, numbers in the twelve cells belonging to the board's two diagonals should all be prime.

Answer 1

One solution to part A:

02 01 21 20 19
25 03 22 17 18
04 24 23 15 16
06 05 14 13 12
07 08 09 10 11

Answer 2

Solution for the $5$x$5$ grid

11 12 15 16 17
10 13 14 19 18
  9 24 23 22 20
  8   5 25   3 21
  7   6   4   1   2

Other solutions for the same grid are

Any rotations or reflections of the above solution as the requirements don't prevent those. We can also get a new solution by exchanging many pairs of numbers. For example we can swap the 14 and 15 in the above solution to get another valid solution.
11 12 14 16 17
10 13 15 19 18
  9 24 23 22 20
  8   5 25   3 21
  7   6   4   1   2

Via computer search I found 264 solutions in total. This was done with a standard depth first search, with the constraints that no composite numbers can be placed on a diagonal line, and since there are only 9 primes, primes can only be placed along a diagonal.

For the $6$x$6$ grid I noted that

As the numbers 2, 3, and 37 are prime, they must all lie along the diagonals. As they are 'consecutive' the 2 cannot go in a corner, as there is only one connecting square that can take a prime, whereas we need two of them. This limits the starting position to
_ _ _ _ _ _
_ X _ _ X _
_ _ X X _ _
_ _ X X _ _
_ X _ _ X _
_ _ _ _ _ _

This leads to this conclusion for the $6$x$6$ grid

Just like above rotations, reflections and some exchanges give rise to other solutions once we have one. Using the same computer search as above with the same constraints gives a total of 128 solutions. For instance
23 24 25 27 28 29
22   5   6 26 31 30
21   4 37   7   8 32
20 36   3   2 33   9
18 19 35 34 13 10
17 16 15 14 12 11

I didn't find any solution where the 2 was not in the centre $2$x$2$ region of the grid, but I don't have a piece of logic that eliminates that possibility.

Answer 3

A solution for part B:

11 12 14 15 16 17
10 13 34 35 19 18
09 33 02 03 36 20
32 08 07 37 04 21
30 31 26 06 05 22
29 28 27 25 24 23