算法设计与分析: 5

算法设计与分析: 5

5-7 n色方柱问题

问题描述

设有 n 个立方体，每个立方体的每一面用红、黄、蓝、绿等 n 种颜色之一染色。要把这n 个立方体叠成一个方形柱体，使得柱体的 4 个侧面的每一侧均有 n 种不同的颜色。试设计一个回溯算法，计算出 n 个立方体的一种满足要求的叠置方案。

对于给定的 n 个立方体以及每个立方体各面的颜色，计算出 n 个立方体的一种叠置方案，使得柱体的 4 个侧面的每一侧均有 n 种不同的颜色。

数据输入：
第一行有 1 个正整数 n，0< n< 27，表示给定的立方体个 数和颜色数均为 n。第 2 行是 n 个大写英文字母组成的字符串。该字符串的第 k(0≤ k< n) 个字符代表第 k 种颜色。接下来的 n 行中，每行有 6 个数，表示立方体各面的颜色。立方体各面的编号如下图所示。

图中 F 表示前面，B 表示背面，L 表示左面，R 表示右面，T 表示顶面，D 表示底面。相 应地，2 表示前面，3 表示背面，0 表示左面，1 表示右面，5 表示顶面，4 表示底面。
例如，在示例输出文件中，第3行的6个数0 2 1 3 0 0分别表示第1个立方体的左面的颜色为R, 右面的颜色为B, 前面的颜色为G, 背面的颜色为Y, 底面的颜色为R, 顶面的颜色为 R。

Java

package Chapter5HuiSuFa;import java.util.Scanner;public class NSeFangZhu {private static int n,ans;private static int[][] board,solu;private static boolean[] used;private static char[] color;private static String colors;public static void main(String[] args){Scanner input = new Scanner(System.in);while (true){n = input.n