rendered paste body#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; } } }