目录
1. 问题描述
2. 解题分析
3. 代码及测试
4. 后记
1. 问题描述
将棋棋盘纵横各9格（9*9=81个格子），假设在将棋棋盘上的任意两格内分别放入飞车和角行这两颗棋子。两颗棋子不能放在同一格，假设棋盘上没有其它棋子。
问题：将所有可能的棋子摆放位置都考虑在内，求两颗棋子的棋步范围内所有格子数之和。
注1：所谓棋步范围，说成是“攻击范围”更容易理解吧。本题的求解问题也可以说是两颗棋子的组合攻击范围的大小
注2：飞车攻击范围为与自己同一行和同一列的所有格子，但是不能越过其它棋子。类似于中国象棋中的“车”。角行的攻击范围为位于与自己位置所谓的正反45度角对角线上的所有格子，但是不能越过其它棋子。在如下例子图中，例1，2，3，4的攻击范围内的格子数总和分别为24,23,23,15。注意，攻击范围当然不包含自身，也不包含另一颗棋子（可以理解为都为同一方棋子）
2. 解题分析
这道题目感觉相当直白啊。
简单的暴力搜索就好，遍历{飞，角}的所有各种可能的位置组合，因为棋盘为9*9=81个格子，所以总的位置组合数为81*80=6480中。
针对每种位置组合，统计两个棋子的攻击范围内的格子总数。这个算是本题的焦点。有以下几个注意点：
(1) 在扫描各棋子的攻击范围时，从棋子自身出发分别有4个方向。对于飞车来说是{up, down, left, right}，对于角行来说是{right-up, right-down, left-up, right-down}
本题解中，就是傻傻地分别针对飞车和角行的各自4个方向进行查询。查询到对方棋子或者边界时就停止
(2) 扫描各个方向时，碰到另一颗棋子时即停止，因为都不能越过别的棋子进行攻击（如以上例图2、4所示）
(3) 有些格子处于双方共同攻击范围，需要注意不要重复计数
在本题解中，采用将格子置1的方式表明格子处于某颗棋子或者两者的攻击范围，最后统计2维数组中的1的个数。这样就自然地解决了重复计数的问题。因为两次对同一格子置1不会导致被重复计数。
(4) 边界处理。“对于棋盘类问题，很多时候，在问题界定的范围外侧加上围栏就可以简化边界条件的判定（原书语）”。以下本题解在将棋盘设为11*11大小，并将四周格子值置为2即为此意。
3. 代码及测试
# -*- coding: utf-8 -*-
"""
Created on Thu Sep 16 08:51:58 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
from math import sqrt, floor, ceil
import numpy as np
N = 9
M = 9
total_count = 0
tStart = time.perf_counter()
for i in range(N*M):
for j in range(N*M):
if i==j:
continue
# Board initialization for each of (fei,jiao) position combination
board = np.zeros((N+2, M+2),dtype = 'int')
board[0,:] = 2
board[:,0] = 2
board[N+1,:] = 2
board[:,M+1] = 2
# Convert i,j to 2-D coordinate
fei_0 = (i//M) + 1
fei_1 = (i%M) + 1
jiao_0 = (j//M) + 1
jiao_1 = (j%M) + 1
# Calculate the grids within Fei's attack range
# Up direction from the current position
k = fei_0-1
while not (board[k,fei_1]==2 or (k,fei_1) == (jiao_0,jiao_1)):
# if (k,fei_1) != (jiao_0,jiao_1):
board[k,fei_1] = 1
k -= 1 # Move up by one grid
# Down direction from the current position
k = fei_0+1
while not (board[k,fei_1]==2 or (k,fei_1) == (jiao_0,jiao_1)):
board[k,fei_1] = 1
k += 1 # Move up by one grid
# Left direction from the current position
k = fei_1-1
while not (board[fei_0,k]==2 or (fei_0,k) == (jiao_0,jiao_1)):
board[fei_0,k] = 1
k -= 1 # Move left by one grid
# Right direction from the current position
k = fei_1+1
while not (board[fei_0,k]==2 or (fei_0,k) == (jiao_0,jiao_1)):
board[fei_0,k] = 1
k += 1 # Move left by one grid
# Calculate the grids within Jiao's attack range
# Need to handle the repetition removal
jiao_count = 0
# Up-Right direction from the current position
k = jiao_0-1
l = jiao_1+1
while not (board[k,l]==2 or (k,l) == (fei_0,fei_1)):
board[k,l]=1
k -= 1
l += 1
# Up-Left direction from the current position
k = jiao_0-1
l = jiao_1-1
while not (board[k,l]==2 or (k,l) == (fei_0,fei_1)):
board[k,l]=1
k -= 1
l -= 1
# Down-Left direction from the current position
k = jiao_0+1
l = jiao_1-1
while not (board[k,l]==2 or (k,l) == (fei_0,fei_1)):
board[k,l]=1
k += 1
l -= 1
# Down-Right direction from the current position
k = jiao_0+1
l = jiao_1+1
while not (board[k,l]==2 or (k,l) == (fei_0,fei_1)):
board[k,l]=1
k += 1
l += 1
total_count += np.sum(board[1:N+1,1:N+1])
tCost = time.perf_counter() - tStart
print('total_count = {0}, tCost = {1:6.3f}(sec)'.format(total_count,tCost)) 运行结果：total_count = 149424, tCost = 0.192(sec)
4. 后记
以上代码几乎是直译式的写法，虽然可能显得啰嗦冗长，但是应该很好理解。"Make it work, then optimize"总是一个不错的策略。原书的ruby代码用的是递归的方式实现，但是我确实没有看明白。。。惭愧。后面再回头补课看能不能给出个代码更简洁的实现版本。
上一篇：Q31: 计算最短路径
下一篇：
本系列总目录参见：程序员的算法趣题：详细分析和Python全解