寒訓 01/29 基礎班 範例代碼

Sylveon

[C++] 純文本查看 復制代碼

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

int map[9][9];
int N,NN;
bool check()
{
	set<int> s;
	
	for(int i=0;i<NN;++i)
	{
		//line
		s.clear();
		for(int j=0;j<NN;++j)
		{
			if( map[i][j] != 0 )
				if( s.find( map[i][j] ) == s.end() )
					s.insert(map[i][j]);
				else
					return false;
		}
		//row
		s.clear();
		for(int j=0;j<NN;++j)
		{
			if( map[j][i] != 0 )
				if( s.find( map[j][i] ) == s.end() )
					s.insert(map[j][i]);
				else
					return false;
		}
	}
	//block
	for(int i=0;i<N;++i)
		for(int j=0;j<N;++j)
		{
			s.clear();
			for(int k=0;k<N*N;++k)
			{
				int I = i*N + k/N;
				int J = j*N + k%N;
				if( map[I][J] != 0 )
					if( s.find( map[I][J] ) == s.end() )
						s.insert(map[I][J]);
					else
						return false;
			}
		}
	return true;
}
bool dfs(int id)
{
	
	if( id == NN*NN )
	{
		if( check() )
		{
			for(int i=0;i<NN;++i)
			{
				for(int j=0;j<NN;++j)
					cout<<map[i][j]<<' ';
				cout<<'\n';
			}
			return true;
		}
		return false;
	}
	int I = id/NN;
	int J = id%NN;
	if( map[I][J] )
		return dfs(id+1);
	for(int i=1;i<=NN;++i)
	{
		map[I][J]=i;
		if( check() )
			if( dfs(id+1) )
				return true;
		map[I][J]=0;
	}
	return false;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	while(cin>>N)
	{
		NN=N*N;
		for(int i=0;i<NN;++i)
		{
			for(int j=0;j<NN;++j)
			{
				cin>>map[i][j];
			}
		}
		if(!dfs(0))
			cout<<"NO SOLUTION\n";
	}
	return 0;
}