# 放棋子
今有6×6的棋盘，其中某些格子已预放了棋子。现在要再放上去一些，使得每行每列都正好有3颗棋子。我们希望推算出所有可能的放法，下面的代码就实现了这个功能。初始数组中，“1”表示放有棋子，“0”表示空白。  
![](https://img-blog.csdn.net/20170302185510449)

## aop
### before
```cpp
#include <iostream>
#include <cstdio>
int N = 0;
bool CheckStoneNum(int x[][6])
{
    for (int k = 0; k < 6; ++k)
    {
        int NumRow = 0, NumCol = 0;
        for (int i = 0; i < 6; ++i)
        {
            if (x[k][i])
                NumRow++;
            if (x[i][k])
                NumCol++;
        }
        if (NumRow != 3 || NumCol != 3)
            return false;
    }
    return true;
}
int GetRowStoneNum(int x[][6], int r)
{
    int sum = 0;
    for (int i = 0; i < 6; ++i)
    {
        if (x[r][i])
            sum++;
    }
    return sum;
}
int GetColStoneNum(int x[][6], int c)
{
    int sum = 0;
    for (int i = 0; i < 6; ++i)
    {
        if (x[i][c])
            sum++;
    }
    return sum;
}
void show(int x[][6])
{
    for (int i = 0; i < 6; ++i)
    {
        for (int j = 0; j < 6; ++j)
        {
            printf("%2d", x[i][j]);
        }
        printf("\n");
    }
    printf("\n");
}
void f(int x[][6], int r, int c);
void GoNext(int x[][6], int r, int c)
{
    if (c < 6)
    {
        f(x, r, c + 1);
    }
    else
    {
        f(x, r + 1, 0);
    }
}
```
### after
```cpp
int main()
{
    int x[6][6] = {
        {1, 0, 0, 0, 0, 0},
        {0, 0, 1, 0, 1, 0},
        {0, 0, 1, 1, 0, 1},
        {0, 1, 0, 0, 1, 0},
        {0, 0, 0, 1, 0, 0},
        {1, 0, 1, 0, 0, 1},
    };
    f(x, 0, 0);
    printf("%d\n", N);
    return 0;
}
```

## 答案
```cpp
void f(int x[][6], int r, int c)
{
    if (r == 6)
    {
        if (CheckStoneNum(x))
        {
            N++;
            show(x);
        }
        return;
    }
    if (x[r][c])
    {
        GoNext(x, r, c);
        return;
    }
    int rr = GetRowStoneNum(x, r);
    int cc = GetColStoneNum(x, c);
    if (cc >= 3)
    {
        GoNext(x, r, c);
    }
    else if (rr >= 3)
    {
        f(x, r + 1, 0);
    }
    else
    {
        x[r][c] = 1;
        GoNext(x, r, c);
        x[r][c] = 0;
        if (!(3 - rr >= 6 - c || 3 - cc >= 6 - r))
        {
            GoNext(x, r, c);
        }
    }
}
```
## 选项

### A
```cpp
void f(int x[][6], int r, int c)
{
    if (r == 6)
    {
        if (CheckStoneNum(x))
        {
            N++;
            show(x);
        }
        return;
    }
    if (x[r][c])
    {
        GoNext(x, r, c);
        return;
    }
    int rr = GetRowStoneNum(x, r);
    int cc = GetColStoneNum(x, c);
    if (cc >= 3)
    {
        GoNext(x, r, c);
    }
    else if (rr >= 3)
    {
        f(x, r + 1, 0);
    }
    else
    {
        x[r][c] = 1;
        GoNext(x, r, c);
        x[r][c] = 0;
    }
}
```

### B
```cpp
void f(int x[][6], int r, int c)
{
    if (r == 6)
    {
        if (CheckStoneNum(x))
        {
            N++;
            show(x);
        }
        return;
    }
    if (x[r][c])
    {
        GoNext(x, r, c);
        return;
    }
    int rr = GetRowStoneNum(x, r);
    int cc = GetColStoneNum(x, c);
    if (cc >= 3)
    {
        GoNext(x, r, c);
    }
    else if (rr >= 3)
    {
        f(x, r + 1, 0);
    }
    else
    {
        if (!(3 - rr >= 6 - c || 3 - cc >= 6 - r))
        {
            GoNext(x, r, c);
        }
    }
}
```

### C
```cpp
void f(int x[][6], int r, int c)
{
    if (r == 6)
    {
        if (CheckStoneNum(x))
        {
            N++;
            show(x);
        }
        return;
    }
    if (x[r][c])
    {
        GoNext(x, r, c);
        return;
    }
    int rr = GetRowStoneNum(x, r);
    int cc = GetColStoneNum(x, c);
    if (cc >= 3)
    {
        GoNext(x, r, c);
    }
    else if (rr >= 3)
    {
        f(x, r + 1, 0);
    }
    else
    {
        x[r][c] = 0;
        if (!(3 - rr >= 6 - c || 3 - cc >= 6 - r))
        {
            GoNext(x, r, c);
        }
    }
}
```