题目
题解思路
4大剪枝常用剪枝策略
首先进行优化搜索顺序，每次搜索可以放的数最少的的点 。
再根据行列九宫格不能相同，想到位运算优化（我是想不到）。
利用按位与 & 的 清零性质 （即一位为0 按位与出来的一定是 0 ）
用 0 表示放了这个位置的数 ， 1表示没放 。
这样的话 每行列和九宫格的 所有状态 就可以用一个 2 ^ 9 - 1 的 数 表示了
其次这里可以lowbit来快速找出1的位置来让我们放数 。
实现
初始化
将 所有行列 子棋盘的状态变为1 即表示都没放 即 2 ^ 9 - 1
我们先将 棋盘中已经有的数放入棋盘 ， 将 这个数的行列以及归属的子棋盘 的状态更新 。 即 减上这个数的二进制 表示 。 （ 如 2 （10） 4（1000）） 代表这个位置放了数 （ 0 代表放了）。
这里可以写个函数 因为之后我们会再放数进去 。
再进去 dfs 去搜索出能放的答案
每次搜索可以放的数最少的的点
这样我们要对整个棋盘搜索出每个可以放的位置 可以放的数量 （即状态为1 的总数 ） 取 min
（ 这里我们只有 对这个位置的3个状态 & 可以得出他的总状态 ，但是lowbit只能得出最低位的1 ， 这样的话 我们要预处理出一个代表每个状态有多少个1的数组 nosum ）
然后取出这个1最小的状态 ， 利用lowbit 拿出 每个 1 进行尝试放入数 。
（这样又有问题了，我们只有这个状态值的1，但是我们要的是直接得出这个位置放什么数，
又是预处理。。。，我们利用一个数组mp存入每个1的真正代表的数 即 100 代表3 1000 代表 4
但是位运算左移缺了1 1 >> 1 得出的是 10 1>>2 得出 100 这样我们就在放入棋盘的函数中修改让他把数自增一个1即直接加 '1 ’ ）
这样我们只需在尝试放入后，进行复原（回溯） 。
但是我们要保证答案在原地要怎么呢 ？
复原前需要知道这个点是不是答案。这样我们只需要在搜索到答案的时候return true ， 当dfs返回true时就不需要复原了。
这题磕了很久，没有找到写的仔细的博客，自己写了个。
AC代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>
#include <map>
#include <string>
using namespace std;
const int N = 9 , M = 1 << N ;
int nosum [M] , mp[M] ;
int row[N] , col [N] , cell[3][3] ;
char st[100] ;
void init()
{
for (int i = 0 ; i < N ; i++ )
row[i] = col[i] = (1 << N ) - 1 ;
for (int i = 0 ; i < 3 ; i++ )
for (int j = 0 ; j < 3 ; j++ )
cell[i][j] = (1 << N) - 1 ;
}
int lowbit (int x )
{
return x & -x ;
}
void draw ( int x ,int y , int t , bool is_set )
{
if ( is_set )
st [ x * N + y ] = '1' + t ;
else
st [ x*N + y ] = '.' ;
int v = 1 << t ;
if ( ! is_set )
v = - v ;
row[x] -= v ;
col[y] -= v ;
cell[ x / 3 ][ y / 3 ] -= v ;
}
int gett( int x , int y )
{
return cell[x/3][y/3] & row[x] & col[y] ;
}
bool dfs( int p )
{
if ( p == 0 )
return true ;
int mi = N ;
int x , y ;
for (int i = 0 ; i < N ; i++ )
for (int j = 0 ; j < N ; j++ )
{
if ( st [ i*N + j ] == '.' )
{
int sat = gett( i , j ) ;
if ( nosum[sat] < mi )
{
mi = nosum[sat] ;
x = i ;
y = j ;
}
}
}
int sat = gett( x , y ) ;
for (int i = sat ; i ; i -= lowbit(i) )
{
int t = mp[lowbit(i)] ;
draw( x , y , t , 1 ) ;
if ( dfs( p - 1 ) )
return true ;
draw( x , y , t , 0 ) ;
}
return false ;
}
int main ()
{
ios::sync_with_stdio(false);
for (int i = 0; i < N; i ++ )
mp[1 << i] = i;
for (int i = 0 ; i < 1 << N ; i++ )
for (int j = 0 ; j < N ; j++ )
nosum[ i ] += i >> j & 1 ;
while ( cin >> st , st[0] != 'e' )
{
init() ;
int cnt = 0 ;
for (int i = 0 , k = 0 ; i < N ; i++ )
for (int j = 0 ; j < N ; j++ , k++ )
{
if ( st[k] != '.' )
{
int t = st[k] - '1' ;
draw( i , j , t , 1 ) ;
}else
cnt++ ;
}
dfs(cnt) ;
cout << st << "\n" ;
}
return 0 ;
}