C程序重新排列跳棋

Question

我想看看我是否可以将这个名为移动西洋跳棋的数学难题编写成 C 程序。假设我们有 4 个空位和 6 个黑白交替的棋子比如这个 0,0,0,0,b,w,b,w,b,w

现在您只能成对移动跳棋。一次 2 个，将它们滑到空位，您不能打乱它们的顺序。这本书展示了这通过 3 个步骤完成，如下所示。

0,0,0,0,b,w,b,w,b,w 开始

0,0,w,b,b,0,0,w,b,w 第一关

0,0,w,b,b,b,w,w,0,0 秒通过

w,w,w,b,b,b,0,0,0,0 第三遍

我研究过合并排序和冒泡排序等算法。但它们似乎对我来说不是什么有用的代码来解决这个问题。

我考虑过将其放入数组中。运行来自 4-9 的 for 循环，因为它们不为空。比较左右，然后有逻辑移动它。但是我对如何在 C 代码中实现这一点感到困惑。 for 循环和比较不是问题。这是移动它们的逻辑，直到我一开始就得到三个白色的棋子。

Answer 1

下面是我的代码。 while 循环不再输出任何内容

#include<stdio.h>
int main ()
{
    char checkers[10] = {0,0,0,0,'b','w','b','w','b','w'};
    int a,temp1,temp2,cntr;
    cntr = 1;
    int i;
    //check each value right and left adjacent
    printf("%d a position",a);
    while(!(checkers[0] == 'w') && !(checkers[1] == 'w') && !(checkers[2] == 'w'))
    {
        for(a=4;a>9;a++){
            // if 3 white in a row followed by 3 black in a row done and exit
            printf("%d a position\n",a);
            if(checkers[0] == 'w' && checkers[1] == 'w' && checkers[2] == 'w' && checkers[3] == 'b' && checkers[4] == 'b' && checkers[5] == 'b')
            {
                printf("workd");
                for(i=0;i<(sizeof(checkers)/sizeof (checkers[0]));i++)
                {
                    printf("Checkers have finished being moved result is:%c",checkers[i]);
                    break;
                }
            }
            //once w and b found move it to empty space 2 and 3
            if(checkers[a-1] == 'b' && checkers[a+1] == 'b')
            {
            //check if 2-3 position is empty
                if(checkers[1] == 0 && checkers[2] == 0)
                {
                    temp1 = checkers[a];
                    temp2 = checkers[a+1];
                    checkers[cntr] = temp1;
                    checkers[cntr+1] = temp2;
                    break;
                }
            }
        // looking for b followed by w, checking if 6 and 7th spot is empty
        // then moving it into that spot
            if(checkers[a-1] == 'w' && checkers[a+1] == 'w' && checkers[2] == 'b' && checkers[5] && checkers[6] == 0)
            {
                temp1 = checkers[a];
                temp2 = checkers[a+1];
                checkers[5] = temp1;
                checkers[6] = temp2;
                // move 2 and 3 down one
                temp1 = checkers[1];
                temp2 = checkers[2];
                checkers[2+1] = temp1;
                checkers[1+1] = temp2;
                // finally move two whites to the front
                temp1 = checkers[8];
                temp2 = checkers[9];
                checkers[0] = temp1;
                checkers[1] = temp2;
                break;
            }
        }
    }
}
/*
just shows what swapping looks like
{0,0,0,0,b,w,b,w,b,w};
{0,w,b,0,b,0,0,w,b,w};
{0,w,b,0,b,b,w,w,0,0};
{0,0,w,b,b,b,w,w,0,0};
*/

我正在做很多移动，它最终应该会被正确放置。我难过的是，可能有一些数学方法和算法来解决这类问题。所以想知道它如何在代码中工作。我的代码是根据我已经弄清楚的内容来安排它，以使其匹配。如果开始时空白空间的数量发生变化或添加了更多片段怎么办？我研究了堆排列排序和冒泡排序，但它在示例中一次显示一项被移动。

Answer 2

有一个意见是对的，没有通用的排序算法，稍后你会看到问题是缺少严格的顺序。因此，让我们尝试从头开始设计一个。这个答案并不完整，只是关于如何解决此类问题的想法。

由于您的代码片段是已知方法的实现，因此不会有太大帮助。那么让我们开始吧：您的第一种方法不应该在意运行时的复杂性，而是获取正确的对象。我们试图概括。已经评论说双元素交换是关键。所以有 9(n) 个元素使它成为 n-1 对。这些是您拥有的字母表的有序对。这些是00 0w 0b w0 ww wb b0 bw bb，给他们起个新名字可能会有帮助，比如 A B C D E F G H I 数学上它们与第二个版本的一些限制相同： A 只能跟随 B 和 C 等等。你可以只写两个方法来翻译它们。所有交换和检查操作都将在此版本上完成。

这里是缺少订单的问题 obviuos：就像没有答案是 greater/smaller 例如D 和 G 对于排序算法的问题没有任何价值。也许以后会有。

交换：一个必须是 A=00，另一个必须与那个相距超过 1 个索引。这使得识别互换指数的一侧变得容易（冷是最多 2 个元素）（或在均衡分配层（n/3））交换后，邻居元素改变了它们的值！

我们想去的地方：我们需要某处序列 www 意味着一个必须是 E 和一个额外的 w，所以我们需要寻找 BE, ED, EF, HE ,广义 BE..E, E..ED, E..EF, HE..E

核心算法：一步一个脚印，有点递归的意思。从中我们可以检查机会树*。当没有 A 了（没有地方可以交换）时，我们处于死胡同，所以我们停止递归或者我们找到了解决方案 www 如果我们只寻找一个解决方案，否则附加路径那棵树到解决方案列表，直到你有足够的。因此，遍历所有 As，然后遍历距它一个索引的其余索引。每个迭代将具有 A (a) 的参数交换索引、另一个交换索引 (i) 和您的数组 T

通常您现在会在递归树中寻找模式和机会：

第一：交换永远不会破坏 A，所以总是有机会继续，但是：新的交换对不能是旧的（它会回到树中）。遍历不会结束（因为总是有一个 A），所以没有直接的递归调用或至少递归深度的中断条件。可以通过必须检查的树创建一个任务列表，每个元素包含 (a,i,T) 或序列 [(a0,i0),...,(an,in)] 并且您的递归调用将替换为将此元素添加到列表中。

其次：不断变化的邻居中的模式：如果一个人想创建 Es 有通往它们的方法（只需检查哪些方法结合到 ww）这些是交换的主要候选者，它们越近，它们就越应该被优先考虑。由于这些方式是有限的，所以它们偶尔会重复一次。使用该模式，交换选项会大大减少。这些模式也可以被你的新字母表的序列所取代。因此，您会寻找三元组，例如 'BAH' 和 'CDC'，它们在交换内部字母时会变成新的三元组。这可以制表，然后可以对 table 进行评级、排序，并且在检查时需要应用此顺序。

既然您直接询问了关于如何处理此类问题的数学或算法方法，那么这应该是一种看待事物的方法。一般来说：花时间给你的结构命名。或者说到编程，我想应该是 Stroustrup 曾经说过的话：如果你能想到，就把它做成 class!

*致所有喜欢评论的人：bruteforce...指数复杂度yadda yadda，我完全知道，这是设计步骤！

C程序重新排列跳棋

C program rearrange checkers

c

sorting

puzzle

math