// Backtracking: Rösselsprung-Problem lösen
//
// Aufruf: roess
//
// Klaus Kusche, 2002

#include <stdio.h>
#include <stdlib.h>

// für usleep, nur Linux
#include <unistd.h>
// für Sleep, nur Windows
//#include <windows.h>

// Größe des Schachbrettes
#define BOARDSIZE 8
// Anzeige-Verzögerung zwischen zwei Lösungen in Millisekunden
#define DELAY 300

// Schachbrett
// Jedes Feld speichert, als wievieltes Feld es besucht wurde
// 0 ... Feld wurde noch nicht besucht
// Rundherum 2 Reihen mit Wert -1, um Sprünge über den Brettrand zu erkennen
int board[BOARDSIZE+4][BOARDSIZE+4];

// board initialisieren
void init(void)
{
  // zuerst alles auf -1
  for (int row = 0; row < BOARDSIZE + 4; ++row) {
    for (int col = 0; col < BOARDSIZE + 4; ++col) {
      board[row][col] = -1;
    }
  }
  // ... und dann den gültigen Bereich auf 0
  for (int row = 2; row < BOARDSIZE + 2; ++row) {
    for (int col = 2; col < BOARDSIZE + 2; ++col) {
      board[row][col] = 0;
    }
  }
}

// board ausgeben
void output(void)
{
  // Terminal-Fenster-Inhalt löschen
  system("clear");  // Linux
  //system("cls");    // Windows
  
  putchar('\n');
  for (int row = 2; row < BOARDSIZE + 2; ++row) {
    for (int col = 2; col < BOARDSIZE + 2; ++col) {
      printf(" %2d", board[row][col]);
    }
    putchar('\n');
  }

  // DELAY ms warten
  usleep(DELAY * 1000);  // Linux, aus unistd.h, Argument = Mikrosekunden
  //Sleep(DELAY);          // Windows, aus windows.h, Argument = Millisekunden
}

// besuche das Feld row/col als Zug Nummer cnt 
void jump(int row, int col, int cnt)
{
  // aktuelles Feld als "besucht im Zug Nummer cnt" markieren
  board[row][col] = cnt; 
  if (cnt == BOARDSIZE*BOARDSIZE) {
    // So viele Züge gemacht, wie es Felder gibt ==> fertig!
    output();
  } else {
    // alle 8 Möglichkeiten für nächsten Zug probieren
    // Wenn Ziel-Feld frei ist: Rekursiv dorthin ziehen
    if (board[row-1][col-2] == 0) jump(row-1, col-2, cnt+1);
    if (board[row-2][col-1] == 0) jump(row-2, col-1, cnt+1);
    if (board[row-2][col+1] == 0) jump(row-2, col+1, cnt+1);
    if (board[row-1][col+2] == 0) jump(row-1, col+2, cnt+1);
    if (board[row+1][col+2] == 0) jump(row+1, col+2, cnt+1);
    if (board[row+2][col+1] == 0) jump(row+2, col+1, cnt+1);
    if (board[row+2][col-1] == 0) jump(row+2, col-1, cnt+1);
    if (board[row+1][col-2] == 0) jump(row+1, col-2, cnt+1);
  }
  board[row][col] = 0;  // aktuellen Zug wieder löschen!
}

int main(void)
{ 
  init();

  // Beginne links oben (= Index 2/2 wegen Rand) mit Zug 1
  jump(2, 2, 1);

  exit(EXIT_SUCCESS);
}