Zagadka taka o:
ustaw na kwadratowej szachownicy o wymiarach a figury krolowej (hetmana) tak by zmiescic il takich krolowych (hetmanow) i żeby żadna królowa (hetman) nie atakowała innej królowej(hetmana).
porady? uwagi?
// -------------------------------------------------------------------------------------------------
// Szachownica -----------------------------------------------------------------------------
// -------------------------------------------------------------------------------------------------
/**
*
* @author Julian_
*
* Szachownica kwadratowa, znaczenie pól: 0 - pole wolne 1 - pole, które
* jest atakowane przez figurę od 2 idki figur
*
* Zawiera 3 główne metody którymi są: ustawianie figur, zabieranie
* figur oraz oznaczanie pól atakowanych
*/
public class Chessboard {
int a; // dlugosc boku szachownicy w polach (ilosc pol na 1 bok szachownicy)
int[][] tab = null; // szachownica
Chessboard(int a) {
super();
this.a = a;
tab = new int[a][a];
}
/**
* Na podstawie wybranego pola z krolowa zleca oznaczenie odpowiednich pol
* jako atakowane metodzie setAttacked()
*
* @param x
* kordynat poziomy szachownicy
* @param y
* kordynat pionowy szachownicy
*/
public void defineAttack(int x, int y, Figure fig) {
for (int j = 0; j < tab.length; j++) {
for (int i = 0; i < tab[j].length; i++) {
if (tab[j][i] == 0 && fig.isAttacked(x, y, i, j)) {
this.setAttacked(i, j);
}
}
}
}
/**
* Oznacza atakowane pola na calej szachownicy analizujac postawione figury
* na szachownicy. Odznaczenie pol jako wolne zleca metodzie setFree() a
* zaznaczenie jako atakowane metodzie defineAttack().
*/
public void setAttack(Figure fig) {
for (int j = 0; j < tab.length; j++) {
for (int i = 0; i < tab.length; i++) {
if (tab[j][i] == 1) {
this.setFree(i, j);
}
}
}
for (int j = 0; j < tab.length; j++) {
for (int i = 0; i < tab.length; i++) {
if (tab[j][i] > 1) {
defineAttack(i, j, fig);
}
}
}
}
/**
* Ustawia dana figure na wskazanym polu na szachownicy, jesli nie stoi tam
* inna figura i pole nie jest atakowane przez zadna z figur postawionych do
* tej pory. Ustawianie robi zmieniajac pole na id figury
*
* @param x
* kordynat szachownicy, os pozioma
* @param y
* kordynat szachownicy, os pionowa
* @param figureId
* odpowiednie id figury oznaczajacy ktora figury ktora ma byc
* polozona
* @return czy mozliwe jest polozenie tej figury na wskazanym miejscu, efekt
* uboczny - zmiana wskazanego pola szachownicy na id figury
*/
public boolean putFigure(int x, int y, Figure fig) {
if (tab[y][x] != 0 && tab[y][x] != 1) {
return false;
} else {
tab[y][x] = fig.getId();
this.setAttack(fig);
return true;
}
}
/**
* Zabiera figure z szachownicy ze wskazanego pola, oznaczajac to pole jako
* puste (czyli 0)
*
* @param x
* kordynat szachownicy os pozioma
* @param y
* kordynat szachownicy os pionowa
*/
public void unputFigure(int x, int y, Figure fig) {
tab[y][x] = 0;
this.setAttack(fig);
}
/**
* Ustawia dane pole na atakowane za pomoca oznaczenia pola nr 1
*
* @param x
* kodynat szachownicy os pozioma
* @param y
* kordynat szachownicy os pionowa
*/
public void setAttacked(int x, int y) {
tab[y][x] = 1;
}
/**
* Ustawia dane pole na wole za pomoca oznaczenia pola nr 0
*
* @param x
* kodynat szachownicy os pozioma
* @param y
* kordynat szachownicy os pionowa
*/
public void setFree(int x, int y) {
tab[y][x] = 0;
}
/**
*
* @return długosc boku szachownicy w polach (ilosc pol na 1 bok
* szachownicy)
*/
public int getA() {
return a;
}
/**
* @param figureId
* id figury do zliczenia
* @return ilosc figur postawionych na szachownicy o danym id
*/
public int countFigures(int figureId) {
int c = 0;
for (int j = 0; j < tab.length; j++) {
for (int i = 0; i < tab[j].length; i++) {
if (tab[j][i] == figureId) {
c++;
}
}
}
return c;
}
/**
* Zwraca wartosc danego pola, jesli kordynaty wykraczaja poza szachownice
* to zwraca -1
*
* @param x
* kodynat szachownicy os pozioma
* @param y
* kordynat szachownicy os pionowa
* @return wartosc danego pola
*/
public int checkPosition(int x, int y) {
try {
return tab[y][x];
} catch (ArrayIndexOutOfBoundsException e) {
return -1;
}
}
/**
* Wyswietla szachownice w postaci zaawansowanej wizualizacji tablicowej
*/
public void show() {
for (int j = 0; j < tab.length; j++) {
for (int i = 0; i < tab[j].length; i++) {
System.out.print(tab[j][i] + " ");
}
System.out.println("");
}
System.out.println(" ------------- ");
}
}
// -------------------------------------------------------------------------------------------------
// Figura --------------------------------------------------------------------
// -------------------------------------------------------------------------------------------------
/**
* FIGURE_ID:
* pionek: 2
* skoczek: 3
* goniec: 4
* wieza: 5
* krolowa: 8
* krol: 9
*
*/
public abstract class Figure{
int FIGURE_ID;
public int getId(){
return FIGURE_ID;
}
public abstract boolean isAttacked(int x, int y, int xx, int yy);
}
// -------------------------------------------------------------------------------------------------
// Krolowa --------------------------------------------------------------------
// -------------------------------------------------------------------------------------------------
public class Queen extends Figure{
final int FIGURE_ID = 8;
public int getId(){
return FIGURE_ID;
}
public boolean isAttacked(int x, int y, int xx, int yy) {
return (x == xx || y == yy || Math.abs(x - xx) == Math.abs(y - yy));
}
}
// -------------------------------------------------------------------------------------------------
// rozwiazanie ---------------------------------------------------
// -------------------------------------------------------------------------------------------------
public class Solution {
/**
* Pierwsze 2 petle while sluza do przelatywania przez wszystkie mozliwe
* kordynaty poczatkowe (start algorytmu). np. jesli zacznie od kordynatow
* [0][0] i nie znajdzie rozwiazania to poleci dalej [0][1] itd. az znajdzie
* rozwiazanie albo az do [a][a], gdzie a to dlugosc boku szachownicy
* mierzona w ilosci pol.
*
* potem ustawia najblizej do porzedniego ustawienia figure i tak dalej
* rekurencyjnie, jesli znajdzie rozwiazanie to zwraca true i konczy. Jesli
* nie znajdzie to wraca do poprzedniego kroku i probuje kolejne pola, az
* znajdzie rozwiazanie lub az wroci do pierwszej postawionej figury, a
* wtedy patrz wyzej.
*
* @param cb
* szachownica
* @param il
* ile ma ustawic figur na szachownicy
* @return czy udalo sie znalezc roziwazanie, jesli tak to wyswietla
* zaawansowana wizualizacje szachownicy z ustawionymi figurami
*/
public static boolean rekur(Chessboard cb, Figure fig, int il) {
boolean x = false;
int j = 0, i = 0;
while (x == false && j < Math.min(il, cb.getA())) {
while (x == false && i < Math.min(il, cb.getA())) {
x = Solution.rekur(i, j, cb, fig, il);
i++;
}
j++;
}
if (x) {
cb.show();
}
return x;
}
/**
*
* @param x kordynaty szachownicy os pozioma
* @param y kordynaty szachownicy os pionowa
* reszta patrz wyzej
*/
public static boolean rekur(int x, int y, Chessboard cb, Figure fig, int il) {
int kx = 1, ky = 1;
cb.putFigure(x, y, fig);
if (cb.countFigures(8) >= il) {
return true;
}
while (cb.countFigures(8) < il && ky < cb.getA()) {
kx = 1;
while (cb.countFigures(8) < il && kx < cb.getA()) {
// System.out.println(cb.checkPosition(x, y));
if (cb.checkPosition(x, y + ky) == 0 && rekur(x, y + ky, cb, fig, il)) {
return true;
}
if (cb.checkPosition(x + kx, y + ky) == 0 && rekur(x + kx, y + ky, cb, fig, il)) {
return true;
}
if (cb.checkPosition(x + kx, y) == 0 && rekur(x + kx, y, cb, fig, il)) {
return true;
}
if (cb.checkPosition(x + kx, y - ky) == 0 && rekur(x + kx, y - ky, cb, fig, il)) {
return true;
}
if (cb.checkPosition(x, y - ky) == 0 && rekur(x, y - ky, cb, fig, il)) {
return true;
}
if (cb.checkPosition(x - kx, y - ky) == 0 && rekur(x - kx, y - ky, cb, fig, il)) {
return true;
}
if (cb.checkPosition(x - kx, y) == 0 && rekur(x - kx, y, cb, fig, il)) {
return true;
}
if (cb.checkPosition(x - kx, y + ky) == 0 && rekur(x - kx, y + ky, cb, fig, il)) {
return true;
}
kx++;
}
ky++;
}
cb.unputFigure(x, y, fig);
return false;
}
/**
*
* JEDZIEMY Z KOKSEM!
*
*/
public static void main(String args[]) {
Chessboard cb = new Chessboard(20);
Figure queen = new Queen();
//boolean x = cb.putFigure(1, 1, queen);
boolean x = Solution.rekur(cb, queen, 19);
System.out.println(x);
cb.show();
}
}