Судоку | Откат-7

01.01.2020Backtracking, Матрицы

Учитывая частично заполненный двумерный массив 9 × 9 «сетка [9] [9]», цель состоит в том, чтобы назначить цифры (от 1 до 9) пустым ячейкам, чтобы каждая строка, столбец и подсетка размера 3 × 3 содержали ровно один экземпляр цифр от 1 до 9.

Наивный Алгоритм
Наивный алгоритм состоит в том, чтобы генерировать все возможные конфигурации чисел от 1 до 9, чтобы заполнить пустые ячейки. Попробуйте каждую конфигурацию одну за другой, пока не найдете правильную конфигурацию.

Алгоритм возврата
Как и все другие проблемы с возвратом , мы можем решать судоку по одному, присваивая номера пустым ячейкам. Прежде чем присваивать номер, мы проверяем, можно ли его присваивать. Мы в основном проверяем, что одно и то же число не присутствует в текущей строке, текущем столбце и текущей подсети 3X3. После проверки безопасности мы присваиваем номер и рекурсивно проверяем, приводит ли это назначение к решению или нет. Если назначение не приводит к решению, то мы пробуем следующий номер для текущей пустой ячейки. И если ни одно из чисел (от 1 до 9) не приводит к решению, мы возвращаем false.

  Find row, col of an unassigned cell
  If there is none, return true
  For digits from 1 to 9
    a) If there is no conflict for digit at row, col
        assign digit to row, col and recursively try fill in rest of grid
    b) If recursion successful, return true
    c) Else, remove digit and try another
  If all digits have been tried and nothing worked, return false

Ниже приведена реализация проблемы судоку. Он печатает полностью заполненную сетку в качестве вывода.

C ++

// Программа возврата в C ++ для решения проблемы судоку
#include <bits/stdc++.h>

using namespace std;

// UNASSIGNED используется для пустых ячеек в сетке судоку
#define UNASSIGNED 0

// N используется для размера сетки Судоку.
// Размер будет NxN
#define N 9

// Эта функция находит запись в сетке
// это все еще не назначено

bool FindUnassignedLocation(int grid[N][N],

int &row, int &col);

// Проверяет, будет ли это законно
// присвоить номер данной строке, столбец

bool isSafe(int grid[N][N], int row,

int col, int num);

/ * Принимает частично заполненную сетку и пытается
назначить значения для всех неназначенных мест в
такой способ удовлетворить требования для
Решение судоку (не дублирование строк,
колонны и ящики) *

bool SolveSudoku(int grid[N][N])

