I am trying to build a sudoku game in c, I dont need it to solve the sudoku, but for the user to input the first couple numbers and then choose the moves he wants, however the moves need to be in a decision tree, which i dont know how to build. I will provide the entire script but i am pretty sure that the problem is in the fillintree function. That function should take the first sudoku matrix, and based on other functions it should fill in the tree to the end(all the possibilities). Another important thing is that the possiblemoves function return a pointer to a list which keeps the possible moves in a row/col/val format (112 for example, would be putting a two in the first row and first column position). CheckValid just checks if the board is valid (has duplicates in either the same row, column, etc.) EmptyCount just returns how many empty spaces on the board there are (empty spaces are zeroes). Here is my entire code so far. Thank you.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void printMatrix(int matrix[4][4]){
int tmp = 0;
for (int i = 0; i < 4; i++){
for (int j = 0; j < 4; j++){
tmp++;
printf("%d ", matrix[i][j]);
if (tmp%4 == 0){
putchar('n');
}
}
}
}
int checkValid(int matrix[4][4]){
// 0 = nevalidno
//1 = validno
int count[4] = {0,0,0,0};
for (int i = 0; i < 4; i++){
for (int j = 0; j < 4; j++){
if (matrix[i][j] != 0){
count[matrix[i][j] - 1] += 1;
}
else {
continue;
}
if (matrix[i][j] < 1 || matrix[i][j] > 4){
printf("Tabla je nevalidnan");
return 0;
}
}
for (int i = 0; i < 4; i++){
if (count[i] > 1){
printf("Tabla je nevalidnan");
return 0;
}
}
for (int k = 0; k < 4; k++){
count[k] = 0;
}
}
for (int j = 0; j < 4; j++){
for (int i = 0; i < 4; i++){
if (matrix[i][j] != 0){
count[matrix[i][j] - 1] += 1;
}
else {
continue;
}
if (matrix[i][j] < 1 || matrix[i][j] > 4){
printf("Tabla je nevalidnan");
return 0;
}
}
for (int i = 0; i < 4; i++){
if (count[i] > 1){
printf("Tabla je nevalidnan");
return 0;
}
}
for (int k = 0; k < 4; k++){
count[k] = 0;
}
}
for (int i = 0; i < 2; i++){
for (int j = 0; j < 2; j++){
if (matrix[i][j] != 0){
count[matrix[i][j] - 1] += 1;
}
else {
continue;
}
if (matrix[i][j] < 1 || matrix[i][j] > 4){
printf("Tabla je nevalidnan");
return 0;
}
}
}
for (int i = 0; i < 4; i++){
if (count[i] > 1){
printf("Tabla je nevalidnan");
return 0;
}
}
for (int k = 0; k < 4; k++){
count[k] = 0;
}
for (int i = 2; i < 4; i++){
for (int j = 0; j < 2; j++){
if (matrix[i][j] != 0){
count[matrix[i][j] - 1] += 1;
}
else {
continue;
}
if (matrix[i][j] < 1 || matrix[i][j] > 4){
printf("Tabla je nevalidnan");
return 0;
}
}
}
for (int i = 0; i < 4; i++){
if (count[i] > 1){
printf("Tabla je nevalidnan");
return 0;
}
}
for (int k = 0; k < 4; k++){
count[k] = 0;
}
for (int i = 0; i < 2; i++){
for (int j = 2; j < 4; j++){
if (matrix[i][j] != 0){
count[matrix[i][j] - 1] += 1;
}
else {
continue;
}
if (matrix[i][j] < 1 || matrix[i][j] > 4){
printf("Tabla je nevalidnan");
return 0;
}
}
}
for (int i = 0; i < 4; i++){
if (count[i] > 1){
printf("Tabla je nevalidnan");
return 0;
}
}
for (int k = 0; k < 4; k++){
count[k] = 0;
}
for (int i = 2; i < 4; i++){
for (int j = 2; j < 4; j++){
if (matrix[i][j] != 0){
count[matrix[i][j] - 1] += 1;
}
else {
continue;
}
if (matrix[i][j] < 1 || matrix[i][j] > 4){
printf("Tabla je nevalidnan");
return 0;
}
}
}
for (int i = 0; i < 4; i++){
if (count[i] > 1){
printf("Tabla je nevalidnan");
return 0;
}
}
return 1;
}
int emptyCount(int matrix[4][4]){
int count = 0;
for (int i = 0; i < 4; i++){
for (int j = 0; j < 4; j++){
if (matrix[i][j] == 0){
count += 1;
}
}
}
return count;
}
int* possibleMoves(int matrix[4][4]){
int num, i, j, k, p = 0;
int *a = malloc(100*sizeof(int));
for (num = 1; num < 5; num++){
for (i = 0; i < 4; i++){
for (j = 0; j < 4; j++){
if (matrix[i][j] == 0 && matrix[i][0] != num && matrix[i][1] != num && matrix[i][2] != num && matrix[i][3] != num && matrix[0][j] != num && matrix[1][j] != num && matrix[2][j] != num && matrix[3][j] != num && matrix[(i/2)*2][(j/2)*2] != num && matrix[(i/2)*2 + 1][(j/2)*2] != num && matrix[(i/2)*2 + 1][(j/2)*2 + 1] != num && matrix[(i/2)*2][(j/2)*2 + 1] != num){
a[p++] = i*100 + j*10 + num;
}
}
}
}
return a;
}
typedef struct Node{
int matrix[4][4];
struct Node** children;
int numchildren;
int issolution;
} Node;
Node* createNode(int matrix[4][4]){
Node* newnode = (Node*)malloc(sizeof(Node));
newnode->numchildren = 0;
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
newnode->matrix[i][j] = matrix[i][j];
}
}
if (emptyCount(matrix) == 0 && checkValid(matrix) == 1){
newnode->issolution = 1;
}
else{
newnode->issolution = 0;
}
newnode->children = NULL;
return newnode;
}
void addChild(Node* parent, Node* child){
parent->children = (Node**)realloc(parent->children, (parent->numchildren + 1)*sizeof(Node*));
parent->children[parent->numchildren++] = child;
}
void fillinTree(int matrix[4][4]) {
Node* root = createNode(matrix);
if (root == NULL) {
return;
}
Node** nodesToProcess = (Node**)malloc(30 * sizeof(Node*));
if (nodesToProcess == NULL) {
free(root);
return;
}
nodesToProcess[0] = root;
int numNodesToProcess = 1;
for (int index = 0; index < numNodesToProcess; index++) {
Node* current = nodesToProcess[index];
int* moves = possibleMoves(current->matrix);
if (moves == NULL) {
free(nodesToProcess);
free(root);
return;
}
for (int i = 0; moves[i] != 0; i++) {
int move = moves[i];
int row = move / 100;
int col = (move % 100) / 10;
int value = move % 10;
int newMatrix[4][4];
memcpy(newMatrix, current->matrix, sizeof(newMatrix));
newMatrix[row][col] = value;
Node* newNode = createNode(newMatrix);
if (newNode == NULL) {
free(nodesToProcess);
free(root);
free(moves);
return;
}
addChild(current, newNode);
nodesToProcess[numNodesToProcess++] = newNode;
}
free(moves);
}
free(root);
free(nodesToProcess);
}
void printTree(Node* root){
if (root == NULL) {
return;
}
//printf("%d -> ", root->issolution);
printMatrix(root->matrix);
for (int i = 0; i < root->numchildren; ++i) {
printTree(root->children[i]);
}
}
int main(){
int matrix[4][4] = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, *movelist;
for (int i = 0; i < 4; i++){
scanf("%d%d%d%d", &matrix[i][0], &matrix[i][1], &matrix[i][2], &matrix[i][3]);
}
putchar('n');
if (checkValid(matrix) && emptyCount(matrix) <= 11){
printMatrix(matrix);
}
else{
return 1;
}
movelist = possibleMoves(matrix);
for (int i = 0; i < 100; i++){
if (movelist[i] != 0){
printf("%d (%d) ", movelist[i], i);
}
}
putchar('n');
fillinTree(matrix);
Node* root = createNode(matrix);
printTree(root);
free(movelist);
return 0;
}