Thread: 3 dimentional arrays

ummm row 6 column 7 can only be a 6 same with column 9 this is why you got the wrong answer with my code

ummm row 6 column 7 can only be a 6 same with column 9 this is why you got the wrong answer with my code

ummm, okay. Luckily I have other things to do with my time.

what possible numbers do you get after running my code for row 6 column 7 and row 6 column 9 before passing it through locked numbers i have 2, 3, 4 and 6 for Column 7 and 3,4 and 6 for column 9.

as locked numbers removes the other possible numbers i assume this is at fault especially as the correct answer is 2 for column 7 and 4 for column 9 all i can see by putting a conditional break point when row = 6 (index 5) and column = 7 (index 6) is the break statement isn't breaking the loop so the rest of the code is being executed and removing these numbers. but 2 seconds later the break statements work

Did you guys tried the classical recursive solver?

Code:

/* sudoku.c */
#include <stdio.h>
#include <stdlib.h>

static _Bool solve ( unsigned int [][9] );

int main ( void )
{
  // Puzzles, define PUZ from 0 to 9...
  static unsigned int puzzle[9][9] = {
#if PUZ == 0
        { 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 }
#elif PUZ == 1
        { 0, 0, 0, 5, 0, 6, 0, 0, 0 },
        { 0, 0, 0, 0, 0, 0, 0, 6, 2 },
        { 7, 0, 4, 0, 1, 0, 0, 0, 0 },
        { 9, 0, 0, 0, 4, 3, 0, 0, 7 },
        { 0, 2, 0, 0, 0, 0, 0, 0, 0 },
        { 0, 8, 0, 0, 9, 0, 0, 5, 0 },
        { 0, 0, 0, 0, 0, 0, 0, 0, 0 },
        { 3, 0, 0, 0, 0, 8, 7, 0, 0 },
        { 0, 5, 0, 3, 0, 4, 0, 0, 1 }
#elif PUZ == 2
        { 0, 9, 3, 4, 7, 0, 0, 6, 0 },
        { 0, 8, 0, 0, 0, 0, 0, 0, 0 },
        { 0, 0, 0, 6, 0, 0, 0, 0, 1 },
        { 8, 0, 0, 0, 0, 0, 0, 3, 0 },
        { 0, 3, 4, 0, 0, 9, 0, 0, 5 },
        { 1, 0, 0, 0, 4, 0, 0, 0, 0 },
        { 0, 0, 0, 0, 0, 5, 2, 0, 0 },
        { 0, 6, 7, 0, 9, 0, 0, 1, 0 },
        { 4, 0, 0, 0, 0, 0, 0, 0, 0 }
#elif PUZ == 3
        { 3, 0, 0, 2, 0, 0, 0, 0, 0 },
        { 0, 0, 0, 1, 0, 7, 0, 0, 0 },
        { 7, 0, 6, 0, 3, 0, 5, 0, 0 },
        { 0, 7, 0, 0, 0, 9, 0, 8, 0 },
        { 9, 0, 0, 0, 2, 0, 0, 0, 4 },
        { 0, 1, 0, 8, 0, 0, 0, 5, 0 },
        { 0, 0, 9, 0, 4, 0, 3, 0, 1 },
        { 0, 0, 0, 7, 0, 2, 0, 0, 0 },
        { 0, 0, 0, 0, 0, 8, 0, 0, 6 }
#elif PUZ == 4
        { 0, 0, 0, 0, 0, 0, 0, 1, 2 },
        { 0, 0, 8, 0, 3, 0, 0, 0, 0 },
        { 0, 0, 0, 0, 0, 0, 0, 4, 0 },
        { 1, 2, 0, 5, 0, 0, 0, 0, 0 },
        { 0, 0, 0, 0, 0, 4, 7, 0, 0 },
        { 0, 6, 0, 0, 0, 0, 0, 0, 0 },
        { 5, 0, 7, 0, 0, 0, 3, 0, 0 },
        { 0, 0, 0, 6, 2, 0, 0, 0, 0 },
        { 0, 0, 0, 1, 0, 0, 0, 0, 0 }
#elif PUZ == 5
        { 0, 0, 0, 0, 0, 0, 0, 1, 2 },
        { 0, 5, 0, 4, 0, 0, 0, 0, 0 },
        { 0, 0, 0, 0, 0, 0, 0, 3, 0 },
        { 7, 0, 0, 6, 0, 0, 4, 0, 0 },
        { 0, 0, 1, 0, 0, 0, 0, 0, 0 },
        { 0, 0, 0, 0, 8, 0, 0, 0, 0 },
        { 9, 2, 0, 0, 0, 0, 8, 0, 0 },
        { 0, 0, 0, 5, 1, 0, 7, 0, 0 },
        { 0, 0, 0, 0, 0, 3, 0, 0, 0 }
#elif PUZ == 6
        { 0, 0, 0, 0, 0, 0, 0, 1, 2 },
        { 3, 0, 0, 0, 0, 0, 0, 6, 0 },
        { 0, 0, 0, 0, 4, 0, 0, 0, 0 },
        { 9, 0, 0, 0, 0, 0, 5, 0, 0 },
        { 0, 0, 0, 0, 0, 1, 0, 7, 0 },
        { 0, 2, 0, 0, 0, 0, 0, 0, 0 },
        { 0, 0, 0, 3, 5, 0, 4, 0, 0 },
        { 0, 0, 1, 4, 0, 0, 8, 0, 0 },
        { 0, 6, 0, 0, 0, 0, 0, 0, 0 }
#elif PUZ == 7
        { 0, 0, 0, 0, 0, 0, 0, 1, 2 },
        { 4, 0, 0, 0, 9, 0, 0, 0, 0 },
        { 0, 0, 0, 0, 0, 0, 0, 5, 0 },
        { 0, 7, 0, 2, 0, 0, 0, 0, 0 },
        { 6, 0, 0, 0, 0, 0, 4, 0, 0 },
        { 0, 0, 0, 1, 0, 8, 0, 0, 0 },
        { 0, 1, 8, 0, 0, 0, 0, 0, 0 },
        { 0, 0, 0, 0, 3, 0, 7, 0, 0 },
        { 5, 0, 2, 0, 0, 0, 0, 0, 0 }
#elif PUZ == 8
        { 0, 0, 0, 0, 0, 0, 0, 1, 2 },
        { 5, 0, 0, 0, 0, 8, 0, 0, 0 },
        { 0, 0, 0, 7, 0, 0, 0, 0, 0 },
        { 6, 0, 0, 1, 2, 0, 0, 0, 0 },
        { 7, 0, 0, 0, 0, 0, 4, 5, 0 },
        { 0, 0, 0, 0, 3, 0, 0, 0, 0 },
        { 0, 3, 0, 0, 0, 0, 8, 0, 0 },
        { 0, 0, 0, 5, 0, 0, 7, 0, 0 },
        { 0, 2, 0, 0, 0, 0, 0, 0, 0 }
#elif PUZ == 9
        { 0, 0, 0, 0, 0, 0, 0, 1, 2 },
        { 7, 0, 0, 0, 6, 0, 0, 0, 0 },
        { 0, 0, 0, 0, 0, 0, 0, 5, 0 },
        { 0, 8, 0, 2, 0, 0, 0, 0, 0 },
        { 6, 0, 0, 0, 0, 0, 4, 0, 0 },
        { 0, 0, 0, 1, 0, 9, 0, 0, 0 },
        { 0, 1, 9, 0, 0, 0, 0, 0, 0 },
        { 0, 0, 0, 0, 3, 0, 8, 0, 0 },
        { 5, 0, 2, 0, 0, 0, 0, 0, 0 }
#endif
  };

  if ( ! solve ( puzzle ) )
  {
    fputs( "No solution found.\n", stderr );
    return EXIT_FAILURE;
  }

  // show the solution.
  for ( unsigned int r = 0; r < 9; ++r )
  {
    for ( unsigned int c = 0; c < 9; ++c )
      printf ( " %d", puzzle[r][c] );
    putchar( '\n' );
  }

  return EXIT_SUCCESS;
}