{

int row, col;

// Если нет назначенного местоположения,

// мы сделали

if (!FindUnassignedLocation(grid, row, col))

return true; // успех!

// рассмотрим цифры от 1 до 9

for (int num = 1; num <= 9; num++)

{

// если выглядит многообещающе

if (isSafe(grid, row, col, num))

{

// сделать предварительное назначение

grid[row][col] = num;

// вернемся, если получится, ура!

if (SolveSudoku(grid))

return true;

// неудача, разобрать и попробовать еще раз

grid[row][col] = UNASSIGNED;

}

return false; // это вызывает возврат

}

/ * Поиск в сетке, чтобы найти запись, которая
все еще не назначен Если найдено, ссылка
Параметр row, col будет указывать местоположение
это не назначено, и истина возвращается.
Если не осталось ни одной неназначенной записи, возвращается false. * /

bool FindUnassignedLocation(int grid[N][N],

int &row, int &col)

{

for (row = 0; row < N; row++)

for (col = 0; col < N; col++)

if (grid[row][col] == UNASSIGNED)

return true;

return false;

}

/ * Возвращает логическое значение, которое указывает, является ли
назначенная запись в указанной строке соответствует
данный номер. * /

bool UsedInRow(int grid[N][N], int row, int num)

{

for (int col = 0; col < N; col++)

if (grid[row][col] == num)

return true;

return false;

}

/ * Возвращает логическое значение, которое указывает, является ли
назначенная запись в указанном столбце
соответствует заданному номеру. * /

bool UsedInCol(int grid[N][N], int col, int num)

{

for (int row = 0; row < N; row++)

if (grid[row][col] == num)

return true;

return false;

}

/ * Возвращает логическое значение, которое указывает, является ли
назначенная запись в указанном окне 3x3
соответствует заданному номеру. * /

bool UsedInBox(int grid[N][N], int boxStartRow,

int boxStartCol, int num)

{

for (int row = 0; row < 3; row++)

for (int col = 0; col < 3; col++)

if (grid[row + boxStartRow]

[col + boxStartCol] == num)

return true;

return false;

}

/ * Возвращает логическое значение, которое указывает, является ли
будет законным присвоить число данным
строка, col местоположение. * /

bool isSafe(int grid[N][N], int row,

int col, int num)

{

/ * Проверьте, не находится ли num в

текущая строка, текущий столбец и текущий блок 3х3 * /

return !UsedInRow(grid, row, num) &&

!UsedInCol(grid, col, num) &&

!UsedInBox(grid, row - row % 3 ,

col - col % 3, num) &&

grid[row][col] == UNASSIGNED;

}

/ * Утилита для печати сетки * /

void printGrid(int grid[N][N])

{

for (int row = 0; row < N; row++)

{

for (int col = 0; col < N; col++)

cout << grid[row][col] << " ";

cout << endl;

}

// Код драйвера

int main()

{

// 0 означает неназначенные ячейки

int grid[N][N] = {{3, 0, 6, 5, 0, 8, 4, 0, 0},

{5, 2, 0, 0, 0, 0, 0, 0, 0},

{0, 8, 7, 0, 0, 0, 0, 3, 1},

{0, 0, 3, 0, 1, 0, 0, 8, 0},

{9, 0, 0, 8, 6, 3, 0, 0, 5},

{0, 5, 0, 0, 9, 0, 6, 0, 0},

{1, 3, 0, 0, 0, 0, 2, 5, 0},

{0, 0, 0, 0, 0, 0, 0, 7, 4},

{0, 0, 5, 2, 0, 6, 3, 0, 0}};

if (SolveSudoku(grid) == true)

printGrid(grid);

else

cout << "No solution exists";

return 0;

}

// Это код, предоставленный rathbhupendra

// Программа Backtracking на C для решения проблемы судоку
#include <stdio.h>

// UNASSIGNED используется для пустых ячеек в сетке судоку
#define UNASSIGNED 0

// N используется для размера сетки Судоку. Размер будет NxN
#define N 9

// Эта функция находит запись в сетке, которая еще не назначена

bool FindUnassignedLocation(int grid[N][N], int &row, int &col);

// Проверяет, будет ли разрешено присваивать num данной строке, col

bool isSafe(int grid[N][N], int row, int col, int num);

/ * Принимает частично заполненную сетку и пытается присвоить значения

все неназначенные места таким образом, чтобы соответствовать требованиям

для решения Судоку (не дублирование строк, столбцов и блоков) * /

bool SolveSudoku(int grid[N][N])

{

int row, col;

// Если нет неназначенного местоположения, мы закончили

if (!FindUnassignedLocation(grid, row, col))

return true; // успех!

// рассмотрим цифры от 1 до 9

for (int num = 1; num <= 9; num++)

{

// если выглядит многообещающе

if (isSafe(grid, row, col, num))

{

// сделать предварительное назначение

grid[row][col] = num;

// вернемся, если получится, ура!

if (SolveSudoku(grid))

return true;

// неудача, разобрать и попробовать еще раз

grid[row][col] = UNASSIGNED;

}

return false; // это вызывает возврат

}

/ * Выполняет поиск в сетке, чтобы найти запись, которая все еще не назначена. Если

найдено, ссылка на строку параметров, col будет указывать местоположение

это не назначено, и истина возвращается. Если нет неназначенных записей

остаются, ложь возвращается. * /

bool FindUnassignedLocation(int grid[N][N], int &row, int &col)

{

for (row = 0; row < N; row++)

for (col = 0; col < N; col++)

if (grid[row][col] == UNASSIGNED)

return true;

return false;

}

/ * Возвращает логическое значение, которое указывает, назначена ли запись

в указанной строке совпадает с заданным номером. * /

bool UsedInRow(int grid[N][N], int row, int num)

{

for (int col = 0; col < N; col++)

if (grid[row][col] == num)

return true;

return false;

}

/ * Возвращает логическое значение, которое указывает, назначена ли запись

в указанном столбце соответствует заданный номер. * /

bool UsedInCol(int grid[N][N], int col, int num)

{

for (int row = 0; row < N; row++)

if (grid[row][col] == num)

return true;

return false;

}

/ * Возвращает логическое значение, которое указывает, назначена ли запись

в пределах указанного поля 3х3 соответствует заданному номеру. * /

bool UsedInBox(int grid[N][N], int boxStartRow, int boxStartCol, int num)

{

for (int row = 0; row < 3; row++)

for (int col = 0; col < 3; col++)

if (grid[row+boxStartRow][col+boxStartCol] == num)

return true;

return false;

}

/ * Возвращает логическое значение, которое указывает, будет ли разрешено присваивать

num к данному ряду, col col. * /

bool isSafe(int grid[N][N], int row, int col, int num)

{

/ * Проверить, не находится ли num в текущей строке,

текущий столбец и текущий ящик 3х3 * /

return !UsedInRow(grid, row, num) &&

!UsedInCol(grid, col, num) &&

!UsedInBox(grid, row - row%3 , col - col%3, num)&&

grid[row][col]==UNASSIGNED;

}

/ * Утилита для печати сетки * /

void printGrid(int grid[N][N])

{

for (int row = 0; row < N; row++)

{

for (int col = 0; col < N; col++)

printf("%2d", grid[row][col]);

printf("\n");

}

/ * Программа драйвера для проверки вышеуказанных функций * /

int main()

{

// 0 означает неназначенные ячейки

int grid[N][N] = {{3, 0, 6, 5, 0, 8, 4, 0, 0},

{5, 2, 0, 0, 0, 0, 0, 0, 0},

{0, 8, 7, 0, 0, 0, 0, 3, 1},

{0, 0, 3, 0, 1, 0, 0, 8, 0},

{9, 0, 0, 8, 6, 3, 0, 0, 5},

{0, 5, 0, 0, 9, 0, 6, 0, 0},

{1, 3, 0, 0, 0, 0, 2, 5, 0},

{0, 0, 0, 0, 0, 0, 0, 7, 4},

{0, 0, 5, 2, 0, 6, 3, 0, 0}};

if (SolveSudoku(grid) == true)

printGrid(grid);

else

printf("No solution exists");

return 0;

}

Джава

/ * Программа возврата в
Java для решения проблемы судоку * /

class GFG

{

public static boolean isSafe(int[][] board,

int row, int col,

int num)

{

// строка имеет уникальный (row-clash)

for (int d = 0; d < board.length; d++)

{

// если число мы пытаемся

// место уже присутствует в

// эта строка, возвращаем false;

if (board[row][d] == num)

{

return false;

}

// столбец имеет уникальные номера (column-clash)

for (int r = 0; r < board.length; r++)

{

// если число мы пытаемся

// место уже присутствует в

// этот столбец, return false;

if (board[r][col] == num)

{

return false;

}

// соответствующий квадрат имеет

// уникальный номер (box-clash)

int sqrt = (int) Math.sqrt(board.length);

int boxRowStart = row - row % sqrt;

int boxColStart = col - col % sqrt;

for (int r = boxRowStart;

r < boxRowStart + sqrt; r++)

{

for (int d = boxColStart;

d < boxColStart + sqrt; d++)

{

if (board[r][d] == num)

{

return false;

}

// если нет конфликта, это безопасно

return true;

}

public static boolean solveSudoku(int[][] board, int n)

{

int row = -1;

int col = -1;

boolean isEmpty = true;

for (int i = 0; i < n; i++)

{

for (int j = 0; j < n; j++)

{

if (board[i][j] == 0)

{

row = i;

col = j;

// осталось еще немного

// пропущенные значения в судоку

isEmpty = false;

break;

}

if (!isEmpty)

{

break;

}

// пустого места не осталось

if (isEmpty)

{

return true;

}

// еще для возврата каждой строки

for (int num = 1; num <= n; num++)

{

if (isSafe(board, row, col, num))

{

board[row][col] = num;

if (solveSudoku(board, n))

{

// print (доска, n);

return true;

}

else

{

board[row][col] = 0; // замени это

}

return false;

}

public static void print(int[][] board, int N)

{

// мы получили ответ, просто распечатайте его

for (int r = 0; r < N; r++)

{

for (int d = 0; d < N; d++)

{

System.out.print(board[r][d]);

System.out.print(" ");

}

System.out.print("\n");

if ((r + 1) % (int) Math.sqrt(N) == 0)

{

System.out.print("");

}

// Код драйвера

public static void main(String args[])

{

int[][] board = new int[][]

{

{3, 0, 6, 5, 0, 8, 4, 0, 0},

{5, 2, 0, 0, 0, 0, 0, 0, 0},

{0, 8, 7, 0, 0, 0, 0, 3, 1},

{0, 0, 3, 0, 1, 0, 0, 8, 0},

{9, 0, 0, 8, 6, 3, 0, 0, 5},

{0, 5, 0, 0, 9, 0, 6, 0, 0},

{1, 3, 0, 0, 0, 0, 2, 5, 0},

{0, 0, 0, 0, 0, 0, 0, 7, 4},

{0, 0, 5, 2, 0, 6, 3, 0, 0}

};

int N = board.length;

if (solveSudoku(board, N))

{

print(board, N); // распечатать решение

}

else

{

System.out.println("No solution");

}

}
}

// Этот код добавлен
// от MohanDas

питон

# Программа возврата в Python для решения проблемы судоку

# Сервисная функция для печати сетки

def print_grid(arr):

for i in range(9):

for j in range(9):

print arr[i][j],

print ('n')

# Функция для поиска записи в сетке, которая до сих пор не используется
# Выполняет поиск в сетке, чтобы найти запись, которая все еще не назначена. Если
# найдено, в строке параметров ссылки, col будет указано местоположение
# это не назначено, и true возвращается. Если нет неназначенных записей
# остается, ложь возвращается.
# 'l' - это переменная списка, которая была передана из функции solve_sudoku
# отслеживать приращение строк и столбцов

def find_empty_location(arr,l):

for row in range(9):

for col in range(9):

if(arr[row][col]==0):

l[0]=row

l[1]=col

return True

return False

# Возвращает логическое значение, которое указывает, назначена ли какая-либо запись
# в указанной строке соответствует указанному номеру.

def used_in_row(arr,row,num):

for i in range(9):

if(arr[row][i] == num):

return True

return False

# Возвращает логическое значение, которое указывает, назначена ли какая-либо запись
# в указанном столбце соответствует указанному номеру.

def used_in_col(arr,col,num):

for i in range(9):

if(arr[i][col] == num):

return True

return False

# Возвращает логическое значение, которое указывает, назначена ли какая-либо запись
# в пределах указанного поля 3х3 соответствует заданному номеру

def used_in_box(arr,row,col,num):

for i in range(3):

for j in range(3):

if(arr[i+row][j+col] == num):

return True

return False

# Проверяет, будет ли разрешено присваивать num данной строке, col
# Возвращает логическое значение, которое указывает, будет ли разрешено присваивать
# номер данной строки, расположение столбца.

def check_location_is_safe(arr,row,col,num):

# Проверьте, не находится ли num в текущей строке,

# текущий столбец и текущий блок 3х3

return not used_in_row(arr,row,num) and not used_in_col(arr,col,num) and not used_in_box(arr,row - row%3,col - col%3,num)

# Принимает частично заполненную сетку и пытается присвоить значения
# все неназначенные места таким образом, чтобы соответствовать требованиям
# для решения Судоку (не дублирование строк, столбцов и блоков)

def solve_sudoku(arr):

# 'l' - это переменная списка, которая хранит записи о строках и столбцах в функции find_empty_location

l=[0,0]

# Если нет назначенного местоположения, мы сделали

if(not find_empty_location(arr,l)):

return True

# Присвоение значений списка строкам и столбцам, которые мы получили из вышеуказанной функции

row=l[0]

col=l[1]

# считать цифры от 1 до 9

for num in range(1,10):

# если выглядит многообещающе

if(check_location_is_safe(arr,row,col,num)):

# сделать предварительное назначение

arr[row][col]=num

# вернись, если удачи, да!

if(solve_sudoku(arr)):

return True

# неудача, разобрать и попробуйте снова

arr[row][col] = 0

# это вызывает возврат

return False

# Основная функция драйвера для проверки вышеуказанных функций

if __name__=="__main__":

# создание 2D массива для сетки

grid=[[0 for x in range(9)]for y in range(9)]

# присвоение значений сетке

grid=[[3,0,6,5,0,8,4,0,0],

[5,2,0,0,0,0,0,0,0],

[0,8,7,0,0,0,0,3,1],

[0,0,3,0,1,0,0,8,0],

[9,0,0,8,6,3,0,0,5],

[0,5,0,0,9,0,6,0,0],

[1,3,0,0,0,0,2,5,0],

[0,0,0,0,0,0,0,7,4],

[0,0,5,2,0,6,3,0,0]]

# в случае успеха распечатать сетку

if(solve_sudoku(grid)):

print_grid(grid)

else:

print "No solution exists"

# Приведенный выше код был предоставлен Харшитом Сидхвой.

C #

/ * Программа возврата в
C # для решения проблемы судоку * /

using System;

class GFG

{

public static bool isSafe(int[,] board,

int row, int col,

int num)

{

// строка имеет уникальный (row-clash)

for (int d = 0; d < board.GetLength(0); d++)

{

// если число мы пытаемся

// место уже присутствует в

// эта строка, возвращаем false;

if (board[row, d] == num)

{

return false;

}

// столбец имеет уникальные номера (column-clash)

for (int r = 0; r < board.GetLength(0); r++)

{

// если число мы пытаемся

// место уже присутствует в

// этот столбец, return false;

if (board[r, col] == num)

{

return false;

}

// соответствующий квадрат имеет

// уникальный номер (box-clash)

int sqrt = (int) Math.Sqrt(board.GetLength(0));

int boxRowStart = row - row % sqrt;

int boxColStart = col - col % sqrt;

for (int r = boxRowStart;

r < boxRowStart + sqrt; r++)

{

for (int d = boxColStart;

d < boxColStart + sqrt; d++)

{

if (board[r,d] == num)

{

return false;

}

// если нет конфликта, это безопасно

return true;

}

public static bool solveSudoku(int[,] board, int n)

{

int row = -1;

int col = -1;

bool isEmpty = true;

for (int i = 0; i < n; i++)

{

for (int j = 0; j < n; j++)

{

if (board[i, j] == 0)

{

row = i;

col = j;

// осталось еще немного

// пропущенные значения в судоку

isEmpty = false;

break;

}

if (!isEmpty)

{

break;

}

// пустого места не осталось

if (isEmpty)

{

return true;

}

// еще для возврата каждой строки

for (int num = 1; num <= n; num++)

{

if (isSafe(board, row, col, num))

{

board[row, col] = num;

if (solveSudoku(board, n))

{

// print (доска, n);

return true;

}

else

{

board[row, col] = 0; // замени это

}

return false;

}

public static void print(int[,] board, int N)

{

// мы получили ответ, просто распечатайте его

for (int r = 0; r < N; r++)

{

for (int d = 0; d < N; d++)

{

Console.Write(board[r,d]);

Console.Write(" ");

}

Console.Write("\n");

if ((r + 1) % (int) Math.Sqrt(N) == 0)

{

Console.Write("");

}

// Код драйвера

public static void Main(String []args)

{

int[,] board = new int[,]

{

{3, 0, 6, 5, 0, 8, 4, 0, 0},

{5, 2, 0, 0, 0, 0, 0, 0, 0},

{0, 8, 7, 0, 0, 0, 0, 3, 1},

{0, 0, 3, 0, 1, 0, 0, 8, 0},

{9, 0, 0, 8, 6, 3, 0, 0, 5},

{0, 5, 0, 0, 9, 0, 6, 0, 0},

{1, 3, 0, 0, 0, 0, 2, 5, 0},

{0, 0, 0, 0, 0, 0, 0, 7, 4},

{0, 0, 5, 2, 0, 6, 3, 0, 0}

};

int N = board.GetLength(0);

if (solveSudoku(board, N))

{

print(board, N); // распечатать решение

}

else

{

Console.Write("No solution");

}

}
}

// Этот код предоставлен 29AjayKumar

Выход:

  3 1 6 5 7 8 4 9 2
  5 2 9 1 3 4 7 6 8
  4 8 7 6 2 9 5 3 1
  2 6 3 4 1 5 9 8 7
  9 7 4 8 6 3 1 2 5
  8 5 1 7 9 2 6 4 3
  1 3 8 9 4 7 2 5 6
  6 9 2 3 5 1 8 7 4
  7 4 5 2 8 6 3 1 9

Ссылки:
http://see.stanford.edu/materials/icspacs106b/H19-RecBacktrackExamples.pdf

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Судоку | Откат-7

0.00 (0%) 0 votes