[HaBo]

Corni · 17.08.06, 20:10

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

gruß Corni

Boar · 18.08.06, 13:01

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

Gruß, Boar

lagalopex · 21.08.06, 01:22

Lösung in C++

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 · 26.08.06, 15:26

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).

Hier der interessante Code-Ausschnitt: Die Klasse SudokuSolver

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** · 26.08.06, 17:44

Hallo,
hier die Funktion des Knacken in Java:

Java

Eydeet · 09.01.07, 18:37

Auf dieser Seite werden die kürzesten Sudoku-Solver in verschiedenen Sprachen gesammelt. Der Code ist zwar grauenvoll, dafür aber (in K) nur 101 Bytes groß

:
http://markbyers.com/moinmoin/moin.c...stSudokuSolver

Wer trotzdem nicht so ganz weiterkommt, kann sich zusätzlich zu KSudoku (was eigentlich keine Sudokus löst) mal YASSS anschauen. Das Programm löst jedes lösbare Sudoku, gibt die Anzahl der möglichen Lösungen aus, kann Sudokus erstellen u.v.m.

pi() · 27.06.07, 02:10

Ich habe auch eine Lösung vorliegen.Man, dafür habe ich aber echt grauenhaft lange gebraucht.Werd sie aber noch verfeinern und optimiern.Noch brauch ich für die allerschwersten (mit 17 vorgegeben Zahlen-für Menschen nicht wirklich schaffbar,oder ?) dieser Welt ca bis zu 7 Sekunden (bis zu 100 Mio Durchläufe).Da kann man noch was rausholen.
Die Idee für ein solches Programm ist jedenfalls GENIAL.Danke Elderan.Hat Spaß gemacht.Und man kann es auch noch brauchen.

3,1416

Edit:

Hier meine noch immer optmierbare Löung:

Code:

# include <stdio.h>
# include <time.h>

int sudoku [9] [9];

int setzeFelder [9]={0,0,0,3,3,3,6,6,6};
int i,j,k,o,zahl,r,t,wert,x,dL;
//@sauwichtig: IN C SIND DIE KOORDINATEN EINES 2 DIM ARRAYS: Y X
int darfichquer () {
    for (o=0;o<9;o++) {
      if(sudoku[i][o]==zahl||sudoku[i][o]==-zahl) {
        return 0;
      }
    }
  return 1;
}
  int darfichsenkrecht () {
    for (k=0;k<9;k++) {
      if(sudoku[k][j]==zahl||sudoku[k][j]==-zahl) {
        return 0;
      }
    }
   return 1;
  }
  int darfichkasten (int y, int x) {
    x=setzeFelder[x];
    y=setzeFelder[y];

    if(
    sudoku[y][x]==zahl     || sudoku[y][x]==-zahl         ||
    sudoku[y][x+1]==zahl   ||   sudoku[y][x+1]==-zahl     ||
    sudoku[y][x+2]==zahl   ||   sudoku[y][x+2]==-zahl     || 
    sudoku[y+1][x]==zahl   ||   sudoku[y+1][x]==-zahl     ||
    sudoku[y+1][x+1]==zahl ||     sudoku[y+1][x+1]==-zahl ||
    sudoku[y+1][x+2]==zahl ||     sudoku[y+1][x+2]==-zahl ||
    sudoku[y+2][x]==zahl   ||   sudoku[y+2][x]==-zahl     ||
    sudoku[y+2][x+1]==zahl ||     sudoku[y+2][x+1]==-zahl ||
    sudoku[y+2][x+2]==zahl || sudoku[y+2][x+2]==-zahl
    ) {
    return 0;
    }
    return 1;
  }
