Thread: 3 dimentional arrays

Here's some code to read in a grid and an input file with 5 grids. My simple program seems to solve all of them more or less instantly, so maybe sudoku is computationally easy? I thought it was potentially quite difficult. Except for the wikipedia puzzle, the puzzles are from Play Free Sudoku online - solve web sudoku puzzles. To select a particular puzzle, enter it's offset as a command line parameter.

Code:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
void read(int grid[][9], int pos) {
    FILE *f = fopen("sudoku.txt", "r");
    char line[256];
    for (int i = 0; fgets(line, sizeof line, f); )
        if (strncmp(line, "===", 3) == 0 && i++ == pos) break;
    if (feof(f)) {
        fprintf(stderr, "Puzzle %d does not exist\n", pos);
        exit(EXIT_FAILURE);
    }
    for (int r = 0; r < 9; ++r)
        for (int c = 0; c < 9; ++c) {
            int n = 0;
            fscanf(f, "%d", &n); // fscanf will eat the dash if present
            grid[r][c] = n; // n is 0 if no number was read
        }
    fclose(f);
}
 
void print(int grid[][9]) {
    for (int r = 0; r < 9; ++r) {
        for (int c = 0; c < 9; ++c) {
            if (c && c % 3 == 0) printf("  ");
            if (grid[r][c])
                printf("%d ", grid[r][c]);
            else
                printf("- ");
        }
        putchar('\n');
        if (r < 8 && r % 3 == 2) putchar('\n');
    }
}
 
int main(int argc, char **argv) {
    int pos = 0;
    if (argc == 2) pos = atoi(argv[1]);
    int grid[9][9];
    read(grid, pos);
    print(grid);
    return 0;
}

Input file:

Code:

=== wikipedia 0
5 3 -   - 7 -   - - -
6 - -   1 9 5   - - -
- 9 8   - - -   - 6 -

8 - -   - 6 -   - - 3
4 - -   8 - 3   - - 1
7 - -   - 2 -   - - 6

- 6 -   - - -   2 8 -
- - -   4 1 9   - - 5
- - -   - 8 -   - 7 9

5 3 4   6 7 8   9 1 2 
6 7 2   1 9 5   3 4 8 
1 9 8   3 4 2   5 6 7 

8 5 9   7 6 1   4 2 3 
4 2 6   8 5 3   7 9 1 
7 1 3   9 2 4   8 5 6 

9 6 1   5 3 7   2 8 4 
2 8 7   4 1 9   6 3 5 
3 4 5   2 8 6   1 7 9 

=== easy 1
5 - -   - 1 6   2 - -
- - -   9 8 -   5 - 4
- 3 -   - - -   - - 9

- - -   6 - -   1 - -
9 - 6   - - -   - - 2
- 2 3   - 4 9   - - -

- 4 -   - - -   - 8 1
3 1 5   2 9 -   - 6 7
8 - 9   4 7 1   - 2 5

5 9 4   3 1 6   2 7 8 
6 7 1   9 8 2   5 3 4 
2 3 8   7 5 4   6 1 9 

4 8 7   6 2 5   1 9 3 
9 5 6   1 3 7   8 4 2 
1 2 3   8 4 9   7 5 6 

7 4 2   5 6 3   9 8 1 
3 1 5   2 9 8   4 6 7 
8 6 9   4 7 1   3 2 5 

=== expert 2
- - -   5 - 6   - - -
- - -   - - -   - 6 2
7 - 4   - 1 -   - - -

9 - -   - 4 3   - - 7
- 2 -   - - -   - - -
- 8 -   - 9 -   - 5 -

- - -   - - -   - - -
3 - -   - - 8   7 - -
- 5 -   3 - 4   - - 1

1 3 2   5 8 6   4 7 9 
5 9 8   4 3 7   1 6 2 
7 6 4   9 1 2   5 3 8 

9 1 5   2 4 3   6 8 7 
4 2 7   8 6 5   9 1 3 
6 8 3   7 9 1   2 5 4 

8 7 1   6 2 9   3 4 5 
3 4 9   1 5 8   7 2 6 
2 5 6   3 7 4   8 9 1 

