2
\$\begingroup\$

Here is the puzzle:

Put il queens (a figure in chest) on the chessboard with quadratic dimensions a x a. The figures cannot attack each other!

This is my solution (my first lengthy programme in Java):

Chessboard:

/**
 * 
 * @author Julian_
 *
 *         Quadratic chessboard, the meaning of fields: 0 - free field 1 - field
 *         which is being attack by a figure/figures.
 * 
 *         Class contains 3 main methods: putting figures on the chessboard,
 *         taking away figures from the chess board and marking the fields which
 *         are being attack by a figure/figures.
 *         
 *         values of the chessboard:
 *         0 - empty field
 *         1 - field being attacked by any figure/figures
 */
public class Chessboard {
    int a; // length of the side of the chess board measured in the amount of
            // fields
    int[][] tab = null; // the chessboard

    Chessboard(int a) {
        super();
        this.a = a;
        tab = new int[a][a];
    }

    /**
     * Put a figure on the selected field on the chessboard, if the field is
     * free (there is other figure placed and the field is not being attacked by
     * any other figure placed on the chess board. The putting is made by
     * changing value of the field to FIGURE_ID of the figure. The method also
     * calls updateFields() method.
     * 
     * @param x
     *            horizontal coordinate of the chessboard
     * @param y
     *            vertical coordinate of the chessboard
     * @param figureId
     *            the id of the figure which is to placed
     * @return is it possible to putting there a figure, the side-effect is
     *         changing the value of the field where figure is put to the value
     *         of FIGURE_ID of the put figure.
     */
    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.updateFields(fig);
            return true;
        }
    }

    /**
     * Takes away a figure from the chosen field by changing it's value to 0
     * with setFree() method.
     * 
     * @param x
     *            horizontal coordinate of the chessboard
     * @param y
     *            vertical coordinate of the chessboard
     */
    public void unputFigure(int x, int y, Figure fig) {
        setFree(x, y);
        this.updateFields(fig);
    }

    /**
     * Marks attacked fields on the chessboard by analyse of the put figures on
     * the chess board.
     */
    public void updateFields(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);
                }
            }
        }

    }

    /**
     * Calls setAttacked() method to set a field into being attacked.
     * 
     * @param x
     *            horizontal coordinate of the chessboard
     * @param y
     *            vertical coordinate of the chessboard
     */
    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);
                }
            }
        }
    }

    /**
     * Set a field into being attacked by changing it's value to 0.
     * 
     * @param x
     *            horizontal coordinate of the chessboard
     * @param y
     *            vertical coordinate of the chessboard
     */
    public void setAttacked(int x, int y) {
        tab[y][x] = 1;
    }

    /**
     * Set free the selected field by changing it's value to 0.
     * 
     * @param x
     *            horizontal coordinate of the chessboard
     * @param y
     *            vertical coordinate of the chessboard
     */
    public void setFree(int x, int y) {
        tab[y][x] = 0;
    }

    /**
     * 
     * @return the lenght of the chessboard measured by the number of fields of
     *         1 side.
     */
    public int getA() {
        return a;
    }

    /**
     * @param figureId
     *            id figure to being count
     * @return the number of selected figures located on the chessboard.
     */
    public int countFigures(Figure fig) {
        int c = 0;
        for (int j = 0; j < tab.length; j++) {
            for (int i = 0; i < tab[j].length; i++) {
                if (tab[j][i] == fig.getId()) {
                    c++;
                }
            }
        }
        return c;
    }

    /**
     * 
     * @param x
     *            horizontal coordinate of the chessboard
     * @param y
     *            vertical coordinate of the chessboard
     * @return value of the selected field. If the field is outside the chessboard it returns -1.
     */
    public int checkPosition(int x, int y) {
        try {
            return tab[y][x];
        } catch (ArrayIndexOutOfBoundsException e) {
            return -1;
        }
    }

    /**
     * Visualise the chessboard
     */
    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(" ------------- ");
    }

}

Figure:

/**
 * FIGURE_ID:
 * pawn: 2
 * knight: 3
 * runner: 4
 * tower: 5
 * the queen: 8
 * the king: 9
 * 
 * cannot be 0 or 1
 *
 */

public abstract class Figure{
    private int FIGURE_ID;

    public int getId(){
        return FIGURE_ID;
    }

    public abstract boolean isAttacked(int x, int y, int xx, int yy);
}

The Queen:

public class Queen extends Figure {
    final private 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));
    }

}

The solution:

public class Solution {

