〇〇 发表于 2009-10-15 18:26:55

划数游戏

在如下的4*4方格中，2人
依次划去1~4个相邻的数（可以是纵横或斜45度），比如：0102,0408,030609
但当划的路径中已经有数被划去，则不能再划.比如02已划，则不能010203
划去最后一个方格的数者判负，请问先后手谁有必胜的策略？

01 02 03 04
05 06 07 08
09 10 11 12
13 14 15 16

mathe 发表于 2009-10-16 07:08:52

这个题目用计算机很简单.状态只有最多$2^16$种

gxqcn 发表于 2009-10-16 07:35:24

重新排版

$[(1,2,3,4),(5,6,7,8),(9,10,11,12),(13,14,15,16)]$
■ 用数学公式LaTeX重新排版01 02 03 04
05 06 07 08
09 10 11 12
13 14 15 16 ■ 用code标签重新排版，可避免英文字母或数字对不齐现象+----+----+----+----+
| 01 | 02 | 03 | 04 |
+----+----+----+----+
| 05 | 06 | 07 | 08 |
+----+----+----+----+
| 09 | 10 | 11 | 12 |
+----+----+----+----+
| 13 | 14 | 15 | 16 |
+----+----+----+----+■ 再手工加上表格线

01020304050607080910111213141516
■ 直接用表格排版（如果表格比较小，应限定table=xxx；如果将table居中，其内的所有单元格均居中）

〇〇 发表于 2009-10-16 08:16:32

有几种必胜和必败的形
必胜：
倒数第3步：曲3和不相连的1，方4,不是直4的双直2,对方下步无论如何不能给出直1

必败：
倒数第3步：直2，直3，直4，对方下步总能给出直1

mathe 发表于 2009-10-16 16:20:53

N*N的格子,
N=1,2,4先手败
N=3,5先手胜
#include <string.h>
#include <assert.h>
#include <stdlib.h>
#include <vector>
using namespace std;
#define N 4
#define BITS (N*N)
typedef unsigned int SET;
#define BIT(x,y)((x)+(y)*N)
char result;
vector<SET> lines;
void init_lines()
{
    int i;
    for(i=0;i<BITS;i++){///single element
      SET s=1<<i;
      lines.push_back(s);
    }
    for(i=0;i<N;i++){
      int x=i,y=0;
      SET s=1<<BIT(x,y);
      while(++y<N){
            s|=1<<BIT(x,y);
            lines.push_back(s);
      }
    }
    for(i=0;i<N;i++){
      int x=0,y=i;
      SET s=1<<BIT(x,y);
      while(++x<N){
            s|=1<<BIT(x,y);
            lines.push_back(s);
      }
    }
    for(i=0;i<N;i++){
      int x=i,y=0;
      SET s=1<<BIT(x,y);
      while(--x>=0&&++y<N){
            s|=1<<BIT(x,y);
            lines.push_back(s);
      }
    }
    for(i=0;i<N;i++){
      int x=i,y=0;
      SET s=1<<BIT(x,y);
      while(++x<N&&++y<N){
            s|=1<<BIT(x,y);
            lines.push_back(s);
      }
    }
    for(i=1;i<N-1;i++){
      int x=i,y=N-1;
      SET s=1<<BIT(x,y);
      while(--x>=0&&--y>=0){
            s|=1<<BIT(x,y);
            lines.push_back(s);
      }
    }
    for(i=1;i<N-1;i++){
      int x=i,y=N-1;
      SET s=1<<BIT(x,y);
      while(++x<N&&--y>=0){
            s|=1<<BIT(x,y);
            lines.push_back(s);
      }
    }
}
#define FAIL (char)-1
#define SUCC (char)1
char search(SET s)
{
    int i;
    if(result!=0)
      return result;
    for(i=0;i<lines.size();i++){
      if((s&lines)==lines){
            char r=search(s&~lines);
            if(r==FAIL)
                break;
      }
    }
    if(i==lines.size()){
      result=FAIL;
    }else{
      result=SUCC;
    }
    return result;
}

