import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Random;

public class Generator {

    public static void main(String[] args) {
        System.out.println(Generator.generate(5));
    }

    public static String generate(int width) {
        int[][] board = new int[width][width];
        for (int[] row: board) {
            Arrays.fill(row, 0);
        }
        fillBoard(board, 0, 0, width);
        ArrayList<ArrayList<Integer>> cages = generateCages(board, width);
        StringBuilder cageConfig = new StringBuilder();

        for(ArrayList<Integer> cage : cages) {
            int target = 0;
            char operator;

            if(cage.size() == 1) {
                target = getValueFromBoard(cage.get(0), board);
                operator = 's';
            } else {
                ArrayList<Integer> numbersInCage = new ArrayList<>();
                for(int x : cage) {
                    numbersInCage.add(getValueFromBoard(x, board));
                }
                int divCheck = checkDivision(numbersInCage);
                int subCheck = checkSubtraction(numbersInCage);
                operator = chooseOperator(divCheck, subCheck);
                if(operator == '÷') {
                    target = divCheck;
                } else if(operator == '-') {
                    target = subCheck;
                } else if(operator == '+') {
                    for(int i : numbersInCage) {
                        target += i;
                    }
                } else if(operator == 'x') {
                    target = 1;
                    for(int i : numbersInCage) {
                        target *= i;
                    }
                }
            }
            if(operator != 's') {
                cageConfig.append(target);
                cageConfig.append(operator);
                cageConfig.append(" ");
            } else {
                cageConfig.append(target).append(" ");
            }
            String cellIDS = cage.toString().substring(1, cage.toString().length() - 1);
            cellIDS = cellIDS.replaceAll("\\s+", "");
            cageConfig.append(cellIDS).append("\n");
        }
        return cageConfig.toString();
    }

    public static char chooseOperator(int divCheck, int subCheck) {
        Random r = new Random();
        int divChance = 4, subChance = 4;
        if(divCheck <= 0) {
            divChance = 0;
        }
        if(subCheck <= 0) {
            subChance = 0;
        }
        subChance += divChance;
        double addChance = ((10.0 - subChance)/2) + subChance;
        int opChoice = r.nextInt(11);
        if(opChoice < divChance) {
            return '÷';
        } else if(opChoice < subChance) {
            return '-';
        } else if(opChoice < addChance) {
            return '+';
        } else {
            return 'x';
        }
    }

    public static int checkSubtraction(ArrayList<Integer> cageValues) {
        Collections.sort(cageValues);
        Collections.reverse(cageValues);
        int total = cageValues.get(0);
        for (int i : cageValues.subList(1, cageValues.size())) {
            total -= i;
        }
        return total;
    }

    public static int checkDivision(ArrayList<Integer> cageValues) {
        Collections.sort(cageValues);
        Collections.reverse(cageValues);
        double total = (double) cageValues.get(0);
        for (int i : cageValues.subList(1, cageValues.size())) {
            total = total / i;
        }
        if ((total == Math.floor(total)) && !Double.isInfinite(total)) {
            return (int) total;
        } else {
            return -1;
        }
    }

    public static int getValueFromBoard(int cellID, int[][] board) {
        cellID -= 1;
        int x = cellID % board.length;
        int y = (cellID - x)/board.length;
        return board[x][y];
    }

    public static ArrayList<ArrayList<Integer>> generateCages(int[][] board, int width) {
        Random r = new Random();
        ArrayList<Integer> untakenCellIDs = new ArrayList<>();
        ArrayList<ArrayList<Integer>> cages = new ArrayList<>();
        for (int i = 1; i < (width * width) + 1; i++) {
            untakenCellIDs.add(i);
        }

        while(!untakenCellIDs.isEmpty()) {
            ArrayList<Integer> tempCage = new ArrayList<>();
            int cellID = getCell(untakenCellIDs);
            int cageSize = getCageSize(untakenCellIDs.size());
            tempCage.add(cellID);
            while(tempCage.size() < cageSize) {
                ArrayList<Integer> neighbours = getNeighbours(board, untakenCellIDs, cellID);
                if(neighbours.size() > 0) {
                    tempCage.add(neighbours.get(0));
                    untakenCellIDs.remove(Integer.valueOf(neighbours.get(0)));
                } else {
                    cellID = tempCage.get(r.nextInt(tempCage.size()));
                    cageSize -= 1;
                }
            }
            cages.add(tempCage);
        }
        return cages;
    }

    public static ArrayList<Integer> getNeighbours(int[][] board, ArrayList<Integer> untakenCells, int cellID) {
        ArrayList<Integer> neighbours = new ArrayList<>();
        for(int cell : untakenCells) {
            if(checkIfCellsAreAdjacent(cell, cellID, board)) {
                neighbours.add(cell);
            }
        }
        return neighbours;
    }

    public static int getCageSize(int untakenCellArraySize) {
        Random r = new Random();
        int chance = r.nextInt(10);
        if(untakenCellArraySize == 1) {
            return 1;
        } else if(untakenCellArraySize == 2 || chance < 4) {
            return 2;
        } else if(untakenCellArraySize == 3 || chance < 7) {
            return 3;
        } else {
            return 4;
        }
    }

    public static int getCell(ArrayList<Integer> untakenCells) {
        Random r = new Random();
        int index = r.nextInt(untakenCells.size());
        int cellID = untakenCells.get(index);
        untakenCells.remove(index);
        return cellID;
    }

    public static boolean checkIfCellsAreAdjacent(int unclaimedCell, int cellInCage, int[][] board) {
        return unclaimedCell == cellInCage + board.length || unclaimedCell == cellInCage - board.length
                || (unclaimedCell == cellInCage + 1 && cellInCage % board.length != 0)
                || (unclaimedCell == cellInCage - 1 && unclaimedCell % board.length != 0);
    }

    public static boolean fillBoard(int[][] board, int x, int y, int width) {
        if(x+1 > width && y+1 == width) {
            return true;
        }
        if(x + 1 > width) {
            x -= width;
            y += 1;
        }
        ArrayList<Integer> values = new ArrayList<>();
        for(int i=1; i<width + 1; i++) {
            values.add(i);
        }
        Collections.shuffle(values);
        for(int value : values) {
            if(!isInRowOrColumn(board, x, y, value, width)) {
                board[x][y] = value;
                if(fillBoard(board, x + 1, y, width)) {
                    return true;
                }
            }
        }
        board[x][y] = 0;
        return false;
    }

    public static boolean isInRowOrColumn(int[][] board, int x, int y, int value, int width) {
        for(int i=0; i<width; i++) {
            if(board[x][i] == value && board[x][i] != 0) {
                return true;
            }
            if(board[i][y] == value && board[i][y] != 0) {
                return true;
            }
        }
        return false;
    }

}