// Verify is a guess for a cell is valid.
static _Bool valid ( unsigned int puzzle[][9], unsigned int row, unsigned int column, unsigned int guess )
{
  unsigned int block_x, block_y;

  // test row and column.
  for ( unsigned int i = 0; i < 9; ++i )
    if ( puzzle[row][i] == guess || puzzle[i][column] == guess )
      return 0;

  block_x = row / 3 * 3 + 1;
  block_y = column / 3 * 3 + 1;

  // test diagonals
  if ( puzzle[block_x - 1][block_y - 1] == guess ||
       puzzle[block_x - 1][block_y + 1] == guess ||
       puzzle[block_x + 1][block_y - 1] == guess ||
       puzzle[block_x + 1][block_y + 1] == guess )
    return 0;

  return 1;
}

// Scan the board for the next empty cell.
static _Bool findEmptyCell ( unsigned int puzzle[][9], unsigned int *row, unsigned int *column )
{
  for ( unsigned int r = 0; r < 9; r++ )
    for ( unsigned int c = 0; c < 9; c++ )
      if ( ! puzzle[r][c] )
      {
        *row = r;
        *column = c;

        return 1;
      }

  return 0;
}

// Recursivelly try to solve the board.
_Bool solve ( unsigned int puzzle[][9] )
{
  unsigned int row;
  unsigned int column;

  // If there are no empty cells, it is solved.
  if ( ! findEmptyCell ( puzzle, &row, &column ) )
    return 1;

  for ( unsigned int guess = 1; guess <= 9; guess++ )
    // if there's no values of guess in a row, column of local block...
    if ( valid ( puzzle, row, column, guess ) )
    {
      // mark the empty cell with the guess and try to solve...
      puzzle[row][column] = guess;

      if ( solve ( puzzle ) )
        return 1;

      // if not solved, mark back with empty and try the next guess.
      puzzle[row][column] = 0;
    }

  return 0;
}

