// Die Implementierungs-Klasse für Sudoku
// In dieser Klasse ist die Lösungslogik
// Klaus Kusche, 2010

#include "solver.h"
#include <assert.h>

// Verwandlung Zahl ==> Bitmaske:
// Liefert einen int mit dem n. Bit (von hinten) gesetzt
#define BIT(n) (1 << (n - 1))

Solver::Solver(Sudoku *gui) :
  myGui(gui)
{
  int pos;

  // Initialisiere die konstanten Arrays
  for (pos = 0; pos < NUM_POS; ++ pos) {
    col[pos] = pos % 9;
    row[pos] = pos / 9;
    block[pos] = (row[pos] / 3) * 3 + col[pos] / 3;
  }
}

int Solver::Go()
{
  int n;
  
  n = GetInput();
  if (n > 0) {
    return -n;
  } else {
    solvCnt = 0;
    Solve(0);
    return solvCnt;
  }
}

int Solver::Solve(int pos)
{
  int x, y, z;  // Zeile / Spalte / Block von pos
  int avail;    // Bitmaske: noch verfügbare Zahlen für Position pos
  int v;        // die Zahl, die wir gerade probieren
  int bit;      // Bitmaske von v
  int i;
  
  // überspringe schon belegte Positionen,
  // suche die nächste noch nicht belegte Position (Inhalt 0)
  for (;; ++pos) {
    if (pos >= NUM_POS) {
      // alle Positionen sind erfolgreich belegt ==> Lösung!
      // Zur Sicherheit: Wirklich überall jede Zahl genau einmal?
      for (i = 0; i < NUM_COL; ++i) {
        assert((xUsed[i] == 0x1ff) &&
               (yUsed[i] == 0x1ff) &&
               (zUsed[i] == 0x1ff));
      }
      return myGui->Solution(++solvCnt);
    }
    if (value[pos] == 0) break;   /* Position pos ist noch unbelegt */
  }

  x = col[pos]; y = row[pos]; z = block[pos];
  avail = 0x1ff & ~(xUsed[x] | yUsed[y] | zUsed[z]);

  // probiere alle zur Verfügung stehenden Zahlen
  for (v = 1; (bit = BIT(v)) <= avail; ++v) {
    if (bit & avail) {
      // die Zahl ist noch frei, speichere sie
      value[pos] = v;
      xUsed[x] |= bit; yUsed[y] |= bit; zUsed[z] |= bit;
      if (myGui->SetValue(pos, v)) return 1;
      // belege rekursiv die restlichen Plätze
      if (Solve(pos + 1)) return 1;
      // mach unsere Zahl wieder rückgängig
      value[pos] = 0;
      xUsed[x] &= ~bit; yUsed[y] &= ~bit; zUsed[z] &= ~bit;
      if (myGui->ResetValue(pos)) return 1;
    }
  }

  return 0;
}

int Solver::GetInput()
{
  int x, y, z;
  int pos, v, bit;
  int i;
  
  for (i = 0; i < NUM_COL; ++i) {
    xUsed[i] = yUsed[i] = zUsed[i] = 0;
  }
  
  for (pos = 0; pos < NUM_POS; ++pos) {
    x = col[pos]; y = row[pos]; z = block[pos];

    value[pos] = v = myGui->GetValue(pos);
    assert((v >= 0) && (v <= 9));
    if (v > 0) {
      bit = BIT(v);
      if ((bit & xUsed[x]) || (bit & yUsed[y]) || (bit & zUsed[z])) {
        return v;
      }
      xUsed[x] |= bit; yUsed[y] |= bit; zUsed[z] |= bit;
    }
  }
  
  return 0; // Erfolg
}