int loese (int y,int x,int dasEine,int rueckwaerts)  {
         dL++;
         wert=sudoku[y][x];

         if(wert<0&&rueckwaerts==0)
           return 1;
         if(wert<0&&rueckwaerts==1)
           return 0;

         if(wert>=0) {
           if(dasEine==1)
             zahl=wert+1;
           else
             zahl=1;

          while(zahl<=9) {
            if((darfichquer()==1&&darfichsenkrecht()==1&&darfichkasten(y,x)==1)) {
              sudoku[y][x]=zahl;
              return 1;
            }else{
              zahl++;
            }
          }
          if(sudoku[y][x]==wert) { 
           return 0;
          }
        }
        return 1;
}

void druckeSudoku () {
     int waag,senk;
              for(senk=0;senk<9;senk++) {
                for(waag=0;waag<9;waag++) {
                  if(sudoku[senk][waag]>0)
                    printf("|%d",sudoku[senk][waag]);
                  else
                    printf("|%d",sudoku[senk][waag]*-1);
                }
                printf("|\n");
              }
              printf("\n");
}

int main (int argc,char ** argv) {
  printf("Der Sudoku-Hacker\n");
  
  int A,B,input;  
  for (A=0;A<9;A++) {
    for(B=0;B<9;B++) {
      printf("Geben Sie bitte die Reihe %d Spalte %d Zahl an",A+1,B+1);
      scanf("%d",&input);
      if(input!=0)
        input=0-input;
        sudoku[A][B]=input;
    }
  }
  printf("\n");
 
     for (i=0;i<9;i++) {//j=x,i=y
       for (j=0;j<9;j++) {
           x=loese(i,j,0,0);
         while(x==0){
           if(sudoku[i][j]>0)
             sudoku[i][j]=0;
           if(j==0) {
               i--;
               j=8;
               x=loese(i,j,1,1);
           }else{
             j--;
             x=loese(i,j,1,1);
           }
         }
       }
     }
     druckeSudoku();
     printf("Sudoku in %d Durchläufen geknackt\n",dL);
 return 0;
}

MontyPerl · 22.03.08, 14:42

Hier mal ein Sudoku-Solver mit tk-gui in perl:

clicking here will set off the doomsdaydevice

Code:

#!/usr/bin/env perl
use warnings;
use strict;
use Tk;


sub getclensedSudoku {
    my @sudoku = @_;
    foreach my $rowRef (@sudoku) {
        foreach my $col (@{$rowRef}) {
            $col = ''
        }
    }
}

sub matrixToSTDOUT {
    my @matrix = @_;
    print "####################START####################\n";
    foreach my $y (0..$#matrix) {
        if (($y == 3) or ($y == 6)) {print "\n"}
        foreach my $x (0..$#{$matrix[$y]}) {
            if (($x == 3) or ($x == 6)) {print " "}
            if (${matrix[$y][$x]}) {print "${matrix[$y][$x]} "}
            else {print ". "}
        }
        print "\n"
    }
    print "#####################END#####################\n";
}

sub createEmptySudoku {
    return      (   ['', '', '',   '', '', '',    '', '', ''],
                    ['', '', '',   '', '', '',    '', '', ''],
                    ['', '', '',   '', '', '',    '', '', ''],

                    ['', '', '',   '', '', '',    '', '', ''],
                    ['', '', '',   '', '', '',    '', '', ''],
                    ['', '', '',   '', '', '',    '', '', ''],

                    ['', '', '',   '', '', '',    '', '', ''],
                    ['', '', '',   '', '', '',    '', '', ''],
                    ['', '', '',   '', '', '',    '', '', '']);
}


###############################################################
###############################################################
########## Here the sudoku-solver subs start ##################
###############################################################
###############################################################

sub scanObvious {
    my @sudoku = @_;
    my $switch = 0;
    foreach my $y (0..8) {
        foreach my $x (0..8) {
            unless (${sudoku[$y][$x]}) {
                my @validDigits = getValidDigits($x, $y, @sudoku);
                if (@validDigits == 1) {${sudoku[$y][$x]} = $validDigits[0]; $switch++}
            }
        }
    }
    return $switch
}

