功能性n-皇后

Question

在“计算机程序的结构和解释”一书之后，我尝试实现N皇后问题的函数解决方案(由函数nQueens实现)。但是，我并不满足于对for循环的依赖和代码的一般可读性。我能听听你对密码的看法吗？

import functools as fn

def safe(positions, k):
    """ Given a list of positions, returns if the queen on the k column
    is safe. """
    enumeratedPos = tuple(enumerate(positions));
    menacesK = fn.partial(menaces, enumeratedPos[k]);
    return not any(map(menacesK,
        filter(lambda pair: pair[0] != k, enumeratedPos)));

def addNewColumn(positions, n):
    """ Given an array of k-length positions maps each position
    to n new k+1-length positions by appending numbers from 0 to n-1 
    Example:
    ((),) -> ((0), (2) ... (n-1))
    ((a),(b)) -> ((a, 0), (a,2) ... (a,n-1), (b,0) ... (b,n-1))
    """
    for position in positions:
        for i in range(0, n):
            yield position + (i,);

def menaces(pair1, pair2):
    colK, rowK = pair1;
    col, row = pair2;
    return abs(rowK - row) == abs(colK - col) or rowK == row;

def nQueens(boardSize):
    """ Given a dimension boardSize, returns a filter with all the solutions to
    n-queens problem where n is boardSize"""
    def recur(i):
        if (i == 0): return ((),);
        safeK = lambda x: safe(x, i-1);
        return filter(safeK, addNewColumn(recur(i-1), boardSize));
    return recur(boardSize);

Answer 1

看起来像是一些相当辛辣(格式很好的)代码:)

我将解释我的步骤，使它看起来更好，并向你展示最终的结果。你可以跟着它们，在它们弹出的时候改变它们。

1. 移除分号:P这是Python，不是Javascript或C++或(插入另一种语言)。虽然它们是可选的，很好地放进去，但它们会造成混乱，降低可读性。
2. 所有函数和变量都应该是lower_case_with_underscores，类为UpperCase，常量为UPPER_CASE_WITH_UNDERSCORES。我们将用正确的惯例取代它们。
3. 用生成器表达式替换map和filter。它们可能会慢一点，但因为它类似于一般的Python语法，比如for循环和if语句，所以它的可读性更强。
4. 底部的递归函数可以更改，这样它就不需要lambda了。它可以使它看起来更好，没有隐藏的额外论据。
5. 上面的功能看起来很复杂..。这里是如何改变它，使它不需要任何变量。menaces的第一个参数总是相同的，因此可以手动输入。这是enumerate(positions)的第四项，所以参数是(k, positions[k])。注意:我们可以删除import functools as fn行。
6. 第二个函数是生成器函数，这意味着它返回一个迭代器。这一项只是结合了两个for循环的结果。不鼓励嵌套的for循环，所以让我们用itertools.product(positions, range(n))替换它。我们还必须导入迭代工具。注意：range(0, n)与range(n)相同。
7. 我已将position + (i,)的表达式更改为(*position, i)。我不确定哪个看起来更好，但就个人而言，第二个类似于元组，它产生的效果比第一个更好。
8. 第三种功能可以用一点改造来完成。新的变量并不是真正需要的。我用col_diff和row_diff替换了它们，它们存储abs(pair1[n] - pair2[n])，其中n是行的1，0是列的。我还显式地返回了True或False，看起来更好:)
9. 文档字符串也有一个约定(出于某种原因)。单行文档字符串可以在行的开头和结尾使用三元引号(""")，但是多行文档字符串在它们自己的行上有它们。注意:我在add_new_column中编辑了这个示例，使其看起来像一个交互式会话，展示了该函数的工作原理。

最后的结果如下：

import itertools


def safe(positions, k):
    """Given a list of positions, return True if the queen on the `k` column is safe."""
    return not any(
        menaces((k, positions[k]), pair)
        for pair in enumerate(positions)
        if pair[0] != k
    )


def add_new_column(positions, n):
    """
    Given an array of k-length `positions`, map each position to `n` new
    k+1-length positions by appending numbers from 0 to `n` - 1.

    >>> list(add_new_column(((),), 3))
    [(0,), (1,), (2,)]
    >>> list(add_new_column(((1,), (2,)), 3))
    [(1, 0), (1, 1), (1, 2), (2, 0), (2, 1), (2, 2)]
    """
    for position, i in itertools.product(positions, range(n)):
        yield (*position, i)


def menaces(pair1, pair2):
    row_diff = abs(pair1[1] - pair2[1])
    col_diff = abs(pair1[0] - pair2[0])
    if row_diff == col_diff:
        return True
    elif pair1[1] == pair2[1]:
        return True
    else:
        return False


def n_queens(board_size):
    """
    Given a dimension `board_size`, return an iterator with all the solutions
    to n-queens problem where n is `board_size`.
    """
    def _recur(i):
        if not i:
            return ((),)
        else:
            return (
                row
                for row in add_new_column(_recur(i - 1), board_size)
                if safe(row, i - 1)
            )
    return _recur(board_size)

我要做的一个额外的更改是对add_new_column函数进行修改。它首先接收positions，这意味着它必须是一个元组。通过将n参数移动到前面，并使用可变长度参数(*positions)，调用看起来更少重复。

下面是新的函数签名：(如果您愿意，可以更改其他调用)

def add_new_column(n, *positions):
    """
    Given an array of k-length `positions`, map each position to `n` new
    k+1-length positions by appending numbers from 0 to `n` - 1.

    >>> list(add_new_column(3, ()))
    [(0,), (1,), (2,)]
    >>> list(add_new_column(3, (1,), (2,)))
    [(1, 0), (1, 1), (1, 2), (2, 0), (2, 1), (2, 2)]
    """
    # Here's the code