IDA*是什么，能吃吗

IDA* 为 估价函数+迭代加深的DFS

显然，最小操作次数 $\le9$

$\text{证明：}$

对于每一个行，列，九宫格，它的1的数量为奇数或偶数。对于每一步操作，一定会将 一行，一列，一九宫格 反转。你所做的每一步操作一定要尽量将奇数改为偶数。 反证法，若次数 $>9$ 则一定会有一个被更改两次，显然不是最优

$证毕$

那么，根据迭代加深dfs的思想，只需要限制深度，让最大深度等于 $1到9$ ，跑9次就行

接下来继续优化，可以估计剩下所需的步数，如果 $当前的步数+估计剩下的步数>规定的深度（步数）$ ，就直接回溯

显然，$估计出的剩下的步数$ 一定要保证 $\le$ $实际的步数$ ，不然会错

综上，设估价函数为 $$\frac{不合法的行数，列数，子九宫格的个数}{3}$$

因为改变一位至多使一行，一列，一个子九宫格变成合法的，满足上述的限制

剩下的代码在解释里

#include<iostream>
#include<cstdio>

#define int long long

using namespace std;

int a[12][12],minn,tot,ans=2147483647;
int x[12],y[12],z[5][5];

//行列编号从0开始 

void dfs(int x0,int y0,int dep,int mx_dep){
	if (dep+tot/3+((bool)(tot%3))>mx_dep) return;//tot为估价 
	if (x0==9){
		bool flag=0;
		for (int i=0;i<9;i++){
			if (y[i]){
				flag=1;
				break;
			}
		}
		if (!flag) ans=dep;//结尾 
		return;
	}
	int x2=x0,y2=(y0+1)%9; bool flag=1;
	if (y2==0) x2++;
	
	if (y2==0&&x[x0]) flag=0;//一行结尾时，若奇数个，不继续搜索 
	if ((x0==2||x0==5||x0==8)&&y0/3!=y2/3&&z[x0/3][y0/3]) flag=0;//九宫格的结尾时，若有奇数个，不继续搜索 
	if (flag) dfs(x2,y2,dep,mx_dep);
	
	
	tot-=(2*(x[x0]+y[y0]+z[x0/3][y0/3])-3);//更改评估函数 
	x[x0]^=1; y[y0]^=1; z[x0/3][y0/3]^=1;//更改状态 
	
	flag=1;
	if (y2==0&&x[x0]) flag=0;
	if ((x0==2||x0==5||x0==8)&&y0/3!=y2/3&&z[x0/3][y0/3]) flag=0;
	if (flag) dfs(x2,y2,dep+1,mx_dep);
	
	x[x0]^=1; y[y0]^=1; z[x0/3][y0/3]^=1;//回溯 
	tot+=(2*(x[x0]+y[y0]+z[x0/3][y0/3])-3);
	
}

signed main(){
	for (int i=0;i<9;i++){
		for (int j=0;j<9;j++){ 
			char c; cin>>c; a[i][j]=c-'0';
			if (a[i][j]){
				x[i]^=1; y[j]^=1; z[i/3][j/3]^=1;
				//行     列       九宫格 
			}
		}
	}
	for (int i=0;i<9;i++) tot=tot+x[i]+y[i];//tot的预处理 
	for (int i=0;i<3;i++) for (int j=0;j<3;j++) tot=tot+z[i][j];
	
	for (int i=1;i<=9;i++){//迭代加深dfs 
		dfs(0,0,0,i);
		if (ans!=2147483647) break;
	}
	printf("%lld",ans);
	return 0;
} 

赛时怎么也没想到是dfs

思路

ans小于等于9，考虑一行一行的更改，每一行最多改一个数是最优的，当改两个数时，对奇偶性无影响（相当于啥也没干）

技巧

用三个数组h[n] l[n] k[n]，分别表示每行、每列、每块的奇偶性（0：偶数个，1：奇数个），判断是否合法的时候，就可以这样：

for (ll i=1; i<=n; i++)
	if (h[i]|l[i]|k[i]) return;

dfs的时候，如果一个数，它所在的行、列、块都满足要求，显然不需要更改他，这样判断：

if (h[x]|l[y]|k[t]) {
	//略 
}else dfs(x, y+1, cnt);

用三个变量，a b c，分别表示行、列、块为奇数的个数，剪枝的时候就可以这样：

