Thread: malloc, structures, arrays and sudoku!!

  1. #1
    Registered User
    Join Date
    Oct 2007
    Location
    Glasvegas, Scotland.
    Posts
    68

    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.

  2. #2
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    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?
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  3. #3
    Registered /usr
    Join Date
    Aug 2001
    Location
    Newport, South Wales, UK
    Posts
    1,273
    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!

  4. #4
    Registered User
    Join Date
    Oct 2007
    Location
    Glasvegas, Scotland.
    Posts
    68
    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!

  5. #5
    Registered User
    Join Date
    Oct 2007
    Location
    Glasvegas, Scotland.
    Posts
    68
    Quote Originally Posted by SMurf View Post
    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?

  6. #6
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    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.

  7. #7
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  8. #8
    Registered User
    Join Date
    Oct 2007
    Location
    Glasvegas, Scotland.
    Posts
    68
    Quote Originally Posted by Adak View Post
    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.

  9. #9
    Registered User
    Join Date
    Oct 2007
    Location
    Glasvegas, Scotland.
    Posts
    68
    Quote Originally Posted by matsp View Post
    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]);

  10. #10
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    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?
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  11. #11
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    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.

    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.
    Last edited by Adak; 10-14-2008 at 05:02 PM.

  12. #12
    Registered User
    Join Date
    Sep 2008
    Location
    Toronto, Canada
    Posts
    1,834
    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]

  13. #13
    Registered User
    Join Date
    Oct 2007
    Location
    Glasvegas, Scotland.
    Posts
    68
    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.

  14. #14
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    Quote Originally Posted by nonoob View Post
    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]
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. sudoku - arrays
    By rocketman50 in forum C++ Programming
    Replies: 2
    Last Post: 03-21-2008, 09:20 AM