sub getObvious {
    my @sudoku = @_;
    my $switch = scanObvious(@sudoku);
    while($switch) {$switch = scanObvious(@sudoku)}
    return
}

sub getSec {
    my ($x, $y, @sudoku) = @_;
    my @sector;
    my $intX = 3*int($x/3);
    my $intY = 3*int($y/3);
    foreach my $i ($intY..$intY+2) {
        foreach my $j ($intX..$intX+2) {
            if (${sudoku[$i][$j]}) {push(@sector, ${sudoku[$i][$j]})}
        }
    }
    return @sector
}

sub getValidDigits {
    my ($x, $y, @sudoku) = @_;
    my @row = grep(($_), @{$sudoku[$y]});
    my @col = map {${sudoku[$_][$x]} ? ${sudoku[$_][$x]} : ()} (0..8);
    my @sec = getSec($x, $y, @sudoku);
    my %digitPresence = map {$_, 1} (@row, @col, @sec);
    return grep $_ ne '' && !exists $digitPresence{$_}, (1..9)
}

sub getNextFreeField {
    my @sudoku = @_;
    my ($nextX, $nextY) = (-1, -1);
    my $count = 10;
    foreach my $y (0..8) {
        foreach my $x (0..8) {
            unless (${sudoku[$y][$x]}) {
                my @validDigits = getValidDigits($x, $y, @sudoku);
                if (@validDigits < $count) {
                    ($nextX, $nextY) = ($x, $y);
                    $count = @validDigits
                }
            }
        }
    }
    return ($nextX, $nextY)
}

sub useBruteforce {
    my ($x, $y, @sudoku) = @_;
    my ($nextX, $nextY) = getNextFreeField(@sudoku);
    unless ($nextX == -1) {
        foreach (getValidDigits($nextX, $nextY, @sudoku)) {
            ${sudoku[$nextY][$nextX]} = $_;
            if (useBruteforce($nextX, $nextY, @sudoku)) {return 1}
        }
        ${sudoku[$nextY][$nextX]} = 0;
        return 0
    }
    return 1
}

sub solveIt {
    my @sudoku = @_;
    getObvious(@sudoku);
    useBruteforce(0, 0, @sudoku);
    return
}

###############################################################
###############################################################
############ Here the sudoku-solver subs end ##################
###############################################################
###############################################################


my @sudoku = createEmptySudoku();

my $mw = new MainWindow;
my $topFrame = $mw->Frame->pack(-side => 'top');
$mw->title("Sudoku hihi");
$topFrame->Button(-text => "dump2con", -command => [\&matrixToSTDOUT, @sudoku])->pack(-side => 'left');
$topFrame->Button(-text => "clear",   -command => [\&getclensedSudoku, @sudoku])->pack(-side => 'right');
$mw->Button(-text => "kthxlol", -command => sub {exit})->pack(-side => 'bottom', -fill => 'x');
$mw->Button(-text => "cheque",  -command => sub {print "nej\n"})->pack(-side => 'left', -fill => 'both');
$mw->Button(-text => "solve",   -command => [\&solveIt, @sudoku])->pack(-side => 'right', -fill => 'both');


my $sFrame = $mw->Frame(-borderwidth => 3, -relief => 'groove'); # $sFrame means sudoku-Frame, guess what i'll put in it :0

# Now generate the sudoku-field in the sudoku-frame

sub putSpace {
    my ($Frame, $row, $col) = @_;
    $Frame->Label(-text => ' ')->grid(-row => $row, -column => $col);
}

foreach my $x (0..8) {
    my ($row, $col);
    foreach my $y (0..8) {
        $col = $x;
        $row = $y;
        if    ($x == 3) {putSpace($sFrame, $row, $col); $col++}
        elsif ($x >  3) {$col++}
        if    ($x == 6) {putSpace($sFrame, $row, $col); $col++}
        elsif ($x >  6) {$col++}

        if    ($y == 3) {putSpace($sFrame, $row, $col); $row++}
        elsif ($y >  3) {$row++}
        if    ($y == 6) {putSpace($sFrame, $row, $col); $row++}
        elsif ($y >  6) {$row++}

        $sFrame->Entry(-width           => 1,
                       -textvariable    => \${sudoku[$y][$x]},
                       -validate        => 'key',
                       -borderwidth => 3,
                       -validatecommand => sub {$_[0] =~ /^[1-9]?$/},
                       -invalidcommand  => sub {$mw->bell}
                      )->grid(-row => $row, -column => $col);
    }
}

