HihoCoder - 1268九宫问题（DFS）

种花家的奋斗兔

发布于 2020-11-12 18:58:28

6930

文章被收录于专栏：NLP小白的学习历程NLP小白的学习历程

九宫

HihoCoder - 1268

小Hi最近在教邻居家的小朋友小学奥数，而最近正好讲述到了三阶幻方这个部分，三阶幻方指的是将1~9不重复的填入一个3*3的矩阵当中，使得每一行、每一列和每一条对角线的和都是相同的。

三阶幻方又被称作九宫格，在小学奥数里有一句非常有名的口诀：“二四为肩，六八为足，左三右七，戴九履一，五居其中”，通过这样的一句口诀就能够非常完美的构造出一个九宫格来。

有意思的是，所有的三阶幻方，都可以通过这样一个九宫格进行若干镜像和旋转操作之后得到。现在小Hi准备将一个三阶幻方（不一定是上图中的那个）中的一些数组抹掉，交给邻居家的小朋友来进行还原，并且希望她能够判断出究竟是不是只有一组解。

而你呢，也被小Hi交付了同样的任务，但是不同的是，你需要写一个程序~

C++描述

#include<iostream>
#include<string>
#include<cstdio>
#include<algorithm> 
#include<cstring>
using namespace std;

const int MAX_N = 10;
int graph[MAX_N], vis[MAX_N], ans[MAX_N];
int flag = 0;
bool check()
{//判断是否满足九宫要求 
	int sum = graph[1] + graph[2] + graph[3];
	for (int i = 4; i <= 9; i += 3)
	{//行相等 
		if (graph[i] + graph[i + 1] + graph[i + 2] != sum)
			return false;
	}
	for (int i = 1; i <= 3; i++)
	{//列相等 
		if (graph[i] + graph[i + 3] + graph[i + 6] != sum)
			return false;
	}
	if ((graph[1] + graph[5] + graph[9] != sum) || (graph[3] + graph[5] + graph[7] != sum))
		return false;//对角线相等	 
	return true;
}

void dfs(int pos)
{
	if (pos == 10 && check())
	{
		flag++;
		if (flag == 1)
			memcpy(ans, graph, sizeof(graph));
		return;
	}
	if (pos < 10&& graph[pos])//注意不要数组越界
		dfs(pos + 1);//&&判断方向为从左到右 
	else
	{
		for (int i = 1; i <= 9; i++)
		{
			if (vis[i])
				continue;
			vis[i] = 1;
			graph[pos] = i;
			dfs(pos + 1);
			vis[i] = 0;
			graph[pos] = 0;
		}
	}
}
int main()
{
	memset(vis, 0, sizeof(vis));
	//读入数据 
	for (int i = 1; i < 10; i++)
	{
		cin >> graph[i];
		vis[graph[i]] = 1;
	}
	dfs(1);
	//输出 
	if (flag == 1)
	{
		for (int i = 1; i < 10; i++)
		{
			cout << ans[i];
			if (i % 3 == 0) cout << endl;
			else cout << " ";
		}
	}
	else if (flag > 1)
	{
		cout << "Too Many" << endl;
	}

	return 0;
}

Java描述

package ninth_palace;
import java.util.Scanner;
public class ninth_palace {
    int MAX_N = 10;
    int graph[] = new int[MAX_N+1];
    int vis[] = new int[MAX_N];
    int ans[] = new int[MAX_N];
    int flag = 0;
 
    public static void main(String[] args) {
        ninth_palace ninth=new ninth_palace();
        Scanner sc=new Scanner(System.in);
        for(int i=0;i<ninth.vis.length;i++)
        {
            ninth.vis[i]=0;
        }
        for(int i=1;i<10;i++)
        {
            ninth.graph[i]=sc.nextInt();
            ninth.vis[ninth.graph[i]]=1;
        }
        ninth.dfs(1);
        if(ninth.flag==1)
        {
            for(int i=1;i<10;i++)
            {
                System.out.print(ninth.ans[i]);
                if(i%3==0) System.out.print("\n");
                else System.out.print(" ");
            }
        }
        else if(ninth.flag>1)
        {
            System.out.println("Too Many");
        }
    }
 
    boolean isok() {
        int sum = graph[1] + graph[2] + graph[3];
        for (int i = 4; i <= 9; i += 3) {
            if (graph[i] + graph[i + 1] + graph[i + 2] != sum)
                return false;
        }
        for (int i = 1; i <= 3; i++) {
            if (graph[i] + graph[i + 3] + graph[i + 6] != sum)
                return false;
        }
        if ((graph[1] + graph[5] + graph[9] != sum) | (graph[3] + graph[5] + graph[7] != sum))
            return false;
        return true;
    }
 
    void dfs(int pos)
    {
        if(pos==10&&isok())
        {
            flag++;
            if(flag==1)
                ans=graph.clone();
            return;
        }
        if(graph[pos]!=0)
            dfs(pos+1);
        else
        {
            for(int i=1;i<=9;i++)
            {
                if(vis[i]!=0)
                    continue;
                vis[i]=1;
                graph[pos]=i;
                dfs(pos+1);
                vis[i]=0;
                graph[pos]=0;
            }
        }
    }
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2019/03/16 ，如有侵权请联系 cloudcommunity@tencent.com 删除

java