Thread: Sudoku how to include algorithm into this code?

  1. #1
    Registered User
    Join Date
    Oct 2012
    Location
    Svitavy, Czech Republic
    Posts
    37

    Sudoku how to include algorithm into this code?

    Hello, I would like to ask you for help with this program, it should open file with sudoku soubor.txt
    Code:
    65 7 2 93
    7       6
       365
    9 85 13 2
      5 2 7
    4 68 39 5
       936
    3       9
    59 2 7 34
    After it should be able to solve sudoku and print it into file output.txt

    Here is code:
    Code:
    #include <stdio.h> 
    #include <stdlib.h>
    #include <stdbool.h>
    #include <string.h>
    
    const int SUDOKU_UNKNOWN_VALUE = 0;
    const int FULL_ROW = (9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1);
    
    
    typedef struct Sudoku
    {
        int values[9][9];
        int unknown_count;
    }Sudoku;
    
    typedef int Row[9];
    typedef Row* pRow;
    
     
    bool sudoku_isInputNumberValid(char cisloDoSudoku) {
        const char nejmensiPlatneCisloChar = '1';
        const char nejvetsiPlatneCisloChar = '9';
     
        return cisloDoSudoku <= nejvetsiPlatneCisloChar &&
             cisloDoSudoku >= nejmensiPlatneCisloChar;
    }
     
    int convertCharToNumber(char number) {
        return number - '0';
    }
     
    Sudoku* sudoku_init() {
    Sudoku* sudoku = malloc(sizeof(Sudoku));
        for (int y = 0; y < 9; y++) {
            for (int x = 0; x < 9; x++) {
                sudoku->values[y][x] = SUDOKU_UNKNOWN_VALUE;
                sudoku->unknown_count = 81;
            }
        }
    return sudoku;
    }
    
     
    void sudoku_nactiZeSouboru(char* fileName, Sudoku* sudoku) {
        FILE *fileHandle;
        if ((fileHandle = fopen(fileName, "r")) == NULL) {
            perror("Error opening file");
            exit(EXIT_FAILURE); 
        }
            for (int y = 0; y < 9; y++) 
            {
                for (int x = 0; x < 10; x++) 
                {
                    char nactenyZnakZeVstupu = fgetc(fileHandle);
                    if(nactenyZnakZeVstupu == '\n') {
                        break;
                    }else if(nactenyZnakZeVstupu == ' ') {
                        continue;
                    }
                    if(!sudoku_isInputNumberValid(nactenyZnakZeVstupu)) {
                        perror("Chybny vstup. Cislo neni cislo. :-(");
                        exit(EXIT_FAILURE);
                    }
                    if(x>9) {
                        perror("Podivne, vstup prosel validaci, ale jsme v 10 sloupci. Mate v souboru spravny pocet sloupcu?");
                        exit(EXIT_FAILURE);
                    }
                    
                    sudoku->values[y][x] = convertCharToNumber(nactenyZnakZeVstupu);
                }
            }
        fclose(fileHandle);
    }
    
    void sudoku_print(char* outputFile, Sudoku* sudoku) {
        FILE *filePrinter;
        if ((filePrinter = fopen(outputFile, "w")) != NULL) 
        {
            //fputc(c,filePrinter);//...WHY?
            for (int y = 0; y < 9; y++) {
                for (int x = 0; x < 9; x++) {
                    if(sudoku->values[y][x]==0){
                        printf(" ");
                        fprintf(filePrinter," ");
                    }
                    else {
                    printf("%d", sudoku->values[y][x]);
                    fprintf(filePrinter, "%d", sudoku->values[y][x]);
                    }
                }
                printf("\n");
                fprintf(filePrinter, "\n");
            }
            fclose(filePrinter);
        }
    }
    
    /*
    Returns just an array of missing numbers
    10-th member is count of mi
    */
    int* diagnoseRow(Row row){
        int* missed = malloc(sizeof(int)*10);
        memset(missed, 0, 10*sizeof(int));
        int count = 0;
        int numbers[] = {1,2,3,4,5,6,7,8,9};
        for(int i = 0; i < 9; i++)
        {
            if(row[i] == 0){
            missed[count] = i;
            count++;
            }else{
            for(int o=0;o<9;o++){
                if(numbers[o]==row[i]) 
                    numbers[o] = -1;
            }
            }
    
        }
        missed[9] = count;
        count = 0;
        for(int o=0;o<9;o++){
            if(numbers[o]!=-1) {
                missed[count] = numbers[o];
                count++;
            }
        }
        return missed;
    }
    
    //Evaluates how much missing numbers there still is (isn't)
    void updateCount(Sudoku* sudoku)
    {
        int count = 0;
        for(int i=0;i<9;i++)
        {
            int* row = diagnoseRow(sudoku->values[i]);
            count += row[9];
        }
    }
    
    //trivial check for last number which can be simply filled in
    void lastNCheck(pRow row)
    {
        
        int ucount = 0;
        int index = -1;
        int sum = FULL_ROW;
        int reach = sum;
        for(int i = 0; i < 9; i++)
        {
            if((*row)[i] == SUDOKU_UNKNOWN_VALUE)
            {
                ucount++;
                index = i;
            }
            else{
            reach -= (*row)[i];
            }
        }
        if(ucount==1)
        {
            (*row)[index] = reach;
        }
    }
    
    
    void row_procedure(pRow row)
    {
        lastNCheck(row);
        int* mn = diagnoseRow(*row);
        //...
        //more procedures...
        //...
        free(mn);
    }
    
    Sudoku transpose(Sudoku sudoku)
    {
        Sudoku outputSud;
        for(int p = 0; p < 9; p++) {
            
            for(int q = 0;q < 9; q++) {
                outputSud.values[p][q] = sudoku.values[q][p];
            }
        }
        outputSud.unknown_count = sudoku.unknown_count;
        return outputSud;
    }
     
    
    //Algoritmus bude potreba trochu dotunit
    void sudoku_resolve(Sudoku* sudoku) {
        //do {
            for(int p = 0; p < 9; p++) {
                row_procedure(&(sudoku->values[p]));
                for(int q = 0;q < 9; q++) {
                    Sudoku tr = transpose(*sudoku);//transponuje
                    row_procedure(&(tr.values[q]));//vyresi sloupec, resp. radek
                    tr = transpose(tr);//transponuje zpet
                    *sudoku = tr;//ulozi do sudoka
                }
            }
            updateCount(sudoku);
        //} while (sudoku->unknown_count > 0);
    }
    
     
    int main() {
        
        // 0) Inicializace
        Sudoku* sudoku = sudoku_init();
     
        // 1) načtu soubor
        sudoku_nactiZeSouboru("soubor.txt", sudoku);
        
        // 2) vyřeším
        sudoku_resolve(sudoku);
        
        // 3) zkusím to vypsat
        sudoku_print("output.txt", sudoku);
            
        
        return 0;
    }

  2. #2
    Registered User
    Join Date
    Jun 2011
    Posts
    4,509
    What exactly did you need help with? Is it failing to compile? Is it crashing? Is it giving the wrong output? What specifically is the problem?

  3. #3
    Registered User
    Join Date
    Oct 2012
    Location
    Svitavy, Czech Republic
    Posts
    37
    Program is crashing because algorithm for solving isn't correct and I really don't know, how to make it correctly. And too I don't know which algorithm could be faster (backtracking?).

    Thank you.

  4. #4
    Registered User
    Join Date
    Jun 2011
    Posts
    4,509
    To be quite honest, there's not much I can personally do to help. There's a lot of code, and the comments and variable names are in a language I don't understand, so following the flow of the program is exceedingly difficult for me. I simply don't have the time to dig through this and help figure it out. Especially since you gave almost no details about the nature and location of the problem you're having.

    This would be a good time to learn how to use a debugger. Set some break points in your solving function (I'm guessing it's the "sudoku_resolve()" function), step through the code, check the values of your variables, and see where they are going wrong.

    ...algorithm for solving isn't correct and I really don't know, how to make it correctly. And too I don't know which algorithm could be faster...
    Focus on getting an algorithm to work, before worrying too much about trying to make it faster.

  5. #5
    Registered User
    Join Date
    Oct 2012
    Location
    Svitavy, Czech Republic
    Posts
    37

    problem part of sudoku solving program

    When I run program after compile process then it fall down (after some time) because I don't know how to write part of program which is responsible for solving sudoku.
    Code:
    #include <stdio.h> 
    #include <stdlib.h>
    #include <stdbool.h>
    #include <string.h>
    
    const int SUDOKU_UNKNOWN_VALUE = 0;
    const int FULL_ROW = (9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1);
    
    
    typedef struct Sudoku
    {
        int values[9][9];
        int unknown_count;
    }Sudoku;
    
    typedef int Row[9];
    typedef Row* pRow;
    
     
    bool sudoku_isInputNumberValid(char cisloDoSudoku) {
        const char nejmensiPlatneCisloChar = '1';
        const char nejvetsiPlatneCisloChar = '9';
     
        return cisloDoSudoku <= nejvetsiPlatneCisloChar &&
             cisloDoSudoku >= nejmensiPlatneCisloChar;
    }
     
    int convertCharToNumber(char number) {
        return number - '0';
    }
     
    Sudoku* sudoku_init() {
    Sudoku* sudoku = malloc(sizeof(Sudoku));
        for (int y = 0; y < 9; y++) {
            for (int x = 0; x < 9; x++) {
                sudoku->values[y][x] = SUDOKU_UNKNOWN_VALUE;
                sudoku->unknown_count = 81;
            }
        }
    return sudoku;
    }
    
     
    void sudoku_nactiZeSouboru(char* fileName, Sudoku* sudoku) {
        FILE *fileHandle;
        if ((fileHandle = fopen(fileName, "r")) == NULL) {
            perror("Error opening file");
            exit(EXIT_FAILURE); 
        }
            for (int y = 0; y < 9; y++) 
            {
                for (int x = 0; x < 10; x++) 
                {
                    char nactenyZnakZeVstupu = fgetc(fileHandle);
                    if(nactenyZnakZeVstupu == '\n') {
                        break;
                    }else if(nactenyZnakZeVstupu == ' ') {
                        continue;
                    }
                    if(!sudoku_isInputNumberValid(nactenyZnakZeVstupu)) {
                        perror("Chybny vstup. Cislo neni cislo. :-(");
                        exit(EXIT_FAILURE);
                    }
                    if(x>9) {
                        perror("Podivne, vstup prosel validaci, ale jsme v 10 sloupci. Mate v souboru spravny pocet sloupcu?");
                        exit(EXIT_FAILURE);
                    }
                    
                    sudoku->values[y][x] = convertCharToNumber(nactenyZnakZeVstupu);
                }
            }
        fclose(fileHandle);
    }
    
    void sudoku_print(char* outputFile, Sudoku* sudoku) {
        FILE *filePrinter;
        if ((filePrinter = fopen(outputFile, "w")) != NULL) 
        {
            //fputc(c,filePrinter);//...WHY?
            for (int y = 0; y < 9; y++) {
                for (int x = 0; x < 9; x++) {
                    if(sudoku->values[y][x]==0){
                        printf(" ");
                        fprintf(filePrinter," ");
                    }
                    else {
                    printf("%d", sudoku->values[y][x]);
                    fprintf(filePrinter, "%d", sudoku->values[y][x]);
                    }
                }
                printf("\n");
                fprintf(filePrinter, "\n");
            }
            fclose(filePrinter);
        }
    }
    
    /*
    Returns just an array of missing numbers
    10-th member is count of mi
    */
    int* diagnoseRow(Row row){
        int* missed = malloc(sizeof(int)*10);
        memset(missed, 0, 10*sizeof(int));
        int count = 0;
        int numbers[] = {1,2,3,4,5,6,7,8,9};
        for(int i = 0; i < 9; i++)
        {
            if(row[i] == 0){
            missed[count] = i;
            count++;
            }else{
            for(int o=0;o<9;o++){
                if(numbers[o]==row[i]) 
                    numbers[o] = -1;
            }
            }
    
        }
        missed[9] = count;
        count = 0;
        for(int o=0;o<9;o++){
            if(numbers[o]!=-1) {
                missed[count] = numbers[o];
                count++;
            }
        }
        return missed;
    }
    
    //Evaluates how much missing numbers there still is (isn't)
    void updateCount(Sudoku* sudoku)
    {
        int count = 0;
        for(int i=0;i<9;i++)
        {
            int* row = diagnoseRow(sudoku->values[i]);
            count += row[9];
        }
    }
    
    //trivial check for last number which can be simply filled in
    void lastNCheck(pRow row)
    {
        
        int ucount = 0;
        int index = -1;
        int sum = FULL_ROW;
        int reach = sum;
        for(int i = 0; i < 9; i++)
        {
            if((*row)[i] == SUDOKU_UNKNOWN_VALUE)
            {
                ucount++;
                index = i;
            }
            else{
            reach -= (*row)[i];
            }
        }
        if(ucount==1)
        {
            (*row)[index] = reach;
        }
    }
    
    
    void row_procedure(pRow row)
    {
        lastNCheck(row);
        int* mn = diagnoseRow(*row);
    
        free(mn);
    }
    
    Sudoku transpose(Sudoku sudoku)
    {
        Sudoku outputSud;
        for(int p = 0; p < 9; p++) {
            
            for(int q = 0;q < 9; q++) {
                outputSud.values[p][q] = sudoku.values[q][p];
            }
        }
        outputSud.unknown_count = sudoku.unknown_count;
        return outputSud;
    }
     
    
    //Algorithm isn't working correctly and that is the PROBLEM
    void sudoku_resolve(Sudoku* sudoku) {
    
        do {
            for(int p = 0; p < 9; p++) {
                row_procedure(&(sudoku->values[p]));
                for(int q = 0;q < 9; q++) {
                    Sudoku tr = transpose(*sudoku);//transponuje
                    row_procedure(&(tr.values[q]));//vyresi sloupec, resp. radek
                    tr = transpose(tr);//transponuje zpet
                    *sudoku = tr;//ulozi do sudoka
                }
            }
            updateCount(sudoku);
        } while (sudoku->unknown_count > 0);
    }
    
     
    int main() {
        
        // 0) Inicializace
        Sudoku* sudoku = sudoku_init();
     
        // 1) načtu soubor
        sudoku_nactiZeSouboru("soubor.txt", sudoku);
        
        // 2) vyřeším
        sudoku_resolve(sudoku);
        
        // 3) zkusím to vypsat
        sudoku_print("output.txt", sudoku);
            
        
        return 0;
    }

  6. #6
    Registered User
    Join Date
    Jun 2011
    Posts
    4,509
    ...because I don't know how to write part of program which is responsible for solving sudoku.
    Did you research for any such algorithms? A quick web search for "sudoku solving algorithm" brought up a lot of results - there is even a wikipedia page specifically on the topic.

  7. #7
    Registered User
    Join Date
    Oct 2012
    Location
    Svitavy, Czech Republic
    Posts
    37
    I know this, but I don't know how to include for example backtracking method (like here) into the program? Please I need this program for my friend, I thought I'll be able to make it for him, but I am not so advanced yet and deadline is tomorrow, that is why I am asking you for help here.

    Thank you for your help.

  8. #8
    Registered User
    Join Date
    Jun 2011
    Posts
    4,509
    Your best bet would be to start a fresh program from scratch and practice implementing the given method in a simplified setting. When you get it to work, you can incorporate it into the program you have provided above.

    If/when you run into problems, post the simplified (yet complete) program with specific questions. Using a simplified "demo" program in this way will make it easier for you to develop, and easier for us to help when you get stuck.

  9. #9
    Registered User
    Join Date
    Jun 2005
    Posts
    6,815
    Quote Originally Posted by maestorm View Post
    When I run program after compile process then it fall down (after some time) because I don't know how to write part of program which is responsible for solving sudoku.
    Sorry, but this forum isn't here so you can get people to write code because you don't understand the required algorithm (or, possibly, algorithms in this case).

    You need to do the work to understand the algorithm(s) needed, and work out how to implement them in code. Yes, that may be a little challenging but, if folks here do that for you, you learn exactly nothing of value.
    Right 98% of the time, and don't care about the other 3%.

    If I seem grumpy or unhelpful in reply to you, or tell you you need to demonstrate more effort before you can expect help, it is likely you deserve it. Suck it up, Buttercup, and read this, this, and this before posting again.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Explain sudoku brute force algorithm
    By suryak in forum C Programming
    Replies: 9
    Last Post: 08-07-2011, 01:56 PM
  2. include's in the middle of the code?
    By dayalsoap in forum C Programming
    Replies: 1
    Last Post: 09-16-2010, 12:25 AM
  3. Sudoku Brute Force Algorithm Help (recursion?)
    By ridilla in forum C Programming
    Replies: 22
    Last Post: 05-07-2010, 03:31 PM
  4. Sudoku solution generator algorithm
    By Swarvy in forum C++ Programming
    Replies: 21
    Last Post: 12-08-2008, 04:37 AM
  5. Why I don't have to include code.c in this example?
    By meili100 in forum C++ Programming
    Replies: 2
    Last Post: 06-11-2008, 02:11 AM