Sudoku Cheat-Prog.

Eydeet · Jan 9, 2007

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.cgi/ShortestSudokuSolver

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() · Jun 27, 2007

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 · Mrz 22, 2008

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

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 · Jun 4, 2008

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! · Jun 8, 2008

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 · Jun 9, 2008

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 · Aug 20, 2008

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"

):

Code:

:-use_module(library(clpfd)).
:-consult(processfile).
:-consult(sudoku_prettyprint).

constrain_rows([]).
constrain_rows([Row|Rows]):- all_different(Row),constrain_rows(Rows).

constrain_lines([]).
constrain_lines([Line|Lines]):- all_different(Line),constrain_lines(Lines).

constrain_blocks([]).
constrain_blocks([Block|Blocks]):- all_different(Block),constrain_blocks(Blocks).

constrain_all(Domain,Cells,Ln,Rw,Bl):- domain(Cells,1,Domain),    %Cells ins 1..Domain,
                   constrain_rows(Rw),
                   constrain_lines(Ln),
                   constrain_blocks(Bl).
solve(File):-processfile(File,Cells,Domain,Ln,Rw,Bl),
                   constrain_all(Domain,Cells,Ln,Rw,Bl),
                   labeling([ff],Cells),board(Domain,LinesInBlock,RowsInBlock),
                   print(Ln,LinesInBlock,RowsInBlock).

der Code macht nichts anderes, als sich erstmal das Spielfeld (Zeilen,Spalten,Blöcke)
zu holen und ihre Bereiche zu definieren. Die Lösung ist dann eine Platzierung aller Ziffern, die diese Regeln nicht verletzen.
Wer SWI nutzt, sollte in Zeile 14 das "domain(...)" durch das auskommentierte "Cells ins 1..Domain" ersetzen.

Jetzt die 2 Begleitmodule:

Code:

print(Lines,LinesInBlock,RowsInBlock):-print(Lines,1,LinesInBlock,RowsInBlock),!.
print([],_,_,_).
print([Line|Lines],Count,LinesInBlock,RowsInBlock):-
             print_line(Line,1,RowsInBlock),
             (0 is mod(Count,LinesInBlock),nl,nl;nl),
             NewCount is Count+1,print(Lines,NewCount,LinesInBlock,RowsInBlock).

print_line([E],_,_):-write(E).
print_line([E|Elements],Count,RowsInBlock):-
             (0 =\= mod(Count,RowsInBlock),
                          format('~q,',[E]);
                          format('~q  ',[E])),
             NewCount is Count+1,
             print_line(Elements,NewCount,RowsInBlock),!.

sorgt für die schöne formatierte Ausgabe

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/Algorithmics_of_sudoku#Solving_sudokus_by_a_brute-force_algorithm

000000000
000003085
001020000
000507000
004000100
090000000
500000073
002010000
000040009

Ausgabe:

SICStus 4.0.4 (x86-win32-nt-4): Tue Jun 17 00:06:53 WEST 2008
?- time(solve('worstcase.sudoku')).
9,8,7 6,5,4 3,2,1
2,4,6 1,7,3 9,8,5
3,5,1 9,2,8 7,4,6

1,2,8 5,3,7 6,9,4
6,3,4 8,9,2 1,5,7
7,9,5 4,6,1 8,3,2

5,1,9 2,8,6 4,7,3
4,7,2 3,1,9 5,6,8
8,6,3 7,4,5 2,1,9

solve('worstcase.sudoku') took 0.313 sec.

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

Andere:

time(solve('eastermonster.sudoku')).
1,7,4 3,8,5 9,6,2
2,9,3 4,6,7 1,5,8
5,8,6 1,9,2 7,3,4

4,5,1 9,2,3 8,7,6
9,2,8 6,7,4 3,1,5
3,6,7 8,5,1 2,4,9

7,1,9 5,4,8 6,2,3
6,3,5 2,1,9 4,8,7
8,4,2 7,3,6 5,9,1

solve('eastermonster.sudoku') took 0.031 sec.
yes

| ?- time(solve('tarek.sudoku')).
7,6,1 3,5,4 2,8,9
2,9,8 1,6,7 3,4,5
4,5,3 9,2,8 1,6,7

