魔方：如何检查随机面是否与实际可解的立方体匹配？

Question

我想知道，给定一个随机生成的魔方面，我是否能判断出该面是否对应于(至少)魔方的一个可解配置。也许每一张随机的脸都可以匹配到一个可解的立方体，也许不是，我也不确定。

我认为一个好的方法是，对于一个固定的随机面，以一种最终可以解决的方式构建立方体的其余部分。如果我能做到这一点，那么脸是有效的，否则是无效的。

我需要实现一个算法来做到这一点，但我真的不知道从哪里开始。

有什么建议吗?

Answer 1

也许每个随机面都可以匹配到一个可解的立方体

是的，这是可能的。甚至在立方体的其他面还有许多剩余的可能性。

我认为一个好的方法是，对于一个固定的随机面，以一种最终可以解决的方式构建立方体的其余部分。

。实现这一点的最简单方法可能是尝试从解决的立方体开始获得随机面配置。就像人类会做的那样，表演一些动作，把正确的颜色放在合适的位置，最终形成一张特定面孔的给定颜色模式。

这将永远是可能的。因此，这意味着你已经找到了一个可以解决的立方体状态(具有特定的面)，因为解决方案包括逆转你到达那里的移动。

给给定的脸配上正确的颜色并不是那么困难。从脸的中心开始。如果不正确，就把整个立方体翻转到正确的位置。

然后关注每条边。在不触及已经就位的面的情况下，将边缘就位并不难。

最后对角落做同样的处理。它只是稍微难一点，因为现在你需要保持所有四个边的位置，以及任何已经放置好的角。

实施

我想试一试。下面我实现了一个简单的魔方类。实例表示默认情况下处于已解状态的多维数据集。一个或多个动作可以应用于它。任何可能的移动都是54个贴图的排列，所以所有可能的移动都是这样编码的。

然后添加一个特定于此任务的函数makeTopFace:它将所需的模式作为参数，这是一个包含9个值的数组，每个值代表立方体上表面这些位置的贴纸颜色:

0  1  2
3  4  5 
6  7  8

该函数将使用Rubik实例来执行移动，以将一个接一个的贴纸放入位置。最后，该函数返回将立方体带入所需状态的移动字符串。我们并没有尽力使这个搬家清单尽可能地短，因为我们在这里只感兴趣的事实是它是否可能。

主程序使用这个移动列表再次生成立方体并在屏幕上显示(平展)，格式如下:

(left side) (upper side)
(front side) (right side)
(down side)  (back side)

可以通过点击上面的贴纸(这是平面表示中的第二面)交互式地给出输入。一次单击将所需的颜色更改为另一种颜色(轮询)。因此，您可以单击这些贴纸来构建所需的配置。解决方案是在您单击时计算的，因此您可以立即看到围绕您所配置的边的有效立方体的结果，以及使用Wikipedia上的符号的移动列表。

所以，如果你手里拿着一个解决了的立方体，蓝色的一面在你的前面，白色的在上面，红色的在左边，并应用这些移动，因为它们出现在这个应用程序中，你会得到你的立方体的上面所需的配置。

下面是一个用JavaScript创建的可运行代码片段:

// A simple Rubik class. An instance represents a cube that can mutate by applying moves.
class Rubik {
static init() {
// Define a unique letter for each of the stickers
this.stickers = "ABCDEFGHIJKLMNOPQRSTUVWXYZ0abcdefghijklmnopqrstuvwxyz1";
let codes = {
// Define three moves as explicit permutation of 54 stickers:
L: "MGAyEFNHBzKLOIC1QRDTUVWXJZ0abcPefghijklmnopqrstuSYdvwx",
M: "ABCDsFGHIJtLMNOPuRSEUVWXYK0abcdQfghijklmnoTZepqrvwxyz1",
z: "lrxABCkqwGHIjpvMNOdYSPJDeZTQKEf0URLFVWXou1abcntzghimsy",
// Define all other moves as combinations of already defined moves
x: "L'M'z2Lz2",
y: "zxz'",
U: "z'Lz",
F: "yLy'",
R: "z2Lz2",
D: "zLz'",
B: "y'Ly",
E: "zMz'",
S: "yMy'",
l: "LM",
u: "UE'",
f: "FS",
r: "RM'",
d: "DE",
b: "BS'",
};
// Register the above moves, together with their doubles and opposites:
for (let [move, code] of Object.entries(codes)) {
this[move] = code.length === 54 ? this.fromCode(code) : new Rubik().apply(code);
this[move+"2"] = this[move].clone().apply(this[move]);
this[move+"'"] = this[move+"2"].clone().apply(this[move]);
}
this.stickerColor = `
LLLUUU
LLLUUU
LLLUUU
FFFRRR
FFFRRR
FFFRRR
DDDBBB
DDDBBB
DDDBBB`.match(/S/g);
}
static fromCode(code) {
return new Rubik(Array.from(code, c => Rubik.stickers.indexOf(c)))
}
constructor(permutation=Array(54).keys()) { // Optional argument: a permutation array with 54 entries
if (!Rubik.stickers) Rubik.init();
// We identify 54 stickers and 54 possible locations with the same numbering:
this.state = [...permutation];
// Index = address at fixed location in space. 
// Value = sticker, i.e. the home-address of the sticker at this address.
this.log = ""; // Keep track of moves that have been applied to this cube
}
clone() {
return Object.assign(new Rubik, { state: [...this.state] });
}
apply(other) {
if (typeof other === "string") {
this.log += other;
for (let move of other.match(/w['2]?/g) || []) {
this.apply(Rubik[move]);
}
} else {
this.state = other.state.map(orig => this.state[orig]);
}
return this;
}
getLog() {
// Remove the most obvious cases of neutralising moves
return this.log.replace(/(w)'/g, "$1$1$1")
.replace(/(w)2/g, "$1$1")
.replace(/(w)1{3}/g, "") // removal
.replace(/(w)1{2}/g, "$1'")
.replace(/(w)1/g, "$12");
}
toCode() {
return this.state.map(i => Rubik.stickers[i]).join("");
}
toString() {
return this.state.map((sticker, i) => 
(i%6 ? "" : "n".padEnd(1 + Math.floor(i / 18) * 3)) + Rubik.stickerColor[sticker]
).join("").slice(1);
}
toHtml() {
return "<table><tr>" 
+ this.toString().replace(/./gs, m => m === "n" ? '</tr><tr>' : `<td class="${m}"></td>`)
+ "</tr></table>";
}
}
// Specific function for this question.
// Takes an array with 9 "colors" (from "LUFRDB"), which represents a target 
//  configuration of the upper side.
// This function will return moves that turn a solved cube into a cube
//  that has the upper side look like the given pattern.
function makeTopSide(topSide) {
let cube = new Rubik;
// Center:
let k = [7, 25, 28, 43, 46].map(i => Rubik.stickerColor[cube.state[i]]).indexOf(topSide[4]);
if (k > -1) { // Need to turn the cube to bring the right center piece into position
cube.apply(["z", "x", "z'", "z2", "x'"][k]);
}
// Edges:
for (let j of [7, 5, 1, 3]) { // For each edge
let color = topSide[j]; // Get its desired color
if (Rubik.stickerColor[cube.state[16]] !== color) {
for (let i = 0; i < 4; i++) {
let k = [13, 42, 27, 34].map(i => Rubik.stickerColor[cube.state[i]]).indexOf(color);
if (k > -1) {
cube.apply(["F", "F2", "F'", "RF'R'"][k]);
break;
}
cube.apply("d");
}
if (Rubik.stickerColor[cube.state[19]] === color) {
cube.apply("Fd'F");
}
}
cube.apply("y"); // Turn the next edge into view
}
// Corners:
for (let j of [8, 2, 0, 6]) { // For each corner:
let color = topSide[j]; // Get its desired color
if (Rubik.stickerColor[cube.state[17]] !== color) {
for (let i = 0; i < 4; i++) {
let k = [32, 33, 36].map(i => Rubik.stickerColor[cube.state[i]]).indexOf(color);
if (k > -1) {
cube.apply(["FDF'", "R'D'R", "R'DRFD2F'"][k]);
break;
}
cube.apply("D");
}
let k = cube.state.slice(20, 22).map(st => Rubik.stickerColor[st]).indexOf(color);
if (k > -1) {
cube.apply(["R'DRFDF'", "FD'F'R'D'R"][k]);
}
}
cube.apply("y"); // Turn the next corner into view
}
return cube.getLog();
}
// I/O handling
let output = document.getElementById("output");
let log = document.getElementById("log");
let topSide = [..."UUUUUUUUU"];
function display(cube) {
output.innerHTML = cube.toHtml();
log.textContent = cube.getLog();
}
display(new Rubik);
function changeSticker(i) {
// Change the color of the clicked sticker
topSide[i] = "UFRDBL"["LUFRDB".indexOf(topSide[i])];
// Find out which moves generate a cube that has this upper side pattern
let moves = makeTopSide(topSide);
let cube = new Rubik().apply(moves);
display(cube);
}
output.addEventListener("click", function (e) {
let td = e.target;
// Only allow changing stickers on the upper side of the cube
if (td.tagName !== "TD" || td.cellIndex < 3 || td.parentNode.rowIndex > 2) return;
changeSticker(td.cellIndex - 3 + td.parentNode.rowIndex * 3);
});

#output td { width: 15px; height: 15px }
#output .L { background: red }
#output .U { background: #eee }
#output .F { background: blue }
#output .R { background: orange }
#output .D { background: yellow }
#output .B { background: green }
#output tr:first-child td:nth-child(4),
#output tr:first-child td:nth-child(5),
#output tr:first-child td:nth-child(6),
#output tr:nth-child(2) td:nth-child(4),
#output tr:nth-child(2) td:nth-child(5),
#output tr:nth-child(2) td:nth-child(6),
#output tr:nth-child(3) td:nth-child(4),
#output tr:nth-child(3) td:nth-child(5),
#output tr:nth-child(3) td:nth-child(6) { cursor: pointer }

<div id="output"></div>
<div id="log"></div>

Answer 2

每个面都可以来自一个可解的立方体。构建面，然后以某种方式完成立方体。立方体可解有三个条件，"排列奇偶性"，"边奇偶性";还有"角对等"。如果排列奇偶校验是错误的，它可以通过交换对面的两条边来修复。如果边奇偶性是错误的，可以通过在相反的面上翻转一条边来修正。如果角奇偶校验是错误的，扭转一个角一次或两次就可以修复它。

这个证明依赖于每个面都是可构造的这一事实，但这很容易，因为你选择了中心正方形，然后选择任何带有正确颜色的边和角。你得好好想想，才能让自己相信不可能缺少合适的颜色。