Sudoku solver problem

Рейтинг: 2Ответов: 1Опубликовано: 12.11.2014

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

class Game
{
    private int[,] puzzle = new int[9, 9];

    public bool isAvailable(int row, int col, int num)
    {
        int rowStart = (row / 3) * 3;
        int colStart = (col / 3) * 3;

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

    public bool fillSudoku(int row, int col)
    {

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

                        if (fillSudoku(row, col)) return true;
                        else puzzle[row,col] = 0;
                    }
                }
            }
            return false;
        }
        else return true;
    }

    public void checkSolutions()
    {
        if (!fillSudoku(0, 0))
        {
            Console.Write("\n\nNow Solutions\n\n");
        }
    }

}

Вот пример, там, где зацикливание:

0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 
0 0 0 0 5 5 0 0 0 
0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0

Полный код: https://dotnetfiddle.net/YoyWdN.

Ответы

▲ 1

Такое судоку нельзя решить. Рекомендую в самом начале сделать простенькую верификацию правильности входных данных. Если они неверные, то даже не пытаться решать судоку.