Sudoku Cheat-Prog.

Elderan · Aug 9, 2006

Hallo,
ich denke die meisten hab schon mal was von Sudoku gehört, und wissen wie man es spielt.
Für alle 'Unwissenden': Wikipedia

So für alle die Ungeduldig sind, wäre es schön ein 'Cheat' Programm zu schreiben.
Dies ist eigentlich eine sehr schöne Aufgabe, und hört sich am Anfang schwerer an, als es ist.

Aufgabe
Also der User gibt seine Zahlen der Sudoku-Vorlage ein, am besten per Interface, sonst kann man dies aber z.B. fest im Source Code verankern.
Der Computer soll dann ermitteln, was man in die freien Felder eintragen muss, um das Soduko zu lösen, und am Ende das Ergebnis ausgeben.

Evt. Erweiterung:
Generieren von eindeutigen Sodukos, bei dem der User den Schwierigkeitsgrad bestimmen kann.

Man kann hierbei die Backtracking-Methode verwenden.

Allgemeine Sachen:
Fertige Programme können ein vorgegebenes Sudoku in wenigen Sekunden knacken, also ist der Algorithmus nicht extrem Zeitintensiv, und sehr viele Code-Zeilen sind es auch nicht (der Algorithmus zum Lösen braucht ca. 30 Zeilen).
Aber die Theorie dahinter ist eigentlich ganz intressant.

Mehr zu Backtracking

Sven · Aug 9, 2006

Man muss es ja nicht zum Cheaten verwenden, je nach dem kann man es ja auch als "Lösungsvergleich" nehmen.

Hört sich auf jeden Fall interessant an

lagalopex · Aug 9, 2006

Hmm... genau so eine Aufgabe hab ich Xalon geschickt... mit der möglichen Erweiterung zum generieren eines (eindeutigen) Rätsels... (eine Lösung hab ich auch schon, werde aber noch warten) =)

LX · Aug 9, 2006

Ich hab vor ein paar Monaten mal eine Sudoku-Klasse in PHP für Sudokus beliebiger Größe geschrieben, die auch eine Lösungsmethode enthält. Darin sind mehrere Algorithmen implementiert, die versuchen das Ding logisch aufzulösen sowie auch ein Trial&Error-Mechanismus, falls man mit Logik allein nicht weiter kommt. Eine Demo des ganzen kann man hier angucken

Es ist allerdings nicht zu empfehlen, die Trial&Error-Methode als einzige anzuwenden, die ist ziemlich ressourcenfressend, da sie für jeden Versuch eine Kopie des aktuellen Sudokus anlegt, und dauert auch im Vergleich zu einer Kombination mit den anderen Methoden erheblich länger (bis zum Script-Timeout, den ich aus naheliegenden Gründen dafür nicht deaktivieren wollte *g).

lagalopex · Aug 9, 2006

Original von LX
Es ist allerdings nicht zu empfehlen, die Trial&Error-Methode als einzige anzuwenden, die ist ziemlich ressourcenfressend, da sie für jeden Versuch eine Kopie des aktuellen Sudokus anlegt, und dauert auch im Vergleich zu einer Kombination mit den anderen Methoden erheblich länger (bis zum Script-Timeout, den ich aus naheliegenden Gründen dafür nicht deaktivieren wollte *g).

Meine Lösung in C++ braucht etwa 5 ms (AMD64 3700+) für das Bsp bei Wikipedia, wobei aber auch keine Kopien benutzt werden (müssen).

NULL!=NULL · Aug 9, 2006

dann zeig uns die doch mal

