通过爬山算法实现8个皇后区解决方案 [英] 8 queens solution via the hill climbing algorithm

问题描述

大家好，

我正在寻找通过爬山"算法解决"8个皇后区"问题的解决方案的C/C ++/C#/Perl实现.

我在网上找到了针对该特定问题的大量理论解释，但没有一个单独的代码示例.

在我坐下来自己编写这部分AI的一刻之前，我想问一下你们中有哪些好人可以指出我要寻找的东西.

预先感谢，
Matthew.S.

Hello all,

I''m looking for a C/C++/C#/Perl implementation of the solution to the "8 queens" problem via a "Hill Climbing" algorithm.

I found tons of theoretical explanations on that specific issue on the web but not a single code example.

A moment before I sit down to code this piece of AI myself, I wanted to ask if any of you good people can point me to what I''m looking for.

Thanks in advance,
Matthew.S.

推荐答案

马修，

这种气味像作业，但无论如何我都会给你一些提示.
希望您能理解8个皇后区的问题，所以我不会再赘述了.

爬山"算法从随机选择的起点开始，并且
尝试做一些小的逐步优化，以寻求解决方案(
可能甚至不存在).

因此，我首先将第一个女王放置在随机选择的位置上
在板上.

将下一个女王/王后放在棋盘上(当然是随机的).现在可以发生两件事:
1.没有皇后的碰撞->继续下一个女王
2.皇后区发生碰撞->将女王移动到下一个可用位置，然后重新检查，直到没有更多可用位置或冲突解决为止.
(记住离开木板的右下角时要包裹到左上角，直到到达皇后的起始位置为止)

如果女王在整个木板上移动，而没有找到没有碰撞的位置.先前放置的女王需要重新放置(当然是随机的).

这应该给您一个很好的主意，以开始实现简单的算法.

最好的问候，

曼弗雷德(Manfred)

Hi Matthew,

this kind of smells like homework, but I''ll give you a couple of hints anyhow.
I hope you understand the 8 queens problem so I wont go into that.

"Hill Climbing" algorithms start at a randomly selected start point, and
try to do small gradual optimizations trying to obtain a solution (which
may not even exist).

So I''d start this by placing the first queen on a randomly selected position
on the board.

Place the next queen on the board (randomly of course). Two things can happen now:
1. No collision of queens -> proceed with next queen
2. Queens collide -> move queen to next available position and re-check until either there are no more available positions or the collision is resolved.
(Remember to wrap around to top left corner when leaving bottom right corner of board until starting position of queen is reached)

If a queen was moved all over the board without finding a collision free position. The previously placed queen needs to be repositioned (randomly of course).

This should give you a pretty good idea to start implementing a straight forward algorithm.

Best Regards,

Manfred

这篇关于通过爬山算法实现8个皇后区解决方案的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！