root/eda/codi/backtracking/sudoku.cpp

#include <iostream>
#include <fstream>
#include <iomanip>

using namespace std;

int N, N2, W;
int ** tauler, solucions = 0;

void printSol() {
  for(int i = 0; i < N2; ++i){
    // Imprimeix barres horitzontals.
    if(i % N == 0){
      for(int j = 0; j < N2; ++j){
        if(j % N == 0) cout << setw(W) << "+";
        cout << setw(W) << "-";
      }
      cout << setw(W) << "+" << endl;
    }

    // Imprimeix nombres i barres verticals.
    for(int j = 0; j < N2; ++j){
      if(j % N == 0) cout << setw(W) << "|";
      cout << setw(W) << tauler[i][j];
    }
    cout << setw(W) << "|" << endl;
  }
  
  // Imprimeix la última de barres horitzontals i verticals.
  for(int i = 0; i < N2; ++i){
    if(i % N == 0){
      cout << setw(W) << "+";
    }
    cout << setw(W) << "-";
  }
  cout << setw(W) << "+" << endl << endl;
}

bool factible_h(int f, int c, int k){
  for(int i = 0; i < N2; ++i)
    if(tauler[f][i] == k && i != c) return false;
  return true;
}

bool factible_v(int f, int c, int k){
  for(int i = 0; i < N2; ++i)
    if(tauler[i][c] == k && i != f) return false;
  return true;
}

bool factible_q(int f, int c, int k){
  int fb = (f / N) * N;
  int cb = (c / N) * N;

  for(int i = fb; i < fb+N; ++i){
    for(int j = cb; j < cb+N; ++j){
      if(tauler[i][j] == k && (i != f || j != c)) return false;
    }
  }
  return true;
}

// És factible com a solució el valor k en la posició i, j?
bool factible(int i, int j, int k){
  return ((tauler[i][j] == 0 || tauler[i][j] == k) && 
          factible_h(i, j, k) && factible_v(i, j, k) && 
          factible_q(i, j, k));
}

void sudoku(int f, int c){
  if(f >= N2){
    printSol();
    ++solucions;
  } else {
    for(int s = 1; s <= N2; ++s){
      if(factible(f, c, s)){
        int prev = tauler[f][c];
        tauler[f][c] = s;
        if(c < N2-1) sudoku(f, c+1);
        else sudoku(f+1, 0);
        tauler[f][c] = prev;
      }
    }
  }
}

int main(int argc, char ** argv){
  if(argc != 2){
    cerr << "Usage: " << argv[0] << " sudoku" << endl;
    return 1;
  }

  ifstream file(argv[1]);
  if(!file){
    cerr << argv[1] << " could not been opened!" << endl;
    return 2;
  }

  file >> N;
  N2 = N*N;

  // Crea el tauler de N^2 * N^2.
  tauler = new int* [N2];
  for(int i = 0; i < N2; ++i)
    tauler[i] = new int [N2];

  // Llegeix les dades...
  for(int i = 0; i < N2; ++i){
    for(int j = 0; j < N2; ++j){
      file >> tauler[i][j];
      if(cin.eof()){
        cerr << "Invalid file!" << endl;
        return 3;
      }
    }
  }

  W = 1;
  int t = N2;
  while(t > 0){
    t /= 10;
    W++;
  }
  
  sudoku(0,0);
  
  cout << "Hi ha un total de " << solucions << " solucions possibles"
       << " per a aquest Sudoku." << endl;
  
  // Allibera memòria.
  for(int i = 0; i < N2; ++i)
    delete [] tauler[i];
  delete [] tauler;
  
  return 0;
}