Генератор Судоку вызывает случайный бесконечный цикл [C]

Question

Я создаю генератор sudoku в C, но когда я запускаю программу, он становится случайным в бесконечном цикле. Иногда он печатает все строки, иногда только один и т. Д. И т. Д. (См. Изображения ниже) Это код В чем проблема?

#include <string.h> 
#include <stdlib.h> 
#include "sudoku.h" 
#include <stdio.h> 
#include <time.h> 

int dimension = 9; 

int main(int argc, char** argv){ 
    int dimension = 9; 
    int j ,k,i ; 
    int ** sudo = malloc(sizeof(*sudo)*dimension); 
    for (j = 0; j< dimension; j++){ 
    sudo[j] = malloc(sizeof(int)*dimension); 
    } 
    riempiSudoku(sudo); 
    return 0; 

void riempiSudoku(int** sudo){ //fill sudoku 
    int j,i,k,f; 
    int len; 
    //srand (time(NULL)); 
    int ran; 
    for (i=0;i<dimension;i++){ 
    for(j=0;j<dimension;j++){ 
     if(!thereisNumber(sudo, i,j)){ 
    printf("\nNon ci sono numeri\n");//no solution, stop the program 
    exit(0); 
     } 
     printf("%d ", sudo[i][j]); 
    } 
    printf("\n"); 
    } 
} 


int checkRow(int** sudo, int row, int value){ //check if the number is in the row 
    int i; 
    for (i = 0; i<dimension; i++){ 
    if (sudo[row][i] == value) 
     return 1; 
    } 
    return 0; 
} 

int checkCol(int** sudo, int col, int value){//check if the number is in the col 
    int i; 
    for (i = 0; i<dimension; i++){ 
    if (sudo[i][col] == value) 
     return 1; 
    } 
    return 0; 

} 


int checkSquare(int** sudo, int row, int col, int value){ 
    int i, j; 
    for(i= (row/3)*3; i<(row/3)*3 +3; i++){ 
    for(j=(col/3)*3; j<(col/3)*3 +3; j++){ 
     if(sudo[i][j] == value) 
    return 1; 
    } 
    } 
    return 0; 

} 
int thereisNumber(int** sudo, int i,int j){ 
    int options[dimension]; 
    int len; 
    for (len=0; len<dimension; len++) 
    options[len] = len + 1;    // populate the array with 1..9 
    while (len) { 
    int ran = rand() % len;   // select an index into the list 
    int digit = options[ran];  // get the number from the available list 
    if (checkSquare(sudo,i,j,digit) || checkRow(sudo,i,digit) || checkCol(sudo,j,digit)) 
     options[ran] = options[--len]; // remove digit from list 
    else{ 
     sudo[i][j]= digit; 
     return len>0; 
    } 
    } 
    return 0; //thereisNumber(sudo,i,j-1); 
} 

те скриншоты http://imgur.com/lQpFOPf это результат БГД http://imgur.com/qp8omko

Answer 1

Ваша программа достигает тупиковой ситуации, когда нет возможных решений - в качестве Ответил @BLUEPIXY.

Но ваша программа не может обнаружить это, она продолжает пробуждать более случайные числа. Я предлагаю использовать что-то вроде Fisher-Yates shuffle, используемого с картами, что удаляет неуспешных кандидатов из множества возможностей.

int options[dimension]; 
int len; 
for (len=0; len<dimension; len++) 
    options[len] = len + 1;    // populate the array with 1..9 
while (len) { 
    int ran = rand() % len;    // select an index into the list 
    int digit = options[ran];   // get the number from the available list 
    if (checkSquare(sudo,i,j,digit) || checkRow(sudo,i,digit) || checkCol(sudo,j,digit)) 
     options[ran] = options[--len]; // remove digit from list 
    else break; 
} 
return len > 0;       // 0 if failed to find digit 

Если функция не удалась, вы должны иметь возможность «отменить» историю посещений номера. Это твоя следующая задача!

EDIT, а не функция «отмены», при каждом размещении номеров вы можете реализовать «массив возможностей», который я показал. Решение довольно сложное, чем вы предполагали, возможно, рекурсивное решение - это то, что необходимо.