$sFrame->pack;

MainLoop;

Die Optimierung des Backtrack-Algorithmus ist mit freundlicher Hilfe von mehlvogel @ mrunix.de und diversen Personen aus #perl @ irc.freenode.net geschehen. (Vorher brauchte der Algo auf meinem PC ca. eine viertel Stunde für das Lösen von "Qassim Hamza", jetzt nur noch ca. 1 Minute.)
BTW: der solve Button ist lediglich "eyecandy"..

edit: jetzt geht der Algorithmus immer den Weg mit den wenigsten Möglichkeiten zuerst, was einen enormen Geschwindigkeitsschub bringt, Idee von BlueJay @ mrunix.de

adrian90 · 04.06.08, 23:06

Ich habe auch mal was kleines probiert. Jedoch ist es extrem langsam. Ich hatte jetzt noch keine Zeit, irgendwas zu optimieren. Leider weiss ich auch nicht recht wo anfangen. Ich möchte es optimieren, ohne dass ich Logische Prüfungen einbaue, welche einzelne Teilprobleme lösen.
Vielleicht hat da ja jemand eine Idee für mich.

Code:

#include <stdlib.h>
#include <stdio.h>

int solve(int sudokufeld[9][9], int solvedsudokufeld[9][9]);

int main()
{
    int i=0;
    int j=0;
    char zahl[1] = {0};
    int sudokufeld[9][9];
    int solvedsudokufeld[9][9] = {0};
    
    printf("Bitte geben sie das ganze Spielfeld an. Alle Eingaben != 1-9 werden als unbekannt angenommen\n");
    for (i=0;i<9;i++)
    {
        for (j=0;j<9;j++)
        {
            zahl[0] = getch();
            sudokufeld[i][j] = atoi(zahl);
            printf("%2i", sudokufeld[i][j]);
        }
        printf("\n");
    }
    
    solve(sudokufeld, solvedsudokufeld);
    
    printf("\n\nLoesung:\n");
    for (i=0;i<9;i++)
    {
        for (j=0;j<9;j++)
        {
            printf("%2i", solvedsudokufeld[i][j]);
        }
        printf("\n");
    }
    //printf("\n%i\n", IstMoeglich(sudokufeld));
    
    //Auf q warten
    getch();
}

void kopiereSudoku(int quelleSudokufeld[9][9], int zielSudokufeld[9][9])
{
    int i, j;
    for (i=0;i<9;i++)
    {
        for (j=0;j<9;j++)
        {
            zielSudokufeld[i][j] = quelleSudokufeld[i][j];
        }
    }
}

//0 wenn wiedersprüche
//1 wenn Sudoku OK
int IstMoeglich(int refSudokufeld[9][9])
{
    int i, j, zusammenh, zusammenv;
    for (i = 0; i < 9; i++)
    {
        //Horizontal
        zusammenh = 0;
        zusammenv = 0;
        for (j = 0; j < 9; j++) //Alle Zellen zusammenrechnen
        {
            zusammenh+=refSudokufeld[i][j];
            zusammenv+=refSudokufeld[j][i];
        }
        if (zusammenh != 45 || zusammenv != 45)
            return 0;
    }
    return 1;
}

