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

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

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

Метод состоит в том, чтобы пройти по каждой ячейке на доске и заполнить все ячейки, в которых есть только одна возможность. Повторяйте, пока все ячейки не будут заполнены. Очень просто, и вот мой код, можно сделать return 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 возможности, что невозможно для завершения цикла.

Я знаю, что упускаю то, о чем не могу думать.


java algorithm sudoku
person Community    schedule 21.05.2011    source источник
comment
Не все головоломки судоку можно решить, просто заполнив квадраты с одной возможностью.   -  person ShreevatsaR    schedule 21.05.2011
comment
конечно, но я уже пробовал довольно много простых игр :)   -  person    schedule 21.05.2011
comment
Обратите внимание, что как только ячейка позволяет использовать все девять чисел, ваше значение count будет 9, и, таким образом, вы получаете доступ к элементу массива save[9], который не существует (сохранение было инициализировано как int[9]).   -  person Howard    schedule 21.05.2011
comment
Хорошо, я могу int [] save = int [10], но это все равно не связано с моим вопросом :)   -  person    schedule 21.05.2011
comment
@Tris Le: обычный алгоритм поиска с возвратом очень короткий и его совсем не сложно написать, и это будет очень интересный эксперимент.   -  person SyntaxT3rr0r    schedule 21.05.2011
comment
Всем привет, я решил алгоритм, проблема не в этом методе, а потому, что я забыл отфильтровать возможность по квадрату 3x3. Очень ценю вашу помощь, поэтому я проголосую за всех, кто пытался мне помочь :)   -  person    schedule 23.05.2011

Ответы (4)


arrow_upward
3
arrow_downward

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

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

person Mat    schedule 21.05.2011
comment
Ваше решение используется для определения возможности решения (сложных) игр. Мой метод нацелен на решение очень простых игр, которые проверены на то, чтобы считаться очень легкими :) Я предполагаю, что игры могут быть решены после цикла. Однако они этого не сделали - person ; 21.05.2011
comment
Я не понимаю: вы говорите, что вводите игровую доску, о которой вы точно знаете, что она разрешима, и ваш решатель не возвращается? Если это так, то как вы убедились, что алгоритм действительно способен их решать? Если головоломки не являются действительно тривиальными, это сделать непросто. - person Mat; 21.05.2011

arrow_upward
3
arrow_downward

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

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

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

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

person Yaur    schedule 21.05.2011

arrow_upward
2
arrow_downward

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

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

person Howard    schedule 21.05.2011
comment
Я уже проверил, getPossible () по-прежнему возвращает правильный ответ для возможных вариантов. - person ; 21.05.2011
comment
@Tris Le Я имел в виду это желание. Либо ваш getPossible не учитывает ограниченные возможности, либо нет решения головоломки с вашим алгоритмом. Используйте отладчик или распечатайте состояние всех ячеек (т.е. возвращаемый массив getPossible) и проверьте вручную, какой из двух случаев применим. - person Howard; 21.05.2011
comment
На самом деле у меня есть 1 способ распечатать текущее состояние игры, я использовал его для тестирования метода выше, поэтому я знаю, что это не проблема с getPossible. - person ; 21.05.2011
comment
@Tris Le И, таким образом, ваша головоломка неразрешима (и цикл не может завершиться). - person Howard; 21.05.2011
comment
Нет, это разрешимо :) В Интернете есть сотни доступных решателей, чтобы я мог проверить, разрешимо это или нет :) Я думаю, проблема в моем методе выше. - person ; 21.05.2011
comment
@Tris Le С неразрешимым я имел в виду, что ваша простая схема не позволяет решить эту головоломку (как и другие, упомянутые, есть головоломки с уникальными решениями, где ваш алгоритм не работает). Если нет ячейки с уникальным номером (который вы подтвердили только что), но не все ячейки заполнены, тогда дело обстоит именно так. - person Howard; 21.05.2011
comment
@Howard: У меня такое чувство, что исходный постер этого не понимает и отказывается принимать ваши логические мысли. - person Hovercraft Full Of Eels; 21.05.2011
comment
@Hovercraft Full Of Eels: Всем нужно время, чтобы подумать, и у меня тоже есть свои логические мысли, я точно знаю, что он пытался мне объяснить, но проблема не в этом диапазоне логики, поэтому ваш комментарий не очень логичен поскольку он не охватывает все аспекты ситуации. @Howard: большое спасибо за ваш ответ, я все равно решил эту проблему, это была моя ошибка, а не проблема с алгоритмом :) См. Мой комментарий о том, почему пост, но проголосовали за. - person ; 23.05.2011
comment
@BeingSimpler Пожалуйста. Я буду рад, если смогу помочь вам найти проблему, хотя и косвенно ;-) - person Howard; 23.05.2011

arrow_upward
2
arrow_downward

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

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

person BFil    schedule 21.05.2011
comment
Я знаю, что вы имеете в виду под рекурсией, но в данном случае не думаю, что это отличается от метода, который я использую сейчас. Не могли бы вы дать более конкретный ответ? - person ; 21.05.2011
comment
С рекурсивной функцией было бы легче разветвлять код, чтобы обрабатывать моменты, когда все оставшиеся ячейки имеют 2 или более возможностей. Ваш код не обрабатывает такие случаи, и даже если бы вы могли соответствующим образом изменить его, ваш код, скорее всего, стал бы беспорядочным .. Лучше проще = D - person BFil; 21.05.2011