Member 13756867 Ответов: 2

Как правильно получить сетку судоку 9х9 ?


#include <bits/stdc++.h>
#include <cstdlib>

using namespace std;

#define SIZE 9

int table[SIZE][SIZE];




void init_table();
void print_table();
void fill_table(int);
void rand_mark(int,int);
bool isValid () ;




void init_table(){
	for (int i=0; i<SIZE; i++){
		for (int j=0; j<SIZE; j++){
			table[i][j] = 0;
		}
	}
}

void print_table(){
	for (int i=0; i<SIZE; i++){
		for (int j=0; j<SIZE; j++){
			if (table[i][j] != 0)
				cout << table[i][j] << "|";
			else
				cout << ' ' << "|";
		}
		cout << endl;
	}
}


void fill_table(int num){
	int x_pos;
	int y_pos;


	int counter = 0;
    while (counter < num){
        x_pos = (rand() % (SIZE));
        y_pos = (rand() % (SIZE));

        if(table[x_pos][y_pos] == 0 ) {
            rand_mark (x_pos, y_pos);
            counter++;
		}
	}
}

void rand_mark(int x_pos, int y_pos){
	int r_num;
	bool exit = false;

	while (exit == false ){
		exit = true;
		r_num = (rand() % (SIZE));

		for (int i=0; i<SIZE; i++)
			if (table[x_pos][i] == r_num || table[i][y_pos] == r_num){
				exit = false;
				break;
			}
	};

	table[x_pos][y_pos] = r_num;
}


bool isValid(int i, int j, const int table[][9])
{
 // Check whether grid[i][j] is valid at the i's row

    for (int column = 0; column < 9; column++)
        if (column != j && table[i][column] == table[i][j])
            return false;

 // Check whether grid[i][j] is valid at the j's column
    for (int row = 0; row < 9; row++)
        if (row != i && table[row][j] == table[i][j])
            return false;

 // Check whether grid[i][j] is valid in the 3-by-3 box
    for (int row = (i / 3) * 3; row < (i / 3) * 3 + 3; row++)
        for (int col = (j / 3) * 3; col < (j / 3) * 3 + 3; col++)
            if (row != i && col != j && table[row][col] == table[i][j])
            return false;
    return true; // The current value at grid[i][j] is valid

}



int main(){
    srand(time(NULL));
	int num;
	init_table();
    cout << "Generate how many numbers (40 max)? ";
    cin >> num;

    while (true) {
	fill_table(num);


	print_table();
    }



}


Что я уже пробовал:

у меня есть функция, чтобы проверить, следует ли сетка правилу судоку, но не могу заставить ее работать

2 Ответов

Рейтинг:
1

OriginalGriff

Не заполняйте сетку судоку случайными числами: почти нет шансов, что в результате вы получите действительную - и тем более разрешимую - сетку. Особенно если вы не делаете никакой проверки любой из цифр, как вы идете!

Я бы начал здесь: Алгоритм судоку: генерирует действительное судоку за 0,018 секунды[^] - это на VB, а не на C++, но это довольно тривиальный язык, и это тот алгоритм, который вам нужен.
Или еще лучше, есть вот это: Генерация головоломок судоку: от простого к злому
[^] который охватывает весь процесс, включая решатели и "рытье ям" в вашей сгенерированной головоломке Судоку, чтобы изменить уровень сложности.

[редактировать]
Я просто пробежал цифры, и количество допустимых сеток судоку (игнорируя отверстия) равно:

6,670,903,752,021,072,936,960
Число возможных различных сеток 9 х 9, которые вы можете сгенерировать со случайными числами, равно:
196,627,050,475,552,913,618,075,908,526,912,116,283,103,450,944,214,766,927,315,415,537,966,391,196,809
Давая вам вероятность того, что
1:29,475,324,151,691,010,931,910,048,396,714,644,277,009,639,903,774,243,212
о создании действительной сетки судоку, используя только случайные числа...Это может занять некоторое время... :)
[/редактировать]


Рейтинг:
0

Patrice T

Я бы начал с того, что сделал бы функцию и прототип совпадающими:

bool isValid () ;
...
bool isValid(int i, int j, const int table[][9]) {

Дело в том, что isValid не используется, тоже не поможет.