Sudoku-Backtracking-solver in C

Dies ist ein Programm mit dem ich gebeten wurde, zu tun, für eine Klasse, hat es zu lösen, ein sudoku der Größe nxn
mit einem backtracking-Algorithmus, aber es ist nicht erforderlich, um zu prüfen, quadratischer Unterteilung, nur Zeilen und Spalten.
das problem mit meinem Programm ist, dass das backtracking Teil nie löst 🙁 wenn es einen Punkt erreicht, wo es nicht weiter, es hält und druckt das board statt dem löschen des letzten Versuch und versuche etwas anderes.
sorry im Voraus für die fehlenden Kommentare, ich habe nur Zugriff auf den code im moment (nicht zu Hause) aber es ist meist ziemlich einfach Funktionen und das problem ist in aux_solveSudoku und sudoku Funktionen, hier der code:

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define UNASSIGNED 0

bool aux_SolveSudoku(int n, int array[][n]);
bool SolveSudoku(int n, int array[][n], int row, int col);
bool check(int n, int array[][n], int row, int col, int number);
bool CheckRow(int n, int array[][n], int row, int number);
bool CheckCol(int n, int array[][n], int col, int number);
bool CheckIfFull(int n, int array[][n]);
void printArray(int n, int array[][n]);

int main()
{
    int n;
    scanf(" %d", &n);
    int array[n][n];

    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            scanf(" %d",&array[i][j]);
        }
    }
    if (aux_SolveSudoku(n, array) == true)
          printArray(n, array);
    else
         printf("No Solution!");


  return 0;
}

bool aux_SolveSudoku(int n, int array[][n]){
    for (int row = 0; row < n; row++){
        for (int col = 0; col < n; col++){
            if (SolveSudoku(n, array, row, col) && CheckIfFull(n, array))
                return true;}
    }
    return false;
}

bool SolveSudoku(int n, int array[][n], int row, int col){
    if(array[row][col] != UNASSIGNED)
        return true;

    for(int i=1; i<=n; i++){
        if(check(n, array, row, col, i)){
            array[row][col] = i;

            if(SolveSudoku(n, array, row, col))
                return true;

            array[row][col] = UNASSIGNED;
        }
    }    
    return false;
}

bool check(int n, int array[][n], int row, int col, int number){
    return (!CheckRow(n, array, row, number) && !CheckCol(n, array, col, number));
} 

bool CheckRow(int n, int array[][n], int row, int number){
    for (int col = 0; col < n; col++){
        if (array[row][col] == number){
            return true;}
    }
    return false;
}

bool CheckCol(int n, int array[][n], int col, int number){
    for (int row = 0; row <  n; row++){
        if (array[row][col] == number){
            return true;}
    }
    return false;

}

bool CheckIfFull(int n, int array[][n]){
    for (int i = 0; i < n; i++){
            for (int j = 0; j < n; j++){
                if(array[i][j] == UNASSIGNED)
                    return false;
                    }
            }
    return true;
}

void printArray(int n, int array[][n]){
    for (int row = 0; row < n; row++){
            for (int col = 0; col < n; col++){
                printf("%d ", array[row][col]);}
            printf("\n");
        }
}

Dies ist ein Beispiel-Datensatz für das Programm:

5
0 0 0 2 4
3 1 0 0 2
0 2 1 0 5
2 0 3 0 0
0 0 0 0 0

Das hat natürlich eine Lösung:

1 3 5 2 4
3 1 4 5 2
4 2 1 3 5
2 5 3 4 1
5 4 2 1 3

Leider das Programm nicht die Lösung finden, aber ich verstehe nicht, warum nicht.

  • Nur so wissen Sie, dass ist keine gültige c-code. Es ist C++, die c-Funktionen verwendet. Es gibt keinen Typ bool in c. Sie haben mit int statt.
  • Es ist ein _Bool geben Sie in C99 und C11; wenn Sie die header - <stdbool.h> gibt es auch eine bool geben, und der code verwendet <stdbool.h> (dem C++ - code nicht machen würde). Vergessen Sie nicht, den MSVC-compiler implementiert einen standard, der fast ein Viertel Jahrhundert alt, (die später in diesem Jahr, es wird ein Viertel Jahrhundert alt), und nicht eine der neueren Versionen der standard.
  • Tatsächlich, es ist ein weiterer Grund, das ist nicht C++ - code; es verwendet C99-VLAs (variable length arrays), die nicht Teil einer standard-version von C++ (obwohl der G++ - compiler akzeptiert Sie als eine Erweiterung).
  • Eines der ersten Dinge zu tun ist, um sicherzustellen, dass Daten, die dem entspricht, was Sie dachte, war eingegeben; drucken Sie die Sudoku-Brett vor dem Aufruf aux_SudokuSolver(). Es könnte eher konventionell zu nennen, der Einstiegspunkt SudokuSolver() und die rekursive Funktion aux_SudokuSolver() (Umkehrung der aktuellen Rollen). Aber das ist trivia. Haben Sie es getestet auf 1x1 und 2x2 boards? Was ist 3x3? Der code fehlerfrei kompiliert wird bei mir (gut). Ich würde mir wünschen, drucken Sie das Brett, wie es verarbeitet wird, auf jedem (rekursiven) Eintrag zu SudokuSolver(), so dass ich sehen konnte, was es war.
InformationsquelleAutor user3208617 | 2014-01-18
Schreibe einen Kommentar