int solve(int refSudokufeld[9][9], int solvedSudokufeld[9][9])
{
    int i, j, k;
    int tempsudokufeld[9][9];
    
    for (i=0;i<9;i++)
    {
        for (j=0;j<9;j++)
        {
            //Das Feld darf nur bearbeitet werden, wenn es unbekannt ist
            if (refSudokufeld[i][j] == 0)
            {
                for (k = 1; k <= 9; k++)
                {
                    kopiereSudoku(refSudokufeld, tempsudokufeld);
                    tempsudokufeld[i][j] = k;
                    //Wenn Sudoku nun gelöst, dann 1 zurück
                    if (IstMoeglich(tempsudokufeld))
                    {
                        kopiereSudoku(tempsudokufeld, solvedSudokufeld);
                        return 1;
                    }
                    else //Sonst sich selber aufrufen
                    {
                        if (solve(tempsudokufeld, solvedSudokufeld))
                            return 1;
                    }
                }
            }
        }
    }
    return 0;
}

Ook! · 08.06.08, 20:48

Java - zu faul für OOP.

Code:

public class Sudoku {
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[][] grid = new int[9][9];
		int[] data = { 0,0,0,0,0,0,0,0,0, 0,7,0,0,4,0,0,1,0, 3,0,1,5,0,6,4,0,8,
				0,0,0,0,0,0,0,0,0, 0,6,0,0,1,0,0,4,0, 1,0,5,7,0,9,8,0,3,
				0,0,0,0,0,0,0,0,0, 0,3,0,0,7,0,0,2,0, 2,0,4,8,0,5,7,0,9 };
		
		fillGrid(data, grid);
		printGrid(grid);
		if(solve(0, 0, grid))
			printGrid(grid);
		else
			System.out.println("Keine Lösung");
	}
	
	/**
	 * @param grid - Sudokufeld
	 */
	public static void printGrid(int[][] grid){
		for(int i=0; i<grid.length; i++) {
			for(int z=0; z<grid[i].length; z++) {
				if((i%3) == 0 && z == 0)
					System.out.println("-------------------------");
				if((z%3) == 0)
					System.out.print("| ");
				
				System.out.print(grid[i][z] +" ");
				
				if(z == grid[i].length-1)
					System.out.print("|");
			}
			System.out.println("");
		}
		System.out.println("-------------------------\n\n");
	}
	
	/**
	 * @param data - Array mit den Zahlen
	 * @param grid - Sudokufeld
	 */
	public static void fillGrid(int[] data, int[][] grid){
		int x = -1;
		for(int i=0; i<81; i++){
			if((i%9) == 0) 
				x++;
			grid[x%9][i%9] = data[i];
		}
	}

	/**
	 * @param row - Zeile
	 * @param col - Spalte
	 * @param grid - Sudokufeld
	 * @return true/false - Lösung gefunden / keine Lösung gefunden
	 */
	public static boolean solve(int row, int col, int[][] grid){
		if(row == 9){   
			row = 0;
			col++;
		    if(col == 9)
		    	return true;
		}           
		   
		if(grid[row][col] > 0)  
			return solve(row+1, col, grid);
		               
		for(int x=1; x<10; x++) {
			if(check(row, col, x, grid)) { 
				grid[row][col] = x;       
		        if(solve(row+1, col, grid))
		        	return true;
			}
		}

		grid[row][col] = 0;
		return false;
	}

	/**
	 * @param row - Zeile
	 * @param col - Spalte
	 * @param x - Wert
	 * @param grid - Sudokufeld
	 * @return true/false - kann gesetzt werden / kann nicht gesetzt werden 
	 */
	public static boolean check(int row, int col, int x, int[][] grid){
		for(int i=0; i<9; i++)
			if(x == grid[i][col])
				return false;
			
		for(int i=0; i<9; i++)
			if(x == grid[row][i])
				return false;
		
		int rowBlockFirst = (int)(row/3)*3;
		int colBlockFirst = (int)(col/3)*3;
		for(int i=0; i<3; i++)
		    for(int z=0; z<3; z++)
				if(x == grid[rowBlockFirst+i][colBlockFirst+z])
					return false;
		
		return true;
	}
	
}

HKA · 09.06.08, 16:57

