malloc, structures, arrays and sudoku!!

Hi everyone,

A while ago i wrote a program to solve a sudoku board by way of learning to program in C. It worked and i learned a lot (and caught the bug!)
Now i'm looking at improving it.

The original program was to solve a 9x9 board. But i'd like to modify it so the user inputs the board size.

So i'd have an array: board[width][width][9]

Can anyone suggest the best way to go about this?
Will i have to use malloc()?
Firstly should i have it as a structure?
like

Code:

---

struct board {
int array[width][width][9]
};

---

Or is there no advantage in having a structure with only one variable type?
Thanks in advance,
Kai.

int array[width][width][9]

Wouldn't this be for producing a sudoku cube?

Why do you want to make the array a struct variable?

You're right, there is no advantage. structs are only for compound types (a collection of a few things, not one). ;)

The declaration would look like:-

Code:

---

int *array;

---

This refers to a pointer to one or more ints. You would then do:-

Code:

---

array = malloc(width  * width);

---

So this allocates width * width ints. Remember to use free(array) when you're finished!

Well the board would be width x width in size and each square would have a maximum of 9 possibilities.

Thats how i was going to store the values. Is there a better way do you think?

Also i thought maybe a structure would be pointless as its only one variable type.
later on maybe when i start making comparisons of 2 arrays maybe then i could put it in a structure?

Any ideas how to use malloc() in this way?

Thanks for your quick reply!

Quote:

---

Originally Posted by SMurf

You're right, there is no advantage. structs are only for compound types (a collection of a few things, not one). ;)

The declaration would look like:-

Code:

---

int *array;

---

This refers to a pointer to one or more ints. You would then do:-

Code:

---

array = malloc(width  * width);

---

So this allocates width * width ints. Remember to use free(array) when you're finished!

---

Wow, replying quicker than i can type! Thanks!

So then how would i refer to specific parts of the array?

Code:

---

int *board;

board = malloc(width * width * 9);

---

would that be right for my example?

Congrats on your Sudoku program. :)

I don't see any advantage to using a structure for the board. I've written two versions of Sudoku solvers - one with a 2D board, and one with a 3D board (using the deeper boards to hold the "possibles" for each square). Both worked with the standard 9 x 9 game boards.

The 2D board was the better choice for speed (slightly), and my logic. I used an array of structs if "human" logic was unable to solve the puzzle, and trial and error was needed.

I never saw a need to malloc the board off the heap. The stack worked fine, and making the board array global, just made sense to me, since every function would need to access or modify it.

Although they are geeks to the core, you may want to check out the sudoku programmers forum, and the more active Sudoku players forum. I've lost the url in my last disk crash, but it's in Google. The regulars there, have forgotten more about programming for Sudoku, than you (and definitely more than I), are ever likely to learn in a lifetime.

Will you be changing your solving algorithm to better handle the larger board size?

In my programs, on a standard board, the human logic functons are fast, but the trial and error function usually does find the solution quickly, also. On a larger board, I would expect the trail and error function to take much longer.

Good luck, and I hope you'll report back how your program progresses.

This would allocate enough memory to hold width * width * 9 bytes:

Code:

---

board = malloc(width * width * 9);

---

You want space for width * width * 9 INTEGERS:

Code:

---

board = malloc(width * width * 9 * sizeof(int));

---

Another point is that now you have a completely flat space with that many integers. If we assume that width is 9, then you would have 729 integers in one array, from board[0] to board[728]. That is not equivalent to your 3 dimensional array you use at the moment. To achieve a multidimensional array, you need to use multi-level pointers, and for dynamic sizing, you'd need to use multiple mallocs.

--
Mats

Quote:

---

Originally Posted by Adak

Congrats on your Sudoku program. :)

I don't see any advantage to using a structure for the board. I've written two versions of Sudoku solvers - one with a 2D board, and one with a 3D board (using the deeper boards to hold the "possibles" for each square). Both worked with the standard 9 x 9 game boards.

The 2D board was the better choice for speed (slightly), and my logic. I used an array of structs if "human" logic was unable to solve the puzzle, and trial and error was needed.

I never saw a need to malloc the board off the heap. The stack worked fine, and making the board array global, just made sense to me, since every function would need to access or modify it.

Although they are geeks to the core, you may want to check out the sudoku programmers forum, and the more active Sudoku players forum. I've lost the url in my last disk crash, but it's in Google. The regulars there, have forgotten more about programming for Sudoku, than you (and definitely more than I), are ever likely to learn in a lifetime.

Will you be changing your solving algorithm to better handle the larger board size?

