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

boevik

Дата 25.9.2006, 12:19 (ссылка)

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

Загрузка ...

Эксперт

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

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

Выкладывай кодна VB, с VB я немного знаком.

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

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

boevik

Дата 25.9.2006, 12:40 (ссылка)

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

Загрузка ...

Эксперт

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

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

Цитата(daNick @ 25.9.2006, 11:34

)

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

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

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

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

ip127001

Дата 26.12.2006, 09:56 (ссылка)

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

Загрузка ...

Бывалый

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

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

самый разумный алгоритм...сначало заполнить матрицу...потом сохранить ее в вирт массиве.

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

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

aqua currit et debere currere ut currere solebat

V.A.KeRneL

Дата 29.12.2006, 09:36 (ссылка)

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

Загрузка ...

Vadim A. Kazantsev

Профиль
Группа: Участник
Сообщений: 291
Регистрация: 3.12.2006
Где: Moscow, Russia

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

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

Это сообщение отредактировал(а) V_A_KeRneL - 29.12.2006, 09:42

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

«C'est un pense-creux d'ici. C'est le meilleur et le plus irascible homme du monde...» © Ф.М. Достоевский, «Бесы»
---/)/)---(\.../)---(\(\
--(':'=)---(=';'=)---(=':')
(")(")..)-(").--.(")-(..(")(")

Magister Y0da

Дата 1.1.2007, 05:10 (ссылка)

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

Загрузка ...

Зелёненький

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

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

http://markbyers.com/moinmoin/moin.cgi/ShortestSudokuSolver

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

SoWa

Дата 1.1.2007, 15:24 (ссылка)

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

Загрузка ...

Харекришна

Профиль
Группа: Комодератор
Сообщений: 2422
Регистрация: 18.10.2004

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

Код


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

Кто нибудь в Алгол может перевести?

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

Всем добра smile

Alex

Дата 6.1.2007, 03:05 (ссылка)

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

Загрузка ...

Эксперт

Профиль
Группа: Экс. модератор
Сообщений: 4147
Регистрация: 25.3.2002
Где: Москва

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

Вот алгоритм 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 (ссылка)

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

Загрузка ...

Новичок

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

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

Помоему прога от "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

Это сообщение отредактировал(а) Vsts - 10.1.2007, 22:17

boevik

Дата 11.1.2007, 11:32 (ссылка)

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

Загрузка ...

Эксперт

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

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

Цитата(Vsts @ 10.1.2007, 21:13

)

Помоему прога от "boevik" много лишнего делает.

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

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

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

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