#include <stdio.h>

#include "fdc_int.h"

#define floor_sqrt(s, n) {for ((s) = 0; (s) * (s) <= (n); ++(s)); --(s);}

#define N 9	// board size

#define NL N	// lines
#define NC N	// columns
#define _ 0

typedef int sudoku_i[N][N];

int unsolvable[9][9] = {1, _, _, 9, _, 7, _, _, 3,
			_, 8, _, _, _, _, _, 7, _,
			_, _, 9, _, _, _, 6, _, _,
			_, _, 7, 2, _, 9, 4, _, _,
			4, 1, _, _, _, _, _, 9, 5,
			_, _, 8, 5, _, 4, 3, _, _,
			_, _, 3, _, _, _, 7, _, _,
			_, 5, _, _, _, _, _, 4, _,
			2, _, _, 8, _, 6, _, _, 9};

int unsolvable2[9][9] = {1, _, _, 9, _, 7, _, _, 3,
			 _, 8, _, _, _, _, _, 7, _,
			 _, _, 9, _, _, _, 6, _, _,
			 5, 3, 7, 2, 8, 9, 4, 1, 6,
			 4, 1, 2, 7, 6, 3, 8, 9, 5,
			 6, 9, 8, 5, 1, 4, 3, 2, 7,
			 8, 4, 3, 1, 9, 5, 7, 6, 2,
			 9, 5, 6, 3, 7, 2, 1, 4, 8,
			 2, 7, 1, 8, 4, 6, 5, 3, 9};

int unsolvable3[9][9] = {1, _, _, 9, _, 7, _, _, 3,
			 _, 8, _, _, _, _, _, 7, _,
			 7, 2, 9, 4, 3, 8, 6, 5, 1,
			 5, 3, 7, 2, 8, 9, 4, 1, 6,
			 4, 1, 2, 7, 6, 3, 8, 9, 5,
			 6, 9, 8, 5, 1, 4, 3, 2, 7,
			 8, 4, 3, 1, 9, 5, 7, 6, 2,
			 9, 5, 6, 3, 7, 2, 1, 4, 8,
			 2, 7, 1, 8, 4, 6, 5, 3, 9};

int unsolvable4[9][9] = {1, _, _, 9, _, 7, _, _, 3,
			 _, 8, _, 6, 2, 1, 9, 7, 4,
			 7, 2, 9, 4, 3, 8, 6, 5, 1,
			 5, 3, 7, 2, 8, 9, 4, 1, 6,
			 4, 1, 2, 7, 6, 3, 8, 9, 5,
			 6, 9, 8, 5, 1, 4, 3, 2, 7,
			 8, 4, 3, 1, 9, 5, 7, 6, 2,
			 9, 5, 6, 3, 7, 2, 1, 4, 8,
			 2, 7, 1, 8, 4, 6, 5, 3, 9};

int unsolvable5[9][9] = {1, _, _, 9, _, 7, 2, 8, 3,
			 _, 8, _, 6, 2, 1, 9, 7, 4,
			 7, 2, 9, 4, 3, 8, 6, 5, 1,
			 5, 3, 7, 2, 8, 9, 4, 1, 6,
			 4, 1, 2, 7, 6, 3, 8, 9, 5,
			 6, 9, 8, 5, 1, 4, 3, 2, 7,
			 8, 4, 3, 1, 9, 5, 7, 6, 2,
			 9, 5, 6, 3, 7, 2, 1, 4, 8,
			 2, 7, 1, 8, 4, 6, 5, 3, 9};

int unsolvable6[9][9] = {1, _, _, 9, 5, 7, 2, 8, 3,
			 3, 8, 5, 6, 2, 1, 9, 7, 4,
			 7, 2, 9, 4, 3, 8, 6, 5, 1,
			 5, 3, 7, 2, 8, 9, 4, 1, 6,
			 4, 1, 2, 7, 6, 3, 8, 9, 5,
			 6, 9, 8, 5, 1, 4, 3, 2, 7,
			 8, 4, 3, 1, 9, 5, 7, 6, 2,
			 9, 5, 6, 3, 7, 2, 1, 4, 8,
			 2, 7, 1, 8, 4, 6, 5, 3, 9};

int gentle[9][9] = {_,_,8,2,_,5,_,_,_,
		    _,_,_,_,_,_,_,9,6,
		    2,_,_,6,1,_,_,8,_,
		    1,2,_,_,_,3,_,_,9,
		    3,_,_,_,5,_,_,_,7,
		    8,_,_,1,_,_,_,2,4,
		    _,4,_,_,8,7,_,_,1,
		    7,3,_,_,_,_,_,_,_,
		    _,_,_,3,_,4,7,_,_};