Hab auch mal eine PHP Klasse für Sudokus erstellt, aber nur um diese zu generieren und am Schluss zu überprüfen.

Wer sie mal ausprobieren möchte:
http://www.thomas-wollmann.de/sonstiges/sudokutest.php

MFG HKA

**CDW** · 20.08.08, 13:21

Eine etwas andere Lösungsweise:
Wir betrachten einmal die Regeln: es gibt Zeilen, Spalten und Blöcke. Darin sollen Ziffern von 1 bis N stehen. Weder in einer Zeile,noch Spalte noch Block soll eine Ziffer doppelt vorkommen.
D.h ein intelligenter Brutforcer sollte beim Ausprobieren erstmal berücksichtigen, welche Ziffern überhaupt als Kandidaten in Frage kommen, bevor er etwas einträgt.
Damit wären wir auch schon bei der Lösung

:
http://de.wikipedia.org/wiki/Constraintprogrammierung
Umsetzung (ja, in diesem Stück Code steckt wirklich sowohl der "Löser" wie auch der "Korrektheit-Checker"

):

sudoku.pl, Sicstus Version,mit SWI kompatibel

Jetzt die 2 Begleitmodule:

sudoku_prettyprint

processfile, liest die Datei ein und zerlegt das Spielfeld in Zeilen/Spalten/Blöcke

Code:

%anpassbar: für jeden:
%Zeichen, die als Platzhalter dienen:
char('0',_).
char('.',_).
char(X,Num):-number_chars(Num,[X]).
%festcodierte Blockgrößen: board(Seitenlänge,Zeilen im Block,Spalten im Block)
board(6,2,3).
board(8,2,4).
board(9,3,3).
board(12,3,4).
board(16,4,4).
board(25,5,5).
board(X,_,_):- \+member(X,[6,8,9,12,16,25]),write('Unbekannte Sudoku Größe, bitte die Aufteilung des Feldes\n'),
              write('in Blocks(wieviele Zeilen/Spalten im Block sind) vornehemen!\n'),
              write('In: processfile.pl, ab Zeile 7'),fail.

%anpassbar: nicht für jeden ;-)
:-use_module(library(lists)).

processfile(File,Cells,Domain,Lines,Rows,Blocks):-open(File,read,Stream),
                         (reader(Stream,Cells)->close(Stream);close(Stream)),
                         check(Cells,Domain),lines(Cells,Lines),rows(Lines,Rows),
                         blocks(Cells,Blocks).

check(Cells,Size):-length(Cells,Len),Size is ceiling(sqrt(Len)),board(Size,_,_),!.

reader(Stream,[]):- peek_char(Stream,end_of_file),!.
reader(Stream,[Cell|Cells]):- get_char(Stream,Char),get_cell(Char,Cell),reader(Stream,Cells),!.
reader(Stream,T):-reader(Stream,T),!.

get_cell(Char,Cell):-
          Char\='\n',char(Char,Cell).

/*Konstruiere Spalten
 Parameter: +Input,-Result; Zeilenlänge muss =Zeilenanzahl */
rows(Lines,Res):-length(Lines,RowSize),rows(Lines,0,RowSize,Res),!.
rows(_,Size,Size,[]).
rows(Lines,Count,Size,[Row|Rows]):- NewCount is Count+1 ,
                                    row(Lines,NewCount,Row),
                                    rows(Lines,NewCount,Size,Rows).
row([],_,[]).
row([Line|Lines],Nth,[E|Row]):-     nth1(Nth,Line,E),row(Lines,Nth,Row).

/*Konstruiere aus Raw Data Zeilen
Parameter: +Input,-List of Lines,Inputgröße sollte X*X sein, wobei X ganzzahlig ist*/
lines([],[],_).
lines(Data,[Line|Lines],Len):-      line(Data,0,Len,Line,Tail),lines(Tail,Lines,Len).
lines(Data,Lines):-                 line_len(Data,LineLen),
                                    lines(Data,Lines,LineLen),!.
