目錄

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全解