ich habe shcon mal versucht ein lösungs algo für koruko (oder wie das heißt und nein ich meine nicht soduko!!) herzustellen bin aber gescheitert... :-(

LX · Aug 9, 2006

Original von lagalopex
Meine Lösung in C++ braucht etwa 5 ms (AMD64 3700+) für das Bsp bei Wikipedia, wobei aber auch keine Kopien benutzt werden (müssen).

Is' ja irre *g

Einfaches Doubletten-streichen mit meiner PHP-Klasse braucht dafür 33ms auf einem Athlon 2400+.

Mein Schwerpunkt bei der Klasse lag bei den übrigen Algorithmen, die möglichst intelligent vorgehen sollten, nicht beim stupiden ausprobieren. Das hab ich nur noch mit reingenommen, da es gelegentlich ja mal vorkommen kann, dass ein Sudoku allein durch Logik nicht lösbar ist.

Elderan · Aug 9, 2006

Hallo,
@LX: Bei solchen Sachen ist PHP eh super langsam, um den Faktor 1000 bis xxxx...

Guter Vergleich: Ackermann-Funktion mit n = 3 und m = 12

In C ca. 22 Sek, in PHP bricht der Script vorzeitig (zumindest bei mir):

hab

PHP:

<?php
set_time_limit(0);

$start = time();
$n = 3;


for($m=0;$m<=12;$m++)   
      $x = ack($n,$m);
    

$ende = time();

echo "Dauer: ".($ende-$start);

function ack($m, $n)
	{	
      $x=0;

   if($m != 0)
      {
      if($n == 0)
         {
         $x=ack($m-1,1);
         }
      else
         {
         $x = ack($m-1, ack($m, $n - 1));
         }
      }
   else
      {
      $x= $n+1;
      }
   return $x;

   }

?>

Vielleicht gehts woanders.

lagalopex · Aug 10, 2006

Mit n = 3 und m = 12 braucht C++ 7,2 Sekunden und PHP bricht mit einem Segfault ab.
Verkürzt man auf n = 3 und m = 10 braucht C++ nur noch 0.49 Sekunden und PHP 140 Sekunden. (Was etwa Faktor 285,7 entspricht.)

@NULL!=NULL: koruko kenn ich nicht und google bringt mich da auch nicht weiter. Worum geht es denn?

LX · Aug 10, 2006

Ich bin mir dessen bewusst, mit PHP sicherlich keinen Geschwindigkeitsrekord aufzustellen, darum ging's mir auch nicht. Also bitte wieder zum Thema "Sudoku-Solver" zurück und nicht "Programmiersprache X vs. PHP"

elite-noob · Aug 15, 2006

wollte nur mal so nebenbei fragen ob diese aufgabe einer von euch zufällig so programmiert hat das man zahlen selber vorgeben kann!?

ich habe mir von bild am sonntag (bitte jetzt nichts dazu sagen) ein sudoku aufs handy geholt und bis auf zwei alles durchbekommen, aber diese zwei bekommt einfach keiner gelöst daher wollte ich wissen ob wir alle zu doof oder das sudoku unlösbar ist!

lange reder kurzer sinn, hat des einer ja oder nein

christian

adrian90 · Aug 15, 2006

Eben, auf dieser PHP Seite kannst du ja die Zahlen angeben. Die 0 steht dafür, dass nichts vorhanden ist. Und du fängst die Zahlen von oben links nach rechts unten an anzugeben.

elite-noob · Aug 16, 2006

ups, danke, war z war auf der website, hatte aber das lösungsprinzip net ganz verstanden, nach genauen lesen dann schon *schäm*

christian

lagalopex · Aug 17, 2006

Wenn ich es richtig sehe, gibt es bisher nur eine Lösung in PHP. Es würde mich mal interessieren, ob noch jemand and dieser Aufgabe arbeitet oder schon alle aufgegeben haben.

mig · Aug 17, 2006

bin mehr oder weniger noch am Überlegen wie man das geschickt in Java anstellen könnte

Corni · Aug 17, 2006

Wer mit der Umsetzung nicht weiter kommt, kann sich ja mal den Quellcode von ksudoku (ziemlich cooles proggi) ankuckn....

gruß Corni

Boar · Aug 18, 2006

Ja, die Aufgabe hört sich gut an. Ich werd mich an einer Java-Lösung versuchen.

Gruß, Boar

lagalopex · Aug 21, 2006

Code:

#include <iostream>

/*
Beispiele (eindeutig):
000000000070040010301506408000000000060010040105709803000000000030070020204805709
000105000009060400060000070400010003050402010600030004020000050003090800000206000
000004710080300950000090000307000800006000037050020000000970502400008000090040080
090000002060280070700000030020005000000400009078009600680000005100003040000000300
020900040003014007006005800400560000300000000000102050000006008057000100080000300
*/


using namespace std;

void print_table(short *num)
{
	for(int i = 0 ; i < 81 ; i++) {
		if(num[i])
			cout << num[i];
		else
			cout << " ";
		if(i % 9 == 8) {
			cout << endl;
			if(i % 27 == 26)
				cout << endl;
		}
		else if (i % 3 == 2)
			cout << "  ";
		else
			cout << " ";
	}
}

void crack(short *num, const int pos)
{
	static int number = 0;
	if(pos == 81) {
		cout << ++number << ". solution:" << endl;
		print_table(num);
	}
	else if(num[pos])
		crack(num, pos+1);
	else {
		short a = (pos / 9) * 9, b = pos % 9, c, d, e, i;
		for(i = 1 ; i <= 9 ; i++) {
			for(d = 0 ; d < 9 ; d++) { // horizontal
				if(num[d + a] == i) {
					d = -1;
					break;
				}
			}
			if(d == -1)
				continue;
			for(d = 0 ; d < 9 ; d++) { // vertikal
				if(num[b + d * 9] == i) {
					d = -1;
					break;
				}
			}
			if(d == -1)
				continue;
			c = pos - pos % 3 - (pos / 9 % 3) * 9; // Block
			for(d = 0 ; d < 3 ; d++) {
				for(e = 0 ; e < 3 ; e++) {
					if(num[c + d + e * 9] == i) {
						d = -1;
						break;
					}
				}
				if(d == -1)
					break;
			}
			if(d == -1)
				continue;
			num[pos] = i;
			crack(num, pos + 1);
		}
		num[pos] = 0;
	}
}

int main(int argc, char *argv[])
{
	short num[81];
	int i;
	if(argc != 2 || strlen(argv[1]) != 81) {
		cerr << "usage: " << argv[0] << " [81 digits]" << endl;
		return(1);
	}

	for(i = 0 ; i < 81 ; i++) {
		if(argv[1][i] < '0' || argv[1][i] > '9') {
			cerr << "usage: " << argv[0] << " [81 digits]" << endl;
			return(1);
		}
		num[i] = argv[1][i] - '0';
	}

	print_tables(num);

	crack(num, 0);

	return(0);
}

Boar · Aug 26, 2006

So, hier eine Lösung in Java (siehe Anhang)

Zur Steuerung: Mit der linken Maustaste erhöht man den Wert des Feldes um 1, mit der rechten wird der Wert um 1 erniedrigt. Dann drückt man den Button "Lösen" und die Lösung wird angezeigt (Achtung, bei nicht lösbaren Sudokus hängt sich das Programm auf, hab noch nicht herausgefunden, woran das liegt).

Bei Gelegenheit verbesser ich vllt. noch die Benutzerfreundlichkeit des Programms, dazu fehlt mir im Moment aber die Zeit (und die Lust).

Code:

package solve;

import data.SudokuBoard;
import data.SudokuController;
import data.SudokuRules;

public class SudokuSolver {
	
	private SudokuRules rules;
	private int freeColumn, freeLine;
	private SudokuController controller;

	/**
	 * 
	 * Constructor
	 * @param rules
	 * @param controller
	 */
	public SudokuSolver(SudokuRules rules, SudokuController controller) {
		this.rules = rules;
		this.controller = controller;
	}
	
	/**
	 * Method startSolve - sucht das erste freie Feld und ruft dann die Methode solve auf
	 * @param board - das Sudokufeld (int[][])
	 */
	public void startSolve(SudokuBoard board) {
		//Suche das erste leere Feld
		while(board.getValue(freeLine,freeColumn)!=0) {
			if(freeColumn<8) {
				freeColumn++;
			}
			else {
				freeColumn=0;
				if(freeLine<8) {
					freeLine++;	
				}
				else {
					break;
				}
				
			}
		}
		//Starte die Suche auf dem ersten freien Feld
		if(freeLine!=8 && freeColumn!=8) {
			if(solve(board,freeLine,freeColumn)) {
				controller.showSolution();
			}
		}
	}
	
	/**
	 * Method solve - die Methode löst das Sudoku mittels Backtracking-Algorithmus
	 * @param board - das Sudokufeld (int[][])
	 * @param line - die aktuelle Zeile
	 * @param column - die aktuelle Spalte
	 * @return - true: Lösung gefunden
	 */
	private boolean solve(SudokuBoard board, int line, int column) {
		//Wenn das Feld noch nicht belegt ist
		if(board.getValue(line,column)==0) {
			//Die Schleife überprüft für das aktuelle Feld jeden Wert von 1-9
			for(int i=1; i<10; i++) {
				//Wenn der Zug gültig ist
				if(rules.validMove(i,line,column)) {
					//Setze den Wert
					board.setWert(i,line,column);
					//Wenn das Feld nicht voll ist --> Sudoku noch nicht gelöst
					if(board.getOccupiedFields()<81) {
						//Nächster Zug, falls dieser "false" zurückgibt --> Nehme den aktuellen Zug zurück
						if(column==8) {	
							if(solve(board,line+1,0)) {
								return true;
							}
							else {
								board.setWert(0,line,column);
							}
						}
						else {	
							if(solve(board,line,column+1)) {
								return true;
							}
							else {
								board.setWert(0,line,column);
							}					
						}	
					}
					else {
						return true;						
					}		
				}	
			}
			return false;
		}
		//Wenn das Feld bereits belegt ist (D.h. das Feld wurde vom Benutzer gesetzt)
		else {
		// Nächster Zug, falls dieser "false" zurückgibt --> Sudoku hat keine Lösung
			if(column==8) {	
				if(solve(board,line+1,0)) {
					return true;
				}
				else {
					return false;
				}
			}
			else {	
				if(solve(board,line,column+1)) {
					return true;
				}	
				else {
					return false;
				}
			}	
		}
	}
}

Gruß,
Boar

Elderan · Aug 26, 2006

Hallo,
hier die Funktion des Knacken in Java:

Code:

//check() gibt true, wenn der Wert gesetzt werden kann, sonst false

public boolean Solve(int i, int j) 
{      
   if(j == 9) //Spielfeld zuende
   {   
      i++;
      if(i == 9) //Spielfeld zuende
         return true;
      j = 0;
   }           
   
               
   if(soduko[i][j] > 0)  
       return Solve(i, j+1);
               
   for(int x=1; x<10; x++) 
   {
      if(check(i, j, x)) 
      { 
         soduko[i][j] = x;       
         if(Solve(i, j+1))
               return true;
      }
   }
               
   feld[i][j] = 0;

   return false;
}