line(Tail,Size,Size,[],Tail).
line([E|Data],Count,Size,[E|Line],Tail):-NewCount is Count+1,
                                    line(Data,NewCount,Size,Line,Tail).

line_len(Cells,LineLen):-length(Cells,Len),LineLen is (ceiling(sqrt(Len))).

blocks(Cells,Blocks):-line_len(Cells,Len),board(Len,LnNum,RowNum),
                                    TotalBlocks is ceiling((Len*Len)/(LnNum*RowNum)),
                                    blocks(Cells,TotalBlocks,Len,Blocks),!.
blocks(_,0,_,[]).
blocks(Cells,Count,Len,[Block|Blocks]):-block(Cells,0,Count,Len,Block),NewCount is Count-1,
                                    blocks(Cells,NewCount,Len,Blocks),!.
block([],_,_,_,[]).
block([Cell|Cells],Count,Num,Len,[Cell|Block]):- board(Len,LnNum,RowNum),
                                    VBlocks is ceiling(Len/LnNum),
                                    BlockNum is ceiling(floor(Count/Len+1)/LnNum)
                                    + (ceiling((mod(Count,Len)+1)/RowNum)*VBlocks)-VBlocks,
                                    NewCount is Count+1,BlockNum is Num,
                                    block(Cells,NewCount,Num,Len,Block),!.
block([_|Cells],Count,Num,Len,Block):- NewCount is Count+1,
                                    block(Cells,NewCount,Num,Len,Block),!.

hier wird das Spielfeld eingelesen und in Zeilen, Spalen und Blöcke unterteilt.
Da die Routine mit dynamischen Größen arbeitet sind es eben etwas mehr Zeilen Code ;). Ein festkodiertes 9x9 Board könnte man natürlich auch mit viel weniger Aufwand erstellen.

Diese Sichtweise ist nicht nur extrem bequem bei dieser Problemstellung - sie ist auch viel effizienter, als reines BF. Bsp:
"Near worst case" sudoku puzzle for brute force solver"
http://en.wikipedia.org/wiki/Algorit...orce_algorithm

sudoku als programminput

Ausgabe:

Ausgabe

Die Messzeit beinhaltet den kompletten Vorgang -auch das Lesen/Parsen des Spielfeldes von der Festplatte

Andere:

Eastermonster,tarek,golden nugget

Nutzung:
solve(Filename).

Spielfeldformat: wie in Wikipedia - entweder Ziffern oder Platzhalter(0 oder . (Punkt)),
Zeilenumbrüche sind egal. Wer andere Zeichen als Platzhalter nutzen möchte, sollte sie in 'processfile' (ab Zeile 1 - siehe Kommentar) eintragen.

Spielfeldgrößen: dynamisch. Allerdings gibt es 2 Sachen - zum einen muss bei exotischen Boards die Blockauteilung noch eingetragen werden (wieviele Zeilen/Spalten in einem Block sein sollen). Zum anderen hatte ich dann keine Lust mehr

eine Extraroutine zum Einlesen von Boards>9 (vor allem - jemand müsste diese Boards vorher auch noch abtippen

) zu erstellen, so dass aktuell nur Boards bis 9x9 eingelesen werden.

Joiseppe · 07.10.08, 12:06

koennte einer fuer mich das entschluesseln eines sudoku spiels in eine mathematische Formel bringen?

**Elderan** · 07.10.08, 13:41

Hallo,
glaube kaum, dass es eine mathematische Formel gibt, die das Lösen eines Soduks beschreibt.
Und mathematische Formeln/Sätze für etwas komplexere Probleme sind so extrem kompliziert, dass du sie vermutlich eh nicht verstehen wirst und es leichter ist ein Programm/Algorithmus nachzuvollziehen.

**CDW** · 07.10.08, 14:14

