Python递归实现棋盘分割以最小化均方差

向北走

发布时间：2026-10-13 | 5人浏览过

原创

本文介绍使用Python递归方法解决8x8棋盘分割问题。目标是将棋盘分割成n块矩形，使各块总分均方差最小。通过递归计算所有可能的分割路径，利用记忆化存储中间结果，最终输出最小均方差值。

问题描述与分割规则

题目要求对一个8*8的棋盘进行分割操作。每次分割需将当前棋盘切分为两个矩形，且剩余部分仍保持为矩形结构。重复此过程(n-1)次后，原棋盘将被分割成n个矩形区域。需要注意的是，每次切割必须严格沿着棋盘格子的边界线进行。

棋盘上的每个格子都预设了一个分值。对于任意一个矩形区域，其总分定义为该区域内所有格子分值的累加和。

设Xi表示第i个矩形棋盘的总分。

给定初始棋盘布局和分割数量n，目标是找到一种分割方案，使得这n块矩形棋盘总分的均方差达到最小，并输出该最小均方差值。

算法思路分析

解题思路主要采用递归搜索结合记忆化技术。由于分割方向（横向或纵向）和切割位置具有多种组合，直接暴力搜索会导致指数级复杂度。通过记录已计算过的状态（即特定矩形区域在剩余分割次数下的最小方差贡献），可以避免重复计算，从而优化性能。

以下是具体的Python程序代码实现。代码首先读取分割次数n及8x8棋盘各格子的分值，构建前缀和数组以快速计算任意矩形区域的总分。随后定义递归函数fun，用于计算在指定矩形区域内进行剩余次数分割的最小均方差相关值。最终通过公式计算并输出均方差。

Python代码实现


# -*- coding: utf-8 -*-
"""
Created on Mon Mar 12 09:55:35 2018
@author: lizihua
将一个8*8的棋盘进行分割，将原棋盘分割下一个矩阵，同时确保剩下的棋盘也是矩阵；
再将剩下的棋盘继续进行如上分割，这样割(n-1)次，最后原棋盘被分割成n块矩形棋盘；
注意：每次分割只能沿着棋盘格子的边进行分割
原棋盘每个格子都有一个分值，一个矩形棋盘的总分，为所含各格分值之和；
其中，Xi为第i块矩形棋盘的总分
对给出的棋盘和n，使得矩形棋盘总分的均方差最小，并输出
"""
 
import numpy as np
import math
 
n=int(input("请输入分割次数："))
#每个格子的分值
s=np.zeros((8,8))
for i in range(8):
  s[i]=input("请输入第"+str(i)+"行各格的分值：").split(' ')
  #将line中的元素转换为整型
  s[i] = list(map(int, s[i]))
 
zero1=np.zeros(8)
zero2=np.zeros(9)
#向s中的最上面加入一行0
s=np.insert(s,0,values=zero1,axis=0)
#向s中的第一列加入一列0
s=np.insert(s,0,values=zero2,axis=1)
res=np.ones((15,8,8,8,8))*(-1) #fun的记录表
sums=np.zeros((9,9))       #(1,1)到(i,j)的矩形分值之和
res=np.ones((15,9,9,9,9))*(-1) #fun的记录表
sums=np.zeros((9,9))       #(1,1)到(i,j)的矩形分值之和
for i in range(1,9):
  #rowsum是列之和，所以当i变化时，rowsum要清零
  rowsum=0
  for j in range(1,9):
    
    rowsum+=s[i][j]
    sums[i][j]+=sums[i-1][j]+rowsum
 
print(sums)
 
#(x1,y1)到(x2,y2)的矩形分值之和
def calsum(x1,y1,x2,y2):
  return sums[x2][y2]-sums[x2][y1-1]-sums[x1-1][y2]+sums[x1-1][y1-1]
 
#定义递归函数fun()
def fun(n,x1,y1,x2,y2):
  #注意：MIN是局部变量，一定在函数里赋值，否则结果会有问题
  MIN=10000000
  if res[n][x1][y1][x2][y2] != -1:
    return res[n][x1][y1][x2][y2]
  if n==1:
    t=calsum(x1,y1,x2,y2)  #分割后的矩形棋盘(不再分割的那块)的总分
    res[n][x1][y1][x2][y2]=t*t   #Xi*Xi
    return t*t
  for i in range(x1,x2):
    a=calsum(x1,y1,i,y2)
    c=calsum(i+1,y1,x2,y2)
    t=min(fun(n-1,x1,y1,i,y2)+c*c,fun(n-1,i+1,y1,x2,y2)+a*a)
    if t<MIN:
      MIN=t
    
  for j in range(y1,y2):
    a=calsum(x1,y1,x2,j)
    c=calsum(x1,j+1,x2,y2)
    t=min(fun(n-1,x1,y1,x2,j)+c*c,fun(n-1,x1,j+1,x2,y2)+a*a)
    if t<MIN:
      MIN=t
  res[n][x1][y1][x2][y2]=MIN
  return MIN
 
 
result=n*fun(n,1,1,8,8)-sums[8][8]*sums[8][8]
print(math.sqrt(result/(n*n)))