=== evil 3
- 9 3   4 7 -   - 6 -
- 8 -   - - -   - - -
- - -   6 - -   - - 1

8 - -   - - -   - 3 -
- 3 4   - - 9   - - 5
1 - -   - 4 -   - - -

- - -   - - 5   2 - -
- 6 7   - 9 -   - 1 -
4 - -   - - -   - - -

5 9 3   4 7 1   8 6 2 
6 8 1   9 5 2   4 7 3 
7 4 2   6 3 8   9 5 1 

8 7 9   5 2 6   1 3 4 
2 3 4   7 1 9   6 8 5 
1 5 6   8 4 3   7 2 9 

9 1 8   3 6 5   2 4 7 
3 6 7   2 9 4   5 1 8 
4 2 5   1 8 7   3 9 6 

=== evil 4
5 - -   - 7 8   - - -
- - -   - - -   4 - -
- - 8   - 9 -   1 - 7

- - 7   - - -   - 4 -
2 - -   1 - -   7 - 6
- - -   - 6 -   - 5 -

- 3 -   2 - -   - - -
- - 5   - 1 -   8 - 9
- - -   - - -   - 6 -

5 1 2   4 7 8   6 9 3 
7 6 9   3 2 1   4 8 5 
3 4 8   5 9 6   1 2 7 

6 5 7   8 3 2   9 4 1 
2 8 4   1 5 9   7 3 6 
1 9 3   7 6 4   2 5 8 

9 3 6   2 8 7   5 1 4 
4 2 5   6 1 3   8 7 9 
8 7 1   9 4 5   3 6 2

are you just guessing the answer or working it using the solving rules like pairs of possibilities

I wrote the simplest program I could think of (< 10 minutes, remember?) to see how well it would work. It just tries all the numbers. I don't know anything about sudoku or "solving rules".

does it solve this one because i dont seem to be getting anywhere

My program solves it, but obviously the program I posted doesn't since it is just a program for reading in the grid from an input file. I thought it might be useful to you. If you want me to post the whole program I can do that.

Code:

3 5 1   2 8 6   4 9 7 
4 9 2   1 5 7   6 3 8 
7 8 6   9 3 4   5 1 2 

2 7 5   4 6 9   1 8 3 
9 3 8   5 2 1   7 6 4 
6 1 4   8 7 3   2 5 9 

8 2 9   6 4 5   3 7 1 
1 6 3   7 9 2   8 4 5 
5 4 7   3 1 8   9 2 6

I found an example of a puzzle that my program doesn't solve (in a reasonable time, at least).

Code:

-  -  -   -  -  -   -  1  - 
4  -  -   -  -  -   -  -  - 
-  2  -   -  -  -   -  -  - 

-  -  -   -  5  -   4  -  7 
-  -  8   -  -  -   3  -  - 
-  -  1   -  9  -   -  -  - 

3  -  -   4  -  -   2  -  - 
-  5  -   1  -  -   -  -  - 
-  -  -   8  -  6   -  -  -

My simple program was able to solve the "hard" problem in my previous post in about 0.05 seconds by selecting the most-constrained elements first.

@ordak, I cannot get your program to work.
It gives the error:
ERROR:n exceeded nmax, n is 1000
It also said:
TIME:08:35:58
whatever that means. The actual time taken was over 15 seconds.

My sudoku_input.text, containing the "hard" problem from the post above, looked like this:

Code:

/
* * * * * * * 1 *
4 * * * * * * * *
* 2 * * * * * * *
* * * * 5 * 4 * 7
* * 8 * * * 3 * *
* * 1 * 9 * * * *
3 * * 4 * * 2 * *
* 5 * 1 * * * * *
* * * 8 * 6 * * *
/

if i put the functions above main do they have to be in some specific order ie if function a uses function b does function b have to be above function a

Basically yes. However, you could also:

Code:

void funca() {
    void funcb(); // you can tell a about b here
    funcb();
}
void funcb() {
}

i absolutely detest the GetReigon function

It can certainly be simplified (and spelled correctly) :

Code:

void GetRegion( int Row, int Column, int *x, int *y )
{
    *x = Row / 3 * 3;
    *y = Column / 3 * 3;
}

i have changed the above code to this

Code:

