Как заполнить матрицу(игра Судоку) числами в заданном диапазоне, без повтора в строке и столбце?
Класс содержит следующие методы:
private static long counter; // для подсчета созданных игровых досок
private static int[][] data;
public static int[][] getSuccessRandomTable() { // проверка созданного игрового поля, на правильность заполнения
LocalDateTime from = LocalDateTime.now();
boolean isValid;
int[][] data;
do {
data = getRandomTable();
isValid = TableValidator.checkTable(data);
TableOut.printTable(data);
}
while (!isValid);
LocalDateTime to = LocalDateTime.now();
System.out.println("Заняло времени в секундах " + Duration.between(from, to).toSeconds());
return data;
}
private static int[][] getRandomTable() { //создание игрового поля
int[][] data = new int[Constants.TABLE_SIZE][Constants.TABLE_SIZE];
final int min = 1; // Минимальное число для диапазона
final int max = 9; // Максимальное число для диапазона
for (int i = 0; i < data.length; i++) {
for (int j = 0; j < data.length; j++) {
int rnd = rnd(min, max);
data[i][j] = rnd;
}
}
counter++;
System.out.println("Игровых досок создано " + counter);
return data;
}
private static int rnd(int min, int max) { //генерация случайного числа от 1 до 9
max -= min;
return (int) (Math.random() * ++max) + min;
}
Метод getRandomTable() заполняет матрицу 9*9 значениями из диапазона 1-9.
Метод getSuccessRandomTable() проверяет заполненную матрицу на валидность
Пытаюсь понять, как добавить проверку т.е. доработать getRandomTable() так, чтобы он заполнял построчно значениями из диапазона, без повтора по вертикали и горизонтали, т.е. в ячейку [0][0] записывает число от 1-9, пусть будет 3, шагает к следующей ячейке, проверяю линию, тройка есть, значит нужно записать число от 1-9 за исключением 3 и так далее. В дальнейшем потребуется сделать дополнительную проверку на"малые квадраты"(data[0][0]-data[0][2]; data[1][0]-data[1][2]; data[2][0]-data[2][2]), чтобы в них значения так же были только от 1-9 без повтора.
Ответы (4 шт):
Как и в случае генерации одномерного массива со случайным расположением элементов из заданного набора значений без повторений следует сгенерировать матрицу, для которой будет выполняться условие уникальности всех элементов в строках и колонках, а затем перемешать элементы внутри матрицы. Но если для одномерного массива достаточно использовать стандартный метод Collections.shuffle (см. Как заполнить Arraylist случайными цифрами?; как поместить на случайные индексы в массиве конкретные числа), для перемешивания матрицы придётся реализовать методы для перестановки двух строк / колонок / транспонирования матрицы / циклического сдвига строк и т.п..
private static int[][] generateTable() {
int[][] arr = new int[9][9];
Random r = new Random();
for (int i = 0; i < arr.length;) {
int j = r.nextInt(i + 1);
arr[0][i] = arr[0][j];
arr[0][j] = ++i;
}
// случайный сдвиг влево(1) или вправо(8)
int shift = r.nextBoolean() ? 1 : arr.length - 1;
for (int i = 1; i < arr.length; i++) {
for (int j = 0; j < arr.length; j++) {
arr[i][j] = arr[i - 1][(j + shift) % arr.length];
}
}
return arr;
}
private static void transpose(int[][] arr) {
for (int i = 0, n = arr.length; i < n; i++) {
for (int j = i + 1, m = arr[i].length; j < m; j++) {
int tmp = arr[i][j];
arr[i][j] = arr[j][i];
arr[j][i] = tmp;
}
}
}
private static void swapRows(int r1, int r2, int[][] arr) {
int[] tmp = arr[r1];
arr[r1] = arr[r2];
arr[r2] = tmp;
}
private static void swapCols(int c1, int c2, int[][] arr) {
for (int i = 0, n = arr.length; i < n; i++) {
int tmp = arr[i][c1];
arr[i][c1] = arr[i][c2];
arr[i][c2] = tmp;
}
}
private static void rotateRows(int i, int[][] arr) {
Collections.rotate(Arrays.asList(arr), i);
}
Тогда можно сгенерировать матрицу, используя случайное количество различных перестановок от 20 до 100
public static int[][] getRandomTable() {
int[][] arr = generateTable();
Random r = new Random();
int shuffles = 20 + r.nextInt(81);
while (shuffles-- > 0) {
int i = r.nextInt(9);
int j = r.nextInt(9);
if (i == j) {
if (r.nextBoolean())
transpose(arr);
else
rotateRows(r.nextBoolean() ? i : -i, arr);
} else if (r.nextBoolean()) {
swapRows(i, j, arr);
} else{
swapCols(i, j, arr);
}
}
return arr;
}
Или же используя алгоритм Фишера -- Йетса с определённым количеством перестановок по строкам и столбцам:
public static int[][] getRandomTable() {
int[][] arr = generateTable();
Random r = new Random();
for (int i = arr.length; i-- > 0;) {
int j = r.nextInt(i + 1);
swapRows(i, j, arr);
}
for (int i = arr.length; i-- > 0;) {
int j = r.nextInt(i + 1);
swapCols(i, j, arr);
}
if (r.nextBoolean()) {
transpose(arr);
}
return arr;
}
Также могут быть разные вариации.
Примеры сгенерированных матриц:
int t = 5;
while (t-- > 0) {
int[][] arr = getRandomTable();
for (int[] r : arr) {
System.out.println(Arrays.toString(r));
}
System.out.println("----");
}
Результаты для алгоритма Фишера -- Йетса и рандомизированного начального массива
[1, 3, 4, 5, 6, 2, 8, 7, 9]
[2, 7, 9, 6, 1, 4, 3, 5, 8]
[7, 4, 6, 8, 3, 5, 2, 9, 1]
[4, 5, 8, 1, 2, 9, 7, 6, 3]
[9, 6, 3, 2, 4, 8, 5, 1, 7]
[8, 1, 7, 4, 9, 3, 6, 2, 5]
[5, 9, 1, 3, 7, 6, 4, 8, 2]
[3, 2, 5, 9, 8, 7, 1, 4, 6]
[6, 8, 2, 7, 5, 1, 9, 3, 4]
----
[7, 2, 3, 1, 6, 4, 8, 9, 5]
[4, 9, 6, 2, 8, 5, 3, 1, 7]
[2, 6, 4, 3, 5, 9, 7, 8, 1]
[8, 7, 1, 5, 2, 3, 9, 4, 6]
[5, 1, 8, 9, 3, 7, 6, 2, 4]
[1, 3, 7, 8, 4, 2, 5, 6, 9]
[9, 8, 5, 6, 7, 1, 4, 3, 2]
[6, 5, 9, 4, 1, 8, 2, 7, 3]
[3, 4, 2, 7, 9, 6, 1, 5, 8]
Результаты для рандомизированного количества перестановок:
[6, 7, 4, 5, 8, 2, 1, 9, 3]
[5, 2, 8, 9, 1, 3, 7, 4, 6]
[9, 3, 1, 4, 7, 6, 2, 8, 5]
[4, 6, 7, 8, 2, 5, 3, 1, 9]
[2, 8, 5, 3, 9, 1, 4, 6, 7]
[1, 9, 3, 7, 6, 4, 5, 2, 8]
[8, 5, 2, 1, 3, 9, 6, 7, 4]
[3, 1, 9, 6, 4, 7, 8, 5, 2]
[7, 4, 6, 2, 5, 8, 9, 3, 1]
----
[9, 3, 4, 5, 6, 2, 1, 8, 7]
[3, 8, 1, 2, 4, 7, 6, 9, 5]
[5, 2, 3, 1, 9, 6, 8, 7, 4]
[1, 6, 2, 8, 5, 9, 7, 4, 3]
[7, 5, 9, 4, 8, 1, 3, 2, 6]
[2, 7, 8, 6, 3, 4, 9, 5, 1]
[8, 9, 6, 7, 1, 5, 4, 3, 2]
[6, 4, 7, 9, 2, 3, 5, 1, 8]
[4, 1, 5, 3, 7, 8, 2, 6, 9]
Это не настоящая случайная матрица. Но тому, кто решится проверять, будет сложно это доказать.
Алгоритмом Фишера-Йейтса генерируем случайную перестановку длины девять:
516782394
Строим из неё матрицу смещая строки на единицу. В такой матрице числа в строках и столбцах уникальны, но виден порядок:
516782394 167823945 678239451 782394516 823945167 239451678 394516782 945167823 451678239
С помощью алгоритма Фишера-Йейтса случайно перемешиваем строки и столбцы. Всё:
public class Temp {
private static int[][] randomTable(int n) {
int[] p = randomPermutation(n);
int[] pi = randomPermutation(n);
int[] pj = randomPermutation(n);
int[][] table = new int[n][n];
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
table[pi[i]][pj[j]] = 1 + p[(i + j) % n];
}
}
return table;
}
private static int[] randomPermutation(int n) {
int[] p = new int[n];
for (int i = 1; i < n; ++i) {
int j = (int)(Math.random() * (i + 1));
p[i] = p[j];
p[j] = i;
}
return p;
}
public static void main(String... args) {
int[][] table = randomTable(9);
for (int i = 0; i < table.length; ++i) {
for (int j = 0; j < table[i].length; ++j) {
System.out.print(table[i][j]);
}
System.out.println();
}
}
}
Вариант с "истинно" случайной матрицей:
- создать множество свободных индексов для каждого значения от 0 до
n - для каждой строки, построить список доступных индексов, которые могут быть выбраны
- выбрать случайно ячейку c доступным индексом и записать туда текущее значение, удалить индекс из списка свободных
- вероятна ситуация, когда доступных ячеек не окажется, тогда придется очистить матрицу от текущего значения и повторить попытку.
Вариант реализации (без Stream API, с закешированным множеством индексов и оптимизированной очисткой):
public static int[][] getRandomTable() {
return getRandomTable(9);
}
public static int[][] getRandomTable(final int n) {
int[][] arr = new int[n][n];
Random rand = new Random();
// кеш индексов
Set<Integer> indexes = new LinkedHashSet<>();
List<Integer> values = new ArrayList<>();
for (int i = 0; i < n;) {
indexes.add(i);
values.add(++i);
}
// рандомизировать входные значения
Collections.shuffle(values);
int attempt = 1;
for (int k = 0; k < n; k++) {
int v = values.get(k);
Set<Integer> free = new LinkedHashSet<>(indexes);
boolean filled = true;
int row;
for (row = 0; row < n; row++) {
int[] r = arr[row];
List<Integer> available = new ArrayList<>();
for (int c = 0; c < n; c++) {
if (r[c] == 0 && free.contains(c)) {
available.add(c);
}
}
if (available.isEmpty()) {
filled = false;
break;
}
int i = rand.nextInt(available.size());
r[available.get(i)] = v;
free.remove(available.get(i));
}
if (!filled) {
System.out.println("Bad solution, failed in row: " + row);
for (int i = 0; i < row; i++) {
for (int j = 0; j < n; j++) {
if (arr[i][j] == v) {
arr[i][j] = 0;
break;
}
}
}
k--;
attempt++;
} else {
System.out.println("FILLED: " + v + "; attempt=" + attempt);
attempt = 1;
}
}
return arr;
}
Результаты теста out(getRandomTable()); с рандомизированными значениями:
FILLED: 8; attempt=1
FILLED: 6; attempt=1
FILLED: 4; attempt=1
FILLED: 1; attempt=1
FILLED: 3; attempt=1
FILLED: 2; attempt=1
Bad solution, failed in row: 6
Bad solution, failed in row: 6
Bad solution, failed in row: 8
FILLED: 5; attempt=4
FILLED: 7; attempt=1
FILLED: 9; attempt=1
3 5 7 2 8 6 9 1 4
8 2 9 7 6 1 4 5 3
6 7 1 9 5 4 3 8 2
5 9 8 1 7 3 2 4 6
1 6 3 4 9 2 8 7 5
4 8 6 3 2 5 7 9 1
2 3 5 8 4 7 1 6 9
7 4 2 5 1 9 6 3 8
9 1 4 6 3 8 5 2 7
----
Решение порождает случайную судоку-матрицу с (я надеюсь) достаточно равномерным распределением. Это рекурсивный поиск. Из незаполненных полей выбираются поля с наименьшей степенью свободы. Из них случайно выбирается одно поле. Все доступные для этого поля значения перебираются в случайном порядке.
Этот алгоритм может породить любую возможную матрицу. Обычно он работает достаточно быстро. Он всегда строит какую-то матрицу. Но так как это именно случайный поиск гарантий времени работы нет.
random(n) - случайное целое в диапазоне [0, n);
shuffle(a) - случайное перемешивание массива алгоритмом Фишера-Йейтса;
RandomTable(m) - создаёт объект-калькулятор судоку матрицы размера m2×m2 (0 ≤ m ≤ 7);
RandomTable.print() - ищет случайную судоку матрицу и печатает её;
RandomTable.board - доска для поиска. Это линейный массив размера m4. Для m = 3 доска отображается на матрицу так:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 ... 72 73 74 75 76 77 78 79 80
Доска хранит значения как степени двойки:
Значение в матрице Значение на доске <не определено> 0 1 1 << 0 = 1 2 1 << 1 = 2 3 1 << 2 = 4 ... 9 1 << 8 = 256
RandomTable.i, .j, .k - отображают координату на доске (k) в координаты матрицы (i, j);
RandomTable.occupied(k) - возвращает битовую маску, которая хранит все значения недоступные для индекса k на доске;
RandomTable.select() - отыскивает на доске наиболее занятые позиции, случайно выбирает из них одну;
RandomTable.avaiable(k) - для позиции k строит список всех доступных значений и случайно его перемешивает;
RandomTable.search() - рекурсивный поиск позиции на доске. m4 раз повторяет следующую процедуру: случайно отбирает наименее свободную позицию (select), строит для неё случайно перемешанный список доступных значения (available), пробует каждое значение и рекурсивно продолжает поиск. Если позиция найдена, немедленно возвращает true (в этот момент на доске нет нулей). Если - нет, стирает значение, возвращает false чтобы вызов верхнего уровня перешел к следующему значению.
Выбор наименее свободной позиция для продолжения поиска радикально сокращает время перебора. Случайные выборы и перемешивания улучшают равномерность выбора матриц.
В решении осталось место для существенной оптимизации. Неэффективно написаны occupied и select. Я оставил их в таком виде, чтобы не раздувать код.
public class SudokuRandomMatrix {
private static int random(int n) { return (int)(Math.random() * n); }
private static void shuffle(long[] a) {
for (int i = 1; i < a.length; ++i) {
int j = random(i + 1);
long tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
}
private static class RandomTable {
private final int m;
private final int n;
private final long[] board;
public RandomTable(int m) {
this.m = m;
n = m * m;
board = new long[n * n];
}
public void print() {
java.util.Arrays.fill(board, 0);
search(board.length);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
int v = 1 + Long.numberOfTrailingZeros(board[k(i, j)]);
System.out.print(String.format("%3d", v));
}
System.out.println();
}
}
private int i(int k) { return k / n; }
private int j(int k) { return k % n; }
private int k(int i, int j) { return n * i + j; }
private long occupied(int k) {
final int ii = i(k);
final int jj = j(k);
long occupied = 0;
for (int j = 0; j < n; ++j) {
occupied |= board[k(ii, j)];
}
for (int i = 0; i < n; ++i) {
occupied |= board[k(i, jj)];
}
final int i0 = ii - ii % m;
final int j0 = jj - jj % m;
for (int i = i0; i < i0 + m; ++i) {
for (int j = j0; j < j0 + m; ++j) {
occupied |= board[k(i, j)];
}
}
return occupied;
}
private int select() {
int max = 0;
int c = 0;
int[] ks = new int[board.length];
for (int k = 0; k < board.length; ++k) {
if (board[k] == 0) {
int v = Long.bitCount(occupied(k));
if (v > max) {
ks[0] = k;
c = 1;
max = v;
} else if (v == max) {
ks[c] = k;
++c;
}
}
}
return ks[random(c)];
}
private long[] available(int k) {
long occupied = occupied(k);
long[] available = new long[n - Long.bitCount(occupied)];
int c = 0;
for (int b = 0; b < n; ++b) {
long v = 1L << b;
if ((v & occupied) == 0) {
available[c] = v;
++c;
}
}
shuffle(available);
return available;
}
private boolean search(int s) {
if (s == 0) {
return true;
}
final int k = select();
for (long v : available(k)) {
board[k] = v;
if (search(s - 1)) {
return true;
}
}
board[k] = 0;
return false;
}
}
public static void main(String... args) {
new RandomTable(Integer.parseInt(args[0])).print();
}
}
$ javac SudokuRandomMatrix.java $ time java SudokuRandomMatrix 3 1 9 2 6 3 8 7 4 5 8 5 3 7 1 4 2 9 6 4 7 6 2 9 5 1 3 8 9 8 1 3 4 6 5 7 2 5 2 7 1 8 9 4 6 3 6 3 4 5 2 7 8 1 9 7 6 9 8 5 1 3 2 4 2 1 8 4 6 3 9 5 7 3 4 5 9 7 2 6 8 1 real 0m0.065s user 0m0.072s sys 0m0.004s $ time java SudokuRandomMatrix 4 7 15 10 14 12 1 8 2 11 5 4 9 16 13 3 6 8 13 5 12 11 4 14 6 15 3 7 16 9 2 1 10 2 3 16 1 9 15 5 10 6 13 12 14 8 7 4 11 4 9 11 6 7 13 16 3 2 1 8 10 12 15 14 5 3 7 14 16 10 5 12 4 13 6 9 8 2 1 11 15 11 5 8 13 16 2 1 15 14 12 10 3 4 6 7 9 10 1 12 9 8 6 11 13 4 2 15 7 14 5 16 3 15 6 2 4 3 7 9 14 1 11 16 5 10 8 12 13 9 16 15 2 6 12 4 5 7 10 13 1 3 11 8 14 5 14 13 10 2 3 7 16 8 9 6 11 1 4 15 12 6 8 3 7 1 10 15 11 12 16 14 4 5 9 13 2 12 4 1 11 14 9 13 8 3 15 5 2 6 16 10 7 13 12 6 5 4 11 3 9 16 14 1 15 7 10 2 8 16 10 4 8 15 14 2 12 5 7 11 6 13 3 9 1 14 11 7 3 5 16 10 1 9 8 2 13 15 12 6 4 1 2 9 15 13 8 6 7 10 4 3 12 11 14 5 16 real 0m0.080s user 0m0.096s sys 0m0.016s $ time java SudokuRandomMatrix 5 20 4 24 12 14 17 11 21 6 23 19 1 10 8 3 7 15 9 18 22 5 25 13 2 16 9 15 22 25 6 1 7 8 5 2 20 23 24 12 21 11 13 16 19 3 17 10 4 14 18 17 10 16 8 5 9 18 13 20 3 11 15 22 14 4 23 6 21 25 2 12 7 24 19 1 18 2 11 1 23 19 22 12 16 24 7 25 13 5 6 8 17 4 14 10 3 15 20 9 21 21 13 3 19 7 14 4 15 25 10 2 17 9 16 18 24 20 12 1 5 22 11 6 8 23 8 21 6 5 4 23 24 25 3 15 14 12 7 10 20 2 18 22 11 9 16 19 17 1 13 7 17 19 24 18 20 16 2 21 22 23 11 6 15 25 4 8 13 3 1 9 14 10 12 5 14 12 23 11 1 7 13 19 10 17 18 4 5 21 9 15 24 25 16 6 8 20 22 3 2 13 22 15 10 25 8 12 9 14 18 24 2 16 3 1 19 7 5 17 20 23 21 11 4 6 2 3 20 9 16 6 1 4 11 5 17 8 19 13 22 10 21 14 23 12 25 18 7 15 24 24 5 25 2 13 18 14 6 22 9 12 10 20 23 15 16 1 11 8 21 19 17 3 7 4 19 8 7 6 20 10 21 11 1 25 5 3 17 24 16 18 23 2 9 4 14 12 15 13 22 22 18 10 16 15 3 2 23 19 4 13 21 14 25 8 17 12 24 6 7 20 1 5 11 9 3 14 17 4 9 24 20 16 12 7 6 19 11 1 2 13 5 10 22 15 18 8 23 21 25 12 1 21 23 11 15 17 5 8 13 9 22 4 18 7 25 14 3 20 19 24 16 2 6 10 23 11 8 3 17 12 15 18 9 20 25 6 2 4 14 21 22 1 10 24 13 5 19 16 7 15 19 4 20 24 21 25 14 2 8 16 7 1 22 5 6 3 17 13 11 10 9 18 23 12 25 6 14 7 21 13 19 10 24 1 15 9 18 17 12 5 16 20 2 23 4 3 8 22 11 5 9 12 18 10 16 23 22 17 6 8 13 3 11 19 14 4 7 15 25 1 2 21 24 20 1 16 2 13 22 4 5 3 7 11 10 24 21 20 23 9 19 18 12 8 15 6 25 17 14 6 25 18 14 8 11 9 20 4 12 1 5 23 7 13 3 2 15 24 17 21 22 16 10 19 11 20 1 21 3 22 8 24 13 14 4 16 25 2 17 12 10 19 7 18 6 23 9 5 15 4 7 13 17 12 2 6 1 15 19 21 18 8 9 10 22 25 23 5 16 11 24 14 20 3 10 24 5 15 19 25 3 7 23 16 22 14 12 6 11 20 9 8 21 13 2 4 1 18 17 16 23 9 22 2 5 10 17 18 21 3 20 15 19 24 1 11 6 4 14 7 13 12 25 8 real 0m7.116s user 0m7.132s sys 0m0.072s $ time java SudokuRandomMatrix 6 25 28 11 4 22 34 12 5 9 36 30 3 33 14 31 13 2 32 19 6 26 8 10 21 15 16 24 17 29 7 18 23 27 20 1 35 7 32 16 8 3 9 20 19 28 10 6 31 22 1 11 18 35 21 23 15 29 33 12 34 27 26 25 36 5 30 13 4 17 14 2 24 13 29 10 21 2 19 16 4 8 26 14 7 6 34 17 15 27 9 18 35 30 20 24 22 3 23 1 31 33 28 25 36 5 32 11 12 20 6 36 12 14 27 15 34 24 21 1 17 23 28 26 25 10 19 9 32 2 5 13 3 8 35 4 18 11 22 30 7 33 31 29 16 5 26 1 17 35 24 11 25 32 23 18 33 30 20 4 3 12 29 7 16 27 36 31 28 2 21 13 6 14 19 22 10 8 9 15 34 23 30 18 31 15 33 2 27 35 13 22 29 7 24 8 5 36 16 17 4 25 14 1 11 20 32 34 9 12 10 28 21 6 3 19 26 12 23 33 19 10 3 1 24 5 27 35 8 9 36 16 32 34 11 26 13 14 28 22 7 6 25 18 21 15 4 29 2 20 17 30 31 35 24 22 13 27 6 32 33 31 12 23 4 18 17 1 28 30 20 10 9 34 2 21 8 36 5 26 14 7 29 19 16 11 25 3 15 26 18 14 1 34 17 28 30 11 25 29 16 2 27 10 35 21 15 33 12 19 4 36 5 22 3 20 32 31 24 6 8 9 13 23 7 21 11 15 25 5 29 36 17 22 20 13 2 24 8 6 12 7 31 27 23 3 35 30 32 33 9 19 10 16 1 14 34 18 28 26 4 32 2 30 9 20 31 19 7 26 14 15 18 3 22 25 33 5 4 11 17 6 1 16 29 12 34 8 28 23 13 21 24 10 36 35 27 36 8 7 16 28 4 6 10 34 9 3 21 19 29 13 14 23 26 15 24 20 31 18 25 11 30 35 2 17 27 1 12 22 5 32 33 10 21 3 34 33 36 35 13 7 22 19 9 5 16 14 4 26 23 31 29 11 24 6 18 1 27 32 30 2 17 15 28 25 8 12 20 22 27 5 28 7 25 31 16 1 6 24 26 20 33 18 21 15 2 30 3 9 12 17 4 23 8 14 29 35 11 34 13 36 19 10 32 31 35 12 11 17 26 10 23 21 2 25 28 34 19 9 8 1 22 32 20 16 13 14 33 7 24 15 4 3 36 5 29 30 27 6 18 1 4 6 15 24 14 34 20 29 8 27 12 36 32 7 30 17 35 21 28 5 22 26 10 18 13 31 25 19 16 3 33 23 11 9 2 29 20 2 30 32 8 18 14 4 33 11 15 31 13 28 24 3 25 35 36 23 27 34 19 10 12 5 22 9 6 7 17 21 26 16 1 19 16 13 18 9 23 30 32 3 17 36 5 11 12 27 29 6 10 1 7 8 25 15 2 21 28 33 20 34 26 35 22 31 24 4 14 16 19 26 24 36 20 33 1 2 5 10 35 21 25 23 9 32 6 14 18 12 7 29 31 4 22 27 15 8 3 17 11 34 30 28 13 3 1 35 27 13 21 25 26 14 32 31 36 8 4 33 34 11 12 20 19 22 17 28 15 9 29 30 24 10 23 2 6 16 18 7 5 34 12 9 2 25 11 29 8 16 4 21 6 14 7 36 22 19 17 3 27 32 26 35 30 13 33 28 5 20 18 23 31 15 1 24 10 30 15 31 22 6 5 7 28 20 34 17 13 10 3 2 26 29 18 24 8 36 23 4 1 16 14 11 19 21 35 33 27 32 12 25 9 14 33 28 23 4 10 24 18 19 11 12 22 15 30 35 27 31 13 6 5 21 34 9 16 32 7 17 1 25 2 36 3 26 29 20 8 18 17 29 7 8 32 27 3 23 15 9 30 16 5 24 20 28 1 25 2 33 10 11 13 26 31 6 12 36 34 4 35 14 22 21 19 24 3 4 5 12 35 14 6 10 30 34 20 32 11 15 31 22 8 16 21 18 19 25 26 17 36 23 7 28 33 27 9 1 2 13 29 11 22 19 10 23 15 26 35 25 18 28 32 1 21 29 7 9 33 13 31 17 3 5 36 34 20 2 27 4 12 8 30 24 16 14 6 28 36 21 26 1 7 9 2 13 3 33 27 12 6 20 17 25 30 22 34 4 11 8 14 19 18 29 16 24 32 10 5 35 15 31 23 9 14 25 6 18 13 21 29 17 16 7 23 28 26 19 36 24 27 2 1 35 15 33 20 31 10 3 8 30 5 11 32 12 4 34 22 27 34 17 33 29 2 8 31 12 1 4 11 35 10 3 16 18 5 28 30 24 6 32 23 14 15 22 26 13 9 20 19 7 21 36 25 8 31 32 20 16 30 22 15 36 24 5 19 4 23 34 2 13 14 29 10 7 9 27 12 35 6 21 11 1 25 26 18 3 33 17 28 2 13 34 35 31 28 4 21 27 29 16 14 25 9 5 11 20 24 12 26 1 18 23 6 30 17 7 3 22 8 32 15 19 10 33 36 17 5 24 14 19 18 3 22 15 35 26 10 27 2 12 6 33 28 34 11 13 16 20 9 29 1 36 23 32 21 31 25 4 7 8 30 15 9 27 36 21 22 5 11 6 28 32 1 13 35 30 19 14 7 8 33 10 29 3 24 25 4 12 34 26 31 16 20 2 23 18 17 33 25 20 29 11 16 17 9 30 19 8 24 26 18 21 23 4 34 36 14 31 32 7 27 5 2 10 13 6 15 12 1 28 35 22 3 6 7 23 3 30 1 13 12 18 31 20 25 17 15 32 10 8 36 4 22 28 21 2 35 24 19 16 33 27 14 9 26 29 34 5 11 4 10 8 32 26 12 23 36 33 7 2 34 29 31 22 1 16 3 5 25 15 30 19 17 28 11 9 35 18 20 24 14 13 6 27 21 real 20m4.585s user 20m2.584s sys 0m0.988s