棋盘算法

Ⅰ 围棋的计算方法

这个计算比较抽象，大体上可以分为计算价值和计算变化。
围棋是一种以占地多少来比较胜负的游戏，所以从一开局，双方就尽可能的多占地。从布局（开局）始，双方就挑选棋盘上价值大的点，轮流着子。这种判断为价值大的点，在围棋术语中称为“大场”。打个比方说，有两个人一起分一堆钱，而钱的面值不一，规定双方每次只能拿一张钞票。无疑双方都会挑选当前余额中面值最大的一张。当然棋盘上每个点并没有做价值大小的标志，这个价值需要棋手进行计算来判明。这种计算过程，一直贯彻棋局始终，直至官子（终局）阶段。
棋局的进行，如果双方都对自己的占地满意，平稳进行是一种可能，还有很大的可能，是一方对“分赃”状况不满了——或者是我能力强，应该分得更多；或者是不满对方获利太大——这个时候会挑起战斗，战斗的时候需要计算变化。计算在什么样的周围环境、手段下，战斗的成功性会较大。进行到最后的对杀（互相收气以杀死对方），精确的计算，可能会帮助你直接屠龙获胜。
最后顺便说下计算胜负：棋盘上共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行删除;
将已经缩小的矩阵重复进行上面的运算。