华为OD机试-九宫格游戏-2022Q4 A卷-Py/Java/JS

九宫格又是一款广为流传的游戏，起源于河图洛书。
游戏规则是:1到9九个数字放在3x3的格子中，要求每行、每列以及两个对角线上的三数之和都等于15.
在金麻名著《射雕英雄传》中黃蓉曾给九宫格的一种解法，口诀:戴九恩一，左三右七，二四有肩，八六为足，五居中央。解法如图所示。

4    9    2
3    5    7
8    1    6
现在有一种新的玩法，给九个不同的数字，将这九个数字放在3x3的格子中，要求每行、每列以及两个对角线上的三数之积相等(三阶积幻方)。其中一个三阶幻方如图:

2    9    12
36    6    1
3    4    18

解释:每行、每列以及两个对角线上的三数之积相等，都为216。请设计一种算法，将给定的九个数宇重新排列后，使其满足三阶积幻方的要求。
排列后的九个数宇中:第1-3个数字为方格的第一行，第4-6个数宇为方格的第二行，第7-9个数字为方格的第三行。

输入描述:
九个不同的数宇，每个数字之间用空格分开。
0<数字<10^7。

0<排列后满足要求的每行、每列以及两个对角线上的三数之积<2^31-1。

输出描述:
九个数字所有满足要求的排列，每个数字之间用空格分开。每行输出一个满足要求的排列。
要求输出的排列升序排序，即:对干排列A(A1.A2.A3A9)和排列B(B1.B2.B3…B9)，从排列的第1个数字开始，遇到Ai<Bi，则排列A<排列B (1<=i<=9)。
说明:用例保证至少有一种排列组合满足条件。

示例1：输入输出示例仅供调试，后台判题数据一般不包含示例
输入

75 36 10 4 30 225 90 25 12

输出

10 36 75 225 30 4 12 25 90

10 225 12 36 30 25 75 4 90

12 25 90 225 30 4 10 36 75

12 225 10 25 30 36 90 4 75

75 4 90 36 30 25 10 225 12

75 36 10 4 30 225 90 25 12

90 4 75 25 30 36 12 225 10

90 25 12 4 30 225 75 36 10

注意30永远在中间。

示例2：

输入：

1 2 3 5 10 20 25 50 100
输出：

2 25 20 100 10 1 5 4 50
2 100 5 25 10 4 20 1 50
5 4 50 100 10 1 2 25 20
5 100 2 4 10 25 50 1 20
20 1 50 25 10 4 2 100 5
20 25 2 1 10 100 50 4 5
50 1 20 4 10 25 5 100 2
50 4 5 1 10 100 20 25 2

注意10永远在中间。

Java 代码

import java.util.Scanner;
import java.util.*;
import java.util.stream.Stream;
import java.util.stream.Collectors;class Main {public static ArrayList<Integer[]> result;public static void main(String[] args) {// 处理输入Scanner in = new Scanner(System.in);Integer[] nums = new Integer[9];for(int i=0;i<9;i++) {nums[i]=in.nextInt();}result = new ArrayList<>();//全排列核心思想就是每个数字逐个与后面的数字进行交换Perm(nums,0,8);//排序result.sort((a, b) -> {for (int i = 0; i < 9; i++) {if (a[i] != b[i]) return a[i] - b[i];}return 0;});//输出for (Integer[] single_res : result) {for (int i=0;i<9;i++) {System.out.print(single_res[i]);if (i!=8) {System.out.print(" ");}}System.out.println("");}}public static void Perm(Integer a[], int i, int j) {if(i==j) {if (check(a)) {result.add(Arrays.copyOf(a,9));}}else {for(int k=i;k<=j;k++) {swap(a,i,k);//交换第一个i=k,即交换1和他自己；对后面的数字进行递归Perm(a,i+1,j);//递归swap(a,i,k);//再交换回来，进行下一次交换}}}public static boolean check(Integer a[]) {int fixed_result = a[0] * a[1] * a[2];// 每行if (fixed_result != a[3] * a[4] * a[5] || fixed_result != a[6] * a[7] * a[8]) {return false;} //每列if (fixed_result != a[0] * a[3] * a[6] || fixed_result != a[1] * a[4] * a[7] ||fixed_result != a[2] * a[5] * a[8]) {return false;} //对角线if (fixed_result != a[0] * a[4] * a[8] || fixed_result != a[2] * a[4] * a[6]) {return false;}return true;}public static void swap(Integer a[], int k, int i) {int t=a[k];a[k]=a[i];a[i]=t;}}

Python代码

import functools
import collections
import math
from itertools import combinations
from re import match
import copyclass TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = right#并查集模板
class UF:def __init__(self, n=0):self.count = nself.item = [0 for x in range(n+1)]for i in range(n):self.item[i] = idef find(self, x):if (x != self.item[x]):self.item[x] = self.find(self.item[x])return 0return xdef union_connect(self, x, y):x_item = self.find(x)y_item = self.find(y)if (x_item != y_item):self.item[y_item] = x_itemself.count-=1#处理输入
nums = [int(x) for x in input().split(" ")]
result = []def check(a):fixed_result = a[0] * a[1] * a[2]# 每行if (fixed_result != a[3] * a[4] * a[5] or fixed_result != a[6] * a[7] * a[8]):return False#每列if (fixed_result != a[0] * a[3] * a[6] or fixed_result != a[1] * a[4] * a[7] orfixed_result != a[2] * a[5] * a[8]):return False#对角线if (fixed_result != a[0] * a[4] * a[8] or fixed_result != a[2] * a[4] * a[6]):return Falsereturn Truedef swap(a, k, i):t=a[k]a[k]=a[i]a[i]=tdef Perm(a, i, j):if(i==j):if (check(a)):result.append(a.copy()) else:for k in range(i,j+1):swap(a,i,k)#交换第一个i=k,即交换1和他自己；对后面的数字进行递归Perm(a,i+1,j)#递归swap(a,i,k)#再交换回来，进行下一次交换#全排列核心思想就是每个数字逐个与后面的数字进行交换
Perm(nums,0,8)#排序
result.sort(key=lambda x: (x[0], x[1], x[2], x[3], x[4], x[5], x[6], x[7], x[8]))#输出
for single_res in result:print(" ".join([str(i) for i in single_res]))

JS代码

let result = []
let cnt = 0
function check(a){let fixed_result = a[0] * a[1] * a[2]// 每行if (fixed_result != a[3] * a[4] * a[5] || fixed_result != a[6] * a[7] * a[8])return false//每列if (fixed_result != a[0] * a[3] * a[6] || fixed_result != a[1] * a[4] * a[7] ||fixed_result != a[2] * a[5] * a[8])return false//对角线if (fixed_result != a[0] * a[4] * a[8] || fixed_result != a[2] * a[4] * a[6])return falsereturn true
}function perm(nums, used, path) {if (path.length == 9) {if (check(path)) {result.push([...path]);}} else {for (let i = 0; i < 9; i++) {if (!used[i]) {path.push(nums[i]);used[i] = true;perm(nums, used, path);used[i] = false;path.pop();}}}}function main(nums) {perm(nums,[],[])//排序result.sort(function(a,b){for (let i=0;i<9;i++) {if (a[i]!=b[i])return a[i]-b[i]}})//输出for (let single_res of result)console.log(single_res.join(" "))
}main([75 ,36, 10, 4, 30, 225 ,90 ,25, 12])