魔方：如何检查随机面是否与实际可解立方体相匹配？
Rubik's Cube: How to check if a random face matches an actual solvable cube?
我想知道，给定一个随机生成的魔方面，我是否可以判断该面是否对应于（至少）魔方的一个可解配置。
也许每个随机面都可以匹配到一个可解的立方体，或者也许不能，我也不确定。
我认为一个好的方法是，对于一个固定的随机面，以最终可解的方式构建立方体的其余部分。
如果我能做到，那么这张脸就是有效的，否则就不是。
我需要实现一个算法来做到这一点，但我真的不知道从哪里开始。
有什么建议吗？
每个面都可以来自可解的立方体。构建面部，然后以某种方式完成立方体。立方体可解的三个条件是“排列奇偶性”、“边奇偶性”和“角奇偶性”。如果排列奇偶性错误，可以通过将相反面上的两条边与您关心的边交换来修复。如果边缘奇偶性错误，可以通过翻转相对面上的单个边缘来修复。如果角奇偶性错误，将单个角扭转一两次即可修复。
此证明取决于每个面都是可构建的事实，但这很容易，因为您选择中心正方形，然后选择任何边缘和角上的正确颜色。你必须想一想才能说服自己不会缺少合适的颜色。
Maybe every random face can be matched to a solvable cube
是的，这是可能的。立方体另一边的面孔甚至还有许多剩余的可能性。
I thought that a good approach would be, for a fixed random face, to build the rest of the cube in a manner that it ends up being solvable.
确实如此。实现这一目标的最简单方法可能是尝试从已求解的立方体开始达到随机面配置。像人类一样，执行将正确颜色放置到位的动作，最终形成一张特定面孔的给定颜色模式。
这永远是可能的。因此，这意味着您已经找到了可以解决的立方体状态（具有该特定面），因为解决方案包括反转您到达那里所做的移动。
将正确的颜色带入给定的面部并不难。从那张脸的中心部分开始。如果不对，就把整个立方体转过来。
然后关注每条边。在不触及已经到位的面的情况下将边缘放到位并不难。
最后对角落做同样的事情。它只是稍微难一点，因为现在您需要将所有四个边缘保持在适当的位置，并且任何已经放置好的角落。
实施
我想试试看。所以下面我实现了一个简单的魔方class。实例表示默认情况下处于已解决状态的立方体。可以对其应用一个或多个移动。任何可能的走法实际上都是 54 个贴纸的排列，所以所有可能的走法都是这样编码的。
然后添加一个特定于此任务的函数makeTopFace：它将所需的图案作为参数，这是一个包含 9 个值的数组，每个值代表上面这些位置的贴纸颜色立方体：
0 1 2
3 4 5
6 7 8
该函数将使用 Rubik 实例执行移动，将一张接一张贴到位。最后，函数 returns 将立方体带入所需状态的一系列移动。没有努力使此移动列表尽可能短，因为我们在这里只对它是否可能感兴趣。
主程序使用此移动列表再次生成立方体并将其显示（展平）在屏幕上，格式如下：
(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, "")
.replace(/(\w)2/g, "")
.replace(/(\w){3}/g, "") // removal
.replace(/(\w){2}/g, "'")
.replace(/(\w)/g, "");
}
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>
我想知道，给定一个随机生成的魔方面，我是否可以判断该面是否对应于（至少）魔方的一个可解配置。 也许每个随机面都可以匹配到一个可解的立方体，或者也许不能，我也不确定。
我认为一个好的方法是，对于一个固定的随机面，以最终可解的方式构建立方体的其余部分。 如果我能做到，那么这张脸就是有效的，否则就不是。
我需要实现一个算法来做到这一点，但我真的不知道从哪里开始。
有什么建议吗？
每个面都可以来自可解的立方体。构建面部，然后以某种方式完成立方体。立方体可解的三个条件是“排列奇偶性”、“边奇偶性”和“角奇偶性”。如果排列奇偶性错误，可以通过将相反面上的两条边与您关心的边交换来修复。如果边缘奇偶性错误，可以通过翻转相对面上的单个边缘来修复。如果角奇偶性错误，将单个角扭转一两次即可修复。
此证明取决于每个面都是可构建的事实，但这很容易，因为您选择中心正方形，然后选择任何边缘和角上的正确颜色。你必须想一想才能说服自己不会缺少合适的颜色。
Maybe every random face can be matched to a solvable cube
是的，这是可能的。立方体另一边的面孔甚至还有许多剩余的可能性。
I thought that a good approach would be, for a fixed random face, to build the rest of the cube in a manner that it ends up being solvable.
确实如此。实现这一目标的最简单方法可能是尝试从已求解的立方体开始达到随机面配置。像人类一样，执行将正确颜色放置到位的动作，最终形成一张特定面孔的给定颜色模式。
这永远是可能的。因此，这意味着您已经找到了可以解决的立方体状态（具有该特定面），因为解决方案包括反转您到达那里所做的移动。
将正确的颜色带入给定的面部并不难。从那张脸的中心部分开始。如果不对，就把整个立方体转过来。
然后关注每条边。在不触及已经到位的面的情况下将边缘放到位并不难。
最后对角落做同样的事情。它只是稍微难一点，因为现在您需要将所有四个边缘保持在适当的位置，并且任何已经放置好的角落。
实施
我想试试看。所以下面我实现了一个简单的魔方class。实例表示默认情况下处于已解决状态的立方体。可以对其应用一个或多个移动。任何可能的走法实际上都是 54 个贴纸的排列，所以所有可能的走法都是这样编码的。
然后添加一个特定于此任务的函数makeTopFace：它将所需的图案作为参数，这是一个包含 9 个值的数组，每个值代表上面这些位置的贴纸颜色立方体：
0 1 2
3 4 5
6 7 8
该函数将使用 Rubik 实例执行移动，将一张接一张贴到位。最后，函数 returns 将立方体带入所需状态的一系列移动。没有努力使此移动列表尽可能短，因为我们在这里只对它是否可能感兴趣。
主程序使用此移动列表再次生成立方体并将其显示（展平）在屏幕上，格式如下：
(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, "")
.replace(/(\w)2/g, "")
.replace(/(\w){3}/g, "") // removal
.replace(/(\w){2}/g, "'")
.replace(/(\w)/g, "");
}
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>