int main()
{
    init_lines();
    result=SUCC;
    int i;
    for(i=0;i<BITS;i++){
      result=FAIL;
    }
    char r=search((1<<BITS)-1);
    if(r==SUCC){
      printf("First win\n");
    }else{
      printf("First fail\n");
    }
}

〇〇 发表于 2009-10-16 19:37:49

阅读理解中

〇〇 发表于 2009-10-16 20:14:20

没太看懂，把cpp翻译成标准C,执行结果
58 （才这么多，代表什么？）
First fail
//#include <string.h>
//#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
//#include <vector>
//using namespace std;
#define N 4
#define BITS (N*N)
typedef unsigned int SET;
#define BIT(x,y)((x)+(y)*N)
#define lines_push_back(s) lines=s
char result;
//vector<SET> lines;
SET lines;
int lines_size=0;
void init_lines()
{
    int i;
    int p=0;
    for(i=0;i<BITS;i++){///single element
      SET s=1<<i;
      lines_push_back(s);
    }
    for(i=0;i<N;i++){
      int x=i,y=0;
      SET s=1<<BIT(x,y);
      while(++y<N){
            s|=1<<BIT(x,y);
            lines_push_back(s);
      }
    }
    for(i=0;i<N;i++){
      int x=0,y=i;
      SET s=1<<BIT(x,y);
      while(++x<N){
            s|=1<<BIT(x,y);
            lines_push_back(s);
      }
    }
    for(i=0;i<N;i++){
      int x=i,y=0;
      SET s=1<<BIT(x,y);
      while(--x>=0&&++y<N){
            s|=1<<BIT(x,y);
            lines_push_back(s);
      }
    }
    for(i=0;i<N;i++){
      int x=i,y=0;
      SET s=1<<BIT(x,y);
      while(++x<N&&++y<N){
            s|=1<<BIT(x,y);
            lines_push_back(s);
      }
    }
    for(i=1;i<N-1;i++){
      int x=i,y=N-1;
      SET s=1<<BIT(x,y);
      while(--x>=0&&--y>=0){
            s|=1<<BIT(x,y);
            lines_push_back(s);
      }
    }
    for(i=1;i<N-1;i++){
      int x=i,y=N-1;
      SET s=1<<BIT(x,y);
      while(++x<N&&--y>=0){
            s|=1<<BIT(x,y);
            lines_push_back(s);
      }
    }
    lines_size=p;
    printf("%d\n",lines_size);
}
#define FAIL (char)-1
#define SUCC (char)1
char search(SET s)
{
    int i;
    if(result!=0)
      return result;
    for(i=0;i<lines_size;i++){
      if((s&lines)==lines){
            char r=search(s&~lines);
            if(r==FAIL)
                break;
      }
    }
    if(i==lines_size){
      result=FAIL;
    }else{
      result=SUCC;
    }
    return result;
}

int main()
{
    init_lines();
    result=SUCC;
    int i;
    for(i=0;i<BITS;i++){
      result=FAIL;
    }
    char r=search((1<<BITS)-1);
    if(r==SUCC){
      printf("First win\n");
    }else{
      printf("First fail\n");
    }
}

mathe 发表于 2009-10-16 21:33:11

很简单,我们用一个N*N比特的二进制数表示方格当前的状态.对于每个格子对应比特是1表示这个格子还没有被划掉,0表示被划掉.所以初始状态为((1<<BITS)-1),也就是所有格子没有被划掉.
数组result[]用来保存每个方格状态是先手胜还是后手胜.先手胜结果保存为SUCC,后手胜结果保存为FAIL.
函数search用来计算每个方格状态是先手胜还是后手胜.先查询result[]判断是否已经计算过.
页: [1]
查看完整版本: 划数游戏