Простой метод решения судоку - PullRequest
Новая
       10

Простой метод решения судоку

3 голосов
/ 21 мая 2011

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

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

Метод состоит в том, чтобы пройти каждую ячейку на доске и заполнить все ячейки, которые имеют только 1 возможность.Повторяйте, пока каждая клетка не заполнится.Очень просто, и вот мой код, можно вернуть int число заполнений: 

public int solveGame() {

/*
 variable possible contains 10 elements, the first element is true if there 
 is one or more possible value to fill in, false otherwise. The remaining 
 elements (1-9) are whether true or false depending on their indexes 
 e.g. possible[3] is true if 3 is a possibility.
*/
boolean[] possible; 

int[] save;
int count;
int numresolve = 0;

while (!isFinished()) {

    for (int i = 0; i < GAMESIZE; i++) {
        for (int j = 0; j < GAMESIZE; j++) {
            possible = new boolean[10];
            possible = getPossible(i,j);
            if (possible[0]) {
                count = 0;
                save = new int[9];
                for (int k = 1; k < 10; k++) {
                    if (possible[k]) {
                        count++;
                        save[count] = k;
                    }
                }
                if (count == 1) {
                    setCell(i,j,save[count]);
                    numresolve++;
                }
            }
        }
    }
}

return numresolve;

}

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

Я знаю, что мне не хватает того, о чем я не могу думать.

Ответы [ 5 ]

3 голосов
/ 21 мая 2011

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

рассмотрим ячейку 1 == {a, b}, ячейку 2 = {a, b}, ячейку 3 = {a, b, c}

ячейки 3 разрешимы, и этот сценарий, скорее всего, произойдет в самом простом судоку, который вы найдете в книге и т. Д.

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

3 голосов
/ 21 мая 2011

Чтобы обнаружить, что вы не можете решить больше ничего с помощью этого подхода, сделайте что-то вроде этого: 

 while (!isFinished()) {
   int prevResolved = numresolve;

   .... // your loop

   if (numresolve == prevResolved) {
     // did not find anything - out of luck, can't solve this board.
     return ...; // numresolve or something to indicate that it failed
   }
}

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

В качестве альтернативы просто установите логическое значение на false в верхней части цикла и установите его на true, когда вы сделаетеизменение на доске.Используйте это, чтобы определить, нашел ли ваш алгоритм что-то или нет (и выручить, если это не так).

2 голосов
/ 21 мая 2011

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

Может случиться, что нет ячейки, у которой есть только одна возможность, поэтому ваш код должен быть разветвлен, вызвав саму функцию снова, используя каждую из двух (или более) возможностей, пока сетка не заполнится полностью.

2 голосов
/ 21 мая 2011

Если вы заполните ячейку (вызвав setCell), вы уменьшите число возможностей для всех других ячеек в той же строке / столбце / блоке. Убедитесь, что ваша программа getPossibile учитывает эти изменения.

Обратите внимание, что некоторые головоломки не могут быть решены с помощью вашей простой стратегии. Могут быть ситуации, когда каждая открытая ячейка допускает более одного значения, но в целом существует уникальное решение.

1 голос
/ 21 мая 2011 
int numresolve = 0;

// this variable will be used to track # of changed cells in each loop
// init to -1 to run loop at least once
// loop can be more elegant if you put the condition at the end
int changed = -1;

// stop loop if no cell changed
while (!isFinished() && changed != 0) {

    // initialize # of changed cells in this loop    
    changed = 0;

    for (int i = 0; i < GAMESIZE; i++) {
        for (int j = 0; j < GAMESIZE; j++) {
            boolean[] possible = getPossible(i,j);
            if (possible[0]) {
                int count = 0;
                int[] save = new int[9];
                for (int k = 1; k < 10; k++) {
                    if (possible[k]) {
                        count++;
                        save[count] = k;
                    }
                }
                if (count == 1) {
                    setCell(i,j,save[count]);
                    numresolve++;
                    changed++;
                }
            }
        }
    }
}
...