8,1,2 6,4,9 7,5,3
9,7,6 5,1,3 4,2,8
5,3,4 8,7,2 6,9,1

3,2,7 4,8,5 9,1,6
1,8,9 2,3,6 5,7,4
6,4,5 7,9,1 8,3,2

solve('tarek.sudoku') took 0.062 sec.
yes

| ?- time(solve('goldennugget.sudoku')).
7,5,1 8,4,6 2,3,9
8,9,2 3,7,1 4,6,5
6,4,3 2,5,9 8,7,1

2,3,8 1,9,7 5,4,6
9,7,4 5,6,2 3,1,8
1,6,5 4,3,8 9,2,7

3,1,9 6,8,4 7,5,2
5,2,7 9,1,3 6,8,4
4,8,6 7,2,5 1,9,3

solve('goldennugget.sudoku') took 0.110 sec.
yes

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 · Okt 7, 2008

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

Elderan · Okt 7, 2008

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 · Okt 7, 2008

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

Joiseppe · Okt 27, 2008

Original von Elderan
ermutlich eh nicht verstehen wirst und es leichter ist ein Programm/Algorithmus nachzuvollziehen.

trotzdem vielen dank fuer die einteilung in diese schublade,
ich brauchs fuer nen mathelehrer...

Elderan · Okt 27, 2008

Hallo,

Original von Joiseppe

Original von Elderan
ermutlich eh nicht verstehen wirst und es leichter ist ein Programm/Algorithmus nachzuvollziehen.

Zum Vergrößern anklicken....

trotzdem vielen dank fuer die einteilung in diese schublade,
ich brauchs fuer nen mathelehrer...

Das hat nichts mit der Einteilung in Schubladen zu tun, aber wie bereits erwähnt, selbst simple Sachen lassen sich mathematisch nur so komplex beschreiben, dass sie 99,9[...]% der Menschen nicht verstehen.

Ein simples Beispiel ist, wie man Orangen möglichst platzsparend stapeld: Orangenstapel
Zu beweisen, dass man eine Pyramide bilden muss, dazu benötigt man hunderte von Seiten an höchster Mathematik.

Ebenso simple Sachen wie zu beweisen, dass der Kreis einen eindeutigen Flächeninhalt hat bzw, dass dieser überhaupt einen Flächeninhalt hat [1] ist höchst ansprechend, so dass kaum ein Schüler überhaupt das Problem versteht. Das fängt an beim Begriff der Sigma-Algebra geht über Borel Algebra, Maßräume, Lesbegue Maß, Maßfortsetzung etc., oder kurz: Maßtheorie

Und nun möchtest du mir erzählen, dass du in der Lage bist, mathematische Formeln/Sätze/Definitionen zu verstehen? Mathematik ist viel mehr als nur die Formel A = \pi * r^2.

Ein ganz simple 'Formel' zur Beschreibung wie sich Jäger und Beute in einem geschlossenen Ökosystem verhält wäre:
y(t) := Anzahl der Jäger zum Zeitpunkt t
z(t) := Anzahl der Beute zum Zeitpunkt t

y'(t) = a*y(t) + b(z(t)-c)
z'(t) = d*z(t) + e*y(t)

a := Geburtenrate Jäger > 0
b, c := Schwellenwerte, > 0
d := Geburtenrate Beute > 0
e := Fressrate < 0

Wenn nun a,b,c,d,e gegeben ist, dann lässt sich eine explizite Formel für y und z finden, so dass man sagen kann, nach t Zeiteinheiten gibt es ... Jäger und ... Beutetiere. Es ist also keine Formel für y oder z(t) vorgegeben, sondern die lässt sich dann so bestimmen.

[1] es gibt auch Flächen/Mengen in den reellen Zahlen (R^2), die keinen Flächeninhalt haben, also weder die Fläche 0 noch irgendein einen anderen Flächeninhalt. Nennen sich Vitali-Mengen)

Gaux · Okt 11, 2009

hab das auch mal gecodet in VB.NET.
Ich hab jetzt einfach mal ein SudokuFeld (als Array) initialisiert das komplett leer ist.
Das Programm braucht 0.0156250 Sekunden um es aufzulösen (also ca. 16 Millisekunden wenn ich das richtig seh?)

Hier der Lösungsalgorithmus:

Code:

Private field(9, 9) As Integer
Private line As Integer = 0

Public Function solve() As Boolean
        For x As Integer = line To 8
            For y As Integer = 0 To 8
                'Wenn das aktuelle Feld nicht besetzt ist
                If field(x, y) = 0 Then
                    For val As Integer = 1 To 9
                        'Setze Zahl
                        field(x, y) = val
                        'Wenn Zahl gültig ist
                        If fieldValid() Then
                            line = x
                            'rekursiver Aufruf
                            If solve() Then
                                'wenn gesetzte Zahl richtig war -> beende Schleife
                                'wenn nicht -> setze Schleife fort = setze nächste Zahl in Feld
                                Exit For
                            End If
                        'Wenn die Zahl nicht gültig ist
                        Else
                            'Wenn die Zahl im aktuellen Feld 9 ist -> setze Feld zurück
                            'und return false
                            If val = 9 Then
                                field(x, y) = 0
                                Return False
                            End If
                        End If
                    Next
                End If
            Next
        Next
        Return True
    End Function

und hier noch die Funktion zur Überprüfung auf Gültigkeit:

Code:

    Private Function fieldValid() As Boolean
        Dim numbers1to9(9) As Integer
        numbers1to9(1) = 0
        numbers1to9(2) = 0
        numbers1to9(3) = 0
        numbers1to9(4) = 0
        numbers1to9(5) = 0
        numbers1to9(6) = 0
        numbers1to9(7) = 0
        numbers1to9(8) = 0
        numbers1to9(9) = 0
        Dim i As Integer
        Dim j As Integer

        '---------Überprüfung aller 3x3 Kasten------------------
        For i = 0 To 6 Step 3   'x
            For j = 0 To 6 Step 3   'y
                For k As Integer = j To j + 2 Step 1 'y
                    For l As Integer = i To i + 2 Step 1 'x
                        'Wenn das aktuelle Feld 1-9 als Inhalt hat -> Erhöhund des entsprechenden Zählers
                        If field(k, l) = 1 Or field(k, l) = 2 Or field(k, l) = 3 _
                        Or field(k, l) = 4 Or field(k, l) = 5 Or field(k, l) = 6 _
                        Or field(k, l) = 7 Or field(k, l) = 8 Or field(k, l) = 9 Then
                            numbers1to9(field(k, l)) += 1
                        End If
                    Next
                Next
                'Wenn eine Zahl öfters als ein mal vor kommt -> ungültig
                If numbers1to9(1) > 1 OrElse numbers1to9(2) > 1 OrElse numbers1to9(3) > 1 _
                OrElse numbers1to9(4) > 1 OrElse numbers1to9(5) > 1 OrElse numbers1to9(6) > 1 _
                OrElse numbers1to9(7) > 1 OrElse numbers1to9(8) > 1 OrElse numbers1to9(9) > 1 Then
                    Return False
                End If
                numbers1to9(1) = 0
                numbers1to9(2) = 0
                numbers1to9(3) = 0
                numbers1to9(4) = 0
                numbers1to9(5) = 0
                numbers1to9(6) = 0
                numbers1to9(7) = 0
                numbers1to9(8) = 0
                numbers1to9(9) = 0
            Next
        Next
        '-------------------------------------------------------------------

        '---------Überprüfung aller Reihen nacht unten----------------------
        For i = 0 To 8
            For j = 0 To 8
                'Wenn das aktuelle Feld 1-9 als Inhalt hat -> Erhöhund des entsprechenden Zählers
                If field(i, j) = 1 Or field(i, j) = 2 Or field(i, j) = 3 _
                    Or field(i, j) = 4 Or field(i, j) = 5 Or field(i, j) = 6 _
                    Or field(i, j) = 7 Or field(i, j) = 8 Or field(i, j) = 9 Then
                    numbers1to9(field(i, j)) += 1
                End If
            Next
            'Wenn eine Zahl öfters als ein mal vor kommt -> ungültig
            If numbers1to9(1) > 1 OrElse numbers1to9(2) > 1 OrElse numbers1to9(3) > 1 _
                OrElse numbers1to9(4) > 1 OrElse numbers1to9(5) > 1 OrElse numbers1to9(6) > 1 _
                OrElse numbers1to9(7) > 1 OrElse numbers1to9(8) > 1 OrElse numbers1to9(9) > 1 Then
                Return False
            End If
            numbers1to9(1) = 0
            numbers1to9(2) = 0
            numbers1to9(3) = 0
            numbers1to9(4) = 0
            numbers1to9(5) = 0
            numbers1to9(6) = 0
            numbers1to9(7) = 0
            numbers1to9(8) = 0
            numbers1to9(9) = 0
        Next
        '----------------------------------------------------------------------

        '----------- Überprüfung aller Reihen nach Rechts----------------------
        For i = 0 To 8
            For j = 0 To 8
                'Wenn das aktuelle Feld 1-9 als Inhalt hat -> Erhöhund des entsprechenden Zählers
                If field(j, i) = 1 Or field(j, i) = 2 Or field(j, i) = 3 _
                   Or field(j, i) = 4 Or field(j, i) = 5 Or field(j, i) = 6 _
                   Or field(j, i) = 7 Or field(j, i) = 8 Or field(j, i) = 9 Then
                    numbers1to9(field(j, i)) += 1
                End If
            Next
            'Wenn eine Zahl öfters als ein mal vor kommt -> ungültig
            If numbers1to9(1) > 1 OrElse numbers1to9(2) > 1 OrElse numbers1to9(3) > 1 _
                OrElse numbers1to9(4) > 1 OrElse numbers1to9(5) > 1 OrElse numbers1to9(6) > 1 _
                OrElse numbers1to9(7) > 1 OrElse numbers1to9(8) > 1 OrElse numbers1to9(9) > 1 Then
                Return False
            End If
            numbers1to9(1) = 0
            numbers1to9(2) = 0
            numbers1to9(3) = 0
            numbers1to9(4) = 0
            numbers1to9(5) = 0
            numbers1to9(6) = 0
            numbers1to9(7) = 0
            numbers1to9(8) = 0
            numbers1to9(9) = 0
        Next
        '----------------------------------------------------------------------

        Return True
    End Function

