建房子有多少种方法呢

有多少种建房子的方法
详细描述
要在MM的土地上建造M个房子，为了保证房子的视野，要求每条横向街道上只能有一个房子，每条竖向街道上也只能有一个房子，且任意两个房子都不能在同一斜对角线上，问有多少种建房子的方法?比如44的土地一共有以下两种建造方法，如下：
其他
时间限制：1000ms
内存限制：256.0MB
输入输出示例

这个问题类似八皇后，可以用递归的方法解决
4*4的情况

def conflict(state, nextColumn):

    nextRow = rows = len(state) # 5
    for row in range(rows):   #  0,1,2,3,4
        # 获取当前行的列
        column = state[row]

        if abs(column - nextColumn) in [0, nextRow - row]:
            return True
    return False

# 采用生成器的方式来产生每一个皇后的位置，并用递归来实现下一个皇后的位置
def queens(num, state=()):
    # 每一行的列坐标都是从0:7的
    # 0,1,2,3,4,5,6,7
    for pos in range(num):
        # 默认state为空。长度为0，但是是不冲突的
        # 判断是否冲突，state为空时不冲突
        if not conflict(state, pos): # 回溯法的体现
            # 如果state的长度为7，即到达了倒数第二行，也就是前7行皇后都已经找到了位置，最后一行又没有冲突，返回最后一行的列坐标
            if len(state) == num - 1:
                # 最后一行的（pos,）=最后一行的result，然后再递归回去求倒数第二行的result
                yield (pos,)
            else:
                for result in queens(num, state + (pos,)):
                  
                    yield (pos,) + result

if __name__ == '__main__':
    solutions = queens(4)
    for index, solution in enumerate(solutions):
        print('第%d种解决方案：' %(index + 1), solution )

Python实现八皇后问题（详细注释）_CodingAndCoCoding的博客-CSDN博客_八皇后问题python实现 回溯法在了解八皇后问题之前我们先了解什么是回溯法，因为八皇后问题是回溯法的一个经典算法习题，也是八皇后问题用到的主要算法。根据百度百科解释：回溯法（探索与回溯法）是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。举个集合小例子：列举集合 {1,2,3} 中所有子集的问题使用回溯法。从集合的开头元素开始，对每个元素都有两种操作，直到集合最 https://blog.csdn.net/Wangtuo1115/article/details/106862490