#include <iostream>
using namespace std ;
struct SetOfSmallInts
{
int ival;
SetOfSmallInts()
{
ival = 0;
}
};
const SetOfSmallInts emptySet;
SetOfSmallInts makeSet(int i)
{
SetOfSmallInts s;
s.ival = i;
return s;
}
SetOfSmallInts remove(int x, SetOfSmallInts s)
{
return makeSet(s.ival & ~(1 << x));
}
SetOfSmallInts singletonSet(int x)
{
return makeSet(1 << x);
}
SetOfSmallInts rangeSet(int x, int y)
{
if (x > y) return emptySet;
else return makeSet(((1 << (y - x + 1)) - 1) << x);
}
bool isEmpty(SetOfSmallInts s)
{
return s.ival == 0;
}
int smallest(SetOfSmallInts s)
{
int i, val;
val = s.ival;
if (val == 0) return 0;
i = 0;
if ((val & 31) == 0) { val = val >> 5; i = 5; }
if ((val & 7) == 0) { val = val >> 3; i += 3; }
while ((val & 1) == 0) {
val = val >> 1;
i++;
}
return i;
}
int onlyMember(SetOfSmallInts s)
{
int x;
x = smallest(s);
if (x != 0 && isEmpty(remove(x, s))) return x;
else return 0;
}
bool isSingleton(SetOfSmallInts s)
{
return onlyMember(s) != 0;
}
int size(SetOfSmallInts s)
{
int n, r;
n = 0;
r = s.ival;
while (r != 0) {
if (r & 1) n++;
r = r >> 1;
}
return n;
}
bool member(int x, SetOfSmallInts s)
{
return ((1 << x) & s.ival) != 0;
}
SetOfSmallInts insert(int x, SetOfSmallInts s)
{
return makeSet(s.ival | (1 << x));
}
SetOfSmallInts setDifference(SetOfSmallInts s, SetOfSmallInts t)
{
return makeSet(s.ival & ~t.ival);
}
SetOfSmallInts setUnion(SetOfSmallInts s, SetOfSmallInts t)
{
return makeSet(s.ival | t.ival);
}
SetOfSmallInts setIntersection(SetOfSmallInts s, SetOfSmallInts t)
{
return makeSet(s.ival & t.ival);
}
typedef SetOfSmallInts Puzzle[9][9];
typedef SetOfSmallInts* PuzzleSection[9];
void copyPuzzle(Puzzle pp, Puzzle p)
{
int i, j;
for (i = 0; i < 9; i++)
{
for (j = 0; j < 9; j++)
{
pp[i][j] = p[i][j];
}
}
}
void getRow(PuzzleSection R, Puzzle p, int i)
{
int j;
for (j = 0; j < 9; j++)
{
R[j] = &(p[i][j]);
}
}
void getColumn(PuzzleSection R, Puzzle p, int j)
{
int i;
for (i = 0; i < 9; i++)
{
R[i] = &(p[i][j]);
}
}
void getSquare(PuzzleSection R, Puzzle p, int k)
{
int i;
for (i = 0; i < 9; i++)
{
R[i] = &(p[k - k % 3 + i / 3][3 * (k % 3) + i % 3]);
}
}
void readPuzzle(Puzzle p)
{
char c;
SetOfSmallInts set = rangeSet(1, 9);
for (int i = 0; i < 9; i++)
{
for (int j = 0; j < 9; j++)
{
cin >> c;
if (c == '-') p[i][j] = set;
else p[i][j] = singletonSet(c - '0');
}
}
}
void printPuzzle(Puzzle p)
{
int k;
for(int i=0; i < 9; i++)
{
for(int j=0; j < 9; j++)
{
k= onlyMember(p[i][j]);
if (j == 3 || j == 6) cout << " ";
if (k == 0) cout << "-";
else cout << k;
}
if (i==2 || i == 5) cout << "\n";
cout <<"\n";
}
}
void showPuzzle(Puzzle p)
{
for (int i = 0; i < 9; i++)
{
for (int j = 0; j < 9; j++)
{
std::cout << '[';
for (unsigned k = 1; k <= 9; ++k)
if (member(k, p[i][j]))
std::cout << k;
std::cout << "] ";
}
cout << '\n';
}
}
bool tacticOneOnSection(PuzzleSection section)
{
bool changed = false;
for (unsigned i = 0; i < 9; ++i)
{
SetOfSmallInts* cell = section[i];
if (isSingleton(*cell))
{
const int number = onlyMember(*cell);
for (unsigned j = 0; j < 9; ++j)
if (i != j && member(number, *section[j]))
{
*section[j] = remove(number, *section[j]);
changed = true;
}
}
}
return changed;
}
bool tacticOne(Puzzle puzzle)
{
bool changed = false;
for (unsigned i = 0; i < 9; ++i)
{
PuzzleSection section;
getRow(section, puzzle, i);
if (tacticOneOnSection(section))
changed = true;
getColumn(section, puzzle, i);
if (tacticOneOnSection(section))
changed = true;
getSquare(section, puzzle, i);
if (tacticOneOnSection(section))
changed = true;
}
return changed;
}
int main()
{
Puzzle p;
readPuzzle(p);
printPuzzle(p);
std::cout << '\n';
showPuzzle(p);
std::cout << '\n';
while (tacticOne(p))
{
showPuzzle(p);
std::cout << '\n';
printPuzzle(p);
std::cout << '\n';
}
}