    /**
     * First loops are for checking all possibile start - coordinates. For
     * instance: if method would not find a solution for starting coordinates
     * [0][0] it will loop to [0][1] and so on until if will find the solution
     * or until [][] == [a][a] where a is the lenght of the chess board measured
     * in fields number.
     * 
     * Next it put a figure near the last figure and so on in recursive way. If
     * the number of figures will be equal the expected value algorithms return
     * true. If not it returns falls and backtrack to the last puting on figure
     * and tryin to make it in a different way.
     * 
     * @param cb
     *            the chessboard
     * @param il
     *            how many figures do you want to put on the chessboard
     * @return is the solution found, if yes it also write the chessboard on the
     *         screen.
     */
    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 horizontal coordinate of the chessboard
     * @param y vertical coordinate of the chessboard
     * look at upward at the comments
     */
    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(fig) >= il) {
            return true;
        }

        while (cb.countFigures(fig) < il && ky < cb.getA()) {
            kx = 1;
            while (cb.countFigures(fig) < 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;
    }


    /**
     * 
     * GET THE BALL ROLLING!
     * 
     */
    public static void main(String args[]) {

        Chessboard cb = new Chessboard(8);
        Figure queen = new Queen();
        //boolean x = cb.putFigure(1, 1, queen);
        boolean x = Solution.rekur(cb, queen, 8);

        //boolean x = cb.putFigure(1, 2, queen);
        //cb.show();
        System.out.println(x);

    }
}
\$\endgroup\$
  • \$\begingroup\$ Is there anything in particular you're looking for criticism on? It's often helpful to narrow down your review request, especially for longer bits of code like this. \$\endgroup\$ – Carcigenicate Apr 29 '17 at 18:36
  • \$\begingroup\$ well, agorithm work well for me but I'm afraid of the synthax. Is it chaotical? I look for just generall quick check do you see anything strange? \$\endgroup\$ – wBacz Apr 29 '17 at 19:01
  • \$\begingroup\$ I tried writing a review, but I'm on my phone, so it was paonful to write. The weirdest thing that stood out to me was that giant if-else tree in rekur. You have like 8 ifs that all return true. Really, that should be a single condition connected by ||s. \$\endgroup\$ – Carcigenicate Apr 29 '17 at 19:04
  • \$\begingroup\$ @Carcigenicate, I disagree with that. The way the OP structured those if-statements adds to the readability of the code. If he had done it the way you are suggesting, it will be very unreadable and debugging will be hell \$\endgroup\$ – smac89 Apr 29 '17 at 19:34
  • \$\begingroup\$ And what do ya think bout the try catch clause at method checkPosition at Chessboard class? \$\endgroup\$ – wBacz Apr 29 '17 at 19:46
0
\$\begingroup\$

My first focus is on one method in this answer, and that is the last rekur() of the Solution class. I'm leaving the rest for others to review.

Let me present an alternate solution based upon your code, and then discuss it afterwards related to your code:

public static boolean rekur(int x, int y, Chessboard cb, Figure fig, int il) {
    int kx, ky, dim, figureCount;

    cb.putFigure(x, y, fig);

    figureCount = cb.countFigures(fig);
    dim = cb.getA();

    // Have we reached the correct number of figures? 
    if (dim >= il) {
        return true;
    }


    // Try placing more figures around the current position (i & j),
    // in increasing distances (kx & ky)
    for (int ky=1; figureCount < il && ky < dim; ky++) {
      for (int kx=1; figureCount < il && kx < dim; kx++) {
        // System.out.println(cb.checkPosition(x, y));

        for (int i = -1; i <= 1; i++) {
          for (int j = -1; j <= 1; j++) {

            if (i==0 && j==0) {
              continue;
            }

            if (cb.checkPosition(x + i*kx, y + j*ky) == 0 &&
              rekur(x + i*kx, y + j*ky, cb, fig, il)) {

              return true;
            }
          }
        }
      }
    }

    cb.unputFigure(x, y, fig);
    return false;
}

Here are the changes and why:

  • Calculate once, if possible – At the start I find the dimension and number of figures once, and use the precalculated throughout the function.
  • Simplify disguised for-loop – Your while-loop is simply a for-loop with a slightly more complicated end condition.
  • Avoid multiple similar if-statements – Whenever you find yourself copy-pasting if-loops, which are almost identical, you should start thinking if you can't replace it with some more general code. In this case you vary the coordinates by adding -kx, 0 and kx (and likewise for ky). This can be implemented using a double for-loop (looping through -1, 0, 1) and multiplication, as shown above.

    This kind of simplification avoids repeated code, and shows the pattern you've used clearer. To avoid the current position a special case when both are zero had to be added. Still I think, this is a neater solution to avoid the multiple similar if statements.

  • Added comments related to why you are doing stuff – I've added a few comments, but some more could be added around in your code to describe what you are trying to achieve in the various parts of your code.

