ハノイの塔は、棒に刺さっている大きさが異なる複数の円盤を、次の規則に従ってほかの棒に移動させるパズルです。
ハノイの塔を解くプログラムを作ってください。
1 から 9 までの数字を順番に並べ、間に + と - を補って 100 になる式を作ってください。1 の前に - 符号はつけないものとします。
例 : 1 + 2 + 3 - 4 + 5 + 6 + 78 + 9 = 100
パズルの世界では、1 から 9 までの数字を 1 個ずつすべて使った数字を「小町数」といいます。たとえば、123456789 とか 321654987 のような数字です。「小町算」というものもあり、たとえば 123 + 456 + 789 とか 321 * 654 + 987 のようなものです。この問題は小町算の中でも特に有名なパズルです。
パズルの世界では小町数に 0 を加えた数を大町数といいます。そして、0 から 9 までの 10 個の数字を 1 個ずつ使った計算を大町算といいます。ただし、0123456789 のように最上位の桁に 0 を入れることはできません。それでは問題です。
Ｃ言語でプログラムを作る場合、大町数は整数 (int) の範囲を超えますが、long long int を使えば簡単です。
計算式の数字を文字や記号に置き換えて、それを元の数字に戻すパズルを「覆面算」といいます。異なる文字は異なる数字を表し、同じ文字は同じ数字を表します。使用する数字は 0 から 9 までで、最上位の桁に 0 を入れることはできません。それでは問題です。
S E N D
+ M O R E
-------------
M O N E Y
図 : 覆面算
問題はデュードニーが 1924 年に発表したもので、覆面算の古典といわれる有名なパズルです。
┌─┬─┬─┐ 式
│Ａ│Ｂ│Ｃ│ A + B + C = N, A + E + I = N
├─┼─┼─┤ D + E + F = N, C + E + G = N
│Ｄ│Ｅ│Ｆ│ G + H + I = N
├─┼─┼─┤ A + D + G = N
│Ｇ│Ｈ│Ｉ│ B + E + H = N
└─┴─┴─┘ C + F + I = N
図 : 魔方陣
上図の A から I の場所に 1 から 9 までの数字をひとつずつ配置します。縦横斜めの合計が等しくなるように数字を配置してください。
「8 クイーン」はコンピュータに解かせるパズルの中でも特に有名な問題です。このパズルは 8 行 8 列のチェス盤の升目に、8 個のクイーンを互いの利き筋が重ならないように配置する問題です。クイーンは将棋の飛車と角をあわせた駒で、縦横斜めに任意に動くことができます。解答の一例を下図に示します。
列
1 2 3 4 5 6 7 8
*-----------------*
1 | Q . . . . . . . |
2 | . . . . Q . . . |
3 | . . . . . . . Q |
行 4 | . . . . . Q . . |
5 | . . Q . . . . . |
6 | . . . . . . Q . |
7 | . Q . . . . . . |
8 | . . . Q . . . . |
*-----------------*
図 : 8 クイーンの解答例
8 クイーンを解くプログラムを作ってください。
ナイト (騎士) はチェスの駒のひとつで将棋の桂馬の動きを前後左右にとることができます。次の図を見てください。
┌─┬─┬─┬─┬─┐ ┌─┬─┬─┬─┬─┐
│ │●│ │●│ │ │Ｋ│ │ │ │ │
├─┼─┼─┼─┼─┤ ├─┼─┼─┼─┼─┤
│●│ │ │ │●│ │ │ │ │ │ │
├─┼─┼─┼─┼─┤ ├─┼─┼─┼─┼─┤
│ │ │Ｋ│ │ │ │ │ │ │ │ │
├─┼─┼─┼─┼─┤ ├─┼─┼─┼─┼─┤
│●│ │ │ │●│ │ │ │ │ │ │
├─┼─┼─┼─┼─┤ ├─┼─┼─┼─┼─┤
│ │●│ │●│ │ │ │ │ │ │ │
└─┴─┴─┴─┴─┘ └─┴─┴─┴─┴─┘
● : ナイト (K) が動ける位置 問題
問題 : 騎士の巡歴
このナイトを動かして、N 行 M 列の盤面のどのマスにもちょうど一回ずつ訪れるような経路を求めるのが問題です。ちなみに、3 行 3 列、4 行 4 列の盤面には解がありませんが、5 行 5 列の盤面には解があります。5 行 5 列の盤面でナイトの移動経路の総数を求めてください。
ハノイの塔は、再帰を使えば簡単に解ける問題です。たとえば、3 枚の円盤が左の棒に刺さっているとします。この場合、いちばん大きな円盤を中央の棒に移すには、その上の 2 枚の円盤を右の棒に移しておけばいいですね。いちばん大きな円盤を中央に移したら、右の棒に移した 2 枚の円盤を中央の棒に移すことを考えればよいわけです。したがって、n 枚の円盤を左から中央の棒に移すプログラムは次のように表現できます。
これを素直にプログラムすると次のようになります。
リスト : ハノイの塔 (yacp31.c)
#include <stdio.h>
void hanoi(int n, char *from, char *to, char *via)
{
if (n == 1) {
printf("%s -> %s\n", from, to);
} else {
hanoi(n - 1, from, via, to);
printf("%s -> %s\n", from, to);
hanoi(n - 1, via, to, from);
}
}
int main(void)
{
printf("--- ３枚 ---\n");
hanoi(3, "A", "B", "C");
printf("--- ４枚 ---\n");
hanoi(4, "A", "B", "C");
return 0;
}
引数 n は動かす円盤の枚数、from は最初に円盤が刺さっている棒、to は円盤を移す棒、via は残りの棒を示します。動かす円盤の枚数が 1 枚の場合、from から to へ円盤に移動します。これが再帰の停止条件になっています。
円盤が複数枚ある場合、hanoi を再帰呼び出しして、n - 1 枚の円盤を棒 via に移動します。棒 from に残った円盤は 1 枚なので、それを棒 to に移動します。これを printf で出力します。最後に、棒 via に移した円盤を棒 to に移動します。ここでも再帰呼び出しが行われます。
プログラムはこれで完成です。それでは実行してみましょう。
$ clang yacp31.c $ ./a.out --- ３枚 --- A -> B A -> C B -> C A -> B C -> A C -> B A -> B --- ４枚 --- A -> C A -> B C -> B A -> C B -> A B -> C A -> C A -> B C -> B C -> A B -> A C -> B A -> C A -> B C -> B
それではプログラムを作りましょう。式は次のように + を '+' に、- を '-' として、整数の配列で表すことにします。
1 + 2 + 3 - 4 + 5 + 6 + 78 + 9 => [1, '+', 2, '+', 3, '-', 4, '+', 5, '+', 6, '+', 78, '+', 9]
あとは、式を生成して値を計算するだけです。次の図を見てください。
[1] => [1 + 2] => [1 + 2 + 3]
=> [1 + 2 - 3]
=> [1 + 23]
=> [1 - 2] => [1 - 2 + 3]
=> [1 - 2 - 3]
=> [1 - 23]
=> [12] => [12 + 3]
=> [12 - 3]
=> [123]
式を生成するとき、配列に数字と演算子を順番に追加していきます。数字と +, - を追加する処理は簡単です。プログラムのポイントは数字を連結する処理、たとえば 1 と 2 を連結して一つの数値 12 にする処理です。この処理は配列の末尾の数字 1 を 12 (1 * 10 + 2) に置き換えることで実現できます。配列が [1 + 2] であれば、数字 2 を 23 (2 * 10 + 3) に置き換えます。
式を生成するプログラムは次のようになります。
リスト : 式の生成
void make_expr(int n, int x, int *buff)
{
if (n == 10) {
if (calc_expr(buff, x) == 100) {
print_expr(buff, x);
}
} else {
buff[x] = '+';
buff[x + 1] = n;
make_expr(n + 1, x + 2, buff);
buff[x] = '-';
buff[x + 1] = n;
make_expr(n + 1, x + 2, buff);
int temp = buff[x - 1];
buff[x - 1] = buff[x - 1] * 10 + n;
make_expr(n + 1, x, buff);
buff[x - 1] = temp;
}
}
make_expr の引数 n が追加する数字、buff が生成する式、x が buff に書き込んだ要素の個数を表します。n が 10 の場合は、式が完成したので値を計算します。関数 calc_expr で式 buff を計算します。値が 100 になれば関数 print_expr で式を出力します。
n が 10 未満であれば、演算子 (+. -) と n を buff に追加して make_expr を再帰呼び出しします。最後が数字を連結する処理です。この場合、配列の内容を破壊的に修正するので、配列末尾の数値 buff[x - 1] を変数 temp に保存しておきます。それから、buff[x - 1] の値を buff[x - 1] * 10 + n に書き換えます。これで数字を連結することができます。make_expr を再帰呼び出しして戻ってきたら末尾の数字を元に戻します。この処理を忘れると正常に動作しません。ご注意くださいませ。
次は式を計算する calc_expr を作ります。今回の問題は演算子に + と - しかないので、配列で表現した式を計算することは簡単です。次のプログラムを見てください。
リスト : 式の計算 (+ と - だけ)
int calc_expr(int *buff, int x)
{
int sum = buff[0];
for (int i = 1; i < x; i += 2) {
switch (buff[i]) {
case '+':
sum += buff[i + 1];
break;
case '-':
sum -= buff[i + 1];
break;
default:
fprintf(stderr, "not operator %d\n", buff[i]);
exit(1);
}
}
return sum;
}
buff[0] を変数 sum にセットします。あとは、for ループの中で配列から演算子を表す文字 (buff[i]) と数値を表す文字列 (buff[i + 1]) を順番に取り出して計算します。buff[i] が '+' であれば sum に buff[i + 1] を加算し、"-" であれば sum から buff[i + 1] を減算します。
あとのプログラムは簡単なので説明は割愛します。詳細はプログラムリスト１をお読みください。
それでは実行結果を示します。
$ clang yacp32.c $ ./a.out 1 + 2 + 3 - 4 + 5 + 6 + 78 + 9 = 100 1 + 2 + 34 - 5 + 67 - 8 + 9 = 100 1 + 23 - 4 + 5 + 6 + 78 - 9 = 100 1 + 23 - 4 + 56 + 7 + 8 + 9 = 100 12 + 3 + 4 + 5 - 6 - 7 + 89 = 100 12 + 3 - 4 + 5 + 67 + 8 + 9 = 100 12 - 3 - 4 + 5 - 6 + 7 + 89 = 100 123 + 4 - 5 + 67 - 89 = 100 123 + 45 - 67 + 8 - 9 = 100 123 - 4 - 5 - 6 - 7 + 8 - 9 = 100 123 - 45 - 67 + 89 = 100
全部で 11 通りの解が出力されます。
リスト : 小町算 (yacp32.c)
#include <stdio.h>
#include <stdlib.h>
#define N 18
// 式の計算
int calc_expr(int *buff, int x)
{
int sum = buff[0];
for (int i = 1; i < x; i += 2) {
switch (buff[i]) {
case '+':
sum += buff[i + 1];
break;
case '-':
sum -= buff[i + 1];
break;
default:
fprintf(stderr, "not operator %d\n", buff[i]);
exit(1);
}
}
return sum;
}
// 式の表示
void print_expr(int *buff, int x)
{
buff[x] = '=';
for (int i = 0; i < x; i += 2)
printf("%d %c ", buff[i], buff[i + 1]);
printf("100\n");
}
// 式の生成
void make_expr(int n, int x, int *buff)
{
if (n == 10) {
if (calc_expr(buff, x) == 100) {
print_expr(buff, x);
}
} else {
buff[x] = '+';
buff[x + 1] = n;
make_expr(n + 1, x + 2, buff);
buff[x] = '-';
buff[x + 1] = n;
make_expr(n + 1, x + 2, buff);
int temp = buff[x - 1];
buff[x - 1] = buff[x - 1] * 10 + n;
make_expr(n + 1, x, buff);
buff[x - 1] = temp;
}
}
int main(void)
{
int buff[N];
buff[0] = 1;
make_expr(2, 1, buff);
return 0;
}
最初に整数 n の範囲を絞り込みます。大町数の最大値は 9876543210 で最小値は 1023456789 ですから、n の値は次の範囲内になります。
10234567891/3 => 1007.759 1006 * 1007 * 1008 => 1021146336 < 1023456789
98765432101/3 => 2145.532 2145 * 2146 * 2147 => 9883005990 > 9876543210
これらの計算結果から n は 1007 以上 2144 以下であることがわかります。n の範囲がぐっと狭くなりましたね。これならば、あとは単純に計算して大町数になるかチェックすればいいでしょう。プログラムは次のようになります。
リスト : パズル「３数で大町どうさま」の解法 (yacp33.c)
#include <stdio.h>
#include <stdbool.h>
#define N 10
void check(long long n)
{
bool used[N] = {};
long long m = n * (n + 1) * (n + 2);
for (long long x = m; x > 0; x /= 10) {
int y = x % 10;
if (used[y]) return;
used[y] = true;
}
printf("%lld * %lld * %lld = %lld\n", n, n + 1, n + 2, m);
}
int main(void)
{
for (int n = 1007; n <= 2144; n++)
check(n);
return 0;
}
関数 main で 1007 から 2144 までの数値を生成して、関数 check で大町数になるかチェックします。check は数値 n を受け取り、n * (n + 1) * (n + 2) を計算して変数 m にセットします。m は 10 桁の数値になるので、大町数であれば 10 個の数字がちょうどひとつずつあるはずです。したがって、数字が重複していないことを確認すればいいわけです。
for ループで 1 桁ずつ数字 y を取り出し、配列 used の y 番目の要素をチェックします。true であれば同じ数字があります。return で処理を終了します。false の場合は used[y] を true にセットして次の数字をチェックします。大町数の条件を満たしていれば、for ループを終了するので、最後に printf で解を出力します。
これでプログラムは完成です。さっそく実行してみましょう。
$ clang yacp33.c $ ./a.out 1267 * 1268 * 1269 = 2038719564 1332 * 1333 * 1334 = 2368591704
2 通りの解を見つけることができました。
式 SEND + MORE = MONEY は足し算なので、M が 1 であることはすぐにわかります。ここでは、それ以外の数字を求めるプログラムを作ります。次のリストを見てください。
リスト : 覆面算 (yacp34.c)
#include <stdio.h>
#include <stdbool.h>
#define N 10
// 数字
int nums[N];
bool used[N];
// 文字と添字の対応
// 0 1 2 3 4 5 6 7
// m s e n d o r y
// 1
void check(void)
{
int send = nums[1] * 1000 + nums[2] * 100 + nums[3] * 10 + nums[4];
int more = 1000 + nums[5] * 100 + nums[6] * 10 + nums[2];
int money = 10000 + nums[5] * 1000 + nums[3] * 100 + nums[2] * 10 + nums[7];
if (send + more == money)
printf("%d + %d = %d\n", send, more, money);
}
// 順列の生成
// n から m までの数字の中から k 個を選ぶ
void permutations(int n, int m, int k, int x)
{
if (x == k) {
check();
} else {
for (int i = n; i <= m; i++) {
if (!used[i]) {
used[i] = true;
nums[x] = i;
permutations(n, m, k, x + 1);
used[i] = false;
}
}
}
}
int main(void)
{
nums[0] = 1;
used[1] = true;
permutations(0, 9, 8, 1);
return 0;
}
permutations は n から m までの数字の中から k 個の数字を選ぶ順列を生成します。あとは関数 check で数値 send, more, money を計算して send + more = money を満たしているかチェックします。とても簡単なプログラムですね。さっそく実行してみましょう。
$ clang yacp34.c $ ./a.out 9567 + 1085 = 10652
答えは 9567 + 1085 = 10652 の 1 通りしかありません。興味のある方は、ほかの方法でも試してみてください。
リスト : 魔方陣の解法 (yacp35.c)
#include <stdio.h>
#include <stdbool.h>
#define N 9
// 盤面
int board[N];
bool used[N + 1];
// 直線
int lines[8][3] = {
{0, 1, 2}, {3, 4, 5}, {6, 7, 8}, {0, 3, 6},
{1, 4, 7}, {2, 5, 8}, {0, 4, 8}, {2, 4, 6},
};
// 直線の合計値を求める
int line_sum(int *board, int *pos)
{
return board[pos[0]] + board[pos[1]] + board[pos[2]];
}
// 表示
void print_board(int *board)
{
printf("%d %d %d\n", board[0], board[1], board[2]);
printf("%d %d %d\n", board[3], board[4], board[5]);
printf("%d %d %d\n\n", board[6], board[7], board[8]);
}
// 確認
void check(int *board)
{
int m = line_sum(board, lines[0]);
for (int i = 1; i < 8; i++) {
int n = line_sum(board, lines[i]);
if (m != n) return;
}
print_board(board);
}
// 順列の生成
void permutations(int n, int m)
{
if (n == m)
check(board);
else {
for (int i = 1; i <= n; i++) {
if (used[i]) continue;
board[m] = i;
used[i] = true;
permutations(n, m + 1);
used[i] = false;
}
}
}
int main(void)
{
permutations(9, 0);
return 0;
}
関数 permutations で 1 から 9 までの数字の順列を生成します。それを関数 check に渡して、魔方陣の条件を満たしているかチェックします。関数 line_sum で各直線の和を求めて、すべて同じ値であれば魔方陣の条件を満たすので、print_board で盤面を表示します。
それでは実行結果を示します。
$ clang yacp35.c $ ./a.out 2 7 6 9 5 1 4 3 8 2 9 4 7 5 3 6 1 8 4 3 8 9 5 1 2 7 6 4 9 2 3 5 7 8 1 6 6 1 8 7 5 3 2 9 4 6 7 2 1 5 9 8 3 4 8 1 6 3 5 7 4 9 2 8 3 4 1 5 9 6 7 2
対称解を含めると、解は 8 通りあります。最近のパソコンはハイスペックなので、このままでも高速に解けるのですが、対称解を排除すると枝刈りの効果により、実行時間はもう少し速くなります。興味のある方はプログラムを改良してみてください。
8 クイーンを解くには、すべての置き方を試してみるしか方法はありません。最初のクイーンは、盤上の好きなところへ置くことができるので、64 通りの置き方があります。次のクイーンは 63 通り、その次は 62 通りあるので、置き方の総数は 64 から 57 までの整数を掛け算した 178,462,987,637,760 通りもあります。
ところが、解答例を見ればわかるように、同じ行と列に 2 つ以上のクイーンを置くことはできません。上図の解答例を配列を使って表すと、 次のようになります。
1 2 3 4 5 6 7 8 <--- 列の位置
---------------------------
[1, 7, 5, 8, 2, 4, 6, 3] <--- 要素が行の位置を表す
図 : 配列での行と列の表現方法
列を配列の位置に、行番号を要素に対応させれば、各要素には 1 から 8 までの数字が重複しないで入ることになります。すなわち、1 から 8 までの順列の総数である 8! = 40320 通りの置き方を調べるだけでよいのです。パズルを解く場合、そのパズル固有の性質をうまく使って、調べなければならない場合の数を減らすように工夫することが大切です。あとは、その順列が 8 クイーンの条件を満たしているかチェックすればいいわけです。
それでは、プログラムを作りましょう。次のリストを見てください。
リスト : 8 クイーンの解法 (yacp36.c)
#include <stdio.h>
#include <stdbool.h>
#define N 16
// 盤面
int board[N];
bool used[N + 1];
// 解の個数
int count;
// 衝突の検出
bool attack(int x, int i, int m)
{
int n = 1;
for (; i < m; i++, n++) {
int y = board[i];
if (x == y + n || x == y - n) return true;
}
return false;
}
// 安全か？
bool safe(int m)
{
for (int i = 0; i < m - 1; i++) {
if (attack(board[i], i + 1, m)) return false;
}
return true;
}
void print_board(int m)
{
count++;
for (int i = 0; i < m; i++) printf("%d ", board[i]);
printf("\n");
}
// 順列の生成
void permutations(int n, int m)
{
if (n == m) {
if (safe(n)) print_board(n);
} else {
for (int i = 1; i <= n; i++) {
if (used[i]) continue;
board[m] = i;
used[i] = true;
permutations(n, m + 1);
used[i] = false;
}
}
}
int main(void)
{
permutations(8, 0);
printf("%d\n", count);
return 0;
}
関数 permutations は 1 から n までの順列を生成します。main で permutations を呼び出し、生成された順列 board が 8 クイーンの条件を満たしているかチェックします。関数 safe は board の先頭の要素から順番に衝突のチェックを行います。端にあるクイーンから順番に調べるとすると、斜めの利き筋は次のように表すことができます。
1 2 3 --> 調べる方向
*-------------
| . . . . . .
| . . . -3. . 5 - 3 = 2
| . . -2. . . 5 - 2 = 3
| . -1. . . . 5 - 1 = 4
| Q . . . . . Q の位置は 5
| . +1. . . . 5 + 1 = 6
| . . +2. . . 5 + 2 = 7
| . . . +3. . 5 + 2 = 8
*-------------
図 : 衝突の検出
図を見てもらえばおわかりのように、Q が行 5 にある場合、ひとつ隣の列は 4 と 6 が利き筋に当たります。2 つ隣の列の場合は 3 と 7 が利き筋に当たります。このように単純な足し算と引き算で、利き筋を計算することができます。この処理を関数 attack で行います。
attack は board の i 番目から斜めの利き筋に当たるか調べます。引数 x がクイーンの位置、m がクイーンの総数です。変数 n が差分を表します。for ループで board からクイーン y を取り出し、y + n または y - n が x と等しいかチェックします。等しい場合は衝突しているので true を返します。そうでなければ、次のクイーンを調べます。このとき、差分 n を +1 することをお忘れなく。すべてのクイーンを調べたら false を返します。
これでプログラムは完成です。それでは実行してみましょう。
$ clang yacp36.c $ ./a.out 1 5 8 6 3 7 2 4 1 6 8 3 7 4 2 5 1 7 4 6 8 2 5 3 ・・ 省略 ・・ 8 2 5 3 1 7 4 6 8 3 1 6 2 5 7 4 8 4 1 3 6 2 7 5 92
8 クイーンの場合、回転解や鏡像解を含めると全部で 92 通りあります。なお、このプログラムはクイーンの個数を増やすと極端に遅くなります。興味のある方はプログラムを改良してみてください。
それではプログラムを作りましょう。今回は盤面を 2 次元配列で表すことにします。この場合、騎士の移動手順は 5 行 5 列の盤面に記録したほうが簡単です。騎士が訪れていないマスを 0 とし、騎士の移動手順を 1 から始めれば、移動できるマスの判定を簡単に行うことができます。また、経路の出力も盤面を表示した方が直感的でわかりやすいかもしれません。
次は盤面の構成を考えましょう。単純な 5 行 5 列の 2 次元配列にすると、騎士が盤面から飛び出さないようにするため座標の範囲チェックが必要になります。このような場合、盤面の外側に壁を設定するとプログラムが簡単になります。
騎士は最大で 2 マス移動するので、壁の厚さも 2 マス用意します。したがって、盤面を表す配列は 9 行 9 列の大きさになります。壁に 0 以外の値 (1) を設定しておけば、騎士が盤面から飛び出して壁の位置に移動しようとしても、盤面の値が 0 ではないので実際に移動することはできません。これで騎士を移動したときの範囲チェックを省略することができます。
プログラムは次のようになります。
リスト : 騎士の巡歴 (yacp37.c)
#include <stdio.h>
// 盤面 (真ん中の 5 * 5 が盤面、ほかは壁)
int board[9][9];
// 盤面の初期化
void init_board(void)
{
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++ ) {
if (i >=2 && i < 7 && j >=2 && j < 7)
board[i][j] = 0;
else
board[i][j] = 1; // 壁
}
}
}
// 移動
int dx[8] = { 1, 2, 2, 1, -1, -2, -2, -1};
int dy[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
// 解の個数
int count;
// 盤面の表示
void print_board(void)
{
count++;
for (int i = 2; i < 7; i++) {
for (int j = 2; j < 7; j++)
printf("%2d ", board[i][j]);
printf("\n");
}
printf("\n");
}
// 解法
void solve(int n, int x, int y)
{
if (n > 25)
print_board();
else
for (int i = 0; i < 8; i++) {
int x1 = x + dx[i];
int y1 = y + dy[i];
if (board[x1][y1] == 0) {
board[x1][y1] = n;
solve(n + 1, x1, y1);
board[x1][y1] = 0;
}
}
}
int main(void)
{
init_board();
board[2][2] = 1;
solve(2, 2, 2);
printf("%d\n", count);
return 0;
}
配列 dx は騎士の x 方向の変位、配列 dy は y 方向の変位を表します。現在の座標にこの値を加えることで、次の座標を決定します。配列 board は盤面を表します。関数 init_board で、壁の部分は 1 に、実際の盤面は 0 に初期化しておきます。
関数 solve は引数として手数 n と騎士の座標 x, y を受け取ります。まず、n が 25 よりも大きくなったかチェックします。そうであれば、騎士はすべてのマスを訪れたので、print_board で盤面を出力します。
そうでなければ、次に移動するマスを選びます。for 文で dx と dy の要素を取り出して x と y の値に加え、solve を再帰呼び出しします。board は大域変数なので、再帰呼び出しから戻ってきたら、board[x1][y1] の値を 0 に戻すことをお忘れなく。あとはとくに難しいところはないと思います。
実行結果は次のようになります。
1 16 21 10 25 20 11 24 15 22 17 2 19 6 9 12 7 4 23 14 3 18 13 8 5 ・・・省略・・・ 1 16 11 6 3 10 5 2 17 12 15 22 19 4 7 20 9 24 13 18 23 14 21 8 25 304
解は全部で 304 通りあります。