VPF::Судоку(Sudoku) ? - Форум программистов

unkis

Дата 15.3.2006, 11:41 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 802
Регистрация: 8.9.2004

Репутация: нет
Всего: 1

Ребята здраствуйте!
Тут есть одна интересна игра называется Судоку(Sudoku).
Информация о игре здесь

Предлогаю на форуме обсудить алгоритмы её решения, не просто тупой перебо, а какие-нибудь алгоритмы связаные с KI

Зарания всем благодарен.

--------------------

www.unkis.com

maxim1000

Дата 15.3.2006, 14:01 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Участник
Сообщений: 3334
Регистрация: 11.1.2003
Где: Киев

Репутация: 33
Всего: 110

ну подобные задачи чаще всего решаются перебором с какими-нибудь модификациями
самая частая модификация - отсечение какого-нибудь множества вариантов
еще один вариант - перебор в каком-то определенном порядке

тут сразу же добавляется отсечение - проверка корректности после каждой поставленной цифры
дальше, как мне кажется, нелишним будет упорядочвание перебора: сначала искать те клетки, где количество вариантов наименьшее
если оно - 0, сразу ясно, что надо делать откат
если 1 - и перебора никакого нету
2 - перебрать два варианта

это немного замедлит рост количества вариантов по мере углубления...

--------------------

qqq

unkis

Дата 15.3.2006, 20:16 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 802
Регистрация: 8.9.2004

Репутация: нет
Всего: 1

Я тут в интернете почитал многие к этой проблемме подходят с матиматической точке зрения, некотыре испльзуют какой-то Sword Fish
Кто что про эти методы знает.

--------------------

www.unkis.com

XbiT

Дата 20.3.2006, 22:45 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 65
Регистрация: 9.2.2006

Репутация: 1
Всего: 1

писал пару дней назад перебор на эту задачу, но для поля 5*5 он загибался. 4*4моментально работает.

daNick

Дата 22.8.2006, 11:55 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 114
Регистрация: 12.8.2006
Где: Казахстан, Астана

Репутация: нет
Всего: нет

А скажите лучьше, как генерить это самое поле 9х9?

--------------------

Долго не кончать - преимущество мужчины, а не оратора.Я так много читал о вреде курения, что решил бросить... читать.(с) Сергей Довлатов

Akina

Дата 22.8.2006, 12:23 (ссылка)

(нет голосов)

Загрузка ...

Советчик

Профиль
Группа: Модератор
Сообщений: 20581
Регистрация: 8.4.2004
Где: Зеленоград

Репутация: 20
Всего: 454

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

В случае когда решение единственное, за все решение потребуется максимум 2-3 предположения. К тому же несложно организовывать откат и, следовательно, рекурсивный поиск.

--------------------

О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума.

nostromo

Дата 25.8.2006, 11:35 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 194
Регистрация: 23.3.2006

Репутация: 5
Всего: 10

Пара реализаций решателя sudoku на Erlang:
http://www.erlang-consulting.com/obfuscatederlang.html
http://www.mail-archive.com/[email protected]/msg00274.html

--------------------

На пыльных тропинках далеких планет останутся наши следы.

boevik

Дата 30.8.2006, 22:57 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Участник Клуба
Сообщений: 1452
Регистрация: 31.5.2004
Где: Израиль

Репутация: нет
Всего: 35

Цитата(daNick @ 22.8.2006, 11:55)

А скажите лучьше, как генерить это самое поле 9х9?

Генерил рекурсией.
Есть даче код на Jave, отрабатывает за доли секунды.

--------------------

Никогда не говори никогда

nickless

Дата 3.9.2006, 16:30 (ссылка)

(нет голосов)

Загрузка ...

Гентозавр

Профиль
Группа: Участник Клуба
Сообщений: 2976
Регистрация: 29.8.2005
Где: Germany

Репутация: нет
Всего: 181

Есть еще dancing links algorithm Кнута, смотри линк, там есть пример для судоку

--------------------

Real men don't use backups, they post their stuff on a public ftp server and let the rest of the world make copies
- Linus Torvalds

daNick

Дата 5.9.2006, 11:37 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 114
Регистрация: 12.8.2006
Где: Казахстан, Астана

