フォト
無料ブログはココログ

« 「知っていること」と「できること」 | トップページ | D7849 »

2011年9月15日 (木)

8Queen

 8Queen問題のプログラムを書いてみた.
 8Queen問題といえば,再帰プログラムということで再帰で書いたのだが8051/31は内臓RAMが少ないので関数のネストが深くなる再帰プログラムには厳しい.

DATAとSTACKをXRAMに移したのだがスタックが足りない.ようだ


--- 8queen.mem --
Internal RAM layout:
      0 1 2 3 4 5 6 7 8 9 A B C D E F
0x00:|0|0|0|0|0|0|0|0|a|b|c|c|c|c|c|c|
0x10:|c|c|d|e|e| | | | | | | | | | | |
0x20:|B|T|I|I|I|I|I|I|I|I|I|I|I|I|S|S|
0x30:|S|S|S|S|S|S|S|S|S|S|S|S|S|S|S|S|
0x40:|S|S|S|S|S|S|S|S|S|S|S|S|S|S|S|S|
0x50:|S|S|S|S|S|S|S|S|S|S|S|S|S|S|S|S|
0x60:|S|S|S|S|S|S|S|S|S|S|S|S|S|S|S|S|
0x70:|S|S|S|S|S|S|S|S|S|S|S|S|S|S|S|S|
0x80:| | | | | | | | | | | | | | | | |
0x90:| | | | | | | | | | | | | | | | |
0xa0:| | | | | | | | | | | | | | | | |
0xb0:| | | | | | | | | | | | | | | | |
0xc0:| | | | | | | | | | | | | | | | |
0xd0:| | | | | | | | | | | | | | | | |
0xe0:| | | | | | | | | | | | | | | | |
0xf0:| | | | | | | | | | | | | | | | |
0-3:Reg Banks, T:Bit regs, a-z:Data, B:Bits, Q:Overlay, I:iData, S:Stack, A:Absolute

 よく見てみると,使った覚えはないiDataやBitsが使われている.(20h-2Dh)
 調べたところ,ライブラリで使われているようで,printf_small()をprintf()に変えると95byte使えるようになった.
 できたバイナリはかなり大きいが,CODEにSTACKは代えられない.

-- 8queen.c ---
Internal RAM layout:
      0 1 2 3 4 5 6 7 8 9 A B C D E F
0x00:|0|0|0|0|0|0|0|0|a|b|b|c|d|e|e| |
0x10:| | | | | | | | | | | | | | | | |
0x20:|T|S|S|S|S|S|S|S|S|S|S|S|S|S|S|S|
0x30:|S|S|S|S|S|S|S|S|S|S|S|S|S|S|S|S|
0x40:|S|S|S|S|S|S|S|S|S|S|S|S|S|S|S|S|
0x50:|S|S|S|S|S|S|S|S|S|S|S|S|S|S|S|S|
0x60:|S|S|S|S|S|S|S|S|S|S|S|S|S|S|S|S|
0x70:|S|S|S|S|S|S|S|S|S|S|S|S|S|S|S|S|
0x80:| | | | | | | | | | | | | | | | |
0x90:| | | | | | | | | | | | | | | | |
0xa0:| | | | | | | | | | | | | | | | |
0xb0:| | | | | | | | | | | | | | | | |
0xc0:| | | | | | | | | | | | | | | | |
0xd0:| | | | | | | | | | | | | | | | |
0xe0:| | | | | | | | | | | | | | | | |
0xf0:| | | | | | | | | | | | | | | | |
0-3:Reg Banks, T:Bit regs, a-z:Data, B:Bits, Q:Overlay, I:iData, S:Stack, A:Absolute

ようやく通った
8queen
再帰呼び出しする関数は次のとおりである. が...
char place(char x, char y) __reentrant {
    static char n = 1;     if (check(x,y)) {
        table[y] = x;
        if (y==7) {
            printtb(n++);
            return FALSE;
        } else {
            if (place(0, y+1)) {
                return TRUE;
            } else {
                table[y] = 0xff;
                if (x==7)
                        return FALSE;
                else    return place(x+1,y);
                }
            }
    } else {
        if (x==7)
                return FALSE;
        else    return place(x+1, y);
    }
}

ほんとうはこうしたいのだが, 再帰レベルが増えるのでスタックが足りなくなる.

char place(char x, char y) __reentrant {
    static char n = 1;
    if (7<=y) {  /* 解 */
        printtb(n++);
        return FALSE;
    }
    if (7<=x) {  /* 見つからない */
        return FALSE;
    }
    if (check(x,y)) {
        table[y] = x;
        place(0, y+1);
        table[y] = (u_char)-1;
    }
    return place(x+1, y);
}

« 「知っていること」と「できること」 | トップページ | D7849 »

8031/8052 SBC」カテゴリの記事

プログラミング」カテゴリの記事

コメント

コメントを書く

コメントは記事投稿者が公開するまで表示されません。

(ウェブ上には掲載しません)

トラックバック


この記事へのトラックバック一覧です: 8Queen:

« 「知っていること」と「できること」 | トップページ | D7849 »

2020年9月
    1 2 3 4 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30      

最近のトラックバック