Fuzix-Compiler-Kitの6800用コンパイラ(7)（ベーシックマスター開発 その41）

2024/11/26BASICMASTER, 昔のパソコン

Fuzix-Compiler-Kitの6800用コンパイラ(6)（ベーシックマスター開発 その38） | ず＠沖縄に続いてコードの比較。今度は騎士巡歴問題。

騎士巡歴問題

チェスのナイトを動かして、盤面全部を巡回できるか？という問題。

プログラム

こちらも再帰呼び出しを多用している。大昔のFORTRANとかBASICは再帰呼び出しができなかったので、再帰呼び出しをするプログラムというだけでも珍しかった。

#include	"common.h"

#define N	(8)
#define NN	(8*8)
#define NP	(8*8-2)
unsigned char board[16][16];
char dx[8] = { 2, 1,-1,-2,-2,-1, 1, 2 };
char dy[8] = {  1, 2, 2, 1,-1,-2,-2,-1 };
int	count = 0;
int solution = 0;

void
printboard() 
{
	unsigned char i,j;
    putstr("\nSolution ");print(++solution);putch('\n');
    for (i = 2; i <= N + 1; i++) {
        for (j = 2; j <= N + 1; j++) {
			if(board[i][j]>=10){
				putch(board[i][j]/10+'0');
			}else{
				putch(' ');
			}
			putch(board[i][j]%10+'0');
			putch(' ');
		}
		putch('\n');
    }
	putstr("count=");
	if(count>10){
		putch(count/10+'0');
	}
	putch(count%10+'0');
	putch('\n');
	exit(0);
}


#define	check(cx,cy,x1,y1,x2,y2)	(x==cx+2 && y==cy+2 && board[x1+2][y1+2]==0 && board[x2+2][y2+2]==0)

void
test(unsigned char x, unsigned char y)
{
	unsigned char i;
	unsigned char nx,ny;

	if (board[x][y])	return;
    board[x][y] = ++count;
    if (count == NN){
		cpu_counter();
		printboard();
	}else{
//		if(count>NP){
//			printboard();
//		}
		// TODO: now only 8x8 size, try another.
		if(check(2,1,0,0,1,2)){
			test(0+2,0+2);
		}else if(check(1,2,0,0,2,1)){
			test(0+2,0+2);
		}else if(check(5,1,7,0,6,2)){
			test(7+2,0+2);
		}else if(check(6,2,7,0,5,1)){
			test(7+2,0+2);
		}else if(check(1,5,0,7,2,6)){
			test(0+2,7+2);
		}else if(check(2,6,0,7,1,5)){
			test(0+2,7+2);
		}else if(check(5,6,7,7,6,5)){
			test(7+2,7+2);
		}else if(check(6,5,7,7,5,6)){
			test(7+2,7+2);
		}else{	
			for (i = 0; i < 8; i++){
				nx = x+dx[i];
				if(nx<2 || nx>9)	continue;
				ny = y+dy[i];
				if(ny<2 || ny>9)	continue;
				if (board[nx][ny]==0){
					test(nx,ny);
				}
			}
		}
	}
    board[x][y] = 0;
	count--;
}

void
knight(unsigned char x, unsigned char y)
{
	unsigned char 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;
		}
	}
    test(x,y);
}

int main(int argc, char *argv[])
{
	cpu_counter();
	knight(2,2);
}

速度比較

最初の頃と比べると、実行時間は1/4以下になっている。

コード比較

このプログラムでは縦8横8のチェスボードの周りに番兵を置いて縦横10マスの配列を使っているが、高速になるようにサイズを16x16にしている。

新しいコンパイラは定数乗算をシフト命令の組み合わせに置き換えるので、配列アクセスが高速になっている。

配列サイズが256以下なので、計算はlslbだけ済むはずだが、16bit演算になっているのは惜しい（というか、仕方がない）。

        tsx
        ldb 0,x
        clra
-       pshb
-       psha
-       ldab #16
-       jsr __mul
+       lslb
+       rola
+       lslb
+       rola
+       lslb
+       rola
+       lslb
+       rola
        addb #<_board+0
        adca #>_board+0
        pshb
        psha

この他の差は、前回の8queenとほぼ同様。条件分岐のヘルパー関数呼び出しが重たいんだよなあ。