Функция оценки решения судоку

Question

Так что я пытаюсь написать простой генетический алгоритм для решения судоку (я знаю, что это не самый эффективный способ, а просто практиковать эволюционные алгоритмы). У меня возникли некоторые проблемы при разработке эффективной функции оценки, чтобы проверить, решена ли головоломка или нет, и сколько ошибок. Моим первым инстинктом было бы проверить, есть ли в каждой строке и столбце матрицы (делая это в октаве, которая похожа на matlab) уникальные элементы, упорядочив их, проверив наличие дубликатов, а затем вернув их на прежнее место, что кажется длинным многословно. Есть мысли?

Извините, если раньше об этом спрашивали ...

Answer 1

Проверка очень проста: вы создадите наборы для строк, столбцов и 3х3, добавив число, если оно не существует, и соответственно измените свою пригодность, если его нет.

Однако реальный трюк таков:изменяя свою физическую форму "соответственно.Некоторые проблемы кажутся хорошо подходящими для GA и ES (стратегии эволюции), то есть мы ищем решение в толерантности, у sudoku есть точный ответ ... хитро.

Моя первая проблема, вероятно, будет создавать решения с переменнойдлина хромосом (ну, они могут быть фиксированной длины, но 9x9 с пробелами).Функция пригодности должна быть в состоянии определить, какая часть решения гарантирована, а какая нет (иногда вы должны сделать предположение в темноте в действительно сложной игре судоку и затем проследить, если это не сработает), это будетхорошая идея - создать дочерние элементы для каждой возможной ветви.

Это рекурсивное решениеОднако вы можете начать сканирование с разных позиций на доске.Рекомбинация будет объединять решения, которые объединяют непроверенные части, которые имеют перекрывающиеся решения.

Просто думая об этом в таком высоком и легкомысленном стиле, я понимаю, как это будет реализовано!

Мутация будетприменяется только тогда, когда есть более одного пути, ведь мутация является своего рода догадкой.

Answer 2

ускорения:
Используйте побитовые операции вместо сортировки.

Я сделал 100 строк решателя судоку в c это достаточно быстро. Для суперскорости вам нужно реализовать алгоритм DLX, для этого есть также обмен файлами на matlab.
http://en.wikipedia.org/wiki/Exact_cover
http://en.wikipedia.org/wiki/Dancing_Links
http://en.wikipedia.org/wiki/Knuth's_Algorithm_X

#include "stdio.h"
int rec_sudoku(int (&mat)[9][9],int depth)
{
    int sol[9][9][10]; //for eliminating
    if(depth == 0) return 1;
    for(int i=0;i<9;i++)
    {
        for(int j=0;j<9;j++)
        {
            sol[i][j][9]=9;
            for(int k=0;k<9;k++)
            {
                if(mat[i][j]) sol[i][j][k]=0;
                else sol[i][j][k]=1;
            }
        }
    }
    for(int i=0;i<9;i++)
    {
        for(int j=0;j<9;j++)
        {
            if(mat[i][j] == 0) continue;
            for(int k=0;k<9;k++)
            {
                if(sol[i][k][mat[i][j]-1])
                {
                    if(--sol[i][k][9]==0) return 0;
                    sol[i][k][mat[i][j]-1]=0;
                }
                if(sol[k][j][mat[i][j]-1])
                {
                    if(--sol[k][j][9]==0) return 0;
                    sol[k][j][mat[i][j]-1]=0;
                }
            }
            for(int k=(i/3)*3;k<(i/3+1)*3;k++)
            {
                for(int kk=(j/3)*3;kk<(j/3+1)*3;kk++)
                {
                    if(sol[k][kk][mat[i][j]-1])
                    {
                        if(--sol[k][kk][9]==0) return 0;
                        sol[k][kk][mat[i][j]-1]=0;
                    }
                }
            }
        }
    }
    for(int c=1;c<=9;c++)
    {
        for(int i=0;i<9;i++)
        {
            for(int j=0;j<9;j++)
            {
                if(sol[i][j][9] != c) continue;
                for(int k=0;k<9;k++)
                {
                    if(sol[i][j][k] != 1) continue;
                    mat[i][j]=k+1;
                    if(rec_sudoku(mat,depth-1)) return 1;
                    mat[i][j]=0;
                }
                return 0;
            }
        }
    }
    return 0;
}
int main(void)
{
    int matrix[9][9] =
    {
        {1,0,0,0,0,7,0,9,0},
        {0,3,0,0,2,0,0,0,8},
        {0,0,9,6,0,0,5,0,0},
        {0,0,5,3,0,0,9,0,0},
        {0,1,0,0,8,0,0,0,2},
        {6,0,0,0,0,4,0,0,0},
        {3,0,0,0,0,0,0,1,0},
        {0,4,0,0,0,0,0,0,7},
        {0,0,7,0,0,0,3,0,0}
    };
    int d=0;
    for(int i=0;i<9;i++) for(int j=0;j<9;j++) if(matrix[i][j] == 0) d++;
    if(rec_sudoku(matrix,d)==0)
    {
        printf("no solution");
        return 0;
    }
    for(int i=0;i<9;i++)
    {
        for(int j=0;j<9;j++)
        {
            printf("%i ",matrix[i][j]);
        }
        printf("\n");
    }
    return 1;
}