Of course my solution was recursive!
Mine is about 5 times faster than yours looping through those 10 boards since I added the complexity of filling in the most-constrained values first.
The actual Project Euler problem ( #96 Su Doku - Project Euler ) has 50 puzzles.
I didn't post my solution since the OP clearly wanted to try to solve it on his own.

BTW, I've changed my mind on Project Euler. It's actually kind of interesting. I've only ever seen the odd problem here and there as people asked about them. But now that I've solved 84 of the first 100 over the last couple of weeks I see that some of the problems are quite interesting.

EDIT:
Now that I've retrofitted yours to work on the actual problem, mine runs about 370 times faster and yours seems to get the wrong answer. The answer should be 24702 but yours gets 19274. Maybe I've screwed something up about your code adding in the extra stuff to work with the problem. Here's your code as I ran it:

Code:

#include <stdio.h>
#include <stdlib.h>
 
_Bool solve ( unsigned int [][9] );
int read(FILE *f, unsigned int puzzle[][9]);

int main ( void )
{
  int sum = 0;
  FILE *f = fopen("0096_sudoku.txt", "r");
  if (!f) { perror("fopen"); exit(1); }

  unsigned int puzzle[9][9];

  while (read(f, puzzle)) 
  {
    if ( ! solve ( puzzle ) )
    {
      fputs( "No solution found.\n", stderr );
      return EXIT_FAILURE;
    }

    sum += puzzle[0][0]*100 + puzzle[0][1]*10 + puzzle[0][2];
 
    /*
    for ( unsigned int r = 0; r < 9; ++r )
    {
      for ( unsigned int c = 0; c < 9; ++c )
        printf ( " %d", puzzle[r][c] );
      putchar( '\n' );
    }
    */
  }

  fclose(f);
  printf("%d\n", sum);
  return 0;
}
 
// Verify is a guess for a cell is valid.
static _Bool valid ( unsigned int puzzle[][9], unsigned int row, unsigned int column, unsigned int guess )
{
  unsigned int block_x, block_y;
 
  // test row and column.
  for ( unsigned int i = 0; i < 9; ++i )
    if ( puzzle[row][i] == guess || puzzle[i][column] == guess )
      return 0;
 
  block_x = row / 3 * 3 + 1;
  block_y = column / 3 * 3 + 1;
 
  // test diagonals
  if ( puzzle[block_x - 1][block_y - 1] == guess ||
       puzzle[block_x - 1][block_y + 1] == guess ||
       puzzle[block_x + 1][block_y - 1] == guess ||
       puzzle[block_x + 1][block_y + 1] == guess )
    return 0;
 
  return 1;
}
 
// Scan the board for the next empty cell.
static _Bool findEmptyCell ( unsigned int puzzle[][9], unsigned int *row, unsigned int *column )
{
  for ( unsigned int r = 0; r < 9; r++ )
    for ( unsigned int c = 0; c < 9; c++ )
      if ( ! puzzle[r][c] )
      {
        *row = r;
        *column = c;
 
        return 1;
      }
 
  return 0;
}
 
// Recursivelly try to solve the board.
_Bool solve ( unsigned int puzzle[][9] )
{
  unsigned int row;
  unsigned int column;
 
  // If there are no empty cells, it is solved.
  if ( ! findEmptyCell ( puzzle, &row, &column ) )
    return 1;
 
  for ( unsigned int guess = 1; guess <= 9; guess++ )
    // if there's no values of guess in a row, column of local block...
    if ( valid ( puzzle, row, column, guess ) )
    {
      // mark the empty cell with the guess and try to solve...
      puzzle[row][column] = guess;
 
      if ( solve ( puzzle ) )
        return 1;
 
      // if not solved, mark back with empty and try the next guess.
      puzzle[row][column] = 0;
    }
 
  return 0;
}

int read(FILE *f, unsigned int puzzle[][9]) {
  char line[256];
  if (!fgets(line, sizeof line, f)) return 0;
  for (int r = 0; r < 9; ++r)
    for (int c = 0; c < 9; ++c) {
      int n = 0;
      if (fscanf(f, "%1d", &n) != 1) return 0;
      puzzle[r][c] = n;
    }
  if (fgets(line, sizeof line, f)) {}
  return 1;
}

Here's mine:

Code:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
typedef unsigned char Value;
 
int read(FILE *f, Value grid[][9]) {
    char line[256];
    if (!fgets(line, sizeof line, f)) return 0;
    for (int r = 0; r < 9; ++r)
        for (int c = 0; c < 9; ++c) {
            int n = 0;
            if (fscanf(f, "%1d", &n) != 1) return 0;
            grid[r][c] = n;
        }
    if (fgets(line, sizeof line, f)) {}
    return 1;
}
 
void print(Value 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');
    }
}
 
