Как решить судоку так, чтобы, переставляя любые две соседние подсетки, я все еще получал правильный ответ?

Мне дали сетку ^2 * n^2 с несколькими числами, заполненными в ней. Мне нужно заполнить оставшуюся сетку, используя основные правила судоку, а также еще одно дополнительное условие, которое заключается в том, чтобы, если я поменяю местами любые 2 соседние подсетки (n*n), тогда моя общая сетка (судоку) все еще действительна. Я использую технику возврата, чтобы решить ее. Но я не могу удовлетворить дополнительное условие.

1 2 | 3 4
3 4 | 1 2
---------
2 1 | 4 3
4 3 | 2 1

2 1 | 3 4
4 3 | 1 2
---------
1 2 | 4 3
3 4 | 2 1

Здесь, поменяв местами верхний левый ящик с нижним левым ящиком, я все же получил ответ. Точно так же это может быть возможно, если мы поменяем любые боксы рядом или сверху и снизу, если они соседние.

Пожалуйста, помогите мне. Вот код для подхода обратного отслеживания, взятый из www.geeksforgeeks.org

 bool SolveSudoku(int grid[N][N])
{
    int row, col;

    if (!FindUnassignedLocation(grid, row, col))
       return true;

    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; // this triggers backtracking
}

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;
}

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;
}

bool isSafe(int grid[N][N], int row, int col, int num)
{
    return !UsedInRow(grid, row, num) &&
           !UsedInCol(grid, col, num) &&
           !UsedInBox(grid, row - row%3 , col - col%3, num);
}
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");
    }
}

Как мне включить это условие в это. Прежде всего, пожалуйста, дайте мне знать, если это возможно решить с помощью возврата. Верхняя граница "n" равна 30.

Источник

1 ответ

Дано правильное решение судоку и две подсетки A а также B в нем, которые находятся один над другим (соответственно, помимо другого), вы можете поменять местами A а также B тогда и только тогда, когда они имеют одинаковые элементы (в разных порядках) в каждой из своих строк (соответственно, столбцы). (т.е. sort(A[i, :])==sort(B[i, :] для всех я в 1..n).

Поэтому все, что вам нужно сделать, это добавить некоторые ограничения, отражающие, что:

  • когда вы хотите оценить a в A[i, j] (A будучи подсеткой), рассмотрим Aсоседи. Учитывая сосед B выше или ниже Aход недействителен, если a уже в Bв другом ряду, чем i
  • аналогично для горизонтальных соседей А (с колонками)

Так что на практике вам просто нужно продлить isSafe() с еще несколькими ограничениями:) .

На самом деле он должен работать быстрее, чем без ограничения для больших значений n, так как вы будете исследовать меньше своего дерева.

РЕДАКТИРОВАТЬ

Я бы добавил функции UsedInNeighborsWrongRow (столбец респ), которые могут быть, например, такими:

bool UsedInNeighborsWrongRow(int grid[N][N], int boxStartRow, int boxStartCol, int rowIdw, int num) 
{
    for (int row = 0; row < N; row++)
        if (row != rowIdx)
            for (int col = 0; col < N; col++)
                if (grid[row+boxStartRow][col+boxStartCol] == num)
                    return true;    
    return false;
}

и вызвать их для каждого соседа в isSafe:

bool isSafe(int grid[N][N], int row, int col, int num)
{
    bool OKForSwapping = !UsedInNeighborsWrongRow(grid, neighbor1_row, neighbor1_col, row, num);
    if (there is a 2nd vertical neighbor) 
        OKForSwapping &=!UsedInNeighborsWrongRow(grid, neighbor2_row, neighbor2_col, row, num);
    OKForSwapping &=!UsedInNeighborsWrongColumn(grid, neighbor3_row, neighbor3_col, col, num);
    if (there is a 2nd horizontal neighbor) 
        OKForSwapping &=!UsedInNeighborsWrongColumn(grid, neighbor4_row, neighbor4_col, row, num);
    return !UsedInRow(grid, row, num) &&
               !UsedInCol(grid, col, num) &&
               !UsedInBox(grid, row - row%N , col - col%N, num) &&
               OKForSwapping;
}

Это долго, но я не уверен, что вы можете сделать намного лучше, структура судоку лучше подходит для других ограничений, чем эта...

ВНИМАНИЕ: Вы должны заменить 3 на N в вашей функции UsedInBox И в isSafe

Источник
Другие вопросы по тегам