#include <iostream>

#include <list>

 

using namespace std;

 

int map[9][9]={

     4,0,0,0,0,2,0,0,9,

     9,5,8,0,0,3,7,0,0,

     2,0,7,5,0,0,4,0,0,

     0,0,0,0,0,0,0,1,0,

     1,9,2,0,3,0,0,4,5,

     0,4,0,0,0,0,0,0,0,

     0,0,9,0,0,6,2,0,4,

     0,2,4,3,0,0,8,9,6,

     6,0,0,2,0,0,0,0,0

};

 

int count;

 

struct Point

{

     int i;

     int j;

};

 

int row[9];

int col[9];

int block[9];

 

list<Point> spaces;

 

void Print(int a[][9])

{

     for(int i = 0;i < 9;i++)

     {

         for(int j = 0;j < 9;j++)

         {

              cout<<a[i][j]<<' ';

         }

         cout<<endl;

     }

}

 

/**

 * 提取空格，保存到spaces链表

 * 标记行、列、块的候选数

 */

void PickUp()

{

     int t;

     Point p;

     for(int i = 0;i < 9;i++)

     {

         for(int j = 0;j < 9;j++)

         {

              t = map[i][j] - 1;

              if(t < 0)

              {

                   p.i = i;

                   p.j = j;

                   spaces.push_back(p);

              }

              else

              {

                   t = 0x01 << t;

                   row[i] |= t;

                   col[j] |= t;

                   block[i/3*3 + j/3] |= t;

              }

         }

     }

}

 

/**

 * 返回下一个候选数

 */

int next(Point& p,int d)

{

     int mark = ~(row[p.i] | col[p.j] | block[p.i/3*3 + p.j/3]);

     mark >>= d;

     while(d < 9)

     {

         d++;

         if(mark & 0x01)

              return d;

         mark >>= 1;

     }

     return -1;

}

 

/**

 * 设置某一格所在行、列、块的标记

 */

void set(Point& p)

{

     int t = map[p.i][p.j] - 1;

     if(t < 0)

     {

         cout<<"设置某一格所在行、列、块的标记错误,("<<p.i<<","<<p.j<<")=0"<<endl;

         exit(-1);

         return ;

     }

     t = 0x01 << t;

     row[p.i] |= t;

     col[p.j] |= t;

     block[p.i/3*3 + p.j/3] |= t;

}

 

void reset(Point& p)

{

     int t = map[p.i][p.j] - 1;

     if(t < 0)

     {

         cout<<"设置某一格所在行、列、块的标记错误,("<<p.i<<","<<p.j<<")=0"<<endl;

         exit(-1);

         return ;

     }

     t = ~(0x01 << t);

     row[p.i] &= t;

     col[p.j] &= t;

     block[p.i/3*3 + p.j/3] &= t;

}

 

void Solve(list<Point>::iterator& it)

{

     if(it == spaces.end())

     {

         Print(map);

         count++;

         return;

     }

     //获得该处下一个候选数

     int d = next(*it,0);

     list<Point>::iterator next_it(it);

     ++next_it;