Problem 4 hetmanów

/* HetmaniGT.java */

public class HetmaniGT
{
  static final int N = 4; // liczba hetmanów
  private static int[] pozycja = new int[N];
  
  public static void main(String[] args)
  {
    ustaw(0);
  }
  
  static int d(int wsp1, int wsp2)
  {
    return Math.abs(wsp1 - wsp2);
  }
  
  static boolean nieBije(int wiersz, int kolumna)
  {
    for (int w = 0; w < wiersz; w++) // h1(wiersz, kolumna) R h2(w, pozycja[w]) ?
    {
      if ( d(pozycja[w], kolumna) == d(w, wiersz) ||
           d(pozycja[w], kolumna) == 0 ) return false;
    }
    
    return true;
  }
  
  static void ustaw(int wiersz)
  {
    if (wiersz == N)
    {
      for (int w = 0; w < N; w++)
      {
        for (int k = 0; k < N; k++) // (w, k) = (w, pozycja[w]) ?
        {
          System.out.print(k == pozycja[w] ? "X" : "O");
        }
        
        System.out.println();
      }
      
      System.out.println();
    }
    else
    {
      for (int kolumna = 0; kolumna < N; kolumna++)
      {
        if (nieBije(wiersz, kolumna))
        {
          pozycja[wiersz] = kolumna;
          ustaw(wiersz + 1);
        }
      }
    } 
  }
}

/*
Ustawiamy na szachownicy 4 hetmanów: h0, h1, h2, h3

  0123

0 XOOO
1 OOOX
2 OOXO
3 XOOO

Wspólrzedne hetmanów na szachownicy:

h0(0, 0)
h1(1, 3)
h2(2, 2)
h3(3, 0)

Jesli zalozymy, ze w kazdym wierszu stoi dokladnie jeden hetman, to rozklad
hetmanów na szachownicy mozemy przechowac w jednowymiarowej tablicy o nazwie
pozycja w taki sposób, ze indeks komórki okresla wiersz, a zawartosc komórki
okresla pozycje hetmana w wierszu.

h(wiersz, pozycja[wiersz])

Dla powyzszego rozkladu hetmanów na szachownicy tablica pozycja ma postac:

            0  1  2  3
pozycja -> [0][3][2][0]

Rozwazmy na szachownicy dwóch dowolnych hetmanów: h1, h2

h1(w1, k1)
h2(w2, k2)

Wprowadzamy metryke:

d(wsp1, wsp2) = |wsp1 - wsp2|

Okreslamy relacje R:

h1 R h2 <=> hetman h1 bije sie z hetmanem h2

Zauwazamy:

Hetman h1 bije sie z hetmanem h2 wtedy i tylko wtedy, gdy hetman h1 stoi w tej
samej kolumnie co hetman h2 lub odleglosc miedzy kolumnami, w których stoja hetmani
i odleglosc miedzy wierszami, w których stoja ci sami hetmani jest sobie równa.

Zatem:

h1 R h2 <=> d(k1, k2) = 0 lub d(k1, k2) = d(w1, w2)

Opisy do metod:

static int d(int wsp1, int wsp2)

metryka d(wsp1, wsp2) = |wsp1 - wsp2|

static boolean nieBije(int wiersz, int kolumna)

Metoda nieBije, sprawdza czy hetman na pozycji (wiersz, kolumna)
nie bije sie z hetmanami, które stoja na wczesniejszych wierszach.

static void ustaw(int wiersz)

Metoda ustaw ustawia hetmana na kolejnych pozycjach w wierszu wiersz,
o ile hetman nie bije sie z hetmanami, które stoja na wczesniejszych
wierszach, a nastepnie przeprowadza te operacje dla kolejnego wiersza.
Jesli metoda ustaw zostanie wywolana z parametrem aktualnym N, to na
konsoli zostanie narysowana szachownica z rozwiazaniem.

public static void main(String[] args)

Ustawianie hetmanów rozpoczynamy od pierwszego wiersza z numerem 0.
*/

OXOO
OOOX
XOOO
OOXO

OOXO
XOOO
OOOX
OXOO

Press any key to continue...

Strona główna