Thread: 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;
}

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?

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.

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.

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;
}

...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.

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.

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.