填字游戏

问题描述

在 3×33\times 3 个方格的方阵中要填入数字 11 到 1010 内的某 9 个数字,每个方格填一个整数,使所有相邻两个方格内的两个整数之和为素数

编写一个实验程序,求出所有满足这个要求的数字填法

思路分析

基本的算法流程如下

初始条件:从(1,1)开始搜索

退出条件:x == 4时,即此时前三行已经完成填数,ans自增,代表寻找到了一个合法的值

递归基本思路:

  • 首先对填入的数字进行鉴权,是否满足填入的数使左侧和上方的两个数之和为素数

    由于填数顺序为从左到右,上到下,所以只需要判断左侧和上方的两个数之和是否为素数即可

  • 若该点可以令方阵合法,则填入该点,否则继续循环找一个可选点

  • 使用vis数组标记使用过的数字,将合法的值填入

    • 向左侧继续递归填数,要注意的是,如果当前的数已经是最后一个数字,就另起一行从最左侧进行递归搜索

  • 最后取消标记,回溯上一个点

编码分析

核心算法

递归算法最重要的当然是边界条件的判断,结束条件定义了最简子问题的答案

这里的边界条件是x == 4时,即此时前三行已经完成填数,ans自增,代表寻找到了一个合法的值

写递归的时候,最重要的是明白一个函数的作用并相信它能完成这个任务,千万不要跳进这个函数里面企图探究更多细节,否则就会陷入无穷的细节无法自拔,人脑能压几个栈啊

递归的过程是从鉴权开始,循环所有可能的 10 个数,如果满足鉴权,则填入该值,否则继续循环找一个可选点

接下来是最核心的部分,完成鉴权之后需要进行递归与回溯的操作

1
2
3
vis[i] = 1, maze[x][y] = i;
y != 3 ? dfs(x, y + 1) : dfs(x + 1, 1);
vis[i] = 0, maze[x][y] = 0;

在执行下一步操作之前,对操作的数进行标记,相应的修改也填至方阵中,即vis[i] = 1, maze[x][y] = i;

向左侧继续递归填数,要注意的是,如果当前的数已经是最后一个数字,就另起一行从最左侧进行递归搜索,用代码体现就是y != 3 ? dfs(x, y + 1) : dfs(x + 1, 1);

搜索结束之后,取消标记,回溯上一个点,即vis[i] = 0, maze[x][y] = 0;

即整个递归过程的代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void dfs(int x, int y)
{
    if (x == BORDER)
    {
        ans++;
        return;
    }
    for (int i = 1; i <= 10; i++)
        if (check(x, y, i))
        {
            vis[i] = 1, maze[x][y] = i;
            y != 3 ? dfs(x, y + 1) : dfs(x + 1, 1);
            vis[i] = 0, maze[x][y] = 0;
        }
}

鉴权函数的细节

打表,打啊,为什么不打啊!(痛心疾首)

判断素数,显然即使我们采用埃氏筛法或者直接算的话会有一笔不菲的时间开销,但是在这个情景内我们显然可以完全把握素数出现的可能性:我们只有 1-10 之间的 9 个数字

所以首先就可以大力出奇迹,直接硬编码一个素数表,然后把这个表放到一个数组中,然后我们就可以直接检查这个数组中的数字是否是素数,这样就可以把时间开销降到最低

稍微心算一下,最大的质数就是 1919 ,不可能有更大的结果了,即

1
vector<int> primeNumbers = {2, 3, 5, 7, 11, 13, 17, 19};

查询这个向量内是否有待查找的数字也有非常快的实现,需要注意的是这个硬编码的素数表是按升序排序完毕的,所以我们直接二分查找即可,C++的 STL 提供了一个二分查找的函数 binary_search() ,返回值已经是布尔类型,直接取反即可,这样就可以把每次的查询复杂度维持在 O(logn)O(log n) ,大幅提升运行效率

1
2
bool noPrime(int x)
{ return !binary_search(primeNumbers.begin(), primeNumbers.end(), x);}

接下来就是利用这个函数去鉴权,使用组合条件,在上方或左侧有数字的情况下验证与它们的和是否为素数即可

1
2
3
4
5
6
7
bool check(int x, int y, int t)
{
    if (vis[t] == 1) return false;
    if (x - 1 >= 1 && noPrime(maze[x - 1][y] + t)) return false;
    if (y - 1 >= 1 && noPrime(maze[x][y - 1] + t)) return false;
    return true;
}

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <bits/stdc++.h>
#define ANSEL_DEBUG
#define BORDER 4
using namespace std;
vector<int> primeNumbers = {2, 3, 5, 7, 11, 13, 17, 19};
int maze[BORDER][BORDER], vis[11], ans = 0;
bool noPrime(int x)
{
    return !binary_search(primeNumbers.begin(), primeNumbers.end(), x);
}
bool check(int x, int y, int t)
{
    if (vis[t] == 1) return false;
    if (x - 1 >= 1 && noPrime(maze[x - 1][y] + t)) return false;
    if (y - 1 >= 1 && noPrime(maze[x][y - 1] + t)) return false;
    return true;
}
void dfs(int x, int y)
{
    if (x == BORDER)
    {
        ans++;
        //如果想看结果可以在这里调用文末的Print()函数
        //Print();
        return;
    }
    for (int i = 1; i <= 10; i++)
        if (check(x, y, i))
        {
            vis[i] = 1, maze[x][y] = i;
            y != 3 ? dfs(x, y + 1) : dfs(x + 1, 1);
            vis[i] = 0, maze[x][y] = 0;
        }
}
int main()
{
    cout << (dfs(1, 1), ans);
    return 0;
}

可选的Print()函数如下

1
2
3
4
5
6
7
8
9
10
void Print()
{
    for (int i = 1; i < BORDER; i++)
    {
        for (int j = 1; j < BORDER; j++)
            cout << maze[i][j] << " ";
        cout << endl;
    }
    cout << endl;
}