/* Driver.c Original Author: Shrihari Seshadri, PSC Version 1.00 Description: Trial & Error Sudoku Solver */ #include #include "mpi.h" #include #include #include #include #define STRING_TO_TEST_TAG 123 //Test the string that accompanied this tag #define ANSWER_FOUND_TAG 234 //The message that accompanied this tag is the answer #define DONE_CHECKING_TAG 345 //A slave node is done checking all of its possibilities #define SHUT_DOWN_NOW_TAG 456 //Shut down node. (Finalize and exit) #define MAX_BLANKS 81 #define STANDARDIZED 1 /* Function prototypes */ int isDoneString(char *str); char nextChar(char c); void increment(char *str); void incrementNum(char *str, int num); void makeOnes(int num, char *ans); int check(char *str, int puzzle[9][9]); int fullSet(int rowStart, int rowFinish, int colStart, int colFinish, int puzzle[9][9]); void fillInPuzzle(char *str, int puzzle[9][9]); void randomizePuzzle(int puzzle[9][9], int numBlanks); void writeToFile(int clusterSize, int numBlanks, char *answer, int optimizationLevel, float timeTaken); void printPuzzle(int puzzle[9][9]); int main(int argc, char *argv[]) { //Initializing the MPI world, rank, and size int rank, size; MPI_Init(&argc, &argv); MPI_Comm_size(MPI_COMM_WORLD, &size); MPI_Comm_rank(MPI_COMM_WORLD, &rank); //Declaring status and request variables MPI_Status status; MPI_Request request; /* Program requires at LEAST two processors */ if (size < 2){ printf("Please run with two processors.\n"); fflush(stdout); int q; for(q = 1; q < size; q++){ MPI_Send(" ", MAX_BLANKS, MPI_CHAR, q, SHUT_DOWN_NOW_TAG, MPI_COMM_WORLD); } MPI_Finalize(); exit(1); } /* Set Input / Output options */ int printStuff = 1; //1 for printing, 0 for not int writeStuff = 1; //1 for file writing, 0 for not int scanfNumblanks = 1; //1 for scanning number of blanks through user input, 0 for scanning via file reading "info.in" /* Declare miscellaneous variables for loops and MPI commands */ int i, j, flag, firstRun = 1; int puzzle[9][9] = { {8, 7, 2, 4, 1, 6, 9, 3, 5}, {9, 3, 5, 2, 8, 7, 4, 1, 6}, {1, 4, 6, 5, 9, 3, 2, 7, 8}, {7, 1, 9, 6, 3, 4, 8, 5, 2}, {3, 5, 8, 1, 2, 9, 6, 4, 7}, {2, 6, 4, 7, 5, 8, 3, 9, 1}, {5, 8, 1, 3, 4, 2, 7, 6, 9}, {4, 9, 7, 8, 6, 1, 5, 2, 3}, {6, 2, 3, 9, 7, 5, 1, 8, 4} }; if (rank == 0){ /* Variables necessary for timing the entire operation */ double startTime, finishTime; float timeTaken; int numBlanks; int optimizationLevel; /* Reads numBlanks by prompting the user */ if(scanfNumblanks){ printf("\n\nEnter the number of blanks you want in the puzzle:\t"); scanf("%d", &numBlanks); while(numBlanks < 0 || numBlanks > 81){ printf("\n\nEnter the number of blanks (0 <= x <= 81) you want in the puzzle:\t"); scanf("%d", &numBlanks); } printf("\n"); } /* Read the numBlanks by opening info.in file */ else{ FILE *blanksFile; blanksFile = fopen("info.in", "r"); if(blanksFile == NULL){ printf("Blanks file non-existent. There is no info.in in the current directory.\n"); exit(1); } fscanf(blanksFile, "%d %d\n", &numBlanks, &optimizationLevel); fclose(blanksFile); } /* If there are no blanks, exit the program. Work is done. */ if(numBlanks == 0){ char *useless = ""; if(check(useless, puzzle)) printf("The Sudoku is already correctly completed...\n\n"); else printf("The Sudoku is already completed, but incorrectly...\n\n"); writeToFile(size, 0, useless, optimizationLevel, 0.00); int q; for(q = 1; q < size; q++){ MPI_Send(" ", MAX_BLANKS, MPI_CHAR, q, SHUT_DOWN_NOW_TAG, MPI_COMM_WORLD); } MPI_Finalize(); exit(1); } /* Place numBlanks blank spaces into the puzzle. */ randomizePuzzle(puzzle, numBlanks); /* Initialize the starting time */ startTime = MPI_Wtime(); if(printStuff){ printf("\nNumber of Blanks: %d\n", numBlanks); printPuzzle(puzzle); } char *possibleAnswer = (char *) malloc(sizeof(char) * (numBlanks + 1)); makeOnes(numBlanks, possibleAnswer); //A string such as "11111111" will be generated /* Make the string end in '0' since it will incremented before checking */ possibleAnswer[strlen(possibleAnswer) - 1] = '0'; MPI_Bcast(puzzle, MAX_BLANKS, MPI_INT, 0, MPI_COMM_WORLD); int numDones = 0; char *answerRecv = (char*) malloc(sizeof(char) * MAX_BLANKS); /* Sending starting string to check to all of the nodes */ int cycle; for(cycle = 1; cycle < size; cycle++){ increment(possibleAnswer); MPI_Send(possibleAnswer, MAX_BLANKS, MPI_CHAR, cycle, STRING_TO_TEST_TAG, MPI_COMM_WORLD); } /* Loop until all slaves have reported a DONE or the answer */ while(numDones < size - 1){ /* Polling for answers */ if(firstRun) MPI_Irecv(answerRecv, MAX_BLANKS, MPI_CHAR, MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, &request); /* Test whether Irecv received a value */ MPI_Test(&request, &flag, &status); if(flag){ if(status.MPI_TAG == DONE_CHECKING_TAG){ numDones++; /* Re-initiate Irecv */ MPI_Irecv(answerRecv, MAX_BLANKS, MPI_CHAR, MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, &request); } else{ /* ANSWER FOUND */ /* Calculate time taken to find answer */ timeTaken = (float) (MPI_Wtime() - startTime); /* Print if necessary */ if(printStuff){ printf("\t\tAnswer found (master):\t%s\n", answerRecv); printf("\t\tTime taken: %f second(s)\n", timeTaken); fflush(stdout); } /* Write to file if necessary */ if(writeStuff){ writeToFile(size, numBlanks, answerRecv, optimizationLevel, timeTaken); } /* Instruct all other processors to shut down */ int q; for(q = 1; q < size; q++){ MPI_Send(" ", MAX_BLANKS, MPI_CHAR, q, SHUT_DOWN_NOW_TAG, MPI_COMM_WORLD); } /* Shut down */ free(possibleAnswer); free(answerRecv); MPI_Finalize(); exit(1); } } /* If this statement is ever reached, then the firstRun must be over by now. */ firstRun = 0; } /* NO SOLUTION WAS FOUND, all slaves reported DONE */ /* Calculate time taken */ timeTaken = (float) (MPI_Wtime() - startTime); /* Print if necessary */ if(printStuff){ printf("\n\n\t\tNo answers...\n"); printf("\t\tIt took %f second(s) to evaluate all possibilities.\n\n\n", timeTaken); fflush(stdout); } /* Write to file if necessary */ if(writeStuff){ char *noAns = "No answer"; writeToFile(size, numBlanks, noAns, optimizationLevel, timeTaken); } /* Instruct all other processors to shut down */ int q; for(q = 1; q < size; q++){ MPI_Send(" ", MAX_BLANKS, MPI_CHAR, q, SHUT_DOWN_NOW_TAG, MPI_COMM_WORLD); } /* Shut down */ free(possibleAnswer); free(answerRecv); MPI_Finalize(); exit(1); } else{ /* Current processor is a SLAVE NODE (rank != 0) */ char *possible, *done = "DONE", *endingTag; int incompletePuzzle[9][9]; /* Receive the incompleted puzzle */ MPI_Bcast(&incompletePuzzle, MAX_BLANKS, MPI_INT, 0, MPI_COMM_WORLD); /* Receive the FIRST possibility */ possible = (char*) malloc(sizeof(char) * MAX_BLANKS); MPI_Recv(possible, MAX_BLANKS, MPI_CHAR, 0, STRING_TO_TEST_TAG, MPI_COMM_WORLD, &status); /* Start the non-blocking receive to check for the ending tag */ MPI_Irecv(endingTag, MAX_BLANKS, MPI_CHAR, 0, MPI_ANY_TAG, MPI_COMM_WORLD, &request); while(1){ /* If the possibility is done, then send back DONE and quit */ if(!strcmp("DONE", possible)){ MPI_Send(" ", MAX_BLANKS, MPI_CHAR, 0, DONE_CHECKING_TAG, MPI_COMM_WORLD); MPI_Finalize(); exit(1); } /* Otherwise, check if the string correctly solves the puzzle. */ if(check(possible, incompletePuzzle)){ MPI_Send(possible, MAX_BLANKS, MPI_CHAR, 0, ANSWER_FOUND_TAG, MPI_COMM_WORLD); } /* Increment the possibility (size-1) times. */ incrementNum(possible, size - 1); /* Test to see whether the driver wants all slaves to shut down. */ MPI_Test(&request, &flag, &status); if(flag){ if(status.MPI_TAG == SHUT_DOWN_NOW_TAG){ MPI_Finalize(); exit(1); } else MPI_Irecv(endingTag, MAX_BLANKS, MPI_CHAR, 0, MPI_ANY_TAG, MPI_COMM_WORLD, &request); } } } } char nextChar(char c){ if(c == '9') return '1'; return c + 1; } void randomizePuzzle(int puzzle[9][9], int numBlanks){ char standardizedRandom[20]; int row = (int) ((((float) rand()) / RAND_MAX) * 9); int col = (int) ((((float) rand()) / RAND_MAX) * 9); int i = 0, j, k, foundElem; strcpy(standardizedRandom, "7938938224"); if(STANDARDIZED && (numBlanks <= strlen(standardizedRandom))){ while(i < numBlanks){ for(j = 0; j < 9; j++){ for(k = 0; k < 9; k++){ if(i == numBlanks) return; if(puzzle[j][k] == standardizedRandom[i] - '0'){ puzzle[j][k] = -1; i++; } } } } } else{ for( ; numBlanks > 0; numBlanks--){ while(puzzle[row][col] == -1){ row = (int) ((((float) rand()) / RAND_MAX) * 9); col = (int) ((((float) rand()) / RAND_MAX) * 9); } puzzle[row][col] = -1; } } } void fillInPuzzle(char *str, int puzzle[9][9]){ int i, j, curBlank = 0; for(i = 0; i < 9; i++){ for(j = 0; j < 9; j++){ if(puzzle[i][j] == -1){ puzzle[i][j] = str[curBlank] - '0'; curBlank++; } } } } int isDoneString(char *str){ int i, len = strlen(str); if(str[0] == 'D' && str[1] == 'O' && str[2] == 'N' && str[3] == 'E' && str[4] == 0) return 1; for(i = 0; i < len; i++) if(str[i] != '9') return 0; return 1; } void makeOnes(int num, char *ans){ int i; for(i = 0; i < num; i++) ans[i] = '1'; ans[num] = '\0'; } void increment(char *str){ if(isDoneString(str)){ str[0] = 'D'; str[1] = 'O'; str[2] = 'N'; str[3] = 'E'; str[4] = '\0'; } else{ int len = strlen(str), i = 1; while(str[len - i] == '9'){ str[len - i] = '1'; i++; } str[len - i] = nextChar(str[len - i]); } } void incrementNum(char *str, int num){ int r; for(r = 0; r < num; r++) increment(str); } /* Checks whether a certain string "solves" a puzzle */ int check(char *str, int puzzle[9][9]){ int extraCopy[9][9]; //Copy necessary so the actual puzzle is not altered int i, j; /*Making an extra copy of puzzle so we can leave puzzle unchanged at the end*/ for(i = 0; i < 9; i++) for(j = 0; j < 9; j++) extraCopy[i][j] = puzzle[i][j]; /*Filling in the puzzle with our possible solution*/ fillInPuzzle(str, extraCopy); /*Checking rows*/ for(i = 0; i < 9; i++){ if(!fullSet(i, i, 0, 8, extraCopy)) return 0; } /*Checking columns*/ for(j = 0; j < 9; j++){ if(!fullSet(0, 8, j, j, extraCopy)) return 0; } /*Checking boxes*/ for(i = 0; i < 9; i++){ int rSt = 3 * (i / 3); int rFi = rSt + 2; int cSt = 3 * (i % 3); int cFi = cSt + 2; if(!fullSet(rSt, rFi, cSt, cFi, extraCopy)) return 0; } /*Return 1 if the puzzle works, which it does if it has gotten here without returning.*/ return 1; } /* This method returns whether a given set consists of each digit '1' - '9' exactly once */ int fullSet(int rowStart, int rowFinish, int colStart, int colFinish, int puzzle[9][9]){ int ans[9], i, j, ind = 0, correctIndex; for(i = rowStart; i < rowFinish + 1; i++){ for(j = colStart; j < colFinish + 1; j++){ ans[ind] = puzzle[i][j]; ind++; } } for(i = 1; i < 10; i++){ correctIndex = -1; for(j = 0; j < 9; j++){ if(ans[j] == i) correctIndex = j; } if(correctIndex == -1) return 0; } return 1; } void writeToFile(int clusterSize, int numBlanks, char *answer, int optimizationLevel, float timeTaken){ FILE *file; char fileName[100]; strcpy(fileName, "results"); fileName[7] = (optimizationLevel + '0'); fileName[8] = '\0'; strcat(fileName, ".dat"); file = fopen(fileName, "a"); if (!file) return; fprintf(file, "%d\t\t%d\t\t\t%s\t\t%f\n", clusterSize, numBlanks, answer, timeTaken); fclose(file); } void printPuzzle(int puzzle[9][9]){ int i, j; printf("\nThe puzzle is:\n\n"); for(i = 0; i < 9; i++){ for(j = 0; j < 9; j++){ if(puzzle[i][j] == -1) printf("_"); else printf("%d", puzzle[i][j]); if(j % 3 != 2) printf(" "); if(j % 3 == 2 && j != 8) printf(" | "); } if(i == 2 || i == 5){ printf("\n-------------------------"); } printf("\n"); } printf("\n\n"); }