gistfile1.c

#include <stdio.h>
#include <stdlib.h>
#include "sudoku_lib.h"
#if _SSGRIND_
  #include <ss_valgrind.h>
#endif
#if _EXTRAE_
  #include "extrae_user_events.h"
#endif

#define SIZE 3
#define N SIZE*SIZE*SIZE*SIZE
#define MAX_NUM SIZE*SIZE
#if _EXTRAE_
// Extrae constants
#define PROGRAM		1000
#define END		0
#define SOLVE		1
#endif
unsigned long num_solutions = 0;
int* first_solution = NULL;

/*
 Function that solves the sudoku;
 The parameters it receives are:
   - The number of elements in the sudoku
   - The sudoku grid
   - The point in which it is (sudoku elements vector index)
*/
int solve(int size, int* g, int loc)
{
   int i, solved=0;
   int len = size*size*size*size;
   int guesses[size*size];
   /*
      maximum depth?
      If it has reached the final element, it checks if the solution is valid
      If the solution is valid, adds one to the number of valid solutions and
      if it was the first solution, copies it to the first valid solution grid.
   */
   if (loc == len) {
      //solved = check_solution(size, g);  Next guess siempre nos da resultados posibles con lo que es absurdo comprobarlo todo cuando llegamos a este caso.
      solved = 1;
#if _SSGRIND_
      start_task_valgrind(NULL,"solucion");
      end_task_valgrind();
#endif
      if (solved) {
	      num_solutions++;
	      if (!first_solution)
                 first_solution = new_grid(size, g);
      }
      return solved;
   }

   /* if this node has a solution (a value given by initial puzzle), move to next node */
   if (g[loc] != 0) {
      solved = solve(size, g, loc+1);
      return solved;
   }

   /* try each number (unique to row, column and square) */
   solved = 0;
   next_guess(size, 0, loc, g, guesses);
   #if _SSGRIND_
          start_task_valgrind(NULL, "try_each_guess");
   #endif
   int* ngrid;
   for (i = 0; i < sizeof(guesses)/sizeof(int); ++i) {
      g[loc] = guesses[i];

      if (g[loc] != 0){
	#if _SSGRIND_
          start_task_valgrind(NULL, "try_each_number");
        #endif
	#if _EXTRAE_
	  Extrae_event(PROGRAM, SOLVE);
	#endif
        #pragma omp task shared(solved)
	{
        ngrid = new_grid(size,g);
	if(solve(size, g, loc+1))
	  solved = 1;
        free(ngrid);
	}
	#if _SSGRIND_
          end_task_valgrind();
	#endif
	#if _EXTRAE_
	  Extrae_event(PROGRAM, END);
	#endif
      }

      g[loc] = 0;
     
   }
   #if _SSGRIND_
     end_task_valgrind();
   #endif
   return solved;
}


int main(int argc, char *argv[])
{
   int solved = 0;
   int size = SIZE;

   int* g = new_grid(size, NULL);

#if _SSGRIND_
   start_css_valgrind();
#endif
#if _EXTRAE_
   Extrae_init();
#endif
   /*
      If the puzzle can be read, we copy it to the grid and print it
      Then calls solve puzzle function
   */
   if (read_puzzle(size, g, "puzzle.in")) {
      printf("\nInitial puzzle:\n");
      write_puzzle(size, g);
      printf("\n");
      #pragma omp parallel
      {
          #pragma omp single
          {
      solved = solve(size, g, 0);
          }
      }
   } /* If the puzzle couldn't be read, it tells us so */
   else {
      printf("\nFailed to open file with initial puzzle\n");
      return(!solved);
   }
   /* If the puzzle could be solved, it prints how many solutions were found and the first grid */
   if (solved == 1) {
      printf("\nFound %lu solutions, first one being:\n", num_solutions);
      write_puzzle(size, first_solution);
      printf("\n"); 
   }
   /* If no solutions were found, it tells us so */
   else 
      printf("\nFailed to find a solution\n");

#if _SSGRIND_
   end_css_valgrind();
#endif
#if _EXTRAE_
   Extrae_fini();
#endif
   return(!solved);
}