#include <stdio.h>
#include <stdlib.h>

void RemovePossNum(int, int, int, int [][9][9] );
void GetRegion( int, int, int *, int * );
void RemoveNumRegion( int, int, int, int [][9][9] );
void printSoloution(int [][9] );
void printPossibleNumbers( int [][9][9] );
void SolvedCell( int, int, int, int [][9][9], int [][9] );
int NakedSingles( int [][9][9], int [][9] );
int FindNakedSingle( int, int, int [][9][9], int [][9] );
int HiddenSingles( int [][9][9], int [][9] );
void FindHiddenSingles( int, int, int *, int [][9][9], int [][9] );
int GetHiddenSingles( int, int *, int [][9][9], int [][9] );

int main()
{
    int PossibleNums[9][9][9] = {{{ 0 }}}, Soloution[9][9] = {
                                        { 0, 0, 0, 0, 0, 0, 9, 0, 7 },
                                        { 0, 0, 0, 4, 2, 0, 1, 8, 0 },
                                        { 0, 0, 0, 7, 0, 5, 0, 2, 6 },
                                        { 1, 0, 0, 9, 0, 4, 0, 0, 0 },
                                        { 0, 5, 0, 0, 0, 0, 0, 4, 0 },
                                        { 0, 0, 0, 5, 0, 7, 0, 0, 9 },
                                        { 9, 2, 0, 1, 0, 8, 0, 0, 0 },
                                        { 0, 3, 4, 0, 5, 9, 0, 0, 0 },
                                        { 5, 0, 7, 0, 0, 0, 0, 0, 0 }};


    for ( int i = 0; i < 9; i++ )
        for ( int j = 0; j < 9; j++ )
            for ( int k = 0; k < 9; k++ )
                if ( Soloution[i][j] == 0 )
                    PossibleNums[i][j][k] = k + 1;

    //printPossibleNumbers(PossibleNums);
    int NumcellsSolved = 0;

    for ( int i = 0; i < 9; i++ )
        for ( int j = 0; j < 9; j++ )
        {
            if ( Soloution[i][j] )
            {
                RemovePossNum( i, j, Soloution[i][j], PossibleNums );
                NumcellsSolved++;
            }
        }

    printSoloution( Soloution );
    printf("number of solved cells is %d\n", NumcellsSolved);

    int x = 0;
    while (NumcellsSolved < 81 )
    {
        x = NumcellsSolved;
        NumcellsSolved += NakedSingles( PossibleNums, Soloution );
        NumcellsSolved+= HiddenSingles( PossibleNums, Soloution );
        printf("number of solved cells is %d\n", NumcellsSolved);

        if (x == NumcellsSolved ) break;
    }

    printSoloution( Soloution );
    printPossibleNumbers( PossibleNums );
    printf("number of solved cells is %d\n", NumcellsSolved);

    return 0;
}

void RemovePossNum(int Row, int Column, int NumRemove, int PNum[][9][9] )
{
    int x, y;

    for ( int i = 0; i < 9; i++ )
        PNum[Row][i][NumRemove - 1] = 0;

    for ( int i = 0; i < 9; i++ )
        PNum[i][Column][NumRemove - 1] = 0;

    GetRegion( Row, Column, &x, &y );
    RemoveNumRegion( x, y, NumRemove, PNum );
}

void GetRegion( int Row, int Column, int *x, int *y )
{
    *x = Row / 3 * 3;
    *y = Column / 3 * 3;
}

void RemoveNumRegion( int x, int y, int RemoveNum, int Pnum[][9][9])
{
    for (int i = x; i < x + 3; i++ )
        for ( int j = y; j < y + 3; j++ )
            Pnum[i][j][RemoveNum - 1] = 0;
}

void printSoloution(int Soloution[][9] )
{
    for ( int i = 0; i < 9; i++ )
    {
        if ( i % 3 == 0 )
            putchar('\n');

        for ( int j = 0; j < 9; j++ )
        {
            if ( j % 3 == 0 )
                putchar('\t');

            if ( Soloution[i][j] )
                printf("%d ", Soloution[i][j]);
            else
                printf("- ");
        }
        putchar('\n');
    }
    putchar('\n');
}

