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

ようやく通った


再帰呼び出しする関数は次のとおりである.　が...

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);
}