#include<bits/stdc++.h>
using namespace std;
#define ioio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl "\n"
#define debug(x) cout<<#x<<":"<<x<<endl;
#define L(k) k<<1
#define R(k) k<<1|1
#define P pair
#define P1 first
#define P2 second
#define u_map unordered_map
#define p_queue priority_queue
typedef long ll;
const double eps = 1e-6;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int INF2 = (1 << 31);
const int N = 1e2 + 7;
int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};
/*-------------------------------------------------*/

int n = 16;
int vis[N][N];
int m1[N][N], m2[N][N], m3[N][N];
vector<P<int, int> >V[N];
ll seed;
int wk;
int fx, fy;
int cnt;

void print(int mm[N][N]) {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++)
			printf("%-3d", mm[i][j]);
		cout << endl;
	}
}
bool cheak2(int x, int y, int s) {
	for (int i = 1; i <= n; i++)
		if (i != x && m2[i][y] == s)
			return 0;
	for (int i = 1; i <= n; i++)
		if (i != y && m2[x][i] == s)
			return 0;
	int t = vis[x][y];
	for (P<int, int> id : V[t])
		if (m2[id.P1][id.P2] == s)
			return 0;
	return 1;
}
void dfs(int x, int y) {
	if (x == fx && fy == y) {
		cnt++;
		return ;
	}
	for (int i = x; i <= n; i++)
		for (int j = 1; j <= n; j++)
			if (m2[i][j] == 0)
				for (int k = 1; k <= n; k++)
					if (cheak2(i, j, k)) {
						m2[i][j] = k;
						dfs(i, j);
						m2[i][j] = 0;
					}
}
bool cheak1() {
	cnt = 0;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			if (m2[i][j] == 0)
				fx = i, fy = j;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			if (m2[i][j] == 0)
				for (int k = 1; k <= n; k++)
					if (cheak2(i, j, k)) {
						m2[i][j] = k;
						dfs(i, j);
						m2[i][j] = 0;
						goto en;
					}
en:
	if (cnt >=1)return 1;
	else return 0;
}
bool star() {
	srand(seed);
	seed += 1;
	int a[20] = {0};
	for (int i = 1; i <= n; i++)
		while (a[i] == 0)
			a[i] = rand() % 17;
	int b[20] = {0};
	for (int i = 1; i <= n; i++)
		while (b[i] == 0)
			b[i] = rand() % 17;
	for(int i=1;i<=wk;i++){
		while(m2[a[i]][b[i]]==0){
			a[i] = rand() % 17;
			b[i] = rand() % 17;
		}
		int tt=m2[a[i]][b[i]];
		m2[a[i]][b[i]]=0;
		if(cheak1()==0)
			m2[a[i]][b[i]]=tt;
	}
	if(cheak1()==0)return 0;
	return 1;
}
void op(int op, int a, int b) {
	if (op % 2 == 1)
		for (int i = 1; i <= n; i++)
			swap(m1[a][i], m1[b][i]);
	else
		for (int i = 1; i <= n; i++)
			swap(m1[i][a], m1[i][b]);
}
void daluan(int x) {
	srand(seed);
	seed += 1;
	int a[20007] = {0};
	for (int i = 1; i <= x * 2; i++)
		while (a[i] == 0)
			a[i] = rand() % 17;
	for (int i = 1; i <= x; i++)
		op(i, a[i], a[2 * x - i + 1]);
	memcpy(m2,m1,sizeof m1);
}
void slove() {
	cout << "请输入16*16的满置数独:" << endl;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			cin >> m1[i][j];
	cout << "请输入异形区域:" << endl;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			cin >> vis[i][j];
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			V[vis[i][j]].push_back({i, j});
	cout << "请输入预期生成个数:" << endl;
	int t;
	cin >> t;
	cout << "请输入预期挖空个数:" << endl;
	cin>>wk;
	cout << "请输入随机参数(1-10000):" << endl;
	cin >> seed;
	seed=time(NULL)%seed;
	for (int i = 1; i <= t; i++) {
		cout << "第 " << i << " 次生成开始:" << endl;
		daluan(seed);
		int flag = star();
		if (flag == 0) cout << "生成失败......\n" << endl;
		else {
			cout << "已找到！" << endl;
			int sum=0;
			for(int i=1;i<=n;i++)
				for(int j=1;j<=n;j++)
					if(m2[i][j]==0)
						sum++;
			cout<<"挖空成功数量: "<<sum<<endl;
			cout << "数独:" << endl;
			print(m2);
			cout << "唯一解:" << endl;
			print(m1);
			break;
		}
	}
}
int main() {
	slove();

	cout << "\n程序正常结束" << endl;
	return 0;
}
/*
6  16 1  8  13 10 5  3  14 12 2  4  11 15 7  9
15 10 13 9  1  14 2  4  16 11 3  7  6  12 8  5
12 14 4  11 7  6  15 9  10 5  1  8  13 2  16 3
2  7  3  5  12 11 8  16 15 6  9  13 1  10 4  14
13 6  8  2  5  12 16 15 1  3  11 10 7  14 9  4
3  9  12 14 11 4  7  1  8  2  13 15 16 5  6  10
4  15 7  16 9  8  10 13 6  14 12 5  3  1  11 2
10 5  11 1  6  3  14 2  7  9  4  16 12 8  15 13
5  2  15 6  16 13 9  10 4  7  8  12 14 11 3  1
14 3  10 4  8  2  1  5  11 13 15 6  9  7  12 16
8  13 16 12 3  7  11 6  9  1  5  14 2  4  10 15
1  11 9  7  14 15 4  12 2  16 10 3  5  6  13 8
11 4  5  13 10 9  6  14 3  8  7  1  15 16 2  12
7  12 2  3  4  16 13 8  5  15 14 11 10 9  1  6
16 8  14 15 2  1  12 11 13 10 6  9  4  3  5  7
9  1  6  10 15 5  3  7  12 4  16 2  8  13 14 11

1 1 1 1 2 2 2 2 3 3 3 3 4 4 4 4
1 1 1 1 2 2 2 2 3 3 3 3 4 4 4 4
1 1 1 1 2 2 2 2 3 3 3 3 4 4 4 4
1 1 1 1 2 2 2 2 3 3 3 3 4 4 4 4
5 5 5 5 6 6 6 6 7 7 7 7 8 8 8 8
5 5 5 5 6 6 6 6 7 7 7 7 8 8 8 8
5 5 5 5 6 6 6 6 7 7 7 7 8 8 8 8
5 5 5 5 6 6 6 6 7 7 7 7 8 8 8 8
9 9 9 9 10 10 10 10 11 11 11 11 12 12 12 12
9 9 9 9 10 10 10 10 11 11 11 11 12 12 12 12
9 9 9 9 10 10 10 10 11 11 11 11 12 12 12 12
9 9 9 9 10 10 10 10 11 11 11 11 12 12 12 12
13 13 13 13 14 14 14 14 15 15 15 15 16 16 16 16
13 13 13 13 14 14 14 14 15 15 15 15 16 16 16 16
13 13 13 13 14 14 14 14 15 15 15 15 16 16 16 16
13 13 13 13 14 14 14 14 15 15 15 15 16 16 16 16
*/