Creazione di un risolutore di sudoku efficiente

Question

Sì, so che non è una novità e ci sono già molte domande là fuori (ha persino il suo tag), ma mi piacerebbe creare un risolutore di Sudoku in Java esclusivamente allo scopo di mi sto allenando a scrivere codice più efficiente.

Probabilmente il modo più semplice per farlo in un programma è avere un sacco di cicli di analisi per ogni colonna e riga, raccogliere i valori possibili di ogni cella, quindi eliminare le celle con una sola possibilità (che contengano solo 1 numero, o sono l'unica cella nella loro riga/colonna che contiene questo numero) finché non si ha un puzzle risolto. Naturalmente, un pensiero puro dell'azione dovrebbe sollevare una bandiera rossa nella mente di ogni programmatore.

Quello che sto cercando è la metodologia per risolvere il problema di questo ventoso nel modo più efficiente possibile (si prega di cercare di non includere troppo codice - voglio capire quella parte, me stesso).

Voglio evitare algoritmi matematici se possibile - quelli sarebbero troppo facili e al 100% non è il mio lavoro.

Se qualcuno fosse in grado di fornire un processo di pensiero efficiente, passo dopo passo, per risolvere un puzzle di Sudoku (sia da parte di un essere umano che di un computer), sarei molto felice :). Sto cercando qualcosa di vago (quindi è una sfida), ma abbastanza informativo (quindi non sono totalmente perso) per farmi iniziare.

Molte grazie,

Justian Meyer

EDIT:

Guardando il mio codice, ho avuto modo di pensare: che cosa sarebbe alcune delle possibilità per la memorizzazione di questi stati solving (vale a dire il Griglia Sudoku). Vengono in mente array 2D e array 3D. Quale potrebbe essere la migliore? Il 2D potrebbe essere più facile da gestire dalla superficie, ma gli array 3D fornirebbero anche il numero "box"/"cage".

EDIT:

Nevermind. Vado con un array 3D.

Answer 1

Dipende da come si definisce efficiente.

È possibile utilizzare un metodo forza bruta, che ricerca in ogni colonna e riga, raccoglie i valori possibili di ogni cella, quindi elimina le celle con una sola possibilità.

Se le celle rimangono con più di una possibilità, salva lo stato del puzzle, scegli la cella con il minor numero di possibilità, scegli una delle possibilità e cerca di risolvere il puzzle. Se la possibilità che hai scelto porta a una contraddizione del puzzle, ripristina lo stato del puzzle salvato, torna alla cella e scegli una diversa possibilità. Se nessuna delle possibilità nella cella che hai scelto risolve il puzzle, scegli la prossima cella con il minor numero di possibilità. Passa attraverso le restanti possibilità e celle fino a quando non avrai risolto il puzzle.

Tentare di risolvere il puzzle significa cercare attraverso ogni colonna e riga, raccogliendo i possibili valori di ogni cella, quindi eliminando le celle con una sola possibilità. Quando tutte le celle vengono eliminate, hai risolto il puzzle.

È possibile utilizzare un metodo logico/matematico, in cui il codice prova diverse strategie finché il puzzle non viene risolto. Cerca su Google con "strategie sudoku" per vedere le diverse strategie. Usando metodi logici/matematici, il tuo codice può "spiegare" come è stato risolto il puzzle.

Answer 2

Quando ho creato il mio, ho pensato che potevo risolvere ogni tavola usando una serie di regole senza fare alcun backtracking. Ciò si è dimostrato impossibile in quanto anche i puzzle che prendono di mira giocatori umani potrebbero richiedere alcune ipotesi.

Così ho iniziato con l'implementazione delle "regole" di base per risolvere un enigma, cercando di trovare la prossima regola da implementare che consentirebbe la risoluzione di dove si è fermato l'ultima volta. Alla fine, sono stato costretto ad aggiungere un algoritmo ricorsivo di forzatura bruta, ma la maggior parte degli enigmi viene effettivamente risolta senza l'uso di quello.

Ho scritto un post sul blog del mio risolutore di sudoku. Basta leggere la sezione "L'algoritmo" e avrete una buona idea di come sono andato a riguardo.

http://www.byteauthor.com/2010/08/sudoku-solver/

Answer 3

Se una persona bisogno di un Android implementazione di riferimento, ho scritto una soluzione che utilizza l'algoritmo dal post di cui sopra.

completa codice open-source qui: https://github.com/bizz84/SudokuSolver

Inoltre, questa soluzione carica di Sudoku Puzzle in formato JSON da un server Web e messaggi i risultati.

Answer 4

Si dovrebbe pensare a ridurre il Problema di Sudoku a SATisfiability problem.

Questo metodo eviterà di pensare anche a mathematically ma a più logically sull'IA.

Il passo dopo passo obiettivo è fondamentalmente:

* Find all the constraints that a Sudoku has. (line, column, box). 
* Write these constraints as boolean constraints. 
* Put all these constraints in a Boolean Satisfiability Problem. 
* Run a SAT solver (or write your own ;)) on this problem. 
* Transform the SAT solution into the solution of the initial Sudoku. 

E 'stato fatto da Ivor Spence utilizzando SAT4J e si può trovare l'applet Java del suo lavoro qui: http://www.cs.qub.ac.uk/~I.Spence/SuDoku/SuDoku.html.

È anche possibile scaricare direttamente il codice Java dal sito Web SAT4J per vedere come appare: http://sat4j.org/products.php#sudoku.

E infine, il grande vantaggio di questo metodo è: è possibile risolvere N*N Sudokus, e non solo il tipico 9*9, che è, penso, molto più impegnativo per un AI :).