Судоку решатель для начинающих в C


Я начинающий программист и я заставил себя написать судоку решатель В С. Я закончил его в течение нескольких дней и теперь я хочу сделать это быстрее.

С этого образца время выполнения ввода 1.781 секунд (который включает загрузку программы, я использую код:блоков, в которых время измеряется автоматически)

0 0 0 0 5 0 0 0 1
1 0 0 8 0 0 0 0 0
0 0 8 0 4 6 0 0 2
5 7 0 0 0 0 0 0 0
0 6 0 3 0 0 2 0 0
0 9 0 4 2 0 0 7 0
0 0 0 0 0 0 0 0 4
0 0 0 0 9 8 5 0 0
0 3 0 0 0 0 7 2 0

Вот код:

 #include<stdio.h>

int sudoku[9][9]=
{
    0,0,0,0,0,4,0,0,0,
    0,6,8,0,0,0,5,0,0,
    0,2,0,0,0,0,0,7,6,
    6,0,0,0,0,0,8,9,0,
    0,0,5,2,6,0,0,0,0,
    0,0,0,9,0,0,1,0,0,
    0,0,0,0,0,7,0,5,0,
    0,4,0,0,0,0,0,0,1,
    0,0,0,0,5,1,4,0,0
};
int a[9][9]=
{
    0,0,0,0,0,4,0,0,0,
    0,6,8,0,0,0,5,0,0,
    0,2,0,0,0,0,0,7,6,
    6,0,0,0,0,0,8,9,0,
    0,0,5,2,6,0,0,0,0,
    0,0,0,9,0,0,1,0,0,
    0,0,0,0,0,7,0,5,0,
    0,4,0,0,0,0,0,0,1,
    0,0,0,0,5,1,4,0,0
};
//PRINT SUDOKU
void printSudoku()
{
    int i,j;
    for(i = 0; i < 9; i++) { if(i==3 || i==6) printf("\n");
        for(j = 0; j < 9; j++)    {
            printf("%d",sudoku[i][j]);
            printf(" ");
            if(j>7) printf("\n");
            if(j==2 || j==5) printf("  ");

        }
    }
    printf("\n");
}
//CHECK ROW
int checkRow(int num, int i)    {
    int j,x=1;
    for(j = 0; j < 9; j++)
        if(sudoku[i][j] == num)    return 0;

    return x;
}
//CHECK COLUMN
int checkCol(int num, int j) {
    int i,x=1;
    for(i = 0; i < 9; i++)
        if(sudoku[i][j]==num)    return 0;

    return x;
}

//CHECK SQUARE
int checkSquare(int num, int xj, int yi)
{
    int x=1;
    int i,j;
    for(i = yi; i < yi+3; i++)
        for(j = xj; j < xj+3; j++)
            if(sudoku[i][j]==num)    return 0;

    return x;
}
//MAIN PROGRAM
main()
{
    int i,j,num,row,col;
    int pi,pj,xj,yi,square;

    printSudoku();

    for(i = 0; i < 9; i++)
        for(j = 0; j < 9; j++) {
            if(sudoku[i][j]==0)    {
                num=1;

                do    {
                    if(num>9)    {
                        pi=i;
                        if(j == 0)  {
                            if(i!=0)    {
                                pj=8;
                                pi=i-1;
                            }
                        }
                        else    {
                            pj=j-1;
                        }
                        for(i = pi; i >= 0; i--)
                            for(j = pj; j >= 0; j--)    {
                                pj=8;

                                if(a[i][j]==0 && sudoku[i][j]==9)    {
                                    sudoku[i][j]=0;
                                }
                                else if(a[i][j]==0 && sudoku[i][j]<9)    {

                                    num=sudoku[i][j]+1;
                                    sudoku[i][j]=0;
                                    goto check;
                                }
                            }
                    }
                check:row=checkRow(num,i);
                    col=checkCol(num,j);
                    if(j<3)    xj=0;
                    if(j>2 && j<6) xj=3;
                    if(j>5) xj=6;
                    if(i<3)    yi=0;
                    if(i>2 && i<6) yi=3;
                    if(i>5) yi=6;
                    square=checkSquare(num,xj,yi);
                    if(row==1 && col==1 && square==1)
                        sudoku[i][j]=num;
                    else
                        num++;

                }
                while(row==0 || col==0 || square==0);
            }
        }

    printf("\n");
    printSudoku();

}

Как я уже сказала, Я начинающий программист, поэтому извините, что мой код-это долго и неаккуратно.

Кто-нибудь знает как я могу сделать это быстрее?
Было бы быстрее, если бы я использовал рекурсию?
И также как я могу измерить Реальное время выполнения?



Комментарии
3 ответа

Совет 1

Вместо того checkRow, checkCol и checkSquareЯ предлагаю вам выделить простой массив char в каждой строке, столбце и minisquare:

char visited[10];

Инициализации каждого visited[0], ..., visited[9] к нулю. Далее, когда вы помещаете число в пустую ячейку, пометьте это в три таких "наборов": текущий столбец текущей строки и текущей minisquare. Эта договоренность принесет сложность проверки каждой строке, столбце и minisquare от \$\тета(г)\ долларов \$\тета(1)\$, где$г\$ Ширина/Высота входного судоку борту.

Совет 2

Что касается самого алгоритма, я предлагаю вам использовать рекурсию/откаты. Что позволит очистить ваш код немного, и позволит вам лучше адаптировать его к, скажем, \$4 \4 раза\$ или 16 $\раз 16\$-судоку.

Идея заключается в следующем. Ты походу через доску строк, в каждой строке слева направо. Вы оставляете клетки, которые имеют определенное значение, как это, но вы положили 1 в первую пустую ячейку, и вернуться к следующей ячейке. Если 1 не принадлежит, вы попробуйте 2, 3 и так далее. Как только вы нашли допустимое значение, перейти к следующей пустой ячейке. В какой-то момент может случиться так, чем ни один из номеров подходит. В таком случае вы идете на один шаг назад (откат) и попробовать прирастить Предыдущее значение. Если вы можете перевести из Java, видим это, начиная с серии 163.

3
ответ дан 21 февраля 2018 в 05:02 Источник Поделиться

Быстрее будет идти первым, где у вас меньше возможностей.


  1. рассчитать для каждой пустой клетке как кол можно поставить(проверить по линии, bycolumn и блок)

    1.1 если только одно число в пустую ячейку: вы положили его и обновить таблицу возможностей и дальше, пока у вас есть только одна возможность


  2. если больше одного в одной клетке вы сделать рекурсию для всех возможностей отправки полной копией судоку изменен

О структуре использования:


  • Int [9][9] для судоку

  • Boolean [9][9][9] для возможности

  • Int [9][9] рассчитывать возможности: при изменении ячейки поставить 10, в одной и той же ячейке этой таблицы, поэтому она никогда не была выбрана в качестве любой возможности

  • И количество недостающих клеток, чтобы знать, сколько клеток осталось

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

В то время как вы можете обнаружить более точно возможности. Менее рекурсии и ваша программа будет быстрее. Если нет рекурсии время линейно.

0
ответ дан 22 февраля 2018 в 12:02 Источник Поделиться

Логическое [9][9][9] изначально установлено все верно.

У вас есть 2 в одну ячейку вы кладете ложь в строку и столбец и блок [][][2]

Когда вы проверите все судоку места вы заполнить другую таблицу подсчета правда.

На траверс массива судоку я бы предпочел 2 переменные: одна для столбцов и для блока, так что код будет более читабельным.

-2
ответ дан 22 февраля 2018 в 12:02 Источник Поделиться