Some other general comments

  • The defineAttack() ignores other pieces – With the current definition of your Queen and its isAttacked() other pieces on the chess board is ignored. If a Queen is placed all surrounded by Pawns for example, the Queen is not attacking anything but the Pawns.

    In this particular implementation the other pieces are also Queens with the same attack pattern, so it doesn't matter that much. The moment you add another piece, though, your logic is broken.

  • Strange order of i and j – In most double loops the i is the outer loop, not the inner. It doesn't have to be so, but you're kind of breaking conventions. Similarly, you've chosen to do tab[j][i] switching the dimension. This might confuse future readers of your code.

  • Why a and not dimension? – Why have you chosen you use a for the dimension of your chess board? And a method getA()? That really doesn't make any sense, and would be better replaced by dimension or size or length.

  • Why not have the board arrays of Figures? – Instead of using the array of ints it makes more sense to me to have a board of Figures, with possibly some special figures to indicate the empty or attacked spaces. This way you would have avoided passing the fig all around, and could just check which figure is in a given spot.

    On a related note, that would also simplify the signature of updateFields(), as it isn't natural for this to receive the figure which have just been removed (or added).

  • Why x in the first rekur() method? – This a truly badly named variable. The x has a very strong conation of being a coordinate, but you're using it to test for solutions. Name it appropriatly like foundSolution.

  • Don't test for x == false – Use !x instead, or with new name !foundSolution. Use the booleans directly in conditions and don't test for true or false.

  • Disguised for-loop in the first rekur(), as well – In your first version, where you use the x == false condition, you do a double while loop, which could be changed into a double for loop like the code above. In addition I really don't get the j < Math.min(il, cb.getA()) condition. Is that really correct and functional? Have you tried it after changing the dimensions or number of queens to place?

  • checkPosition() is misleading – It doesn't check the position, it returns the position content. And it reveals inner magic numbers of your chessboard.

    I think it would be better to have it named isEmpty() and return a true/false value depending on content. I would possibly also add an isAttacked() to the chessboard returning true if is already under attack.

  • Change Figure's isAttacked to attacks() – In my head that would be a slightly better name, and would reduce confusion if you implement my previous suggestion.

I'm still not sure if I covered all bases, but I should covered enough for you to get something to think about!

\$\endgroup\$
  • \$\begingroup\$ Thank you very much! I totally agree with the first point. I'm gonna analyse next points and your code. It looks much more clear than mine. \$\endgroup\$ – wBacz Apr 29 '17 at 21:16
  • \$\begingroup\$ Why a and not dimension? — because of puzzle statement;) but size, probably will be better. a - is not clear, dimension could be considered as a number of dimentions of a board: 2d, 3d, or even 4d-chessboard \$\endgroup\$ – maxkoryukov Apr 29 '17 at 22:36
  • \$\begingroup\$ Hi, I have doubts about creating 2 tables: 1 for figures and 1 for info if a field under attack. Every table will use distinctive methods. So should I create 2 inner classes for these tables or 2 classes which inherits from Chessboard? \$\endgroup\$ – wBacz May 3 '17 at 16:06
-1
\$\begingroup\$

The new version of the Solution class where I change if conditions into 1 loop:

public class Solution {

    /**
     * First loops are for checking all possibile start - coordinates. For
     * instance: if method would not find a solution for starting coordinates
     * [0][0] it will loop to [0][1] and so on until if will find the solution
     * or until [][] == [a][a] where a is the lenght of the chess board measured
     * in fields number.
     * 
     * Next it put a figure near the last figure and so on in recursive way. If
     * the number of figures will be equal the expected value algorithms return
     * true. If not it returns falls and backtrack to the last puting on figure
     * and tryin to make it in a different way.
     * 
     * @param cb
     *            the chessboard
     * @param il
     *            how many figures do you want to put on the chessboard
     * @return is the solution found, if yes it also write the chessboard on the
     *         screen.
     */
    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
     *            horizontal coordinate of the chessboard
     * @param y
     *            vertical coordinate of the chessboard look at upward at the
     *            comments
     */
    public static boolean rekur(int x, int y, Chessboard cb, Figure fig, int il) {

        if (cb.countFigures(fig) >= il) {
            return true;
        }

        for (int j = 0; j < cb.getA(); j++) {
            for (int i = 0; i < cb.getA(); i++) {
                if (cb.checkPosition(i, j) == 0) {
                    cb.putFigure(i, j, fig);
                    rekur(i, j, cb, fig, il);
                }
            }
        }
        cb.unputFigure(x, y, fig);
        return false;
    }