void printPossibleNumbers( int PossNum[][9][9] )
{
    for ( int i = 0; i < 9; i++ )
        for ( int j = 0; j < 9; j++ )
        {
            printf("i = %d j = %d possibles = ", i, j);
            for ( int k = 0; k < 9; k++)
                if ( PossNum[i][j][k] )
                    printf("%d ", PossNum[i][j][k]);
            putchar('\n');
        }
}

void SolvedCell( int Row, int Column, int Answer, int pNum[][9][9], int Solved[][9] )
{
    Solved[Row][Column] = Answer;
    RemovePossNum( Row, Column, Answer, pNum );

    for ( int i = 0; i < 9; i++ )
        pNum[Row][Column][i] = 0;
}

int NakedSingles( int PossNum[][9][9], int Solved[][9] )
{
    int CellsSolved = 0;

    for ( int Row = 0; Row < 9; Row++ )
        for ( int Column = 0; Column < 9; Column++ )
            CellsSolved += FindNakedSingle( Row, Column, PossNum, Solved );

    for ( int Column = 0; Column < 9; Column++ )
        for ( int Row = 0; Row < 9; Row++ )
            CellsSolved += FindNakedSingle( Row, Column, PossNum, Solved ); //row and column stay in the same order

    for ( int RegionRow = 0; RegionRow < 9; RegionRow += 3 )
        for ( int RegionColumn = 0; RegionColumn < 9; RegionColumn += 3 )
            for ( int Row = RegionRow; Row < RegionRow + 3; Row++ )
                for ( int Column = RegionColumn; Column < RegionColumn + 3; Column++ )
                    CellsSolved += FindNakedSingle( Row, Column, PossNum, Solved );

    return CellsSolved;
}

int FindNakedSingle( int Row, int Column, int PossNum[][9][9], int Solved[][9] )
{
    int CellsSolved = 0;

    if ( !Solved[Row][Column] )
    {
        int CountPossibleDigits = 0, tmpNum;
        for ( int Digit = 0; Digit < 9; Digit++ )
        {
            if ( PossNum[Row][Column][Digit] )
            {
                CountPossibleDigits++;
                tmpNum = Digit + 1;
            }
            if (CountPossibleDigits == 2 ) break;
        }
        if ( CountPossibleDigits == 1 )
        {
            SolvedCell( Row, Column, tmpNum, PossNum, Solved );
            CellsSolved++;
        }
    }
    return CellsSolved;
}

int HiddenSingles( int PossNum[][9][9], int Solved[][9] )
{
    int CellsSolved = 0;

    for ( int Row = 0; Row < 9; Row++ )
    {
        int CountDigits[9] = { 0 };

        for ( int Column = 0; Column < 9; Column++ )
            FindHiddenSingles( Row, Column, CountDigits, PossNum, Solved );

        CellsSolved += GetHiddenSingles( Row, CountDigits, PossNum, Solved );
    }

    for ( int Column = 0; Column < 9; Column++ )
    {
        int CountDigits[9] = { 0 };

        for ( int Row = 0; Row < 9; Row++ )
            FindHiddenSingles( Row, Column, CountDigits, PossNum, Solved );

        CellsSolved += GetHiddenSingles( Row, CountDigits, PossNum, Solved );
    }
    return CellsSolved;
}

void FindHiddenSingles( int Row, int Column, int *CountDigits, int PossNum[][9][9], int Solved[][9] )
{
    if ( !Solved[Row][Column] )
        for ( int PossDigit = 0; PossDigit < 9; PossDigit++ )
            if ( PossNum[Row][Column][PossDigit] )
            CountDigits[ PossNum[Row][Column][PossDigit] - 1 ] += 1;
}

int GetHiddenSingles( int Row, int *CountedDigits, int PossNum[][9][9], int Solved[][9])
{
    int CellsSolved = 0;

    for ( int Digit = 0; Digit < 9; Digit++ )
        if ( CountedDigits[Digit] == 1 )
            for ( int Column = 0; Column < 9; Column++ )
                if ( PossNum[Row][Column][Digit] == Digit + 1 )
                {
                    SolvedCell( Row, Column,  Digit + 1, PossNum, Solved );
                    CellsSolved++;
                    break;
                }

    return CellsSolved;
}

