#include <stdio.h>

#include <stdlib.h>

#include <ctype.h>



void Fillin(int, int, int, int[][9], int[][9][10]);



int main() {

    

    int r, c, boxr, boxc, squares[9][9], poss[9][9][10];

    int numFilled=0, numNew=0, i, j, holdr, holdc, looped=0;

    int temp1, temp2, temp3;

    char Gridpoint;

    

    /* Initialize the grid to empty, with all possibles. */

    for (r = 0; r < 9; r++) {

        for (c = 0; c < 9; c++) {

            squares[r][c] = 0;

            for (boxr = 1; boxr < 10; boxr++)

                poss[r][c][boxr] = 1;

        }

    }

    

    /* Read in a grid. */

    for (r=0; r < 9; r++) {

        for (c = 0; c < 9; c++) {

            scanf("%c", &Gridpoint);

            if (isdigit(Gridpoint)) {

                Fillin(r, c, Gridpoint-'0', squares, poss);

                numFilled++;

                numNew++;

            }

        }

        scanf("\n");

    }

    printf("%d numbers read into grid.\n", numFilled);

    

    /* Main loop. */

    while ((numFilled < 81) && (numNew > 0)) {

        numNew = 0;

        /* Check each square for unique possibilities. */

        for (r = 0; r < 9; r++) {

            for (c = 0; c < 9; c++) {

                boxr = 0;

                for (boxc = 1; boxc < 10; boxc++)

                    boxr += poss[r][c][boxc];

                if (boxr == 1) {

                    boxc = 1;

                    while (!(poss[r][c][boxc])) boxc++;

                    Fillin(r, c, boxc, squares, poss);

                    numNew++;

                    numFilled++;

                }

            }

        }

        /* Check each row for unique possibilities. */

        for (r = 0; r < 9; r++) {

            for (boxc = 1; boxc < 10; boxc++) {

                boxr = 0;

                for (c = 0; c < 9; c++)

                    boxr += poss[r][c][boxc];

                if (boxr == 1) {

                  c = 0;

                  while (!(poss[r][c][boxc])) c++;

                  Fillin(r, c, boxc, squares, poss);

                  numNew++;

                  numFilled++;

                }

            }

        }

        /* Check each column for unique possibilities. */

        for (c = 0; c < 9; c++) {

            for (boxc = 1; boxc < 10; boxc++) {

                boxr = 0;

                for (r = 0; r < 9; r++)

                    boxr += poss[r][c][boxc];

                if (boxr == 1) {

                  r = 0;

                  while (!(poss[r][c][boxc])) r++;

                  Fillin(r, c, boxc, squares, poss);

                  numNew++;

                  numFilled++;

                }

            }

        }

        /* Check each 9x9 for unique possibilities. */

        for (boxr = 0; boxr < 3; boxr++) {

            for (boxc = 0; boxc < 3; boxc++) {

                for (i = 1; i < 10; i++) {

                    j = 0;

                    for (r = 3*boxr; r < 3*(boxr+1); r++) {

                        for (c = 3*boxc; c < 3*(boxc+1); c++) {

                            j += poss[r][c][i];

                            if (poss[r][c][i]) {holdr = r; holdc = c;}

                        }

                    }

                    if (j == 1) {

                        Fillin(holdr, holdc, i, squares, poss);

                        numNew++;

                        numFilled++;

                    }

                }    

            }

        }    

        printf("%d new this loop -- %d total.\n", numNew, numFilled);

        if (numNew > 0) {

            looped = 0;

        } else {

            printf("Entering desperation loop.\n");

            for (r = 0; r < 9; r++) {

                for (boxc = 1; boxc < 10; boxc++) {

                     temp1 = poss[r][0][boxc]+poss[r][1][boxc]+poss[r][2][boxc];

                     temp2 = poss[r][3][boxc]+poss[r][4][boxc]+poss[r][5][boxc];

                     temp3 = poss[r][6][boxc]+poss[r][7][boxc]+poss[r][8][boxc];

                     if ((temp1) && (!temp2) && (!temp3)) {

                         numNew++;        

                         boxr = r/3;

                         for (i = boxr*3; i < (boxr+1)*3; i++) {

                             for (j = 0; j < 3; j++) {

                                 if (i != r) poss[i][j][boxc] = 0;

                             }

                         }

                     }

                     if ((!temp1) && (temp2) && (!temp3)) {

                         numNew++;

                         boxr = r/3;

                         for (i = boxr*3; i < (boxr+1)*3; i++) {

                             for (j = 3; j < 6; j++) {

                                 if (i != r) poss[i][j][boxc] = 0;

                             }

                         }

                     }

                     if ((!temp1) && (!temp2) && (temp3)) {

                         numNew++;

                         boxr = r/3;

                         for (i = boxr*3; i < (boxr+1)*3; i++) {

                             for (j = 6; j < 9; j++) {

                                 if (i != r) poss[i][j][boxc] = 0;

                             }

                         }

                     }

                }

            }

            for (c = 0; c < 9; c++) {

                for (boxr = 1; boxr < 10; boxr++) {

                     temp1 = poss[0][c][boxr]+poss[1][c][boxr]+poss[2][c][boxr];

                     temp2 = poss[3][c][boxr]+poss[4][c][boxr]+poss[5][c][boxr];

                     temp3 = poss[6][c][boxr]+poss[7][c][boxr]+poss[8][c][boxr];

                     if ((temp1) && (!temp2) && (!temp3)) {

                         numNew++;

                         boxc = c/3;

                         for (j = boxc*3; j < (boxc+1)*3; j++) {

                             for (i = 0; i < 3; i++) {

                                 if (j != c) poss[i][j][boxr] = 0;

                             }

                         }

                     }

                     if ((!temp1) && (temp2) && (!temp3)) {

                         numNew++;

                         boxc = c/3;

                         for (j = boxc*3; j < (boxc+1)*3; j++) {

                             for (i = 3; i < 6; i++) {

                                 if (j != c) poss[i][j][boxr] = 0;

                             }

                         }

                     }

                     if ((!temp1) && (!temp2) && (temp3)) {

                         numNew++;

                         boxc = c/3;

                         for (j = boxc*3; j < (boxc+1)*3; j++) {

                             for (i = 6; i < 9; i++) {

                                 if (j != c) poss[i][j][boxr] = 0;

                             }

                         }

                     }

                }

            }

            for (boxr = 0; boxr < 3; boxr++) {

                for (boxc = 0; boxc < 3; boxc++) {

                    for (i = 1; i < 10; i++) {

                        /* Check rows. */

                        temp1 = poss[3*boxr][3*boxc][i]+poss[3*boxr][3*boxc+1][i]+poss[3*boxr][3*boxc+2][i];

                        temp2 = poss[3*boxr+1][3*boxc][i]+poss[3*boxr+1][3*boxc+1][i]+poss[3*boxr+1][3*boxc+2][i];

                        temp3 = poss[3*boxr+2][3*boxc][i]+poss[3*boxr+2][3*boxc+1][i]+poss[3*boxr+2][3*boxc+2][i];

                        if ((temp1) && (!temp2) && (!temp3)) {

                         numNew++;        

                         r=3*boxr;

                         for (c = 0; c < 9; c++) {

                             if ((c/3) != boxc) poss[r][c][i] = 0;

                         }

                        }

                        if ((!temp1) && (temp2) && (!temp3)) {

                         numNew++;

                         r = 3*boxr+1;

                         for (c = 0; c < 9; c++) {

                                 if ((c/3) != boxc) poss[r][c][i] = 0;

                         }

                        }

                        if ((!temp1) && (!temp2) && (temp3)) {

                         numNew++;

                         r = 3*boxr+2;

                         for (c = 0; c < 9; c++) {

                                 if ((c/3) != boxc) poss[r][c][i] = 0;

                         }

                        }

                        /* Check columns. */

                        temp1 = poss[3*boxr][3*boxc][i]+poss[3*boxr+1][3*boxc][i]+poss[3*boxr+2][3*boxc][i];

                        temp2 = poss[3*boxr][3*boxc+1][i]+poss[3*boxr+1][3*boxc+1][i]+poss[3*boxr+2][3*boxc+1][i];

                        temp3 = poss[3*boxr][3*boxc+2][i]+poss[3*boxr+1][3*boxc+2][i]+poss[3*boxr+2][3*boxc+2][i];

                        if ((temp1) && (!temp2) && (!temp3)) {

                         numNew++;        

                         c=3*boxc;

                         for (r = 0; r < 9; r++) {

                             if ((r/3) != boxr) poss[r][c][i] = 0;

                         }

                        }

                        if ((!temp1) && (temp2) && (!temp3)) {

                         numNew++;

                         c = 3*boxc+1;

                         for (r = 0; r < 9; r++) {

                                 if ((r/3) != boxr) poss[r][c][i] = 0;

                         }

                        }

                        if ((!temp1) && (!temp2) && (temp3)) {

                         numNew++;

                         c = 3*boxc+2;

                         for (r = 0; r < 9; r++) {

                                 if ((r/3) != boxr) poss[r][c][i] = 0;

                         }

                        }

                    }

                }

            }

            numNew = numNew-looped;    

            printf("Out of desperation loop: %d gained.\n",numNew);

            looped += numNew;

        } 

    }

    

    /* Print out results. */

    if (numFilled < 81) printf("I need help--make me smarter!\n");

    for (r = 0; r < 9; r++) {

        if (!(r%3)) printf("+---+---+---+\n");

        for (c = 0; c < 9; c++) {

            if (!(c%3)) printf("|");

            printf("%d", squares[r][c]);

        }

        printf("|\n");

    }

    printf("+---+---+---+\n");

    return 0;

}



void Fillin(int row, int col, int num, int Grid[][9], int Poss[][9][10]) {

     

     int i, j, x, y;

     

     Grid[row][col] = num;

     for (i = 1; i < 10; i++) Poss[row][col][i] = 0;

     for (i = 0; i < 9; i++) Poss[row][i][num] = 0;

     for (i = 0; i < 9; i++) Poss[i][col][num] = 0;

     i = row/3;

     j = col/3;

     for (x = 3*i; x < 3*(i+1); x++) {

         for (y = 3*j; y < 3*(j+1); y++) {

             Poss[x][y][num] = 0;

         }

     }           

}