Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > Алгоритмы > Судоку(Sudoku) ?


Автор: unkis 15.3.2006, 11:41
Ребята здраствуйте!
Тут есть одна интересна игра называется Судоку(Sudoku).
Информация о игре http://ru.wikipedia.org/wiki/%D0%A1%D1%83%D0%B4%D0%BE%D0%BA%D1%83

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


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

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

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

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

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

Автор: XbiT 20.3.2006, 22:45
писал пару дней назад перебор на эту задачу, но для поля 5*5 он загибался. 4*4моментально работает.

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

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

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

Автор: nostromo 25.8.2006, 11:35
Пара реализаций решателя sudoku на Erlang:
http://www.erlang-consulting.com/obfuscatederlang.html
http://www.mail-archive.com/coders@slug.org.au/msg00274.html

Автор: boevik 30.8.2006, 22:57
Цитата(daNick @ 22.8.2006,  11:55)
А скажите лучьше, как генерить это самое поле 9х9?

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

Автор: nickless 3.9.2006, 16:30
Есть еще http://en.wikipedia.org/wiki/Dancing_links Кнута, смотри линк, там есть пример для судоку

Автор: daNick 5.9.2006, 11:37
boevik, на ВБ можешь сделать исходники?

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

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

Автор: boevik 7.9.2006, 14:00
Выкладываю исходники на 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
Спасибо. Попытаюсь разобраться. Хотя я в Яве не шарю, я васче кроме вб и паскаля нде ни шарю, но это дело поправимое.

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

Автор: boevik 25.9.2006, 12:19
Выкладывай кодна VB, с VB я немного знаком.

Автор: boevik 25.9.2006, 12:40
Цитата(daNick @  25.9.2006,  11:34 Найти цитируемый пост)
Переложил на VB, ни фига не работает. Переменная digit принимает значения большее 9. Почему так? 

digit%10 -> digit mod 10  - это выполнил?

Автор: ip127001 26.12.2006, 09:56
самый разумный алгоритм...сначало заполнить матрицу...потом сохранить ее в вирт массиве.

и в зависимости от сложности отчистить ее, оставив нужное количество цифер

Автор: V.A.KeRneL 29.12.2006, 09:36
http://ru.wikipedia.org/wiki/Судоку
http://ru.wikipedia.org/wiki/Обобщённое_судоку

http://en.wikipedia.org/wiki/Sudoku
http://en.wikipedia.org/wiki/Mathematics_of_Sudoku

http://fr.wikipedia.org/wiki/Sudoku

Да, и не забывайте, что задача обобщённого судоку NP-полна => полиномиального решения не существует (по крайней мере, до тех пор, пока мы глобально не пересмотрим существующую теорию вычислений). Лучший здесь вариант -- это, имхо, оптимизированный «умный» перебор.

Автор: Magister Y0da 1.1.2007, 05:10
http://markbyers.com/moinmoin/moin.cgi/ShortestSudokuSolver

Автор: SoWa 1.1.2007, 15:24
Код

main(int j,char**V){char*R=V[1],i=0,k=48;for(;*R>k;*++R||
puts(R-i))++i;for(;++k<58;*R&&main(*R=k,V),*R=1)for(j=81;j
--;)*R*=R[j-i]-k||i/9^j/9&&i%9^j%9&&i/27^j/27|i%9/3^j%9/3;}

Ох. С Си плохо знаком, а еще и написано нечитабельно smile
Кто нибудь в Алгол может перевести?

Автор: Alex 6.1.2007, 03:05
Вот алгоритм boevik переписанный на Delphi:
Код

var
  table: array[0..8,0..8] of Integer;

function legitimateInRow(row, digit: Integer): boolean;
var
  i: Integer;
begin
  Result:= True;
  for i:=0 to 8 do if table[row][i] = digit then Result:= False;
end;

function legitimateInCol(col, digit: Integer): boolean;
var
  i: Integer;
