n王后问题的优化

〇〇

newkid 发表于 2016-11-1 04:31
你11楼似乎是用一个二进制来表示两条斜线，分开左右不就行了吗，轻易就能表达30个QUEEN。
如果算法上没有 ...

知道了

〇〇

加了一个参数,可以输出结果
#include <stdio.h>
#include <stdlib.h>
int n = 12;
int q(int i, int j, int k, int l,int s[20])
{
int ans = 0;
for(int a = ((1 << n) - 1) & ~(i | j | k), p = a & -a; a!=0; a ^= p, p = a & -a)
{s[l]=p;
ans += q(i | p, (j | p) * 2, (k | p) / 2, l + 1,s);
}
if(l == n)
{
        for(int m=0;m<n;m++)
        printf("%d ",s[m]);
        printf("\n");
        }
return l == n ? 1 : ans;
}
int main(int argc,char*argv[])
{
        int t[2]={};
if (argc==2)n=atoi(argv[1]);
printf("%d\n", q(0, 0, 0, 0,t));
}

〇〇

newkid 发表于 2016-11-1 04:31
你11楼似乎是用一个二进制来表示两条斜线，分开左右不就行了吗，轻易就能表达30个QUEEN。
如果算法上没有 ...

不知道怎么分,我是把1个棋盘所有子顺序编号,最后一个格子就要2^(n*n)

〇〇

