Автор оригинала: Pankaj Kumar.
Помните разделы судоку из газет? Эта похожая на сетку головоломка, заполненная цифрами.
Судоку-это основанная на логике комбинаторная головоломка с размещением чисел. В классическом судоку цель состоит в том, чтобы заполнить сетку 9×9 цифрами так, чтобы каждый столбец, каждая строка и каждая из девяти подсетей 3×3, составляющих сетку, содержали все цифры от 1 до 9.
Чтобы решить судоку, вам нужно заполнить цифры таким образом, чтобы ваше решение не нарушало ни одно из ограничений. Это может быть сложнее, чем кажется … но не для компьютера.
В этой статье мы узнаем, как написать Java-код, который решает судоку за считанные секунды.
Мировой рекорд по решению судоку составляет 1 минуту 23,93 секунды. Давайте покончим с этим. Не так ли?
Ограничения на количество судоку
Каковы ограничения при решении судоку?
- Число может встречаться только один раз подряд
- Число может встречаться в столбце только один раз
- Число может встречаться в подсетке только один раз.
При решении мы будем использовать эти ограничения для разработки наших вспомогательных функций.
Давайте начнем!
Представление судоку
Проблема судоку возникает из-за того, что некоторые цифры уже заполнены. Цель состоит в том, чтобы выяснить недостающие цифры методом проб и ошибок.
Судоку будет представлять собой 2D-массив для компьютера.
В нашем представлении мы будем обозначать недостающие цифры 0.
Представление судоку выше является:
int[][] arr = {{5, 8, 0, 2, 0, 0, 4, 7, 0},
{0, 2, 0, 0, 0, 0, 0, 3, 0},
{0, 3, 0, 0, 5, 4, 0, 0, 0},
{0, 0, 0, 5, 6, 0, 0, 0, 0},
{0, 0, 7, 0, 3, 0, 9, 0, 0},
{0, 0, 0, 0, 9, 1, 0, 0, 0},
{0, 0, 0, 8, 2, 0, 0, 6, 0},
{0, 7, 0, 0, 0, 0, 0, 8, 0},
{0, 9, 4, 0, 0, 6, 0, 1, 5}};
Цифра 0 помогает нам определить, какое место должен заполнить пользователь.
Решение судоку на Java
Вот что самое интересное! Пристегните ремни и поехали!
Мы будем использовать множество функций для выполнения конкретных задач.
1. Получение неназначенной позиции
Эта функция вернет позиции в нашем судоку, которые еще не назначены. Он возвращает (-1,-1), если неназначенная позиция недоступна. Это будет иметь место, когда наше судоку будет завершено.
public static int[] Unassigned(int[][] arr) {
int[] ra = new int[2]; //returns the position of first unassigned position
ra[0] = -1;
ra[1] = -1;
for (int row = 0; row < arr.length; row++) {
for (int col = 0; col < arr.length; col++) {
if (arr[row][col] == 0) {
ra[0] = row;
ra[1] = col;
return ra;
}
}
}
return ra;
}
Функция возвращает позицию (i,j) в виде массива. Функция просто находит первую позицию с 0 в качестве входа.
2. Можно ли использовать этот номер в этой позиции?
Чтобы ответить на этот вопрос, нам нужно проверить три вещи. Таковы три ограничения задачи судоку.
Три функции, которые проверяют три ограничения, являются:
используется в строке проверяет наличие числа в строке.
медицинский проверяет наличие num в col.
используется в поле проверяет наличие числа в поле. Чтобы указать, в каком поле (начало строки 1,начало строки 1) укажите координаты первой позиции в поле.
public static boolean usedInRow(int[][] grid, int row, int num) {
for (int i = 0; i < grid.length; i++) {
if (grid[row][i] == num) {
return true;
}
}
return false;
}//is it used in that row?
public static boolean usedIncol(int[][] grid, int col, int num) {
for (int i = 0; i < grid.length; i++) {
if (grid[i][col] == num) {
return true;
}
}
return false;
}//is it used in that col?
public static boolean usedInBox(int[][] grid, int row1Start, int col1Start, int num) {
for (int row = 0; row < 3; row++)
for (int col = 0; col < 3; col++)
if (grid[row + row1Start][col + col1Start] == num) {
return true;
}
return false;
}//is it used in that box?
Эти три функции возвращают значение true или false. Функции возвращают значение true, если num отображается в этой конкретной строке, столбце или поле.
3. Сведение воедино трех условий
Функция с именем безопасна вызывает три вышеперечисленные функции. Функция isSafe проверяет одновременное выполнение всех трех условий.
Роль is Safe заключается в том,чтобы определить, безопасно ли помещать цифру ” num ” в позицию (строка, столбец).
Когда все три функции вернут значение false, isSafe вернет значение true. Это связано с тем, что, когда число не используется в той же строке, столбце или поле, что и позиция, только тогда было бы безопасно, чтобы число находилось в этой позиции.
public static boolean isSafe(int[][] grid, int row, int col, int num) {
return (!usedIncol(grid, col, num) && !usedInRow(grid, row, num) && !usedInBox(grid, row - row % 3, col - col % 3, num));
}//is it safe to place that number at that position, might not be correct nut just safe
4. Метод Решения Судоку
С пониманием описанных выше вспомогательных функций мы можем перейти к части фактического решения судоку.
public static boolean sudoku(int[][] grid) {
int[] ra = Unassigned(grid);
if (ra[0] == -1) {
return true;
}
int row = ra[0];
int col = ra[1];
for (int num = 1; num <= 9; num++) {
if (isSafe(grid, row, col, num)) {
grid[row][col] = num;
boolean check = sudoku(grid);
if (check == true) {
return true;
}
grid[row][col] = 0;
}
}
return false;
}
Чтобы решить судоку, мы используем обратный путь. Рекурсивное отслеживание находит решение текущей проблемы.
Первый шаг-получить первую неназначенную позицию. Если нет неназначенной позиции, это означает, что судоку завершено, и мы возвращаем значение true. Тип возвращаемой функции является логическим, так как это поможет в рекурсии (подробнее об этом чуть позже).
В противном случае, если судоку еще не завершено, мы запускаем цикл от одного до девяти и смотрим, какая из цифр поместится в этой позиции. Для достижения этой цели мы вызываем функцию Безопасно. Координаты, заданные для is Safe, соответствуют неназначенной позиции.
В тот момент, когда мы находим цифру, которая подходит для данной позиции, мы вносим изменения в нашу 2D-матрицу. После внесения изменений мы далее вызываем функцию sudoku в сетке. Это позволит найти следующую неназначенную позицию и попытаться заполнить ее.
Проверка переменной будет верна, если судоку завершено и не осталось неназначенной позиции. В этом случае наше судоку решено, и мы можем считать это днем (вернем true).
Однако, если рекурсивный вызов возвращает false, нам нужно вернуться к нашему текущему назначению. Для этого мы устанавливаем сетку[строка][col] как 0. Это делает его неназначенным, и поскольку он находится в цикле for, следующая цифра между [1-9] будет опробована в этой позиции.
Процесс рекурсивных вызовов и возврата продолжается до тех пор, пока мы не придем к решению.
Java Решатель Судоку Полный Код
Мы знаем, что вам нравится код, который вы можете просто скопировать и запустить, чтобы увидеть его самостоятельно. Так что поехали:
public class Main {
public static void main(String[] args) {
// write your code here
int[][] arr = {{5, 8, 0, 2, 0, 0, 4, 7, 0},
{0, 2, 0, 0, 0, 0, 0, 3, 0},
{0, 3, 0, 0, 5, 4, 0, 0, 0},
{0, 0, 0, 5, 6, 0, 0, 0, 0},
{0, 0, 7, 0, 3, 0, 9, 0, 0},
{0, 0, 0, 0, 9, 1, 0, 0, 0},
{0, 0, 0, 8, 2, 0, 0, 6, 0},
{0, 7, 0, 0, 0, 0, 0, 8, 0},
{0, 9, 4, 0, 0, 6, 0, 1, 5}};
print_initial(arr, arr.length);
sudoku(arr);
System.out.println("AFTER SOLVING : ");
print(arr, arr.length);
}
public static boolean sudoku(int[][] grid) {
int[] ra = Unassigned(grid);
if (ra[0] == -1) {
return true;
}
int row = ra[0];
int col = ra[1];
for (int num = 1; num <= 9; num++) {
if (isSafe(grid, row, col, num)) {
grid[row][col] = num;
boolean check = sudoku(grid);
if (check == true) {
return true;
}
grid[row][col] = 0;
}
}
return false;
}
public static int[] Unassigned(int[][] arr) {
int[] ra = new int[2]; //returns the position of first unassigned position
ra[0] = -1;
ra[1] = -1;
for (int row = 0; row < arr.length; row++) {
for (int col = 0; col < arr.length; col++) {
if (arr[row][col] == 0) {
ra[0] = row;
ra[1] = col;
return ra;
}
}
}
return ra;
}//returns the first unassigned position
public static boolean usedInRow(int[][] grid, int row, int num) {
for (int i = 0; i < grid.length; i++) {
if (grid[row][i] == num) {
return true;
}
}
return false;
}//is it used in that row?
public static boolean usedIncol(int[][] grid, int col, int num) {
for (int i = 0; i < grid.length; i++) {
if (grid[i][col] == num) {
return true;
}
}
return false;
}//is it used in that col?
public static boolean usedInBox(int[][] grid, int row1Start, int col1Start, int num) {
for (int row = 0; row < 3; row++)
for (int col = 0; col < 3; col++)
if (grid[row + row1Start][col + col1Start] == num) {
return true;
}
return false;
}//is it used in that box?
public static boolean isSafe(int[][] grid, int row, int col, int num) {//is it safe to place that number at that position, might not be correct nut just safe
return (!usedIncol(grid, col, num) && !usedInRow(grid, row, num) && !usedInBox(grid, row - row % 3, col - col % 3, num));
}
public static void print(int[][] arr, int N) {// prints the sudoku
for (int i = 0; i < N; i++) {
if (i % 3 == 0 && i != 0) {
System.out.println("----------|---------|----------");
}
int count1 = 0;
for (int j = 0; j < N; j++) {
if (j % 3 == 0) {
System.out.print("|");
}
System.out.print(" " + arr[i][j]
+ " ");
}
System.out.println();
}
}
public static void print_initial(int[][] arr, int N) {// prints the sudoku
for (int i = 0; i < N; i++) {
if (i % 3 == 0 && i != 0) {
System.out.println("----------|---------|----------");
}
int count1 = 0;
for (int j = 0; j < N; j++) {
if (j % 3 == 0) {
System.out.print("|");
}
if(arr[i][j]==0){
System.out.print(" " + "-"
+ " ");
}
else {
System.out.print(" " + arr[i][j]
+ " ");
}
}
System.out.println();
}
}
public static boolean isSafe(int row, int col, int[][] board, int N) {
//checking rows
int i, j;
/* Check this row on left side */
for (i = 0; i < row; i++)
if (board[i][col] == 1)
return false;
/* Check upper diagonal on left side */
for (i = row, j = col; i >= 0 && j >= 0; i--, j--)
if (board[i][j] == 1)
return false;
/* Check lower diagonal on left side */
for (i = row, j = col; i >= 0 && j < N; j++, i--)
if (board[i][j] == 1)
return false;
return true;
}
}
Две функции print и print_initial просто распечатывают сетку в виде судоку.
Вывод
Наш решатель судоку превосходит мировой рекорд, установленный людьми, на 1 минуту и 20 секунд. Код использует обратное отслеживание для решения проблемы. Некоторые из известных проблем, для решения которых требуется вернуться,-это проблема n-королев и крыса в лабиринте.