Репутация: нет
Всего: нет

boevik, на ВБ можешь сделать исходники?

--------------------

boevik

Дата 5.9.2006, 11:42 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Участник Клуба
Сообщений: 1452
Регистрация: 31.5.2004
Где: Израиль

Репутация: нет
Всего: 35

В принципе, не должно быть проблемным.
Можешь и сам попробовать, код не сложный.

--------------------

Никогда не говори никогда

daNick

Дата 7.9.2006, 13:44 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 114
Регистрация: 12.8.2006
Где: Казахстан, Астана

Репутация: нет
Всего: нет

boevik, я пытался сам, но у меня нифига не вышло. Даже на сайте посвященному чисто программированию судоку исходники рабоают неправильно. Т.е. лбо по вертикали, либо по горизонтал, либо в блоках цифры повторяются.Так что, если не жалко, помоги?

--------------------

boevik

Дата 7.9.2006, 14:00 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Участник Клуба
Сообщений: 1452
Регистрация: 31.5.2004
Где: Израиль

Репутация: нет
Всего: 35

Выкладываю исходники на Java, будут затруднения пиши:

Код


    private int randomNumberRecursive(int cell) {
        //stop condition
        if (cell>=81) 
            return -1; 
        int row = cell/9, 
                col=cell%9;
                
        //random any number and check for correctness
        //if the digit is not correct, just check next digit
        int digit = (int)(Math.random()*9+1);
        for (int i=0; i<10; i++){
            digit = ++digit%10;
            if (digit!= 0 &&    //ignore zero digit
                    legitimateDigit(row, col, digit)){
                table[row][col]=digit;
                if (randomNumberRecursive(cell+1)!=0){
                    return digit;
                }
            }
        }
        table[row][col]=0;
        return 0;
    }


    /**
     * Verify corrections of the digit in the sudoku table
     * @param row is row position of the digit
     * @param col is column position of the digit
     * @param digit is number that checks
     */
    public boolean legitimateDigit(int row, int col, int digit){
        return legitimateInRow(row, digit) &&
                legitimateInCol(col, digit) &&
                legitimateInSquare(squareNumber(row, col), digit);
    }
    private boolean legitimateInRow(int row, int digit) {
        for(int i=0; i<9; i++)
            if (table[row][i] == digit)
                return false;
        return true;
    }
    
    private boolean legitimateInCol(int col, int digit) {
        for(int i=0; i<9; i++)
            if (table[i][col] == digit)
                return false;
        return true;
    }
    
    public int squareNumber(int row, int col) {
        if (row < 3 && col < 3) return 1;
        if (row < 3 && col < 6) return 2;
        if (row < 3 && col < 9) return 3;
        if (row < 6 && col < 3) return 4;
        if (row < 6 && col < 6) return 5;
        if (row < 6 && col < 9) return 6;
        if (row < 9 && col < 3) return 7;
        if (row < 9 && col < 6) return 8;
        if (row < 9 && col < 9) return 9;
        return 0;
    }
    
    private boolean legitimateInSquare(int square, int digit) {
        for(int i=0; i<9; i++)
            for (int j=0; j<9; j++)
                if (squareNumber(i, j) == square && table[i][j] == digit)
                    return false;
        return true;
    }

Всё начинается с запуска

Код


randomNumberRecursive(0);

результатом является заполненое поле table.
Если надо получить поля для отгадывания, то есть другая функция которая рандомально затирает цифры в заполненом поле.

Удачи

--------------------

Никогда не говори никогда

daNick

Дата 7.9.2006, 14:41 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 114
Регистрация: 12.8.2006
Где: Казахстан, Астана

Репутация: нет
Всего: нет

Спасибо. Попытаюсь разобраться. Хотя я в Яве не шарю, я васче кроме вб и паскаля нде ни шарю, но это дело поправимое.

--------------------

daNick

Дата 25.9.2006, 11:34 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 114
Регистрация: 12.8.2006
Где: Казахстан, Астана

Репутация: нет
Всего: нет

Переложил на VB, ни фига не работает. Переменная digit принимает значения большее 9. Почему так?

--------------------

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Алгоритмы \| Следующая тема »