// Publico 23MAR08
int dificil[N][N] = {_,2,_,_,_,6,3,_,_,
		     _,_,_,_,8,_,_,_,9,
		     1,_,6,_,_,_,4,_,_,
		     7,_,_,_,9,_,_,_,_,
		     _,3,_,5,_,7,_,4,_,
		     _,_,_,_,4,_,_,_,8,
		     _,_,8,_,_,_,2,_,1,
		     2,_,_,_,6,_,_,_,_,
		     _,_,9,1,_,_,_,5,_};

int gecode[][N][N] = { // (all comments by GECODE -vp)
  // 0
  {_,_,_,2,_,5,_,_,_,
   _,9,_,_,_,_,7,3,_,
   _,_,2,_,_,9,_,6,_,
   2,_,_,_,_,_,4,_,9,
   _,_,_,_,7,_,_,_,_,
   6,_,9,_,_,_,_,_,1,
   _,8,_,4,_,_,1,_,_,
   _,6,3,_,_,_,_,8,_,
   _,_,_,6,_,8,_,_,_},
  // 1
  {3,_,_,9,_,4,_,_,1,
   _,_,2,_,_,_,4,_,_,
   _,6,1,_,_,_,7,9,_,
   6,_,_,2,4,7,_,_,5,
   _,_,_,_,_,_,_,_,_,
   2,_,_,8,3,6,_,_,4,
   _,4,6,_,_,_,2,3,_,
   _,_,9,_,_,_,6,_,_,
   5,_,_,3,_,9,_,_,8},
  // 2
  {_,_,_,_,1,_,_,_,_,
   3,_,1,4,_,_,8,6,_,
   9,_,_,5,_,_,2,_,_,
   7,_,_,1,6,_,_,_,_,
   _,2,_,8,_,5,_,1,_,
   _,_,_,_,9,7,_,_,4,
   _,_,3,_,_,4,_,_,6,
   _,4,8,_,_,6,9,_,7,
   _,_,_,_,8,_,_,_,_,},
  // 3
  // Fiendish puzzle April 21 2005 Times London
  {_,_,4,_,_,3,_,7,_,
   _,8,_,_,7,_,_,_,_,
   _,7,_,_,_,8,2,_,5,
   4,_,_,_,_,_,3,1,_,
   9,_,_,_,_,_,_,_,8,
   _,1,5,_,_,_,_,_,4,
   1,_,6,9,_,_,_,3,_,
   _,_,_,_,2,_,_,6,_,
   _,2,_,4,_,_,5,_,_},
  // 4
  // This one requires search
  {_,4,3,_,8,_,2,5,_,
   6,_,_,_,_,_,_,_,_,
   _,_,_,_,_,1,_,9,4,
   9,_,_,_,_,4,_,7,_,
   _,_,_,6,_,8,_,_,_,
   _,1,_,2,_,_,_,_,3,
   8,2,_,5,_,_,_,_,_,
   _,_,_,_,_,_,_,_,5,
   _,3,4,_,9,_,7,1,_},
  // 5
  // Hard one from http://www.cs.mu.oz.au/671/proj3/node5.html
  {_,_,_,_,_,3,_,6,_,
   _,_,_,_,_,_,_,1,_,
   _,9,7,5,_,_,_,8,_,
   _,_,_,_,9,_,2,_,_,
   _,_,8,_,7,_,4,_,_,
   _,_,3,_,6,_,_,_,_,
   _,1,_,_,_,2,8,9,_,
   _,4,_,_,_,_,_,_,_,
   _,5,_,1,_,_,_,_,_},
  // 6
  // Puzzle 1 from http://www.sudoku.org.uk/bifurcation.htm
  {1,_,_,9,_,7,_,_,3,
   _,8,_,_,_,_,_,7,_,
   _,_,9,_,_,_,6,_,_,
   _,_,7,2,_,9,4,_,_,
   4,1,_,_,_,_,_,9,5,
   _,_,8,5,_,4,3,_,_,
   _,_,3,_,_,_,7,_,_,
   _,5,_,_,_,_,_,4,_,
   2,_,_,8,_,6,_,_,9},
  // 7
  // Puzzle 2 from http://www.sudoku.org.uk/bifurcation.htm
  {_,_,_,3,_,2,_,_,_,
   _,5,_,7,9,8,_,3,_,
   _,_,7,_,_,_,8,_,_,
   _,_,8,6,_,7,3,_,_,
   _,7,_,_,_,_,_,6,_,
   _,_,3,5,_,4,1,_,_,
   _,_,5,_,_,_,6,_,_,
   _,2,_,4,1,9,_,5,_,
   _,_,_,8,_,6,_,_,_},
  // 8
  // Puzzle 3 from http://www.sudoku.org.uk/bifurcation.htm
  {_,_,_,8,_,_,_,_,6,
   _,_,1,6,2,_,4,3,_,
   4,_,_,_,7,1,_,_,2,
   _,_,7,2,_,_,_,8,_,
   _,_,_,_,1,_,_,_,_,
   _,1,_,_,_,6,2,_,_,
   1,_,_,7,3,_,_,_,4,
   _,2,6,_,4,8,1,_,_,
   3,_,_,_,_,5,_,_,_},
  // 9
  // Puzzle 4 from http://www.sudoku.org.uk/bifurcation.htm
  {3,_,5,_,_,4,_,7,_,
   _,7,_,_,_,_,_,_,1,
   _,4,_,9,_,_,_,3,_,
   4,_,_,_,5,1,_,_,6,
   _,9,_,_,_,_,_,4,_,
   2,_,_,8,4,_,_,_,7,
   _,2,_,_,_,7,_,6,_,
   8,_,_,_,_,_,_,9,_,
   _,6,_,4,_,_,2,_,8},
  // 10
  // Puzzle 5 from http://www.sudoku.org.uk/bifurcation.htm
  {_,_,_,7,_,_,3,_,_,
   _,6,_,_,_,_,5,7,_,
   _,7,3,8,_,_,4,1,_,
   _,_,9,2,8,_,_,_,_,
   5,_,_,_,_,_,_,_,9,
   _,_,_,_,9,3,6,_,_,
   _,9,8,_,_,7,1,5,_,
   _,5,4,_,_,_,_,6,_,
   _,_,1,_,_,9,_,_,_},
  // 11
  // Puzzle 6 from http://www.sudoku.org.uk/bifurcation.htm
  {_,_,_,6,_,_,_,_,4,
   _,3,_,_,9,_,_,2,_,
   _,6,_,8,_,_,7,_,_,
   _,_,5,_,6,_,_,_,1,
   6,7,_,3,_,1,_,5,8,
   9,_,_,_,5,_,4,_,_,
   _,_,6,_,_,3,_,9,_,
   _,1,_,_,8,_,_,6,_,
   2,_,_,_,_,6,_,_,_},
  // 12
  // Puzzle 7 from http://www.sudoku.org.uk/bifurcation.htm
  {8,_,_,_,_,1,_,4,_,
   2,_,6,_,9,_,_,1,_,
   _,_,9,_,_,6,_,8,_,
   1,2,4,_,_,_,_,_,9,
   _,_,_,_,_,_,_,_,_,
   9,_,_,_,_,_,8,2,4,
   _,5,_,4,_,_,1,_,_,
   _,8,_,_,7,_,2,_,5,
   _,9,_,5,_,_,_,_,7},
  // 13
  // Puzzle 8 from http://www.sudoku.org.uk/bifurcation.htm
  {6,5,2,_,4,8,_,_,7,
   _,7,_,2,_,5,4,_,_,
   _,_,_,_,_,_,_,_,_,
   _,6,4,1,_,_,_,7,_,
   _,_,_,_,8,_,_,_,_,
   _,8,_,_,_,4,5,6,_,
   _,_,_,_,_,_,_,_,_,
   _,_,8,6,_,7,_,2,_,
   2,_,_,8,9,_,7,5,1},
  // 14
  // Puzzle 9 from http://www.sudoku.org.uk/bifurcation.htm
  {_,_,6,_,_,2,_,_,9,
   1,_,_,5,_,_,_,2,_,
   _,4,7,3,_,6,_,_,1,
   _,_,_,_,_,8,_,4,_,
   _,3,_,_,_,_,_,7,_,
   _,1,_,6,_,_,_,_,_,
   4,_,_,8,_,3,2,1,_,
   _,6,_,_,_,1,_,_,4,
   3,_,_,4,_,_,9,_,_},
  // 15
  // Puzzle 10 from http://www.sudoku.org.uk/bifurcation.htm
  {_,_,4,_,5,_,9,_,_,
   _,_,_,_,7,_,_,_,6,
   3,7,_,_,_,_,_,_,2,
   _,_,9,5,_,_,_,8,_,
   _,_,1,2,_,4,3,_,_,
   _,6,_,_,_,9,2,_,_,
   2,_,_,_,_,_,_,9,3,
   1,_,_,_,4,_,_,_,_,
   _,_,6,_,2,_,7,_,_},
  // 16
  // Puzzle 11 from http://www.sudoku.org.uk/bifurcation.htm
  {_,_,_,_,3,_,7,9,_,
   3,_,_,_,_,_,_,_,5,
   _,_,_,4,_,7,3,_,6,
   _,5,3,_,9,4,_,7,_,
   _,_,_,_,7,_,_,_,_,
   _,1,_,8,2,_,6,4,_,
   7,_,1,9,_,8,_,_,_,
   8,_,_,_,_,_,_,_,1,
   _,9,4,_,1,_,_,_,_},
  // 17
  // From http://www.sudoku.org.uk/discus/messages/29/51.html?1131034031
  {2,5,8,1,_,4,_,3,7,
   9,3,6,8,2,7,5,1,4,
   4,7,1,5,3,_,2,8,_,
   7,1,5,2,_,3,_,4,_,
   8,4,9,6,7,5,3,2,1,
   3,6,2,4,1,_,_,7,5,
   1,2,4,9,_,_,7,5,3,
   5,9,3,7,4,2,1,6,8,
   6,8,7,3,5,1,4,9,2} };


