Решатель судоку, а не решатель с возвратом

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

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

Если бы кто-нибудь мог помочь мне разработать механику того, как это можно сделать, я был бы очень признателен.


java sudoku
person Simon Jensen    schedule 22.06.2014    source источник
comment
Было бы полезно, если бы мы знали ваш код. Используете ли вы чистый поиск с возвратом (обычно известный как грубая сила) или у вас есть алгоритм логического решения, который использует поиск с возвратом только в крайнем случае?   -  person k_g    schedule 22.06.2014
comment
Если судоку (как и все должно) имеет уникальное решение, решение может быть решено с помощью чистой логики и может быть решено человеком. Так что же вы действительно ищете?   -  person Don Roby    schedule 22.06.2014
comment
Разве вы не можете просто создать случайную матрицу, которая подчиняется правилам судоку, а затем случайно удалить одно число, решить его с помощью бэктрекера, чтобы убедиться, что решение существует и оно уникально, если оно разрешимо, вы удаляете другое и повторяете, пока нет решения или решение не уникально, тогда вы просто сохраняете предыдущую судоку. Я думаю, что это будет O (n ^ 3)?   -  person questing    schedule 22.06.2014
comment
@k_g У меня есть метод решения, который использует стандартный поиск с возвратом (грубая сила), но мне нужен метод с логическим алгоритмом решения, как вы упомянули.   -  person Simon Jensen    schedule 22.06.2014
comment
@DonRoby Дон Роби, да, обычная судоку решаема, но не в том случае, если вы случайно удалили неправильные числа, что делает ее неразрешимой с использованием обычной логики.   -  person Simon Jensen    schedule 22.06.2014
comment
@mancuernita Я сделал случайную матрицу в соответствии с правилами судоку, при этом я беру 50%, 55% и 65% шанс удалить число (в зависимости от сложности), просматривая все числа. Разве возврат, о котором вы говорили, не всегда возвращал решение?   -  person Simon Jensen    schedule 22.06.2014

Ответы (2)


arrow_upward
3
arrow_downward

Огромная коллекция стратегий решения судоку для игроков-людей прекрасно представлена ​​и объяснена на Andrew Stuart. Страница судоку:

**Show Possibles**         
1: Hidden Singles      
2: Naked Pairs/Triples     
3: Hidden Pairs/Triples    
4: Naked Quads     
5: Pointing Pairs      
6: Box/Line Reduction      
**Tough Strategies**  
7: X-Wing      
8: Simple Colouring        
9: Y-Wing      
10: Sword-Fish         
11: XYZ Wing       
**Diabolical Strategies** 
12: X-Cycles       
13: XY-Chain       
14: 3D Medusa      
15: Jelly-Fish         
16: Unique Rectangles      
17: Extended Unique Rect.      
18: Hidden Unique Rect's       
19: WXYZ Wing      
20: Aligned Pair Exclusion         
**Extreme Strategies**    
21: Grouped X-Cycles       
22: Empty Rectangles       
23: Finned X-Wing      
24: Finned Sword-Fish      
25: Altern. Inference Chains   
26: Sue-de-Coq         
27: Digit Forcing Chains       
28: Nishio Forcing Chains  
29: Cell Forcing Chains        
30: Unit Forcing Chains        
31: Almost Locked Sets         
32: Death Blossom      
33: Pattern Overlay Method         
34: Quad Forcing Chains        
**"Trial and Error"** 
35: Bowman's Bingo

Как довольно частый игрок, я бы расценил все, кроме стратегии 11, как «уже неинтересно». Но это, наверное, дело вкуса.

person Axel Kemper    schedule 22.06.2014

arrow_upward
1
arrow_downward

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

You initialize an array with a randomized set of the numbers 1 to 9, 
technically it's easier if you initialize 3 arrays each with 3 length.
You can have these numbers be randomized, thus create a different sudoku.

[1 2 3] [4 5 6] [7 8 9]
Then you shift these:
[7 8 9] [1 2 3] [4 5 6]
[4 5 6] [7 8 9] [1 2 3]

Then you shift the numbers inside the arrays:

[3 1 2] [6 4 5] [9 7 8]
Then you shift the arrays themselves again:
[9 7 8] [3 1 2] [6 4 5]
[6 4 5] [9 7 8] [3 1 2]

Then you shift the numbers inside the arrays:

[2 3 1] [5 6 4] [8 9 7]
Then you shift the arrays again:
[8 9 7] [2 3 1] [5 6 4]
[5 6 4] [8 9 7] [2 3 1]

И у вас будет окончательный набор таблицы судоку:

[1 2 3] [4 5 6] [7 8 9]
[7 8 9] [1 2 3] [4 5 6]
[4 5 6] [7 8 9] [1 2 3]
[3 1 2] [6 4 5] [9 7 8]
[9 7 8] [3 1 2] [6 4 5]
[6 4 5] [9 7 8] [3 1 2]
[2 3 1] [5 6 4] [8 9 7]
[8 9 7] [2 3 1] [5 6 4]
[5 6 4] [8 9 7] [2 3 1]

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

person EpicPandaForce    schedule 22.06.2014
comment
У меня уже есть алгоритм, который может создать любую случайную доску судоку, о которой я ее попрошу, и все они являются действительными досками судоку. - person Simon Jensen; 23.06.2014
comment
О, ладно, я думал, это то, что ты ищешь. Итак, у вас уже была правильная доска, но вам нужен был способ удалить числа и сделать ее разрешимой. Помимо случайного выбора чисел и проверки того, сколько существует решений, и если есть только одно решение, сохраните удаление, если нет, то отмените удаление и попробуйте другое - это единственный способ, который я могу придумать на данный момент. - person EpicPandaForce; 23.06.2014
comment
Также у меня есть метод запуска через доску, удаляющую случайные числа с заданным процентом (например, 50% вероятность удаления числа). Что мне нужно, так это пример или объяснение того, как проверить, является ли сгенерированная головоломка решаемой человеком, что означает, что грубая сила (откат) здесь бесполезна. - person Simon Jensen; 23.06.2014
comment
Кроме какой-то умной итеративной переборки, я не уверен, что вы можете сделать. - person EpicPandaForce; 23.06.2014
comment
Технически, если вы поддерживаете список используемых чисел в заданных ячейках в заданном состоянии и повторяете эти списки для грубой силы, это значительно уменьшает количество попыток, которые вам нужно проверить (с 9 ^ n). - person EpicPandaForce; 27.06.2014