Ich hab das ganze auch mal gecodet mit Algorithmen die das Sudoku durch Logik lösen (und Trial&Error falls mit Logik nichts mehr geht). Der Code ist allerdings wesentlich länger. Aber falls jemand Interesse hat kann ich den ja auch mal posten.

P.S.: Wie kann man hier Hide machen? Find des ned

fishfishfish · Apr 12, 2010

Bruteforce, C++, unspektakulär

Code:

#include <iostream>
const int K = 3;	//Kasten
const int D = K*K;	//Seitenlaenge
short feld[D][D];

inline bool test(int x, int y)
{
	for(int i = 0; i< D; i++)
	{
		if( ((feld[x][y] == feld[i][y]) && (x!=i)) || ((feld[x][y] == feld[x][i]) && (y!=i))    ) return false;
	}
	for(int ix = (x/K) *K; ix < (x/K+1)*K; ix++)
	for(int iy = (y/K) *K; iy < (y/K+1)*K; iy++)
		if(ix != x && iy != y && feld[x][y] == feld[ix][iy]) return false;
}

bool fill(int x, int y)
{
	if(y == D)		
		return true;
	if(feld[x][y] == 0)
	{
		for(int i = 1; i < D+1; i++)
		{
			feld[x][y] = i;
			if(test(x,y))
				if(fill((x+1)%D, y+(x+1)/D)) return true;
		}
		feld[x][y] = 0; 
		return false;
	}
	else		
		return test(x,y) ? fill((x+1)%D, y+(x+1)/D) : false;
}

void main()
{
	std::cout << "\n \n Zahl fuer Zahl (Zeilenweise; 0 = frei):\n";
	for(int iy = 0; iy < D; iy++)
	for(int ix = 0; ix < D; ix++)
		std::cin >> feld[ix][iy];
	if(fill(0,0))
		for(int iy = 0; iy < D; iy++)
		{
			std::cout << "\n";
			if(iy%K == 0) std::cout << "\n";
			for(int ix = 0; ix < D; ix++)
			{
				if(ix%K == 0) std::cout << " ";
				std::cout << feld[ix][iy] << " ";
			}
		}
	else
		std::cout << "Es sind Unstimmigkeiten in der Vorgabe.";
	std::cout << "\n";
	std::cin >> feld[0][0];
}

mfg fish