begin
  Result:= True;
  for i:=0 to 8 do if (table[i][col] = digit) then Result:= False;
end;

function squareNumber(row, col: Integer): Integer;
begin
  if (row < 3) and (col < 3) then begin Result:= 1; Exit; end;
  if (row < 3) and (col < 6) then begin Result:= 2; Exit; end;
  if (row < 3) and (col < 9) then begin Result:= 3; Exit; end;
  if (row < 6) and (col < 3) then begin Result:= 4; Exit; end;
  if (row < 6) and (col < 6) then begin Result:= 5; Exit; end;
  if (row < 6) and (col < 9) then begin Result:= 6; Exit; end;
  if (row < 9) and (col < 3) then begin Result:= 7; Exit; end;
  if (row < 9) and (col < 6) then begin Result:= 8; Exit; end;
  if (row < 9) and (col < 9) then begin Result:= 9; Exit; end;
  Result:= 0;
end;

function legitimateInSquare(square, digit: Integer): Boolean;
var
  i, j: Integer;
begin
  Result:= true;
  for i:=0 to 8 do for j:=0 to 8 do
    if (squareNumber(i, j) = square) and (table[i][j] = digit) then
      Result:= false;
end;

function legitimateDigit(row, col, digit: Integer): Boolean;
begin
  Result:= legitimateInRow(row, digit) and
           legitimateInCol(col, digit) and
           legitimateInSquare(squareNumber(row, col), digit);
end;

function randomNumberRecursive(cell: Integer): Integer;
var
  row, col, digit, i: Integer;
begin
  //stop condition
  if (cell>=81) then begin
    Result:= -1;
    Exit;
  end;
  row:= cell div 9;
  col:= cell mod 9;

  //random any number and check for correctness
  //if the digit is not correct, just check next digit
  randomize;
  digit:= random(999999)*9+1;
  for i:=0 to 9 do begin
    digit:= (digit+1) mod 10;
    if ((digit<> 0) and legitimateDigit(row, col, digit)) then begin
      table[row][col]:=digit;
      if (randomNumberRecursive(cell+1)<>0) then begin
        Result:= digit;
        exit;
      end;
    end;
  end;
  table[row][col]:= 0;
  Result:= 0;
end;

Автор: Vsts 10.1.2007, 21:13
Помоему прога от "boevik" много лишнего делает.
Алгоритм можно упростить.
Код

#include <stdio.h>
#include <stdlib.h>

enum 
{
    Width  = 9,
    Height = 9,
    CountSh= 100   //кол-во перемешиваний
};

//тут можно вставить любые начальные условия, главное что бы удовлетворяли правилам игры
int arr[Width][Height]  = {     {0,3,6,1,4,7,2,5,8},   
                                {1,4,7,2,5,8,0,3,6},
                                {2,5,8,0,3,6,1,4,7},
                                {3,6,0,4,7,1,5,8,2},
                                {4,7,1,5,8,2,3,6,0},
                                {5,8,2,3,6,0,4,7,1},
                                {6,0,3,7,1,4,8,2,5},
                                {7,1,4,8,2,5,6,0,3},
                                {8,2,5,6,0,3,7,1,4}};

