----------------------------------
【注意】以下の文章は昨日以前に書かれましたが、本朝（2025年6月15日）悪戦苦闘は解消されましたので、書かれている内容の一部（赤下線）に事実誤認があります。このシリーズの最後に「真犯人」が明らかにされますが、それを踏まえてお読みください。
----------------------------------
前回、C#のウィンドウプログラムに導入するベースプログラムとして、昔入力したC言語のプログラム（注）を選定しました。
注：「今を去る半世紀弱の昔、私がC言語（C++ではないですよ！）を学び始めた1986年に購入して勉強した「実戦Cプログラミング」（略）にあったC言語による8パズルの解法プログラム．．．ソースコードがあるといっても、当時のプログラムは表記が現在とはやや異なり、メモリー対策からコメントも限定されているために、正直内容を理解せずに本からインプットしただけものであることから、改めてその内容を理解することから始めました。」
前回も「一見親類かと思うけど、実は素性は結構違う」とかきましたが、似て非なるとはまさにこのこと、と言えるＣとC#の違い（基本的にそのメモリー管理と参照渡し、値渡しの問題なんですが．．．）から、とうとう「悪戦苦闘の上、一旦すべて白紙に戻し、C#用に再設計する所からやり直す」ことを決定しました。
そんな訳で、
当該Cプログラムは、「考え方」と「処理フロー」を参考にする形にとどめるわけですが、今までの試行錯誤の歴史が少しは皆さんに役に立つかと、または単にブログテーマとして腹を抱えて笑っていただけるかと思い、私の悪戦苦闘の有り様も書いてゆこうかと思います。先ず今回はオリジナルのコードの紹介から。（これを一目見て何をしているのか、が分かる方はすごいと思いますよ。又本当のオリジナルは、
void foo(a, b, c)
int a; char* b; double c; {
...
}
の様な記法を採っていましたが、これは現代風に改めています。又当時の変数をどのようにメモリーやCPUに置くか、という指定のautoとかregisterを使いましたが、これも改めています。）
【8Puzzle.c】
#include <stdio.h>
struct BOARD {
char cell[9];
struct BOARD *next; /* Link to the scenario on the same level */
struct BOARD *back; /* Link to the parent scenario */
};
/* Initial state */
struct BOARD BO = {
2, 3, 5, 7 ,1, 6, 4, 8, 0, NULL, NULL
};
/* State at goal */
struct BOARD BG = {
1, 2, 3, 4 ,5, 6, 7, 8, 0, NULL, NULL
};
struct BOARD *q0 = NULL, *q1 = &BO, *q2 = NULL;
void printboard(struct BOARD* b) {
int i;
for(i = 0; i < 9; i++) {
printf("%1d", b->cell[i]);
if(i % 3 == 2)
putchar('\n');
}
putchar('\n');
}
void traceback(struct BOARD* b) {
int i = 0;
for(; b != NULL; b = b->back) printboard(b);
}
bool equal(struct BOARD* b1, struct BOARD* b2) {
int i;
for(i = 0; i < 9; i++) {
if(b1->cell[i] != b2->cell[i]) return 0;
}
return 1;
}
void putq(struct BOARD* b) {
struct BOARD* n;
for(n = q0; n != NULL; n = n->next)
if(equal(b, n)) {free(b); return;}
if(q2 == NULL) q2 = b;
else {
for(n = q2; n->next != NULL; n = n->next) {
if(equal(b, n)) {free(b); return;}
n->next = b;
}
}
void exchange(struct BOARD* b, int i, int j) {
struct BOARD *m;
m = (struct BOARD*) malloc(sizeof(struct BOARD));
if(m == NULL) {
printf("Memory overflow!\n");
exit(2);
}
int k;
for(k = 0; k < 9; k++) m->cell[k] = b->cell[k];
m->cell[i] = b->cell[j];
m->cell[j] = 0;
m->back = b;
m->next = NULL;
if(equal(m, &BG)) {traceback(m); exit(0);}
putq(m);
}
void expand(struct BOARD* b) {
int i;
for(i = 0; i < 9; i++) /* Looking for where "0" is */
if(b->cell[i] == 0) break;
if(i > 2) exchange(b, i, i - 3); /* Above */
if(i % 3 > 0) exchange(b, i, i - 1); /* Left */
if(i % 3 < 2) exchange(b, i, i + 1); /* Right */
if(i < 6) exchange(b, i, i + 3); /* Below */
}
int main(int argc, char** argv) {
struct BOARD *b;
while(q1 != NULL) {
for(b = q1; b != NULL; b = b->next) expand(b);
q0 = q1; q1 = q2; q2 = NULL;
}
}
ここ迄読んで、「なんのこっちゃ？」と思われた方、今後もっとコメントを増やして、日本語で何をやっているのかを私の修正プログラムと共に解説しますから、今回はかる～～～～く眺めるつもりで結構ですよ。