Dadas dos arrays sudoku[][] y region[][] de tamaño N * N , la tarea es completar el Sudoku dado sobre la base de las regiones irregulares dadas. Si no es posible completar la array sudoku[][] , imprima -1 . Las siguientes son las definiciones de las arrays:
Sudoku Matrix (sudoku[][]): Es una array N×N que contiene los elementos de 0 a N , donde 0 denota la celda vacía que debe llenarse para resolver el Sudoku.
Reglas para resolver el Sudoku:
- Cada fila y columna debe tener números únicos del 1 al N.
- Cada región debe tener números únicos del 1 al N .
Array de Región (región[][]): Es una array N×N que contiene caracteres que denotan la región del Sudoku. Los mismos caracteres en la array denotan una región de Sudoku.
Ejemplos:
Entrada: sudoku[][] = {
{0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 4, 0, 0},
{3, 0, 0, 6, 0, 0, 0},
{0, 0, 0, 0, 6, 0, 1},
{5, 0, 0, 0, 0, 0, 3},
{0, 0, 1, 0, 0, 0, 2},
{2, 0, 0, 0, 0, 0, 5} }
región[][] = {
{r, r, r, b, b, b, b},
{g, r, r , r, r, b, o},
{g, g, g, g, b, b, o},
{p, p, g, o, o, o, o},
{p, p, g, d , o, l, l},
{p, p, p, d, l, l, l},
{d, d, d, d, d, l, l} }
Salida:
7 1 3 4 5 2 6
1 6 5 2 4 3 7
3 5 2 6 1 7 4
4 2 7 3 6 5 1
5 7 4 1 2 6 3
6 3 1 5 7 4 2
2 4 6 7 3 1 5
Explicación:
Sudoku sin resolver con las regiones:
Sudoku resuelto con las regiones:
Entrada: sudoku[][] = {
{ 0, 0 },
{ 0, 1 } },
region[][] = {
{r, r},
{b, b}}
Salida:
1 2
2 1
Explicación:
Elementos de la fila de la array de salida: {1, 2}, {2, 1}
Elementos de la columna de la array: {1, 2}, {2, 1}
Elementos de las mismas regiones de la array: {1, 2}, {2, 1}
Ya que contiene elementos únicos en las filas, columnas y regiones.
Por tanto, es una solución válida del Sudoku.
Enfoque: La idea es usar Backtracking para resolver el Sudoku asignando el número a las celdas vacías una por una recursivamente y retroceder si se viola alguna de las reglas, es decir, cada fila, columna y región debe tener números únicos del 1 al N. A continuación se muestra la ilustración con la ayuda de los pasos:
- Cree una función para verificar si el número asignado a una celda es seguro o no:
- Para verificar la fila y la columna actuales, itere sobre la fila y la columna y verifique si el número asignado está presente en la celda o no.
- Para verificar si el número está presente en la región actual o no, use Breadth-First Search .
- Itere sobre la cuadrícula para verificar si hay alguna celda no asignada y asigne los valores de 1 a N y verifique si el número asignado es seguro o no. Si el número asignado no es seguro, retroceda hasta la celda no asignada.
- Si todas las celdas no asignadas están asignadas por algún número, imprima el Sudoku. De lo contrario, no hay solución posible.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Grid dimension
const int N = 2;
// Function to check if the number to be present
// in the current cell is safe or not
bool issafe(int sudoku[N][N], int i, int j, int n,
int number, char region[N][N])
{
// Check if the number is present in
// i-th row or j-th column or not
for (int x = 0; x < n; x++) {
if (sudoku[x][j] == number
|| sudoku[i][x] == number) {
return false;
}
}
// Check if the number to be filled
// is safe in current region or not
char r = region[i][j];
// Initialize the queue for the BFS
queue<pair<int, int> > q;
// Insert the current cell into queue
q.push(make_pair(i, j));
// Check if the neighbours cell is
// visited or not
int visited[N][N];
// Initialize visited to 0
memset(visited, 0, sizeof visited);
// Mark current cell is visited
visited[i][j] = 1;
// Performing the BFS technique
// Checking for 4 neighbours at a time
while (!q.empty()) {
// Stores front element of the queue
pair<int, int> front = q.front();
// Pop top element of the queue
q.pop();
// Check for neighbours cell
if (front.first + 1 < N
&& region[front.first + 1][front.second] == r
&& !visited[front.first + 1][front.second]) {
// If already contains the same number
if (sudoku[front.first + 1][front.second]
== number) {
return false;
}
q.push(make_pair(front.first + 1,
front.second));
// Mark as neighbour cell as visited
visited[front.first + 1][front.second] = 1;
}
// Checking for 2nd neighbours
if (front.first - 1 >= 0
&& region[front.first - 1][front.second] == r
&& !visited[front.first - 1][front.second]) {
// If neighbours contains the same number
if (sudoku[front.first - 1][front.second]
== number) {
return false;
}
// Insert neighbour cell into queue
q.push(make_pair(front.first - 1,
front.second));
// Mark neighbour cell as visited
visited[front.first - 1][front.second] = 1;
}
// Checking for 3rd neighbours
if (front.second + 1 < N
&& region[front.first][front.second + 1] == r
&& !visited[front.first][front.second + 1]) {
// If neighbours contains the same number
if (sudoku[front.first][front.second + 1]
== number) {
return false;
}
// Insert neighbour cell into queue
q.push(make_pair(front.first,
front.second + 1));
// Mark neighbour cell as visited
visited[front.first][front.second + 1] = 1;
}
// Checking for 4th neighbours
if (front.second - 1 >= 0
&& region[front.first][front.second - 1] == r
&& !visited[front.first][front.second - 1]) {
// If neighbours contains the same number
if (sudoku[front.first][front.second - 1]
== number) {
return false;
}
// Insert neighbour cell into queue
q.push(make_pair(front.first,
front.second - 1));
// Mark neighbour cell as visited
visited[front.first][front.second - 1] = 1;
}
}
return true;
}
// Recursive function to solve the sudoku
bool solveSudoku(int sudoku[N][N], int i, int j,
int n, char region[N][N])
{
// If the given sudoku already solved
if (i == n) {
// Print the solution of sudoku
for (int a = 0; a < n; a++) {
for (int b = 0; b < n; b++) {
cout << sudoku[a][b] << " ";
}
cout << endl;
}
return true;
}
// If the numbers in the current row
// already filled
if (j == n) {
return solveSudoku(sudoku, i + 1, 0, n, region);
}
// If current cell is not empty
if (sudoku[i][j] != 0) {
return solveSudoku(sudoku, i, j + 1, n, region);
}
else {
// Iterate over all possible value of numbers
for (int number = 1; number <= n; number++) {
// If placing the current number is safe
// in the current cell
if (issafe(sudoku, i, j, n, number, region)) {
// Update sudoku[i][j]
sudoku[i][j] = number;
// Fill the remaining cells of the sudoku
bool rest
= solveSudoku(sudoku, i,
j + 1, n, region);
// If remaining cells has been filled
if (rest == true) {
return true;
}
}
}
// Otherwise No Solution
sudoku[i][j] = 0;
return false;
}
}
// Driver Code
int main()
{
// Given sudoku array
int sudoku[N][N] = {
{ 0, 1 },
{ 0, 0 }
};
// Given region array
char region[N][N] = {
{ 'r', 'r' },
{ 'b', 'b' }
};
// Function call
int ans = solveSudoku(
sudoku, 0, 0, N, region);
// No answer exist
if (ans == 0) {
cout << "-1";
}
return 0;
}
Python3
# Python program for the above approach
# Grid dimension
N = 2
# Function to check if the number to be present
# in the current cell is safe or not
def issafe(sudoku, i, j, n, number, region):
# Check if the number is present in
# i-th row or j-th column or not
for x in range(n):
if (sudoku[x][j] == number or sudoku[i][x] == number):
return False
# Check if the number to be filled
# is safe in current region or not
r = region[i][j]
# Initialize the queue for the BFS
q = []
# Insert the current cell into queue
q.append([i, j])
# Check if the neighbours cell is
# visited or not
visited = [[0 for i in range(N)]for j in range(N)]
# Mark current cell is visited
visited[i][j] = 1
# Performing the BFS technique
# Checking for 4 neighbours at a time
while (len(q)>0):
# Stores front element of the queue
front = q[0]
# Pop top element of the queue
q.pop()
# Check for neighbours cell
if (front[0] + 1 < N and region[front[0] + 1][front[1]] == r and visited[front[0] + 1][front[1]] == 0):
# If already contains the same number
if (sudoku[front[0] + 1][front[1]] == number):
return False
q.append([front[0] + 1, front[1]])
# Mark as neighbour cell as visited
visited[front[0] + 1][front[1]] = 1
# Checking for 2nd neighbours
if(front[0] - 1 >= 0 and region[front[0] - 1][front[1]] == r and visited[front[0] - 1][front[1]] == 0):
# If neighbours contains the same number
if (sudoku[front[0] - 1][front[1]] == number):
return False
# Insert neighbour cell into queue
q.append([front[0] - 1, front[1]])
# Mark neighbour cell as visited
visited[front[0] - 1][front[1]] = 1
# Checking for 3rd neighbours
if ( front[1] + 1 < N and region[front[0]][front[1] + 1] == r and visited[front[0]][front[1] + 1] == 0):
# If neighbours contains the same number
if (sudoku[front[0]][front[1] + 1] == number):
return False
# Insert neighbour cell into queue
q.append([front[0], front[1] + 1])
# Mark neighbour cell as visited
visited[front[0]][front[1] + 1] = 1
# Checking for 4th neighbours
if (front[1] - 1 >= 0 and region[front[0]][front[1] - 1] == r and visited[front[0]][front[1] - 1] == 0):
# If neighbours contains the same number
if (sudoku[front[0]][front[1] - 1] == number):
return False
# Insert neighbour cell into queue
q.append([front[0], front[1] - 1])
# Mark neighbour cell as visited
visited[front[0]][front[1] - 1] = 1
return True
# Recursive function to solve the sudoku
def solveSudoku(sudoku, i, j, n, region):
# If the given sudoku already solved
if (i == n):
# Print the solution of sudoku
for a in range(n):
for b in range(n):
print(sudoku[a][b],end = " ")
print()
return True
# If the numbers in the current row
# already filled
if (j == n):
return solveSudoku(sudoku, i + 1, 0, n, region)
# If current cell is not empty
if (sudoku[i][j] != 0):
return solveSudoku(sudoku, i, j + 1, n, region)
else:
#Iterate over all possible value of numbers
for number in range(1,n+1):
# If placing the current number is safe
# in the current cell
if (issafe(sudoku, i, j, n, number, region)):
# Update sudoku[i][j]
sudoku[i][j] = number
# Fill the remaining cells of the sudoku
rest = solveSudoku(sudoku, i, j + 1, n, region)
# If remaining cells has been filled
if (rest == True):
return True
# Otherwise No Solution
sudoku[i][j] = 0
return False
# Driver Code
# Given sudoku array
sudoku = [
[0, 1],
[0, 0],
]
# Given region array
region = [
["r", "r"],
["b", "b"],
]
# Function call
ans = solveSudoku(sudoku, 0, 0, N, region)
# No answer exist
if (ans == 0):
print("-1")
# This code is contributed by shinjanpatra
Javascript
<script>
// Javascript program for the above approach
// Grid dimension
const N = 2;
// Function to check if the number to be present
// in the current cell is safe or not
function issafe(sudoku, i, j, n, number, region)
{
// Check if the number is present in
// i-th row or j-th column or not
for (let x = 0; x < n; x++) {
if (sudoku[x][j] == number || sudoku[i][x] == number) {
return false;
}
}
// Check if the number to be filled
// is safe in current region or not
let r = region[i][j];
// Initialize the queue for the BFS
let q = [];
// Insert the current cell into queue
q.push([i, j]);
// Check if the neighbours cell is
// visited or not
let visited = new Array(N).fill(0).map(() => new Array(N).fill(0));
// Mark current cell is visited
visited[i][j] = 1;
// Performing the BFS technique
// Checking for 4 neighbours at a time
while (!q.length)
{
// Stores front element of the queue
let front = q.front();
// Pop top element of the queue
q.pop();
// Check for neighbours cell
if (
front[0] + 1 < N &&
region[front[0] + 1][front[1]] == r &&
!visited[front[0] + 1][front[1]]
)
{
// If already contains the same number
if (sudoku[front[0] + 1][front[1]] == number)
{
return false;
}
q.push([front[0] + 1, front[1]]);
// Mark as neighbour cell as visited
visited[front[0] + 1][front[1]] = 1;
}
// Checking for 2nd neighbours
if (
front[0] - 1 >= 0 &&
region[front[0] - 1][front[1]] == r &&
!visited[front[0] - 1][front[1]]
) {
// If neighbours contains the same number
if (sudoku[front[0] - 1][front[1]] == number) {
return false;
}
// Insert neighbour cell into queue
q.push([front[0] - 1, front[1]]);
// Mark neighbour cell as visited
visited[front[0] - 1][front[1]] = 1;
}
// Checking for 3rd neighbours
if (
front[1] + 1 < N &&
region[front[0]][front[1] + 1] == r &&
!visited[front[0]][front[1] + 1]
) {
// If neighbours contains the same number
if (sudoku[front[0]][front[1] + 1] == number) {
return false;
}
// Insert neighbour cell into queue
q.push([front[0], front[1] + 1]);
// Mark neighbour cell as visited
visited[front[0]][front[1] + 1] = 1;
}
// Checking for 4th neighbours
if (
front[1] - 1 >= 0 &&
region[front[0]][front[1] - 1] == r &&
!visited[front[0]][front[1] - 1]
) {
// If neighbours contains the same number
if (sudoku[front[0]][front[1] - 1] == number) {
return false;
}
// Insert neighbour cell into queue
q.push([front[0], front[1] - 1]);
// Mark neighbour cell as visited
visited[front[0]][front[1] - 1] = 1;
}
}
return true;
}
// Recursive function to solve the sudoku
function solveSudoku(sudoku, i, j, n, region) {
// If the given sudoku already solved
if (i == n) {
// Print the solution of sudoku
for (let a = 0; a < n; a++) {
for (let b = 0; b < n; b++) {
document.write(sudoku[a][b] + " ");
}
document.write("<br>");
}
return true;
}
// If the numbers in the current row
// already filled
if (j == n) {
return solveSudoku(sudoku, i + 1, 0, n, region);
}
// If current cell is not empty
if (sudoku[i][j] != 0) {
return solveSudoku(sudoku, i, j + 1, n, region);
} else {
// Iterate over all possible value of numbers
for (let number = 1; number <= n; number++) {
// If placing the current number is safe
// in the current cell
if (issafe(sudoku, i, j, n, number, region)) {
// Update sudoku[i][j]
sudoku[i][j] = number;
// Fill the remaining cells of the sudoku
let rest = solveSudoku(sudoku, i, j + 1, n, region);
// If remaining cells has been filled
if (rest == true) {
return true;
}
}
}
// Otherwise No Solution
sudoku[i][j] = 0;
return false;
}
}
// Driver Code
// Given sudoku array
let sudoku = [
[0, 1],
[0, 0],
];
// Given region array
let region = [
["r", "r"],
["b", "b"],
];
// Function call
let ans = solveSudoku(sudoku, 0, 0, N, region);
// No answer exist
if (ans == 0) {
document.write(cout + "-1");
}
// This code is contributed by gfgking
</script>
Producción:
2 1 1 2
Complejidad de Tiempo: O(N N2 )
Espacio Auxiliar: O(N 2 )
Publicación traducida automáticamente
Artículo escrito por kritirikhi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA