棋盤演算法
Ⅰ 圍棋的計算方法
這個計算比較抽象，大體上可以分為計算價值和計算變化。
圍棋是一種以佔地多少來比較勝負的游戲，所以從一開局，雙方就盡可能的多佔地。從布局（開局）始，雙方就挑選棋盤上價值大的點，輪流著子。這種判斷為價值大的點，在圍棋術語中稱為「大場」。打個比方說，有兩個人一起分一堆錢，而錢的面值不一，規定雙方每次只能拿一張鈔票。無疑雙方都會挑選當前余額中面值最大的一張。當然棋盤上每個點並沒有做價值大小的標志，這個價值需要棋手進行計算來判明。這種計算過程，一直貫徹棋局始終，直至官子（終局）階段。
棋局的進行，如果雙方都對自己的佔地滿意，平穩進行是一種可能，還有很大的可能，是一方對「分贓」狀況不滿了——或者是我能力強，應該分得更多；或者是不滿對方獲利太大——這個時候會挑起戰斗，戰斗的時候需要計算變化。計算在什麼樣的周圍環境、手段下，戰斗的成功性會較大。進行到最後的對殺（互相收氣以殺死對方），精確的計算，可能會幫助你直接屠龍獲勝。
最後順便說下計算勝負：棋盤上共361個點。考慮到黑方先行得利，所以現行規則，黑方須貼還3又3/4子、7目半、或者8點不等，然後計算勝負。這里的計算已經是「判定」的概念，只要逐個計數就可以了。
Ⅱ 一道棋盤演算法問題！用（c++）
真巧，pku 1753就是這題。。
前幾天ICPC訓練的時候還寫過，現在懶得再寫了，要用到bfs，我幫你找到了這題的解題報告，你看看吧：
解題思路：
BFS 即寬搜
因為這題說要找出最小值，也就是求最優值問題，那麼，很快就可以想到DP 或者
搜索，而這題很難想出階段以及狀態，所以，構造DP的解法是比較困難的，至於
到底可不可以用DP，我也沒有繼續深思過，所以，我就想到直接搜索，把所有走法
都模擬出來，然後，哪種走法最快能夠實現全盤為白或黑，則答案就出來了！
搜索有BFS和DFS兩種，而BFS有能夠求出最優值的特點，故考慮用BFS！
方法：
如果把走第i步之前，盤子上所有棋子構成的狀態記為S（i-1），並且，初始狀態
記為S（0）。而且，可以發現每走一步時，在棋盤上都有4*4=16中選擇！但，當
如果盤子上出現的狀態在之前也出現過，那麼，就可以不用再繼續走了！（即剪枝）
我們從第一步開始。。。
把走完第一步後盤子的所有狀態都保存起來，如果用
很多個二維數組來保存這些狀態就浪費空間了，並且，在之後的要尋找當前狀態是否
已經出現過，也會出現麻煩！想一想，因為棋子是黑白兩面，可以等價為「0」和「1」
兩種性質，那麼如果用一個一維數組保存起來的話，例如：
bwwb
bbwb
bwwb
bwww 1001110110011000
那麼很快又可以發現另一個特點，圖只有2^16個狀態。
然後，開一個數組sign[65535]標記已經訪問過的狀態，則問題就迎刃而解了！
我的程序：
Problem: 1753 User: jlthero
Memory: 504K Time: 32MS
Language: C++ Result: Accepted
Source Code
#include<stdio.h>
#include<string.h>
#include<vector>
#include<iostream>
using namespace std;
char piece[5][5];
int bina[16];
int sign[65536];
int ans;
int toint()
{
int value=0;
int i;
for(i=15;i>=0;i--)
{
value=value*2;
value+=bina[i];
}
return value;
}
void tochar(int n)
{
int i;
for(i=0;i<16;i++)
{
bina[i]=n%2;
n=n/2;
}
}
void slip(int i)
{
bina[i]=1-bina[i];
if(i%4!=0)
bina[i-1]=1-bina[i-1];
if(i%4!=3)
bina[i+1]=1-bina[i+1];
if(i-4>=0)
bina[i-4]=1-bina[i-4];
if(i+4<16)
bina[i+4]=1-bina[i+4];
}
int DFS()
{
vector<int>quene;
int i=0,j;
int value0,value1;
value0=toint();
if(value0==0||value0==65535)
return 0;
else if(sign[value0]==0)
{
quene.push_back(value0);
sign[value0]=1;
}
while(i<quene.size())
{
value0=quene[i];
tochar(value0);
for(j=0;j<16;j++)
{
slip(j);
value1=toint();
if(value1==0||value1==65535)
return sign[value0];
else if(sign[value1]==0)
{
quene.push_back(value1);
sign[value1]=sign[value0]+1;
}
slip(j);
}
i++;
}
return -1;
}
int main()
{
int i,j;
int t,ans;
while(scanf("%s %s %s %s",piece[0],piece[1],piece[2],piece[3])!=EOF)
{
for(i=0;i<4;i++)
{
t=i*4;
for(j=0;j<4;j++)
bina[t+j]=(piece[i][j]=='b'?1:0);
}
memset(sign,0,sizeof(sign));
ans=DFS();
if(ans==-1)
printf("Impossible\n");
else
printf("%d\n",ans);
}
return 0;
}
下面是王熾輝師兄的代碼，代碼長度要比我短很多^_^：
Problem: 1753 User: wangchi
Memory: 148K Time: 30MS
Language: C Result: Accepted
Source Code
#include<stdio.h>
#include<string.h>
#define MAX 1000000
int a[16], b[16], min;
char ch[4][5];
int legal()
{
int i, t, sum;
static int k = -1;
t = (a[0] + b[0] + b[1] + b[4]) % 2;
for(i = 1; i < 16; i++){
sum = a[i] + b[i];
if(i%4 != 0) sum += b[i-1];
if(i%4 != 3) sum += b[i+1];
if(i-4 >= 0) sum += b[i-4];
if(i+4 < 16) sum += b[i+4];
if(sum % 2 != t) return 0 ;
}
return 1;
}
void dfs(int i, int num)
{
if(i==16) {
if(min > num && legal()) min = num;
return;
}
b[i] = 0;
dfs(i+1, num);
b[i] = 1;
dfs(i+1, num+1);
}
int main()
{
int i, j, t;
while(scanf("%s%s%s%s", ch[0], ch[1], ch[2], ch[3]) != EOF){
for(i = 0; i < 4; i++){
t = i * 4;
for(j = 0; j < 4; j++)
a[t+j] = (ch[i][j]=='w')?0:1;
}
min = MAX;
dfs(0, 0);
if(min == MAX) printf("Impossible\n");
else printf("%d\n", min);
}
return 0;
}
Ⅲ 棋盤覆蓋問題的演算法實現
下面討論棋盤覆蓋問題中數據結構的設計。
（1）棋盤：可以用一個二維數組board[size][size]表示一個棋盤，其中，size=2^k。為了在遞歸處理的過程中使用同一個棋盤，將數組board設為全局變數；
（2）子棋盤：整個棋盤用二維數組board[size][size]表示，其中的子棋盤由棋盤左上角的下標tr、tc和棋盤大小s表示；
（3）特殊方格：用board[dr][dc]表示特殊方格，dr和dc是該特殊方格在二維數組board中的下標;
（4） L型骨牌：一個2^k×2^k的棋盤中有一個特殊方格，所以，用到L型骨牌的個數為(4^k-1)/3，將所有L型骨牌從1開始連續編號，用一個全局變數t表示。
設全局變數t已初始化為0，分治法求解棋盤覆蓋問題的演算法用C++語言描述如下：
void ChessBoard(int tr, int tc, int dr, int dc, int size)
{
int s, t1; //t1表示本次覆蓋所用L型骨牌的編號
if (size == 1) return; //棋盤只有一個方格且是特殊方格
t1 = ++t; // L型骨牌編號
s = size/2; // 劃分棋盤
if (dr < tr + s && dc < tc + s) //特殊方格在左上角子棋盤中
ChessBoard(tr, tc, dr, dc, s); //遞歸處理子棋盤
else{ //用 t1號L型骨牌覆蓋右下角，再遞歸處理子棋盤
board[tr + s - 1][tc + s - 1] = t1;
ChessBoard(tr, tc, tr+s-1, tc+s-1, s);
}
if (dr < tr + s && dc >= tc + s) //特殊方格在右上角子棋盤中
ChessBoard(tr, tc+s, dr, dc, s); //遞歸處理子棋盤
else { //用 t1號L型骨牌覆蓋左下角，再遞歸處理子棋盤
board[tr + s - 1][tc + s] = t1;
ChessBoard(tr, tc+s, tr+s-1, tc+s, s);
}
if (dr >= tr + s && dc < tc + s) //特殊方格在左下角子棋盤中
ChessBoard(tr+s, tc, dr, dc, s); //遞歸處理子棋盤
else { //用 t1號L型骨牌覆蓋右上角，再遞歸處理子棋盤
board[tr + s][tc + s - 1] = t1;
ChessBoard(tr+s, tc, tr+s, tc+s-1, s);
}
if (dr >= tr + s && dc >= tc + s) //特殊方格在右下角子棋盤中
ChessBoard(tr+s, tc+s, dr, dc, s); //遞歸處理子棋盤
else { //用 t1號L型骨牌覆蓋左上角，再遞歸處理子棋盤
board[tr + s][tc + s] = t1;
ChessBoard(tr+s, tc+s, tr+s, tc+s, s);
}
}
Ⅳ 馬踏棋盤的演算法
將馬隨機放在國際象棋的Board[0～7][0～7]的某個方格中，馬按走棋規則進行移動。，走遍棋盤上全部64個方格。編制非遞歸程序，求出馬的行走路線，並按求出的行走路線，將數字1，2，…，64依次填入一個8×8的方陣，輸出之。
Ⅳ 棋盤覆蓋問題的演算法分析
設T(k)是演算法ChessBoard覆蓋一個2^k×2^k棋盤所需時間，從演算法的劃分
策略可知，T(k)滿足如下遞推式：
T(k) = 1 當k=0時
T(k) = 4T(k-1) 當k>0時
解此遞推式可得T(k)=O(4^k)。
Ⅵ 求8x8棋盤完美覆蓋的演算法
如果用1*2覆蓋的話
任意一塊骨牌在棋盤上的擺放都可以用一串長度為64的0、1序列來表示，比如
……0——>表示在棋盤最左上角的位置橫著擺上一塊骨牌。
考慮到骨牌既可以橫著擺也可以豎著擺，一塊骨牌在棋盤上的擺放共有2*7*8=112種情況.
這樣就可以得到一個112*60大小的矩陣，不妨將該矩陣記為A。矩陣中的元素由0和1組成，矩陣中的每一行都有且只有兩個1。
於是上述問題，就轉換成怎樣從矩陣中找出32行，抽取出來的這32行構成的新的32*60的矩陣，如果能滿足每列中有且只有一個1，那麼它就是一個完美覆蓋。
矩陣的演算法如下：
如果矩陣A為空且已經選出了32行，則找到一個完美覆蓋，成功返回；
否則選取一個列c，如果c列中不存在1的話，不成功返回;
選擇C列中每一個滿足A[r,c]=1的行r;
將r值作為解決方案的一個步驟記錄下來；
對於r行中每一個A[r,j]=1的j值，從矩陣A中將第j列刪除;
對於j列中每一個A[i,j]=1的i值，從矩陣A中將第i行刪除;
將已經縮小的矩陣重復進行上面的運算。