Robert Anderson's Blog

暴力找所有解
 
http://nopaste.csie.org/c8f62

轉貼我自己 2008.6.27的文章

這次又更快了，這是從大陸那邊找來的，後來終於想通他們的原理了
他們用的是位元運算，非常快，而我將他們程式碼改了些，因為他們行跟列與我們相反
而且他們所謂的對稱性，似乎無法紀錄解答，這支程式原本也只能算出有幾組解答，目前這支基本程式是紀錄目前解答狀況，若需要記錄解答則另外建立陣列，否則刪除那段就行了
利用這些程式碼，個人成功解答了Another N Queen
#include <cstdlib>
#include <cstdio>
#define MAX 16

long sum = 0, upperlim = 1;    
long now[MAX];

int test(long, long, long, int);

int main(int argc, char *argv[])
{
   int n = 16;

   scanf("%d", &n);

   upperlim = (upperlim << n) - 1;        

   test(0, 0, 0, 0);
   printf("CASE %d: %ld combinations.\n", n, sum);
  
   system("PAUSE");
   return 0;
}

int test(long col, long ld, long rd, int row)
{
   if (col != upperlim)
   {
     long pos = upperlim & ~(col | ld | rd);
     while (pos)
     {
        long p = pos & -pos;                                             

        pos -= p;                          
       
        now[row]=p;
       
        test(col + p, (ld + p) << 1, (rd + p) >> 1, row+1);                             
       }
   }
   else  
   {
  
       sum++;
   }
}

轉貼我自己2008 8/6的文章
 
今天自己寫了一次N皇后的回溯程式，結果發現位元運算有些地方並不如我想像一般，所以今天把所有地方重新做一次整理，其中包括我之前就知道的
關於!與~
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
int main()
{
    int a=1;
    
    printf("%d %d\n", !a, ~a);
    
    system("PAUSE");
    
    return EXIT_SUCCESS;
}
本段程式碼輸出結果: 0 -2
下列以1Byte舉例
因為00000001
每位數取相反為11111110，正好為二的捕數法的-2
而!呢，只是取Boolean值的相反，跟位元運算無關
改成這樣
a=5;
   
printf("%d %d\n", !a, ~a);
將會輸出0 -6，即可證明
另外 || 、 | 與 &&、&之間的關係類似
|、&是針對每一個數字位元去做運算，而||、&&皆是布林值運算
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
int main()
{
    int a=3, b=2;
   
    printf("%d %d\n", a&&b, a||b);
       
   
    system("PAUSE");
   
    return EXIT_SUCCESS;
}
輸出結果 1 1
分解動作→3為true 2為true，則AND之後→true
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
int main()
{
    int a=3, b=2;
   
    printf("%d %d\n", a&b, a|b);
       
   
    system("PAUSE");
   
    return EXIT_SUCCESS;
}
如果是這樣的話，輸出結果 2 3
看成二進位制的運算
11 & 10 = 10 ； 11 | 10 = 11

要先寫好數字的轉換
最後再暴力解即可
 
http://nopaste.csie.org/ab6de

依照他的規定
寫出各進位的轉換函數
暴力找解答即可
 

兩個有牛的Stall之間會有一個gap
把這個gap存取起來作為紀錄
最後排序之後 用貪婪法找要丟棄的gap
 

利用拓展法
 
譬如說
abcba

貪婪的去取成本最低的牛隻就可以了～
 
程式碼好像在其他地方 翻出來後會補上

暴力解
但除了記得他限制的問題 還有數字位數問題
 
http://nopaste.csie.org/ccde3

做DFS的搜尋
然後一個Table紀錄該狀態是否出現過（在這題中過程不重要）
就可以輕鬆解答