void set_values(Value grid[][9], Value values[][9][9], int r, int c) {
    for (int cc = 0; cc < 9; ++cc)
        if (grid[r][cc]) values[r][c][grid[r][cc] - 1] = 1;
    for (int rr = 0; rr < 9; ++rr)
        if (grid[rr][c]) values[r][c][grid[rr][c] - 1] = 1;
    int rstart = r / 3 * 3, cstart = c / 3 * 3;
    for (int rr = rstart; rr < rstart + 3; ++rr)
        for (int cc = cstart; cc < cstart + 3; ++cc)
            if (grid[rr][cc]) values[r][c][grid[rr][cc] - 1] = 1;
}
 
int set_all_values(Value grid[][9], Value values[][9][9]) {
    int empty = 0;
    for (int r = 0; r < 9; ++r)
        for (int c = 0; c < 9; ++c) {
            if (grid[r][c] == 0) ++empty;
            set_values(grid, values, r, c);
        }
    return empty;
}
 
void find_most_constrained(Value grid[][9], Value values[][9][9], int *low_r, int *low_c) {
    for (int r = 0, low = 99; r < 9; ++r)
        for (int c = 0; c < 9; ++c)
            if (grid[r][c] == 0) {
                int cnt = 0;
                for (int v = 0; v < 9; ++v) if (values[r][c][v] == 0) ++cnt;
                if (cnt < low) { low = cnt; *low_r = r; *low_c = c; }
            }
}
 
void adjust(Value values[][9][9], int r, int c, int n, int adj) {
    for (int cc = 0; cc < 9; ++cc) values[r][cc][n] += adj;
    for (int rr = 0; rr < 9; ++rr) values[rr][c][n] += adj;
    int rstart = r / 3 * 3, cstart = c / 3 * 3;
    for (int rr = rstart; rr < rstart + 3; ++rr)
        for (int cc = cstart; cc < cstart + 3; ++cc) values[rr][cc][n] += adj;
}
 
int solve(Value grid[][9], Value values[][9][9], int empty) {
    if (empty == 0) {
        //print(grid);
        return 1;
    }
    int r=0, c=0;
    find_most_constrained(grid, values, &r, &c);
    for (int n = 0; n < 9; ++n)
        if (values[r][c][n] == 0) {
            grid[r][c] = n + 1;
            adjust(values, r, c, n, 1);
            if (solve(grid, values, empty - 1)) return 1;
            adjust(values, r, c, n, -1);
            grid[r][c] = 0;
        }
    return 0;
}
 
int main() {
    int sum = 0;
    FILE *f = fopen("0096_sudoku.txt", "r");
    if (!f) { perror("fopen"); exit(1); }
    Value grid[9][9];
    while (read(f, grid)) {
        Value values[9][9][9] = {{{0}}};
        if (solve(grid, values, set_all_values(grid, values)))
            sum += grid[0][0]*100 + grid[0][1]*10 + grid[0][2];
        else {
            printf("\nERROR: cannot solve grid\n");
            exit(1);
        }
    }
    fclose(f);
    printf("%d\n", sum);
    return 0;
}

Fixing your incorrect block-checking not only gets the correct answer but also speeds up your program a lot.
Mine is still about 20 times faster, though, and is not particularly optimized.
It would have to be faster, of course, since it prunes the search tree by filling in the most constrained values first.

Code:

// Verify is a guess for a cell is valid.
_Bool valid ( unsigned puzzle[][9], unsigned row, unsigned column, unsigned guess )
{
  // test row and column.
  for ( unsigned i = 0; i < 9; ++i )
    if ( puzzle[row][i] == guess || puzzle[i][column] == guess )
      return 0;
 
  // test blocks
  unsigned block_r = row / 3 * 3, block_c = column / 3 * 3;
  for ( unsigned r = block_r; r < block_r + 3; ++r)
    for ( unsigned c = block_c; c < block_c + 3; ++c)
      if ( puzzle[r][c] == guess ) return 0;
 
  return 1;
}