if (cnt+1+max(a, b, c)<=ans)
  dfs(x, y+1, cnt+1);

if (cnt+max(a, b, c)<=ans)
  dfs(x, y+1, cnt);

code

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define max(a, b, c) max(a, max(b, c))

namespace syr
{
	const ll N = 15;
	char ch;
	ll n=9, a, b, c, ans;
	ll h[N], l[N], k[N]; //行 列 块 
	ll id (ll x, ll y) {
		return (x-1)/3*3 + (y-1)/3 + 1;
	}
	void change (ll i, ll j) {
		h[i] ^= 1;
		l[j] ^= 1;
		k[id(i, j)] ^= 1;
		a += h[i] ? 1 : -1;
		b += l[j] ? 1 : -1;
		c += k[id(i, j)] ? 1 : -1;
	}
	void dfs (ll x, ll y, ll cnt) {
		if (cnt>ans) return;
		if (y>9) x++, y=1;
		if (x>9) {
			for (ll i=1; i<=n; i++)
				if (h[i]|l[i]|k[i]) return;
			cout<<ans<<'\n';
			exit(0);
		}
		ll t = id(x, y);
		if (h[x]|l[y]|k[t]) {
			change(x, y);
			if (cnt+1+max(a, b, c)<=ans) dfs(x, y+1, cnt+1);
			change(x, y);
			if (cnt+max(a, b, c)<=ans) dfs(x, y+1, cnt);
		}else dfs(x, y+1, cnt);
	}
	void work()
	{
		for (ll i=1; i<=n; i++) {
			for (ll j=1; j<=n; j++) {
				cin>>ch;
				if (ch=='1') change(i, j);
			}
		}
		for (; ans<10; ans++) dfs(1, 1, 0);
	}
}

int main()
{
	cin.tie(0)->sync_with_stdio(0);
	syr::work();
	return 0;
}

不会正解，但是我会 IDA*。

考虑爆搜，但是总共有 $2^{81}$ 中不同的情况，无法承担。现在设估价函数为不满足条件的行数，列数，子九宫格的个数之和除以 $3$，因为改变一位至多使一行，一列，一个子九宫格变成合法的。然后直接 IDA* 即可。

时间复杂度 $O(能过)$。

古早代码。

#include <iostream>
#define ll long long
using namespace std;
string mp[20];
ll shu[20],heng[20],thth[10][10];
ll tot,ans=2147483647;
void dfs(ll x,ll y,ll cnt,ll deepist){
	bool ch=1;
	if(cnt+tot/3+((bool)(tot%3))>deepist) return;
	if(x==9){
		for(ll i=0;i<9;i++) if(shu[i]){ch=0;break;}
		if(ch) ans=cnt;
		return;	
	}
	ll ty=(y+1)%9,tx=x;
	if(ty==0) tx=tx+1;
	if(ty==0&&heng[x]) ch=0;
	if((x==2||x==5||x==8)&&!(ty/3==y/3)&&thth[x/3][y/3]) ch=0;
	if(ch) dfs(tx,ty,cnt,deepist);
	ch=1;
	ll pl=heng[x]+shu[y]+thth[x/3][y/3];
	ll mi=3-pl;
	tot-=(pl-mi);
	heng[x]^=1;shu[y]^=1;thth[x/3][y/3]^=1;
	if(ty==0&&heng[x]) ch=0;
	if((x==2||x==5||x==8)&&!(ty/3==y/3)&&thth[x/3][y/3]) ch=0;
	if(ch) dfs(tx,ty,cnt+1,deepist);
	heng[x]^=1;shu[y]^=1;thth[x/3][y/3]^=1;
	tot+=(pl-mi); 
}
int main(){
	for(ll i=0;i<9;i++)
		cin>>mp[i];
	for(ll i=0;i<9;i++){
		for(ll j=0;j<9;j++){
			if(mp[i][j]=='1'){
				heng[i]^=1;
				shu[j]^=1;
				thth[i/3][j/3]^=1;
			}
		}
	}
	for(ll i=0;i<9;i++) tot+=heng[i]+shu[i];
	for(ll i=0;i<3;i++) for(ll j=0;j<3;j++) tot+=thth[i][j];
	for(ll i=1;i<=20;i++){
		dfs(0,0,0,i);
		if(ans<2147483647) break;
	}
	cout<<ans;
	return 0;
}