mainly added a solved function and changed how it searches for naked singles ie looks along the row then column then region. This all works fine

I then added the following function

Code:

int HiddenSingles( int PossNum[][9][9], int Solved[][9] )
{    
    int CellsSolved = 0;

    for ( int Row = 0; Row < 9; Row++ )
    {
        int CountDigits[9] = { 0 };

        for ( int Column = 0; Column < 9; Column++ )
        {
            if ( !Solved[Row][Column] )
                for ( int PossDigit = 0; PossDigit < 9; PossDigit++ )
                {
                    if ( PossNum[Row][Column][PossDigit] )
                    {
                        //printf("%d ", PossNum[Row][Column][PossDigit]);
                        CountDigits[ PossNum[Row][Column][PossDigit] - 1 ] += 1;
                    }
                }
        }
        for ( int Digit = 0; Digit < 9; Digit++ )
        {
            if ( CountedDigits[Digit] == 1 )
            {
                for ( int Column = 0; Column < 9; Column++ )
                    if ( PossNum[Row][Column][Digit] == Digit + 1 )
                    {
                        SolvedCell( Row, Column,  Digit + 1, PossNum, Solved );
                        CellsSolved++;
                        //printPossibleNumbers( PossNum );
                        //return CellsSolved;
                        break;
                    }
            }
        }
    }
    
    return CellsSolved;
}

it worked as far as it found all the hidden numbers in the rows but not the columns or regions.

so i broke up the function into two smaller functions and did the same as i did for naked single except on line 208 if i pass row i get an error (undeclaired variable) but if i change it and pass in column it removes already solved cells and changes others

but as what i have solves it i guess there is no need

Does it solve these? You didn't post a complete program, so I can't easily test it myself.

Code:

    int Solution[9][9] = {
        { 5, 0, 0, 0, 7, 8, 0, 0, 0 },
        { 0, 0, 0, 0, 0, 0, 4, 0, 0 },
        { 0, 0, 8, 0, 9, 0, 1, 0, 7 },
        { 0, 0, 7, 0, 0, 0, 0, 4, 0 },
        { 2, 0, 0, 1, 0, 0, 7, 0, 6 },
        { 0, 0, 0, 0, 6, 0, 0, 5, 0 },
        { 0, 3, 0, 2, 0, 0, 0, 0, 0 },
        { 0, 0, 5, 0, 1, 0, 8, 0, 9 },
        { 0, 0, 0, 0, 0, 0, 0, 6, 0 }
    };
/* solution
5 1 2   4 7 8   6 9 3 
7 6 9   3 2 1   4 8 5 
3 4 8   5 9 6   1 2 7 

6 5 7   8 3 2   9 4 1 
2 8 4   1 5 9   7 3 6 
1 9 3   7 6 4   2 5 8 

9 3 6   2 8 7   5 1 4 
4 2 5   6 1 3   8 7 9 
8 7 1   9 4 5   3 6 2 
*/ 
    int Solution[9][9] = {
        { 0, 0, 0, 0, 0, 0, 0, 1, 0 },
        { 4, 0, 0, 0, 0, 0, 0, 0, 0 },
        { 0, 2, 0, 0, 0, 0, 0, 0, 0 },
        { 0, 0, 0, 0, 5, 0, 4, 0, 7 },
        { 0, 0, 8, 0, 0, 0, 3, 0, 0 },
        { 0, 0, 1, 0, 9, 0, 0, 0, 0 },
        { 3, 0, 0, 4, 0, 0, 2, 0, 0 },
        { 0, 5, 0, 1, 0, 0, 0, 0, 0 },
        { 0, 0, 0, 8, 0, 6, 0, 0, 0 }
    };
/* solution
6 9 3   7 8 4   5 1 2 
4 8 7   5 1 2   9 3 6 
1 2 5   9 6 3   8 7 4 

9 3 2   6 5 1   4 8 7 
5 6 8   2 4 7   3 9 1 
7 4 1   3 9 8   6 2 5 

3 1 9   4 7 5   2 6 8 
8 5 6   1 2 9   7 4 3 
2 7 4   8 3 6   1 5 9 
*/