騎士巡歴

 投稿者：Ｔ．Ｔ  投稿日：2010年 2月15日(月)12時56分21秒
  騎士巡歴の問題のプログラムを奥村さんの本で見かけました。このプログラムの骨格を変えずに
十進ＢＡＳＩＣで書き換えるとどうなるのでしょうか。
/***********************************************************
knight.c -- 騎士巡歴の問題
***********************************************************/
#include <stdio.h>
#include <stdlib.h>

#define N  5           /* ${\tt N} \times {\tt N}$ の番面 */

int board[N + 4][N + 4],                /* 番面 */
dx[8] = { 2, 1,-1,-2,-2,-1, 1, 2 }, /* 横変位 */
dy[8] = { 1, 2, 2, 1,-1,-2,-2,-1 }; /* 縦変位 */

void printboard(void)                   /* 番面を出力 */
{
int i, j;
static solution = 0;

printf("\n解 %d\n", ++solution);
for (i = 2; i <= N + 1; i++) {
for (j = 2; j <= N + 1; j++) printf("%4d", board[i][j]);
printf("\n");
}
}

void try(int x, int y)  /* 再帰的に試みる */
{
int i;
static int count = 0;

if (board[x][y] != 0) return;  /* すでに訪れた */
board[x][y] = ++count;
if (count == N * N) printboard();  /* 完成 */
else for (i = 0; i < 8; i++) try(x + dx[i], y + dy[i]);
board[x][y] = 0;  count--;
}

int main()
{
int i, j;

for (i = 0; i <= N + 3; i++)
for (j = 0; j <= N + 3; j++) board[i][j] = 1;
for (i = 2; i <= N + 1; i++)
for (j = 2; j <= N + 1; j++) board[i][j] = 0;
try(2, 2);
return EXIT_SUCCESS;
} 		 

Re: 騎士巡歴

 投稿者：山中和義  投稿日：2010年 2月15日(月)13時47分48秒
  > No.1033[元記事へ]

Ｔ．Ｔさんへのお返事です。

> このプログラムの骨格を変えずに十進ＢＡＳＩＣで書き換えるとどうなるのでしょうか。

Ｑ＆Ａのコーナー
　CやJavaで書かれた数値計算アルゴリズムの移植
を参考に、書き換えてみました。

これより、機械的に置き換えるパターンが見えてきます。手ごろな例題だと思います。
!「knight.c - 騎士巡歴の問題」の移植

LET N=5 !盤の大きさ

DIM board(0 TO N+3,0 TO N+3) !盤面
DIM dx(0 TO 7) !横変位
DATA 2, 1,-1,-2,-2,-1, 1, 2
MAT READ dx
DIM dy(0 TO 7) !縦変位
DATA 1, 2, 2, 1,-1,-2,-2,-1
MAT READ dy

LET solution=0 !解答数
SUB printboard !盤面を出力
   local i,j
   LET solution=solution+1
   PRINT "解"; solution
   FOR i=2 TO N+1
      FOR j=2 TO N+1
         PRINT USING "####": board(i,j);
      NEXT j
      PRINT
   NEXT i
END SUB

LET count=0 !歩数
SUB try(x,y) !再帰的に試みる
   local i
   IF board(x,y)<>0 THEN EXIT SUB !すでに訪れた
   LET count=count+1 !一歩進める
   LET board(x,y)=count
   IF count=N*N THEN !全部の路を歩いたら
      CALL printboard !完成！
   ELSE
      FOR i=0 TO 7 !８方向の候補を検証する
         CALL try(x+dx(i),y+dy(i))
      NEXT i
   END IF
   LET board(x,y)=0 !元に戻す
   LET count=count-1
END SUB

!main()
FOR i=0 TO N+3 !盤を初期化する（壁）
   FOR j=0 TO N+3
      LET board(i,j)=1
   NEXT j
NEXT i
FOR i=2 TO N+1 !（路）
   FOR j=2 TO N+1
      LET board(i,j)=0
   NEXT j
NEXT i
CALL try(2,2)

END
 

騎士巡歴

 投稿者：T.T  投稿日：2010年 2月15日(月)15時03分20秒
  山中様、丁寧なご回答をありがとうございました。
大変助かりました。 		 

戻る