Incremental Union?

Question

I'm trying to describe a Sudoku Board in C++ with a union statement:

union Board
{
    int board[9][9];
    int sec1[3][3];
    int sec2[3][3];
    int sec3[3][3];
    int sec4[3][3];
    int sec5[3][3];
    int sec6[3][3];
    int sec7[3][3];
    int sec8[3][3];
    int sec9[3][3];     
}

Would each section of the board correspond with the correct part of the array? IE,

Would sec4 correspond with board[4-6][0-3]? Is there a better way to do this sort of thing (specifically describing a sudoku board)?

Answer 1

This won't work, as written.

A union behaves as if all its members are at offset 0 from the union's start.

That means that sec9 will have the same offset (zero) as sec1, thus overlap.

I don't think it's possible to do it using a union either, since you would need to express that there's a certain "skip" that needs to happen after the end of each section, to get to the next cell in that section. You can't do that using C or C++ arrays.

Answer 2

You are not going to solve this purely using C++ language features - you need to think about the data structure and operations on that structure that are needed to solve your problem - in other words you need to design a class (or more likely several classes). This is the fun part of programming, so I'm not going to suggest a solution.

Answer 3

You could achieve the effect you want by encapsulating it in a class:

class Board {
public:
    int& sec1(int r, int c) { return board[r][c]); }
    int& sec2(int r, int c) { return board[r][c+3]; }
    // etc.

private:
    int board[9][9];
};

but, I'm not sure this is the best way to represent a Sudoku board. You may find that once you start working on the logic, you'll come up with a better representation.

Answer 4

The answer is no, the memory layout will not be what you expect. Note that whenever you define an array in C/C++ the memory is contiguous, so for the 9x9 array the 4th element is not the first element of the second row, but rather the first element of the first row of the second 3x3 block.

The memory layout of your union will have the sec blocks over each one of the 9 lines of the full object.

Answer 5

Another solution (besides the one proposed by Ferruccio) could be to define arrays of 3 pointers to ints - one for each section, and initialise those arrays accordingly in the constructor.

class Board {
public:
    int *sec1[3]; // sec1[0] = &(board[0][0]), sec1[1] = &(board[1][0]),sec1[2] = &(board[2][0])
    ...

    int board[9][9];
};

But frankly methods for access are probably much better.

Answer 6

Every union member, thus every sec1..sec9 very sec will be in the same location. You could try wrap all sects in a struct, but still they will not correspond to 3x3 squares, but rather 9*1 rows in original structure:

union Board
{
    int board[9][9];
    struct {
        int sec1[3][3];
        int sec2[3][3];
        int sec3[3][3];
        int sec4[3][3];
        int sec5[3][3];
        int sec6[3][3];
        int sec7[3][3];
        int sec8[3][3];
        int sec9[3][3];     
    } sects;

}

To sum up, real class would be the best approach.

Answer 7

That will not work, because each 3 * 3 region in the 9 * 9 board will be occupying non-contiguous memory anyway.

What I have done is:

Cell grid[9][9];
Cell* cell_ptr[3][81]; //0 = by rows; 1 = by columns; 2 = by box

where cell_ptr is populated with pointers into the grid so that cell_ptr[0][0...80] allows iterating over rows, cell_ptr[1][0...80] will be iterating over columns, and cell_ptr[2][0...80] allows iterating over 3 * 3 regions.