We have a square board of size n * n, the cells of which can take values ​​of boolean type: #t is a painted cell, #f is an empty (not painted) cell. The board is considered to be filled correctly only if the painted cell has no neighbors to the right, left, top and bottom (only diagonally). So:

X 0 X 0 X 0 X 0 O

You need to write the method method (boolean [] field, int n), which will take a one-dimensional (!) Array, the size of the board n and show the correctness of the board fill (#t, #f).

Right:

 X 0 0 0 0 X 0 X 0 0 0 0 X 0 0 0

Wrong:

 X 0 0 0 X 0 0 X 0 0 X 0 X 0 0 0

The numbering of elements in the array, respectively:

 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

In conclusion, you need to create a method that will count the number of possible correctly filled fields for a particular n. Ie creating in a naive way all possible options for filling in the fields and checking them with the help method.

Thank you so much for any tips! I searched on the Internet, found a solution for a rook problem that I thought was not applicable to this problem.

My own sketches (not working for even n):

 public static boolean gueltig1(boolean[] feld, int n){ for (int i = 0; i < n * n; i++){ if(i + n <= n * n - 1){ if (feld[i] == true && (feld[Math.abs(i + 1)] == true || feld[Math.abs(i - 1)] == true || feld[Math.abs(i + n)] == true || feld[Math.abs(i - n)] == true)){ return false;} } if(i + n > n * n - 1 && i + 1 < n * n - 1){ if (feld[i] == true && (feld[Math.abs(i + 1)] == true || feld[Math.abs(i - 1)] == true || feld[Math.abs(i - n)] == true)){ return false;} } if(i == n * n - 1){ if (feld[i] == true && (feld[Math.abs(i - 1)] == true || feld[Math.abs(i - n)] == true)){ return false;} } } return true; }

Or so:

 public static boolean gueltig(boolean[] feld, int n){ for (int i = n + 1; i < n * n; i++){ if(feld[i] == true && (feld[i - n] == true || feld[Math.abs(i - 1)] == true)){ return false;} } return true; }

PS: Beginner

    3 answers 3

    Here is the solution in Java.

     public class Main { public static void main(String[] args) { boolean[] board = { true, false, true, false, false, true, false, true, false, false, true, false, false, false, true, false, false, true, true, false, false, false, true, false, false, false, false, false, false, false, true, false, false, true, false, true, }; System.out.println(isCorrect(board)); } private static boolean isCorrect(boolean[] board) { Neighbors neighbor = new Neighbors(board); return neighbor.isCorrect(); } static class Neighbors { boolean left; boolean right; boolean top; boolean bottom; boolean[] board; int dim; Neighbors(boolean[] board) { this.board = board; initDim(); } private void initDim() { double boardDimension = Math.sqrt(board.length); if (boardDimension % 1 != 0) { System.err.println("Warning: you must pass array that have n * n elements. In this case the correct result is not guaranteed."); } dim = (int) boardDimension; } boolean isColored(int position, char operation, int offset) { try { // Если на "краю" и если проверяем вправо или влево. if (isOnEdge(position) && offset != dim) { return false; } if (operation == '+') { return board[position + offset]; } else { return board[position - offset]; } } catch (ArrayIndexOutOfBoundsException ignored) { } return false; } private boolean isOnEdge(int position) { return (position + 1) % dim == 0 || (position) % dim == 0; } private boolean hasColoredNeighbor() { return left || right || top || bottom; // Хотя бы один сосед сосед окрашен. } boolean isCorrect() { for (int i = 0; i < board.length; i++) { boolean field = board[i]; if (field) { left = isColored(i, '-', 1); right = isColored(i, '+', 1); top = isColored(i, '-', dim); bottom = isColored(i, '+', dim); } if (hasColoredNeighbor()) { return false; } } return true; } }

    }

    • Thank you so much !!! This is exactly what I was looking for! Bravo! - Nikolay

    Implemented on js ...
    The neighbors function returns all neighbors of the cell board. checkField method itself.

     var n = 4 var array = [1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0] console.log(checkField(array, n)); function neighbors(pos, array, n) { tmp = []; if (typeof array[pos - 1] != 'undefined') { tmp.push(array[pos - 1]) } if (typeof array[pos + 1] != 'undefined') { tmp.push(array[pos + 1]) } if (typeof array[pos - n] != 'undefined') { tmp.push(array[pos - n]) } if (typeof array[pos + n] != 'undefined') { tmp.push(array[pos + n]) } return tmp; } function checkField(array, n) { var check = true; for (i = 0; i < array.length && array[i] && check; i++) { var _neighbors = neighbors(i, array, n); for (j = 0; j < _neighbors.length; j++) { if (array[i] == _neighbors[j]) { check = false; } } } return check; }

    • Thank you very much! At the moment, it’s not particularly clear how to implement the neighbors method in java, but Google’s help here - Nikolay
    • Well, this is the most common function, somewhere there should be in the basics ... - sepgg

    minified version on js, advantage: it does not make unnecessary steps, the check stops at the first wrong cell. function arguments (checked array, string length), result true / false.

     var array = [ 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0 ], board = [ true, false, true, false, false, true, false, true, false, false, true, false, false, false, true, false, false, true, true, false, false, false, true, false, false, false, false, false, false, false, true, false, false, true, false, true ], test = [ 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0 ]; function chec(d, c) { return !d.some(function(a, b) { if (!a) return a; a = [b + c, b - c]; b % c && a.push(b - 1); (b + 1) % c && a.push(b + 1); return a.filter(function(a) { return 0 <= a && a < d.length && d[a] }).length }) }; console.log(chec(array, 4));//true console.log(chec(board, 6));//true console.log(chec(test, 4));//false