Thread: 3 dimentional arrays

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;
}