Судоку Solver в C

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

#include <stdio.h>

int isAvailable(int puzzle[][9], int row, int col, int num)
{
    int rowStart = (row/3) * 3;
    int colStart = (col/3) * 3;
    int i, j;

    for(i=0; i<9; ++i)
    {
        if (puzzle[row][i] == num) return 0;
        if (puzzle[i][col] == num) return 0;
        if (puzzle[rowStart + (i%3)][colStart + (i/3)] == num) return 0;
    }
    return 1;
}

int fillSudoku(int puzzle[][9], int row, int col)
{
    int i;
    if(row<9 && col<9)
    {
        if(puzzle[row][col] != 0)
        {
            if((col+1)<9) return fillSudoku(puzzle, row, col+1);
            else if((row+1)<9) return fillSudoku(puzzle, row+1, 0);
            else return 1;
        }
        else
        {
            for(i=0; i<9; ++i)
            {
                if(isAvailable(puzzle, row, col, i+1))
                {
                    puzzle[row][col] = i+1;
                    if((col+1)<9)
                    {
                        if(fillSudoku(puzzle, row, col +1)) return 1;
                        else puzzle[row][col] = 0;
                    }
                    else if((row+1)<9)
                    {
                        if(fillSudoku(puzzle, row+1, 0)) return 1;
                        else puzzle[row][col] = 0;
                    }
                    else return 1;
                }
            }
        }
        return 0;
    }
    else return 1;
}

int main()
{
    int i, j;
    int puzzle[9][9]={{0, 0, 0, 0, 0, 0, 0, 9, 0},
                      {1, 9, 0, 4, 7, 0, 6, 0, 8},
                      {0, 5, 2, 8, 1, 9, 4, 0, 7},
                      {2, 0, 0, 0, 4, 8, 0, 0, 0},
                      {0, 0, 9, 0, 0, 0, 5, 0, 0},
                      {0, 0, 0, 7, 5, 0, 0, 0, 9},
                      {9, 0, 7, 3, 6, 4, 1, 8, 0},
                      {5, 0, 6, 0, 8, 1, 0, 7, 4},
                      {0, 8, 0, 0, 0, 0, 0, 0, 0}};

    if(fillSudoku(puzzle, 0, 0))
    {
        printf("\n+-----+-----+-----+\n");
        for(i=1; i<10; ++i)
        {
            for(j=1; j<10; ++j) printf("|%d", puzzle[i-1][j-1]);
            printf("|\n");
            if (i%3 == 0) printf("+-----+-----+-----+\n");
        }
    }
    else printf("\n\nNO SOLUTION\n\n");

    return 0;
}

Тестирование:

$ ./SudokuSolver
+-----+-----+-----+
|7|4|8|6|3|5|2|9|1|
|1|9|3|4|7|2|6|5|8|
|6|5|2|8|1|9|4|3|7|
+-----+-----+-----+
|2|6|5|9|4|8|7|1|3|
|8|7|9|1|2|3|5|4|6|
|3|1|4|7|5|6|8|2|9|
+-----+-----+-----+
|9|2|7|3|6|4|1|8|5|
|5|3|6|2|8|1|9|7|4|
|4|8|1|5|9|7|3|6|2|
+-----+-----+-----+
36 голосов | спросил syb0rg 15 SunEurope/Moscow2013-12-15T21:47:41+04:00Europe/Moscow12bEurope/MoscowSun, 15 Dec 2013 21:47:41 +0400 2013, 21:47:41

2 ответа


18

Ваше решение короткое и сладкое. Надеюсь, мой ответ будет слишком с тех пор, как я покрыл большую часть того, что видел. :)

  1. Возможно, solveSudoku лучше передаст тот факт, что головоломка разрешает . fillSudoku звучит как функция, которая заполняет исходные позиции из файла или строки или что-то в этом роде.

  2. Вы можете сократить значение «Ячейка заполнена», сбросив != 0 для максимальной C-ness:

    if(puzzle[row][col])
    
  3. Вы дублируете код, который продвигает индексы ячеек в fillSudoku: один раз, если ячейка уже заполняется и снова, когда вы добавляете следующее предположение. Вы можете удалить последнее и просто передать те же индексы ячеек, поскольку вы сначала устанавливаете значение ячейки.

    if(isAvailable(puzzle, row, col, i+1))
    {
        puzzle[row][col] = i+1;
    
        if(fillSudoku(puzzle, row, col) return 1;
        else puzzle[row][col] = 0;
    }
    
ответил David Harkness 15 SunEurope/Moscow2013-12-15T23:15:23+04:00Europe/Moscow12bEurope/MoscowSun, 15 Dec 2013 23:15:23 +0400 2013, 23:15:23
16

Мне бы очень хотелось пройти через всевозможные вещи, которые этот код плохо делает ... но он короткий, сладкий и работает, и это само по себе говорит с определенной степенью сложности.

Это решение очень легкое на всех ресурсах, отличных от циклов процессора, и оно не слишком много переносит на стек. В целом, это аккуратно и хорошо структурировано.

Несколько незначительных критических замечаний:

  • в вашем методе isAvailable(), который вы объявляете j, но не используете его.
  • Необычный механизм модуляции /деления (puzzle[rowStart + (i%3)][colStart + (i/3)] == num) для проверки блока - это просто фантазия. .. и, вероятно, нужен какой-то комментарий. Я работал над математикой, и я вижу, что это правильно, но какая-то помощь там была бы полезной.
  • Мне не нравится, что вы проверяете значения несколько раз в isAvailable(), но я должен признать, что я не вижу хорошего способа избежать дублирования без добавления еще более дорогой сложности. По моим расчетам вы дважды проверяете 4 значения и тройную проверку 1. Это 5/27 проверок избыточно. Как я уже сказал, я думаю, что избежать этих проверок будет более дорогостоящим, чем избыточность.
  • в вашем методе fillSudoku, вы объявляете i и используете его как for(i=0; i<9; ++i) , Поскольку в этом случае i на самом деле не является индексом для какого-либо массива или простым ограничителем цикла, но на самом деле это головоломная цифра, вы должны сделать две вещи:
    1. переименуйте его как нечто вроде digit
    2. измените цикл: for(digit=1; digit<=9; ++digit), а затем вы можете удалить все избыточные операции +1 вы делаете внутри цикла (например, isAvailable(puzzle, row, col, i+1))
ответил rolfl 15 SunEurope/Moscow2013-12-15T22:32:41+04:00Europe/Moscow12bEurope/MoscowSun, 15 Dec 2013 22:32:41 +0400 2013, 22:32:41

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132