程序员的算法趣题Q44: 质数矩阵

1. 问题描述

2. 解题分析

一共9个格子，每个格子都从{0,1,2,…,9}中可以任选数字的话，有10的9次方（10亿！）中可能的组合。就这样直接遍历的话会需要很长的时间，需要考虑缩小搜索范围的策略。

考虑9个格子中的数字（按行优先排列）分别记为a0, a1, …, a8。

由于质数肯定不能是偶数，所以个位数不能为{2,4,6,8}。同样也不能为5。因此a2,a5,a6,a7,a8的可选范围缩小为{1,3,7,9}。题设要求限定为三位质数，故首位数字不能为0，所以a0,a1,a2不能为0。只有a4的选择范围仍然为{0,1,2,…,9}，这样总的可能组合数缩小为：

仅为原始的10^9的(1/144)。

进一步，还可以利用early-stop的策略来提高搜索速度。因为总共有6个质数要考察，安排遍历的顺序使得可以尽量早地进行质数判断，如果发现不满足条件，就可以从某条搜索路径提前退出。比如说，已经安排了a0,a1,a2后，就可以先判断(a0,a1,a2)构成的三位数是否为质数；接下来，对a3,a6进行遍历，就可以对(a0,a3,a6)构成的三位数是否为质数进行判断。据此，考虑由外到内的遍历顺序为a0-a1-a2-a3-a6-a4-a5-a7-a8.

题设还要求质数不能重复。因此在以上遍历过程中，将搜索路径上得到的满足条件的质数记录下来，新的质数还要判断是否已经存在与该列表中，如果有不满足条件的也可以提前退出。这样做比把6个质数都凑齐了再判断是否有重复可能能够节约一些时间。在以下代码中，用一个list来实现一个stack(FIFO)，每得到一个新的满足条件的质数就加入到栈中；相应地，退回到上一层的时候要把本层加入到栈中的数要退出（因此代码中prime_lst.append()与prime_lst.pop()是成对出现的）。这个有点类似于深度优先搜索中的入栈退栈处理。因此本题解也可以用递归的方式实现，但是由于针对每个数的搜索范围不完全一致，所以递归方式也有点额外的麻烦。

以上其实也就是深度优先搜索的策略。。。

3. 代码及测试

# -*- coding: utf-8 -*-
"""
Created on Mon Sep 27 07:40:05 2021

@author: chenxy
"""

import sys
import time
import datetime
import math
# import random
from   typing import List
# from   queue import Queue
from   collections import deque
import itertools as it
import numpy as np

def isPrime(n: int)->bool:
    if n == 1 or n == 2:
        return True    
    if n%2 == 0:
        return False

    for i in range(2, int(np.sqrt(n)) + 1):
   		if (n % i == 0):
   			return False
    return True    

prime_lst = [] # Used as a stack, oe LIFO
ans_cnt = 0
tStart = time.perf_counter()
for a0 in range(1,10):
    for a1 in range(1,10):
        for a2 in [1,3,7,9]:
            tmp = a0*100+a1*10+a2
            if not isPrime(tmp):
                continue
            prime_lst.append(tmp)
            for a3 in range(1,10):
                for a6 in [1,3,7,9]:
                    tmp = a0*100+a3*10+a6
                    if not (isPrime(tmp) and (tmp not in prime_lst)):
                        continue
                    prime_lst.append(tmp)
                    for a4 in range(0,10):
                        for a5 in [1,3,7,9]:
                            tmp = a3*100+a4*10+a5
                            if not (isPrime(tmp) and (tmp not in prime_lst)):
                                continue
                            prime_lst.append(tmp)
                            for a7 in [1,3,7,9]:
                                tmp = a1*100+a4*10+a7
                                if not (isPrime(tmp) and (tmp not in prime_lst)):
                                    continue
                                prime_lst.append(tmp)
                                for a8 in [1,3,7,9]:
                                    tmp = a2*100+a5*10+a8
                                    if (isPrime(tmp) and (tmp not in prime_lst)):
                                        prime_lst.append(tmp)
                                        tmp = a6*100+a7*10+a8
                                        if (isPrime(tmp) and (tmp not in prime_lst)):
                                            ans_cnt = ans_cnt + 1        
                                        prime_lst.pop()                     
                                prime_lst.pop()
                            prime_lst.pop()
                    prime_lst.pop()
            prime_lst.pop()                                    
tCost  = time.perf_counter() - tStart
print('ans_cnt={0}, tCost = {1:6.3f}(sec)'.format(ans_cnt,tCost))                                                          
    

运行结果：ans_cnt=29490, tCost = 0.860(sec)

4. 后记

本题也有多种方案可用，但是没时间，暂时先只给这一个题解，后面有时间再回头补充。

本题的难度感觉比之前很多题目都要低（甚至低得多）啊，考虑到本书的编排的原则是从易到难安排的，感觉有点奇怪。或者只是由于不同人的思维习惯导致难和易的感觉只是一个相对的感觉？