In my programs, on a standard board, the human logic functons are fast, but the trial and error function usually does find the solution quickly, also. On a larger board, I would expect the trail and error function to take much longer.

Good luck, and I hope you'll report back how your program progresses.

---

Thanks!

I started it purely as a learning exercise. I don't see the point in following tutorials etc unless you're actually using the code in a problem. So i set myself a problem and set about learning how to complete it. The people on here were a great help!

So in your 2D program, you had an array for the board where each member of the array was a structure?
Mine was purely a 9*9*9 array where the first 2 were the x and y coordinates of the array and the last held the possibilities. I didn't know any other way to be honest. My program is very simple (in technicality) but as a result is probably totally bloated and slow!

To be honest i still have no idea how malloc and pointers work.
I thought that it would be a necessity to use malloc() if the board size was undefined?

If you have any thoughts on this, please let me know!
Cheers
Kai.

Quote:

---

Originally Posted by matsp

This would allocate enough memory to hold width * width * 9 bytes:

Code:

---

board = malloc(width * width * 9);

---

You want space for width * width * 9 INTEGERS:

Code:

---

board = malloc(width * width * 9 * sizeof(int));

---

Another point is that now you have a completely flat space with that many integers. If we assume that width is 9, then you would have 729 integers in one array, from board[0] to board[728]. That is not equivalent to your 3 dimensional array you use at the moment. To achieve a multidimensional array, you need to use multi-level pointers, and for dynamic sizing, you'd need to use multiple mallocs.

--
Mats

---

Ah ok, i think i understand. So malloc() isn't a way to access the array directly, just a method to reserve enough dynamic memory to the potential array?

So as a simple example... if i did:

Code:

---

board = malloc(width * width);

---

and made width = 3;
i'd have reserved (at least?)81 bytes of memory?
so how would i access individual 'cells' of the array?

could i do:

Code:

---

printf("%d\n", board[2][2]);

---

You would reserve space for an array of width * width, of chars.
You access them just as you would an array.
And remember that it's possible to write pointers such as:
int* board = malloc(height * width * sizeof(int)); // Reserves space for a height x width array of int.
(Not the position of the *.)

Again, this is only necessary if you don't know the size of the board prior to the game starting. Arrays sizes must be static - ie the size known at compile time; otherwise you need to do dynamic allocation.

Also, have you read about pointers and how to use them?

I completely agree (and really cheer) you wanting to solve the Sudoku puzzle with your own pogram, without others handing you the solution.

That's just what I did. Later, I found the Sudoku programmer's forum because it's always good to chat and read what the experts are saying. There are subtle ways of working with Sudoku that are unbelievable if you're new to the puzzle.

The only place I used an array of structs was in the trial and error function. In that function, I needed to keep several bits of data on hand for each unsolved sqr: it's sqr #, the number of possibles it still had, and what those possibles were.

So say I had ten squares that were unsolved - then my array of structs would only have 10 entries in it, 0 - 9, that were being used. Now instead of scanning through the entire board to get info on which sqr to take a guess at next, the program just refers to my sorted array of structs, and always gets the sqr with the lowest number of possibles remaining.

My hope was to get this smaller array of structs, all into cache memory, and keep it there. I have no way of knowing if I was successful or not, in that attempt.

If and when you're ready to take a leap into total geek-dom, check out Knuth's "Dancing Links" (aka "DLX"), "chains" and "swordfish", on the Sudoku programmer's forum.

If your blood begins to overheat, or foam comes out your nose or ears - just walk away! And smile, you're not a total geek, just yet. :cool:

Pointers are just an address. In a program that is so focused on an array, working with the board array indices's as much as possible, seems quite natural.

If you want the array size to be variable, then malloc or calloc will be needed.

I'm afraid that once you use dynamically allocated arrays, you can no longer use array[][] or higher rank accessing. You must calculate the element offset yourself:

Code:

---

board[row * width + col - 1]

---

Thanks for the replys guys.

I think maybe its too difficult at the moment to have a dynamic array. I don't even know where to begin with that!!

I'll stick to a fixed array and see how i get on with that!

At the moment, i'm working on a program to calculate interest on my (substantial) debt. Its a bit easier but no doubt i'll need help with that too!!

Thanks.

Quote:

---

Originally Posted by nonoob

I'm afraid that once you use dynamically allocated arrays, you can no longer use array[][] or higher rank accessing. You must calculate the element offset yourself:

Code:

---

board[row * width + col - 1]

---

---

That is incorrect. All you need to do is allocate the correct amount of bytes and use the correct type.
T (*pointer)[cols]