刷题笔记合集🔗

九宫格

问题描述

九宫格是一款广为流传的游戏，起源于河图洛书。游戏规则是：1到9九个数字放在3×3的格子中，要求每行、每列以及两个对角线上的三数之和都等于15。

在金庸名著《射雕英雄传》中小柯曾给九宫格的一种解法，口诀：戴九恩一，左三右七，二四有肩，八六为足，五居中央。

现在有一种新的玩法，给九个不同的数字，将这九个数字放在3×3的格子中，要求每行、每列以及两个对角线上的三数之积相等（三阶积幻方）。

请设计一种算法，将给定的九个数字重新排列后，使其满足三阶积幻方的要求。排列后的九个数字中：第 个数字为方格的第一行，第 个数字为方格的第二行，第 个数字为方格的第三行。

输入格式

九个不同的数字，每个数字之间用空格分开。

• 。
• 。

输出格式

九个数字所有满足要求的排列，每个数字之间用空格分开。每行输出一个满足要求的排列。

要求输出的排列升序排序，即：对于排列 和排列 ，从排列的第1个数字开始，遇到 ，则排列 。

说明：用例保证至少有一种排列组合满足条件。

样例输入

75 36 10 4 30 225 90 25 12

1 2 4 5 10 20 25 50 100

样例输出

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

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

数据范围

题解

这道题目是关于九宫格的特殊玩法，要求找出满足条件的所有排列方式，其中每行、每列以及两个对角线上的三数之积都相等。

解决这个问题最直接的思路是使用全排列算法，枚举所有可能的排列情况，然后检查每种排列是否满足条件。

全排列算法通常使用回溯法实现。对于给定的9个数字，我们需要尝试将它们放在九宫格的不同位置，同时检查是否满足三数之积相等的条件。

核心思路如下：

1. 使用回溯法生成所有可能的排列
2. 对于每个排列，检查是否满足条件（每行、每列、两对角线的三数之积相等）
3. 将满足条件的排列加入结果集
4. 对结果集按照题目要求进行排序

检查条件时，我们需要比较以下几组数的乘积是否相等：

• 第一行：位置0、1、2的数字乘积
• 第二行：位置3、4、5的数字乘积
• 第三行：位置6、7、8的数字乘积
• 第一列：位置0、3、6的数字乘积
• 第二列：位置1、4、7的数字乘积
• 第三列：位置2、5、8的数字乘积
• 主对角线：位置0、4、8的数字乘积
• 副对角线：位置2、4、6的数字乘积

虽然全排列的时间复杂度是O(9!)（约36万种可能），但由于题目给定的约束条件很强，符合条件的排列实际上非常少，所以这种方法在实际应用中是可行的。

时间复杂度：O(9!) 用于生成排列，每次检查条件需要O(1)的时间。 空间复杂度：O(9!) 用于存储所有可能的有效排列。

参考代码

• Python

import sys
input = lambda:sys.stdin.readline().strip()

# 输入获取
nums = list(map(int, input().split()))

# 检查排列是否符合条件：每行、每列、两对角线的乘积相等
def is_valid(arr):
    # 计算第一行的乘积作为基准
    prod = arr[0] * arr[1] * arr[2]
    
    # 检查所有行
    if arr[3] * arr[4] * arr[5] != prod or arr[6] * arr[7] * arr[8] != prod:
        return False
    
    # 检查所有列
    if arr[0] * arr[3] * arr[6] != prod or arr[1] * arr[4] * arr[7] != prod or arr[2] * arr[5] * arr[8] != prod:
        return False
    
    # 检查两条对角线
    if arr[0] * arr[4] * arr[8] != prod or arr[2] * arr[4] * arr[6] != prod:
        return False
    
    return True

# 生成排列并检查
def solve(arr, used, path, res):
    # 当路径长度等于数组长度时，检查是否满足条件
    if len(path) == len(arr):
        if is_valid(path):
            res.append(path[:])
        return
    
    # 回溯生成所有可能的排列
    for i in range(len(arr)):
        if not used[i]:
            # 选择当前数字
            path.append(arr[i])
            used[i] = True
            # 递归处理下一个位置
            solve(arr, used, path, res)
            # 回溯，撤销选择
            used[i] = False
            path.pop()

# 主函数
def get_result(nums):
    res = []
    used = [False] * len(nums)
    solve(nums, used, [], res)
    
    # 按题目要求排序
    res.sort()
    
    for perm in res:
        print(" ".join(map(str, perm)))

# 调用主函数
get_result(nums)

• Cpp

#include <bits/stdc++.h>
using namespace std;

// 检查排列是否满足条件
bool check(vector<int>& a) {
    // 计算第一行的乘积作为基准
    long long r1 = (long long)a[0] * a[1] * a[2];
    
    // 检查每一行
    if ((long long)a[3] *