Nunja, in der DE Wikipedia steht ja schon ein Ansatz:
http://de.wikipedia.org/wiki/Sudoku#...ische_Methoden
die englische bietet sogar eine Extraseite dazu
http://en.wikipedia.org/wiki/Algorithmics_of_sudoku
allerdings kommt dabei die Mengenlehre/Stochastik zum Einsatz.

Empfehlung

07.10.08, 14:14	#30 (permalink)
CDW Moderator Registriert seit: 20.07.05 Likes: 156	Nunja, in der DE Wikipedia steht ja schon ein Ansatz: http://de.wikipedia.org/wiki/Sudoku#...ische_Methoden die englische bietet sogar eine Extraseite dazu http://en.wikipedia.org/wiki/Algorithmics_of_sudoku allerdings kommt dabei die Mengenlehre/Stochastik zum Einsatz. __________________ Noch mal, für alle Pseudo-Geeks: 1+1=0. -> 10 wäre Überlauf! Selig, wer nichts zu sagen hat und trotzdem schweigt.

Themen-Optionen
Druckbare Version zeigen Jemanden per E-Mail auf dieses Thema hinweisen
Ansicht
Linear-Darstellung Zur Hybrid-Darstellung wechseln Zur Baum-Darstellung wechseln

Ähnliche Themen
Thema	Autor	Forum	Antworten	Letzter Beitrag
Sudoku-Generator	CDW	Programmieraufgaben	1	04.08.09 02:12
Sudoku	Ook!	Code Kitchen	2	25.05.08 11:00
The Cheat Report	stone.dr	Fun Section	17	20.03.06 15:18
Sudoku programmieren	jami	Code Kitchen	1	16.10.05 15:05

17.08.06, 20:10	#16 (permalink)
Corni Registriert seit: 13.04.06 Likes: 0	Wer mit der Umsetzung nicht weiter kommt, kann sich ja mal den Quellcode von ksudoku (ziemlich cooles proggi) ankuckn.... gruß Corni

18.08.06, 13:01	#17 (permalink)
Boar Registriert seit: 03.12.04 Likes: 0	Ja, die Aufgabe hört sich gut an. Ich werd mich an einer Java-Lösung versuchen. Gruß, Boar

09.01.07, 18:37	#21 (permalink)
Eydeet Registriert seit: 14.04.06 Likes: 4	Auf dieser Seite werden die kürzesten Sudoku-Solver in verschiedenen Sprachen gesammelt. Der Code ist zwar grauenvoll, dafür aber (in K) nur 101 Bytes groß : http://markbyers.com/moinmoin/moin.c...stSudokuSolver Wer trotzdem nicht so ganz weiterkommt, kann sich zusätzlich zu KSudoku (was eigentlich keine Sudokus löst) mal YASSS anschauen. Das Programm löst jedes lösbare Sudoku, gibt die Anzahl der möglichen Lösungen aus, kann Sudokus erstellen u.v.m.

09.06.08, 16:57	#26 (permalink)
HKA Registriert seit: 15.10.06 Likes: 0	Hab auch mal eine PHP Klasse für Sudokus erstellt, aber nur um diese zu generieren und am Schluss zu überprüfen. Wer sie mal ausprobieren möchte: http://www.thomas-wollmann.de/sonstiges/sudokutest.php MFG HKA

07.10.08, 12:06	#28 (permalink)
Joiseppe Registriert seit: 19.01.07 Likes: 2	koennte einer fuer mich das entschluesseln eines sudoku spiels in eine mathematische Formel bringen?

07.10.08, 13:41	#29 (permalink)
Elderan Moderator Themenstarter Registriert seit: 30.03.04 Likes: 14	Hallo, glaube kaum, dass es eine mathematische Formel gibt, die das Lösen eines Soduks beschreibt. Und mathematische Formeln/Sätze für etwas komplexere Probleme sind so extrem kompliziert, dass du sie vermutlich eh nicht verstehen wirst und es leichter ist ein Programm/Algorithmus nachzuvollziehen.

[HaBo]

Sudoku Cheat-Prog.