回溯：N主教问题 [英] Backtracking: N Bishops Problem

问题描述

这个问题让我疯了......在某种程度上，所有的广场将被占用或攻击其中至少有一个在N×N的主板将正主教。

This problem is driving me crazy... Place N bishops on NxN board in a way, where all squares would be occupied or attacked with at least one of them.

谁能帮我出一个算法来解决这个问题呢？

Could anyone help me out with an algorithm for solving this problem?

推荐答案

为什么要走回头路？使用少数的解决方案，以获得证明。

Why backtrack? Use the small number of solutions to obtain a proof.

即使是贪婪算法就足够了：计数方块从每平方可达数。选择与不以previously拿起范围重叠的最大范围的正方形。重复。

Even a greedy algorithm will suffice: Count the number of squares reachable from each square. Pick a square with the greatest reach that doesn't overlap with a previously picked reach. Repeat.

歧义产生的水平，垂直，和侧中心的变型

Ambiguity generates horizontal, vertical, and side-of-center variations.

ñ主教只够达到每平方与一个主教。如果您选择正方形重叠范围，可达广场最后的帐簿会更低。嗯，也许你需要量化低多少对于任何给定坏的方形。听起来是可行的。

N bishops is only enough to reach each square with exactly one bishop. If you picked squares with overlapping reach, the final tally of reachable squares would be lower. Hmm, maybe you need to quantify how much lower for any given bad square. Sounds doable.

对于这样一个巨大的问题空间，蛮力回溯听起来并不乐观。

For such a huge problem space, brute-force backtracking doesn't sound promising.

这篇关于回溯：N主教问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！