// меняет две строки в массиве
void swapX(unsigned int x1,unsigned int x2)
{
    if(x1 >= Width ||x2 >= Width )   return;
     //проверяем что бы в пределах одного квадрата были перемещаемые строки
    unsigned int c =  (x1>x2) ? (x1-x2) : (x2-x1);
    if( c == 0 || c > 2) return;

    //если все хорошо, меняем их местами
    for(unsigned  int i=0;i<Width;++i)
    {
        int temp   = arr[i][x1];
        arr[i][x1] = arr[i][x2];
        arr[i][x2] = temp;
    }
}
// меняет два столбца в массиве
void swapY(unsigned int x1,unsigned int x2)
{
    if(x1 >= Height ||x2 >= Height )  return;
    
    // все тоже самое,только для столбцов

    unsigned int c =  (x1>x2) ? (x1-x2) : (x2-x1);
    
    if( c == 0 || c > 2) return;

    for(unsigned  int i=0;i<Height;++i)
    {
        int temp   = arr[x1][i];
        arr[x1][i] = arr[x2][i];
        arr[x2][i] = temp;
    }
}
int main()
{
     for(int i=0;i<CountSh;++i)
    {
        unsigned  int sq,x1,x2; 

        sq = rand()%3;  // выбираем что бы попали в нужный диапазон

        x1 = rand()%2 + 1;
        x2 = rand()%x1;

        if(i%2) swapX(x1 +sq *3,x2+sq *3);
        else    swapY(x1 +sq *3,x2+sq *3);
    }
        
    //вывод на экран
    printf("\n-------------------------------\n");
    for(int i=0;i<Width;++i)
    {
        for(int j=0;j<Height;++j)    
        {
            printf("%s %d ",j%3 == 0 ? "|":"",arr[i][j]);
        }
        printf("|");

        if(i%3 == 2)
            printf("\n+---------|---------|---------|\n");
        else
            printf("\n|         |         |         |\n");
    }
    return 0;
}




Пусть есть матрица  ,удовлетворяющая правилам судоку . Например А = 
-------------------------------
| 0  3  6 | 1  4  7 | 2  5  8 |
|            |            |            |
| 1  4  7 | 2  5  8 | 0  3  6 |
|            |            |            |
| 2  5  8 | 0  3  6 | 1  4  7 |
+---------|---------|---------|
| 3  6  0 | 4  7  1 | 5  8  2 |
|            |            |            |
| 4  7  1 | 5  8  2 | 3  6  0 |
|            |            |            |
| 5  8  2 | 3  6  0 | 4  7  1 |
+---------|---------|---------|
| 6  0  3 | 7  1  4 | 8  2  5 |
|            |            |            |
| 7  1  4 | 8  2  5 | 6  0  3 |
|            |            |            |
| 8  2  5 | 6  0  3 | 7  1  4 |
+---------|---------|---------|


что бы получить новую, достаточно в этой поменять две строчки (или столбца) местами,
при уловии что они обе принадлежат [ 0 , 2 ] [ 3 , 5 ] [ 6 , 8 ] .

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

так например меняем первую(нулевую) строку со второй(первой), 4(3) столбец с 6(5) 

---------------------------------
| 1  4  7 | 8  5  2 | 0  3  6 |
|            |            |            |
| 0  3  6 | 7  4  1 | 2  5  8 |
|            |            |            |
| 2  5  8 | 6  3  0 | 1  4  7 |
+---------|----------|---------|
| 3  6  0 | 1  7  4 | 5  8  2 |
|            |            |            |
| 4  7  1 | 2  8  5 | 3  6  0 |
|            |            |            |
| 5  8  2 | 0  6  3 | 4  7  1 |
+---------|---------|---------|
| 6  0  3 | 4  1  7 | 8  2  5 |
|            |            |            |
| 7  1  4 | 5  2  8 | 6  0  3 |
|            |            |            |
| 8  2  5 | 3  0  6 | 7  1  4 |
+---------|---------|---------|

Цитата

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


Других елементарных преобразований я пока не нашел.Возможно ими можно все описать.
И еще не посчитал,сколько порождающих элементов есть.(Извеняюсь если это уже в статях есть,но все просматривать не было времени, да и язык буржуйский smile ...).



ПыСы : математика это хАрАшо, тока за неё не платят... smile 

Автор: boevik 11.1.2007, 11:32
Цитата(Vsts @  10.1.2007,  21:13 Найти цитируемый пост)
Помоему прога от "boevik" много лишнего делает.

Совершенно врно, прога делает много лишнего - в нее уже заложены инструменты для других решений.
К примеру, 1) можно задать начальную мартицу и найти все возможные решения решения; 
2) производить проверку ввода юзером
и т.д и т.п.

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)