    /**
     * 
     * GET THE BALL ROLLING!
     * 
     */
    public static void main(String args[]) {

        Chessboard cb = new Chessboard(10);
        Figure queen = new Queen();
        // boolean x = cb.putFigure(1, 1, queen);
        boolean x = Solution.rekur(cb, queen, 10);

        // boolean x = cb.putFigure(1, 2, queen);
        // cb.show();
        System.out.println(x);

    }
}
\$\endgroup\$
  • \$\begingroup\$ This solution doesn't do the same amount of work as the original code you posted, does it? It seems to skip all the stuff related to checking around the given position you are recursing around. \$\endgroup\$ – holroy Apr 29 '17 at 20:34
  • \$\begingroup\$ I think the results are the same. In the first version it was checking the nearest fields to the last queen and now it goes in a loop for whole chessboard from begining [0][0] to [a][a] until if finds a place to put queen. When it finds then the method is call in recursive and loop goes again from the begining. \$\endgroup\$ – wBacz Apr 29 '17 at 20:46
  • \$\begingroup\$ You've still changed the algorithm from your original algorithm. I doesn't say that it is wrong, but it is a different algorithm. \$\endgroup\$ – holroy Apr 29 '17 at 20:47
  • \$\begingroup\$ You mean the way of solution is different but the results should be almost the same? \$\endgroup\$ – wBacz Apr 29 '17 at 20:49
  • \$\begingroup\$ Yeah, something along those lines. \$\endgroup\$ – holroy Apr 29 '17 at 20:56
-2
\$\begingroup\$

my 5 cents

UPD: About the best algorithm

This is typical example for Dynamic programming problem.

There is another question on SO about Queens on a board, there you could find a good solution and mathematical rationale.

isAttacked observations

In common case, to keep interfaces clean, isAttacked should be converted to isAttackingTo, because every certain figure knows only its own way of attacking, I mean, that implementation of Queen class should not contain attacking technique of Pawn)) But in current case all figures are queens

BTW, tt is easy to keep both methods:

public boolean isAttackedBy(Figure A) {
    return A.isAttackingTo(this);
}
public boolean isAttackingTo(Figure B) {
    // real implementation
}

long bool statements

Another one observation about long bool statements (conditions). Sometimes (not always!!) it is much better to use fast return kung-fu:

// ORIGINAL version

public boolean isAttacked(int x, int y, int xx, int yy) {
    return (x == xx || y == yy || Math.abs(x - xx) == Math.abs(y - yy));
}

// FAST RETURN
public boolean isAttacked(int x, int y, int xx, int yy) {

    // This method will return on first matched condition!

    if (x == xx) return true;
    if (y == yy) return true;
    if (Math.abs(x - xx) == Math.abs(y - yy)) {
        return true;
    }
    return false;
}

Sorry, I am not sure about proper Java-syntax..

Be aware: this is not Java-performance optimization, but human-readability optimization. We have 6 lines, instead of 1, and these 6 are easy to read, understand and cover with unit-tests.

About performance: almost all modern languages use lazy bool evaluation, so both (OLD and NEW) functions will work with about the same speed.

Other observations

  • x and y should be implemented as members of Figure class
  • isAttacked should accept just one parameter — Figure instance.
\$\endgroup\$
  • 1
    \$\begingroup\$ The so-called "FAST RETURN" is unneeded. This is already done through boolean shortcuts. When Java sees that this combination of || it evaluated, it'll skip the rest of the conditions. In other words, when encountering the first false condition, the rest of the conditions are skipped and it returns false. \$\endgroup\$ – holroy Apr 29 '17 at 21:15
  • \$\begingroup\$ Thank you very much! You are right so the object Chessboard should cointains many Figure objects. Connection: 1 - *. But what about return kung-fu I have doubts... The first true || syntax breaks in the first true, doesn't it? for instance: if cond1 = true then return cond1 || cond2 will return true before checking the cond2 ? \$\endgroup\$ – wBacz Apr 29 '17 at 21:17
  • \$\begingroup\$ @holroy of course, it is not needed for Java. But it is more readable, than 3-4-5 OR conditions. We are reading code more often, than writing. Anyway, I will add you notice to the my answer, thanks ;) \$\endgroup\$ – maxkoryukov Apr 29 '17 at 22:14
  • \$\begingroup\$ @wBacz, this is short-circuit evaluation for bool expressions, in short - the evaluation stops, when the answer already known. For example if (A || B || C) ... - when A is true Java will not evaluate B, C, because they already could not affect the result. More information about this on wikipage: en.wikipedia.org/wiki/Short-circuit_evaluation \$\endgroup\$ – maxkoryukov Apr 29 '17 at 22:28
  • \$\begingroup\$ @wBacz, about if cond1 = true then return cond1 || cond2 will return true before checking the cond2 ?. If cond1 is true, then the result of cond1 || cond2 does not depend on cond2 (check it, when cond2==true, result is true, when cond2==false, result is true). There is similar rule about AND statement, but in case of && operator, when the first (of leftmost) operand is false the values of other operands do not matter. \$\endgroup\$ – maxkoryukov Apr 29 '17 at 22:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.