Answer 3

1. Если вы работаете с небольшим набором целых чисел, сортировку можно выполнить в O(n) с использованием сортировки по сегментам.

2. Вы можете использовать tmp массивы для выполнения этой задачи в Matlab:

   function tf = checkSubSet (board, sel) % % с учетом доски 9x9 и выбора (с использованием логической матрицы выбора 9x9) % проверяют, что доска (sel) имеет 9 уникальных элементов % % предположений сделано: % - доска 9х9 с номерами 1,2, ..., 9 % - sel имеет только 9 «истинных» записей: nnz (sel) = 9 % tmp = нули (1,9); tmp (board (sel)) = 1; % сортировка ведра бедного человека tf = all (tmp == 1) && nnz (sel) == 9 && цифра (tmp) == 9; % проверки действительности

Теперь мы можем использовать checkSubSet, чтобы проверить правильность доски

function isCorrect = checkSudokuBoard( board )
%
% assuming board is 9x9 matrix with entries 1,2,...,9
%

isCorrect = true;
% check rows and columns
for ii = 1:9
    sel = false( 9 );
    sel(:,ii) = true;
    isCorrect = checkSubSet( board, sel );
    if ~isCorrect
        return;
    end
    sel = false( 9 );
    sel( ii, : ) = true;
    isCorrect = checkSubSet( board, sel );
    if ~isCorrect
        return;
    end
end
% check all 3x3 
for ii=1:3:9
    for jj=1:3:9
        sel = false( 9 );
        sel( ii + (0:2) , jj + (0:2) ) = true;
        isCorrect = checkSubSet( board, sel );
        if ~isCorrect
            return;
        end
    end
end

Answer 4

Вот мое решение с использованием набора.Если для строки, блока или столбца вы получите заданную длину (скажем, 7), ваша пригодность будет 9 - 7.

Answer 5

Вот мое решение. Решение для решения судоку в C ++

Answer 6

Когда я решил эту проблему, я просто посчитал количество дубликатов в каждой строке, столбце и подрешетке (фактически мне нужно было только сосчитать дубликаты в столбцах и подрешетках, поскольку мои эволюционные операторы никогда не создавали дубликатовв ряды).Я просто использовал HashSet для обнаружения дубликатов.Есть более быстрые способы, но это было достаточно быстро для меня.

Вы можете увидеть это в моем Java-апплете (если это слишком быстро, увеличьте размер популяции, чтобы замедлить его).Цветные квадраты являются дубликатами.Желтые квадраты конфликтуют с одним другим квадратом, оранжевый с двумя другими квадратами и красный с тремя и более.

Answer 7

Звучит хорошо, за исключением части «положить их обратно». Вы можете просто поместить числа из любой строки, столбца или квадрата в головоломку в списке и проверить на двойные значения любым удобным для вас способом. Если есть двойники, есть ошибка. Если все числа уникальны, то нет. Вам не нужно извлекать реальные цифры из головоломки, поэтому нет необходимости их возвращать.

Кроме того, если вы пишете решатель, он не должен делать какие-либо неверные шаги, поэтому эта проверка вообще не понадобится.

Answer 8

Я бы использовал номера сетки в качестве индекса и увеличивал соответствующий элемент массива длиной 9 элементов => s_array [x] ++, где x - это число, взятое из сетки.Каждый элемент должен быть 1 в массиве в конце проверки одной строки.Если где-то в массиве встречается 0, эта строка неверна.

Однако это просто проверка работоспособности, если нет проблем, по строке.

PS: если бы это было 10 летназад, я бы предложил решение сборки с манипулированием битами (1-й бит, 2-й бит, 3-й бит и т. д. для значений 1, 2 или 3) и проверил, равен ли результат 2 ^ 10-1.