int empty[N][N] = {_,_,_,_,_,_,_,_,_,
		   _,_,_,_,_,_,_,_,_,
		   _,_,_,_,_,_,_,_,_,
		   _,_,_,_,_,_,_,_,_,
		   _,_,_,_,_,_,_,_,_,
		   _,_,_,_,_,_,_,_,_,
		   _,_,_,_,_,_,_,_,_,
		   _,_,_,_,_,_,_,_,_,
		   _,_,_,_,_,_,_,_,_};


void constrain_piece(fd_int *variables, int nvariables)
{
#if 0
      fd_fake_all_different(variables, nvariables);
#elif 01
      fd_all_different(variables, nvariables);
#else
      int k;

      for (k = 1; k <= nvariables; ++k)
	fd_exactly_one(variables, N, k);
#endif
}

main(int argc, char *argv[])
{
  fd_int board[N][N];
  sudoku_i *problem;
  fd_int unit[N];
  int sqrN;
  int solutions = 0, one_solution = 1;
  int i, j, np = -1;
  int seed;

  fd_init(&argc, &argv);

#ifdef LOCAL_SEARCH
  seed = time(0);
  //seed = 1206468701;
  seed = 1208196137; // converges to a local minimum with MCH
  srandom(seed);
  _fd_debug("seed = %u\n", seed);
#endif

  for (i = 1; i < argc; ++i)
    if (!strcmp(argv[i], "--all"))
      one_solution = 0;
    else
      np = atoi(argv[i]);

  if (np != -1)
    problem = &gecode[np];
  else
    problem = &unsolvable;//dificil;

#if 01
  for (i = 0; i < NL; ++i)
    for (j = 0; j < NC; ++j)
      if ((*problem)[i][j] == _)
	board[i][j] = fd_new(1, N);
      else
	board[i][j] = fd_new((*problem)[i][j], (*problem)[i][j]);
#else
  for (i = 0; i < NL; ++i)
    for (j = 0; j < NC; ++j)
      if ((*problem)[i][j] == _)
	board[i][j] = fd_new(1, N);

  for (i = 0; i < NL; ++i)
    for (j = 0; j < NC; ++j)
      if ((*problem)[i][j] != _)
	board[i][j] = fd_new((*problem)[i][j], (*problem)[i][j]);
#endif

  // lines
  for (i = 0; i < NL; ++i)
    {
      for (j = 0; j < NC; ++j)
	unit[j] = board[i][j];

      constrain_piece(unit, NC);
    }

  // columns
  for (i = 0; i < NC; ++i)
    {
      for (j = 0; j < NL; ++j)
	unit[j] = board[j][i];

      constrain_piece(unit, NL);
    }

  // square-root(N)
  for (sqrN = 1; sqrN * sqrN < N; ++sqrN)
    ;

  // squares
  for (i = 0; i * i < NL; ++i)
    for (j = 0; j * j < NC; ++j)
      {
	int k, l, m;

	m = 0;
	for (k = 0; k * k < NL; ++k)
	  for (l = 0; l * l < NC; ++l)
	    unit[m++] = board[i * sqrN + k][j * sqrN + l];

	constrain_piece(unit, N);
      }

//return 0;

  while (fd_solve() == FD_OK)
    {
      printf("solution %d:\n", ++solutions);

      for (i = 0; i < NL; ++i)
	{
	  for (j = 0; j < NC; ++j)
	    {
	      fd_print(board[i][j]);
	      putchar('\t');
	    }
	  putchar('\n');
	}

#if !(defined(LOCAL_SEARCH) || defined(DISTRIBUTED_SOLVER))
      if (one_solution)
#endif
	break;
    }

  if (solutions)
    printf("%d solutions found\n", solutions);
  else
    printf("inconsistent CSP\n");

  fd_end();

  return !solutions;
}