欣赏
void Nqueen(int board_size)
{
    int aQueenBitRes[MAX_BOARDSIZE]; /* results */
    int aQueenBitCol[MAX_BOARDSIZE]; /* marks colummns which already have queens */
    int aQueenBitPosDiag[MAX_BOARDSIZE]; /* marks "positive diagonals" which already have queens */
    int aQueenBitNegDiag[MAX_BOARDSIZE]; /* marks "negative diagonals" which already have queens */
    int aStack[MAX_BOARDSIZE + 2]; /* we use a stack instead of recursion */
    register int* pnStack;


    register int numrows = 0; /* numrows redundant - could use stack */
    register unsigned int lsb; /* least significant bit */
    register unsigned int bitfield; /* bits which are set mark possible positions for a queen */
    int i;
    int odd = board_size & 1; /* 0 if board_size even, 1 if odd */
    int board_minus = board_size - 1; /* board size - 1 */
    int mask = (1 << board_size) - 1; /* if board size is N, mask consists of N 1's */


    /* Initialize stack */
    aStack[0] = -1; /* set sentinel -- signifies end of stack */

    /* NOTE: (board_size & 1) is true iff board_size is odd */
    /* We need to loop through 2x if board_size is odd */
    for (i = 0; i < (1 + odd); ++i)
    {
        /* We don't have to optimize this part; it ain't the
           critical loop */
        bitfield = 0;
        if (0 == i)
        {
            /* Handle half of the board, except the middle
               column. So if the board is 5 x 5, the first
               row will be: 00011, since we're not worrying
               about placing a queen in the center column (yet).
            */
            int half = board_size>>1; /* divide by two */
            /* fill in rightmost 1's in bitfield for half of board_size
               If board_size is 7, half of that is 3 (we're discarding the remainder)
               and bitfield will be set to 111 in binary. */
            bitfield = (1 << half) - 1;
            pnStack = aStack + 1; /* stack pointer */
   
            aQueenBitRes[0] = 0;
            aQueenBitCol[0] = aQueenBitPosDiag[0] = aQueenBitNegDiag[0] = 0;
        }
        else
        {
            /* Handle the middle column (of a odd-sized board).
               Set middle column bit to 1, then set
               half of next row.
               So we're processing first row (one element) & half of next.
               So if the board is 5 x 5, the first row will be: 00100, and
               the next row will be 00011.
            */
            bitfield = 1 << (board_size >> 1);
            numrows = 1; /* prob. already 0 */

            /* The first row just has one queen (in the middle column).*/
            aQueenBitRes[0] = bitfield;
            aQueenBitCol[0] = aQueenBitPosDiag[0] = aQueenBitNegDiag[0] = 0;
            aQueenBitCol[1] = bitfield;

            /* Now do the next row.  Only set bits in half of it, because we'll
               flip the results over the "Y-axis".  */
            aQueenBitNegDiag[1] = (bitfield >> 1);
            aQueenBitPosDiag[1] = (bitfield << 1);
            pnStack = aStack + 1; /* stack pointer */
            *pnStack++ = 0; /* we're done w/ this row -- only 1 element & we've done it */
            bitfield = (bitfield - 1) >> 1; /* bitfield -1 is all 1's to the left of the single 1 */
        }

        /* this is the critical loop */
        for (;
        {
            /* could use
               lsb = bitfield ^ (bitfield & (bitfield -1));
               to get first (least sig) "1" bit, but that's slower. */
            lsb = -((signed)bitfield) & bitfield; /* this assumes a 2's complement architecture */
            if (0 == bitfield)
            {
                bitfield = *--pnStack; /* get prev. bitfield from stack */
                if (pnStack == aStack) { /* if sentinel hit.... */
                    break ;
                }
                --numrows;
                continue;
            }
            bitfield &= ~lsb; /* toggle off this bit so we don't try it again */

            aQueenBitRes[numrows] = lsb; /* save the result */
            if (numrows < board_minus) /* we still have more rows to process? */
            {
                int n = numrows++;
                aQueenBitCol[numrows] = aQueenBitCol[n] | lsb;
                aQueenBitNegDiag[numrows] = (aQueenBitNegDiag[n] | lsb) >> 1;
                aQueenBitPosDiag[numrows] = (aQueenBitPosDiag[n] | lsb) << 1;
                *pnStack++ = bitfield;
                /* We can't consider positions for the queen which are in the same
                   column, same positive diagonal, or same negative diagonal as another
                   queen already on the board. */
                bitfield = mask & ~(aQueenBitCol[numrows] | aQueenBitNegDiag[numrows] | aQueenBitPosDiag[numrows]);
                continue;
            }
            else
            {
                /* We have no more rows to process; we found a solution. */
                /* Comment out the call to printtable in order to print the solutions as board position*/
                printtable(board_size, aQueenBitRes, g_numsolutions + 1);  
                ++g_numsolutions;
                bitfield = *--pnStack;
                --numrows;
                continue;
            }
        }
    }

    /* multiply solutions by two, to count mirror images */
    g_numsolutions *= 2;
}

〇〇

8.1 8.2就是queen

newkid

〇〇 发表于 2016-11-1 19:27
不知道怎么分,我是把1个棋盘所有子顺序编号,最后一个格子就要2^(n*n)

没有必要一个格子用一个二进制位。用十进制编号就可以。
需要用二进制的是那些独占的地方。你已经处理了行，绝对不会同行，所以只需用一个位表示列坐标(0-7)，8*8棋盘需要13条左斜线和13条右斜线。这几样东西用三个二进制数来表示，检查占用的时候用三个BITAND操作。

〇〇

newkid 发表于 2016-11-1 22:13
没有必要一个格子用一个二进制位。用十进制编号就可以。
需要用二进制的是那些独占的地方。你已经处理了 ...

我试试

〇〇

〇〇 发表于 2016-11-1 20:11
8.1 8.2就是queen

美观

第92种方案(★表示皇后):
  ▁▁▁▁▁▁▁▁
▕█  █  █  █★▏
▕  █  ★  █  █▏
▕★  █  █  █  ▏
▕  █★█  █  █▏
▕█  █  █★█  ▏
▕  ★  █  █  █▏
▕█  █  █  ★  ▏
▕  █  █★█  █▏
  ▔▔▔▔▔▔▔▔

〇〇

newkid 发表于 2016-11-1 22:13
没有必要一个格子用一个二进制位。用十进制编号就可以。
需要用二进制的是那些独占的地方。你已经处理了 ...

n=16,左斜线也有31条了

〇〇

〇〇 发表于 2016-11-1 19:28
欣赏
void Nqueen(int board_size)
{

原来重点不是递归，而是取半个盘，然后翻转