Trieda na automatické vyriešenie hry Sudoku
Created: 2008-07-04 - 19:08
SudokuSolver
SudokuSolver.jarTáto trieda poskytuje nejaký ten backend na vytvorenie programu pre automatické vyriešenie hry Sudoku. Zvyčajne sa jedná o "ľahšie a stredne ťažké" hádanky, t.j. neočakávajte vyriešenie Sudoku s predvyplnenými napr. 15 číslami. V podstate malo by to riešiť tie klasické verzie problémy, ktoré zvyčajne nájdete v nedeľnajšej prílohe novín.
Algoritmus prebieha v dvoch fázach: (v podstate sú to klasické metódy riešenia Sudoku)
1. Fáza: Určenie, ktoré čísla možno dosadiť na nevyplnené pozície. V prípade, že na niektorú pozíciu je možné dosadiť len jedno číslo, tak je automaticky dosadená do Sudoku.
2. Fáza: Pre každý riadok/stĺpec/malý štvorec hľadáme takú hodnotu, ktorá sa nachádza iba raz v každej množine dosaditeľných hodnôt pre každé voľné políčko v danom riadku/stĺpci/malom štvorci. V podstate hľadáme hodnotu, ktorá sa neopakuje - t.j. vyskytuje sa iba raz.
3. Fáza: (Už len teoreticky: Ak nefunguje ani prvý ani druhý spôsob, tak nám neostáva nič iné iba "tipovať" hodnoty, t.z. nejaký ten upravený backtrack alebo pod.)
Takže najprv si vytvoríme nejakú triedu, ktorá bude spracovávať sudoku z textového súboru a v podstate bude ho reprezentovať (2D pole)
package SudokuSolver;
import java.io.File;
import java.util.Scanner;
public class Sudoku {
int[][] pole = new int[10][10];
public Sudoku(File f){
//konstruktor nacitava zo suboru
try{
Scanner s = new Scanner(f);
for(int i=1;i<10;i++){
for(int j=1;j<10;j++){
pole[i][j]=s.nextInt();
}
}
}
catch(Exception e){
e.printStackTrace();
}
}
public Sudoku(int[][] pole){
this.pole = pole;
}
@Override
public String toString(){
String vystup = "";
for(int i=1;i<10;i++){
for(int j=1;j<10;j++){
vystup += pole[i][j];
}
vystup += "\n";
}
return vystup;
}
public int zistiPocetCisel(){
int count = 0;
for(int i=1;i<10;i++){
for(int j=1;j<10;j++){
if(pole[i][j]!=0)
count++;
}
}
return count;
}
}
package SudokuSolver;
import java.util.*;
public class SudokuSolver {
public static Sudoku solveSudoku(Sudoku vstupneSudoku) {
while (!testSudoku(vstupneSudoku)) {
Map> pomocnaMapa = new TreeMap>();
fazaJedna(vstupneSudoku, pomocnaMapa);
if (testSudoku(vstupneSudoku))
return vstupneSudoku;
fazaDva(vstupneSudoku, pomocnaMapa);
if (testSudoku(vstupneSudoku))
return vstupneSudoku;
}
return null;
}
private static void fazaDva(Sudoku vstupneSudoku,
Map> pomocnaMapa) {
// Druha faza - hlada take cisla z mnoziny dosaditelnych miest (z fazy 1)
// ktore sa nachadzaju v danom riadku/stlpci/malom stvorci iba raz
//prehladaj stlpce
for (int i = 1; i < 10; i++) {
Map jednotlivci = new TreeMap();
for (int j = 1; j < 10; j++) {
HashSet cisla = pomocnaMapa.get(i + "." + j);
for (Iterator iter = cisla.iterator(); iter.hasNext();) {
int element = ((Integer) iter.next()).intValue();
if (!jednotlivci.containsKey(element))
jednotlivci.put(element,i + "." + j);
else
jednotlivci.put(element,"");
}
}
for (Map.Entry k : jednotlivci.entrySet()) {
if (!k.getValue().equals("")) {
int a = Integer.parseInt(String.valueOf(k.getValue()
.charAt(0)));
int b = Integer.parseInt(String.valueOf(k.getValue()
.charAt(2)));
vstupneSudoku.pole[a][b] = k.getKey();
}
}
}
// prehladaj riadky
for (int j = 1; j < 10; j++) {
Map jednotlivci = new TreeMap();
for (int i = 1; i < 10; i++) {
HashSet cisla = pomocnaMapa.get(i + "." + j);
for (Iterator iter = cisla.iterator(); iter.hasNext();) {
int element = ((Integer) iter.next()).intValue();
if (!jednotlivci.containsKey(element))
jednotlivci.put(element,i + "." + j);
else
jednotlivci.put(element,"");
}
}
for (Map.Entry k : jednotlivci.entrySet()) {
if (!k.getValue().equals("")) {
int a = Integer.parseInt(String.valueOf(k.getValue()
.charAt(0)));
int b = Integer.parseInt(String.valueOf(k.getValue()
.charAt(2)));
vstupneSudoku.pole[a][b] = k.getKey();
}
}
}
// prehladaj male stvorce
int x = 0;
int y = 0;
while (y < 4) {
while (x < 4) {
Map jednotlivci = new TreeMap();
for (int i = 1; i < 4; i++) {
for (int j = 1; j < 4; j++) {
HashSet cisla = pomocnaMapa.get(i + "." + j);
for (Iterator iter = cisla.iterator(); iter.hasNext();) {
int element = ((Integer) iter.next()).intValue();
if (!jednotlivci.containsKey(element))
jednotlivci.put(element,i + "." + j);
else
jednotlivci.put(element,"");
}
}
}
for (Map.Entry k : jednotlivci.entrySet()) {
if (!k.getValue().equals("")) {
int a = Integer.parseInt(String.valueOf(k.getValue()
.charAt(0)));
int b = Integer.parseInt(String.valueOf(k.getValue()
.charAt(2)));
vstupneSudoku.pole[a][b] = k.getKey();
}
}
x = x + 3;
}
x = 0;
y = y + 3;
}
}
private static void fazaJedna(Sudoku vstupneSudoku,Map> pomocnaMapa) {
// Prva faza
// Snazi sa vyluci hodnoty, ktore nemozno na volne pozicie dosadit.
// Ak sa na niektoru poziciu hodi len jedno cislo, tak ho dosadi a
// prehodnoti pozicie.
boolean existujuMiestaSJedinouDosaditelnouCifrou = true;
int notnull = 0;
while (existujuMiestaSJedinouDosaditelnouCifrou) {
for (int i = 1; i < 10; i++) {
for (int j = 1; j < 10; j++) {
if (vstupneSudoku.pole[i][j] == 0) {
pomocnaMapa.put(i + "." + j, zistiVolnePozicie(
vstupneSudoku, i, j));
}
if (vstupneSudoku.pole[i][j] != 0) {
notnull++;
pomocnaMapa.put(i + "." + j, new HashSet());
}
}
}
existujuMiestaSJedinouDosaditelnouCifrou = false;
for (int i = 1; i < 10; i++) {
for (int j = 1; j < 10; j++) {
if (!pomocnaMapa.get(i + "." + j).isEmpty()
&& pomocnaMapa.get(i + "." + j).size() == 1) {
vstupneSudoku.pole[i][j] = pomocnaMapa.get(i + "." + j)
.iterator().next();
existujuMiestaSJedinouDosaditelnouCifrou = true;
}
}
}
//System.out.println(notnull);
notnull = 0;
}
}
private static HashSet zistiVolnePozicie(Sudoku s, int x, int y) {
HashSet volnePozicie = new HashSet();
for (int i = 1; i < 10; i++) {
volnePozicie.add(i);
}
// Odstranuje postupne cisla, ktore sa uz nachadzaju v riadkoch,
// stlpcoch a akt. stvorci
//
// skontroluj riadok
for (int i = 1; i < 10; i++) {
if (volnePozicie.contains(s.pole[i][y])) {
volnePozicie.remove(s.pole[i][y]);
}
}
// skontroluj stlpec
for (int i = 1; i < 10; i++) {
if (volnePozicie.contains(s.pole[x][i])) {
volnePozicie.remove(s.pole[x][i]);
}
}
if (x < 4)
x = 0;
else if (x > 3 && x < 7)
x = 3;
else
x = 6;
if (y < 4)
y = 0;
else if (y > 3 && y < 7)
y = 3;
else
y = 6;
// skontroluj maly stvorec
for (int i = 1; i < 4; i++) {
for (int j = 1; j < 4; j++) {
if (volnePozicie.contains(s.pole[x + i][y + j]))
volnePozicie.remove(s.pole[x + i][y + j]);
}
}
return volnePozicie;
}
public static boolean testSudoku(Sudoku vstupneSudoku) {
HashSet test = new HashSet();
// skontroluj riadky
for (int i = 1; i < 10; i++) {
for (int j = 1; j < 10; j++) {
if (!test.contains(vstupneSudoku.pole[i][j]))
test.add(vstupneSudoku.pole[i][j]);
else {
return false;
}
}
test.clear();
}
// skontroluj stlpce
for (int i = 1; i < 10; i++) {
for (int j = 1; j < 10; j++) {
if (!test.contains(vstupneSudoku.pole[j][i]))
test.add(vstupneSudoku.pole[j][i]);
else {
return false;
}
}
test.clear();
}
// skontroluj male stvorce
int x = 0;
int y = 0;
while (y < 4) {
while (x < 4) {
for (int i = 1; i < 4; i++) {
for (int j = 1; j < 4; j++) {
if (!test.contains(vstupneSudoku.pole[x + i][y + j]))
test.add(vstupneSudoku.pole[x + i][y + j]);
else {
return false;
}
}
}
test.clear();
x = x + 3;
}
x = 0;
y = y + 3;
}
return true;
}
}
6 7 0 8 0 0 0 9 0 0 0 8 0 0 4 0 3 0 3 0 0 6 0 1 8 0 5 2 0 0 0 4 0 0 7 0 1 5 0 0 3 0 0 4 9 0 4 0 9 0 6 0 0 3 7 0 3 4 0 2 0 0 1 0 8 0 3 0 0 4 0 0 0 2 0 0 0 9 0 8 7To je všetko :-).