Sudoku zur Kompression verwenden

hehejo

Ich will deine Idee ja nicht madig machen, aber Sudoko ist in NP.
NP ist die Klasse der Probleme die durch eine nichtdeterministische Turingmaschine in polynomieller Zeit gelöst werden kann.
Die nichtdet. TM rät eine Lösung und verifiziert diese dann.
Zufällig rät die nichtdet. TM immer die richtige Lösung.

Ein normales Programm braucht dazu aber eine exponentielle Laufzeit, da es kein besseres Verfahren gibt. als einfach "jede mögliche Lösung ausprobieren".

Exponentielle Laufzeit ist :evil:.
Kannst dir selbst mal ausrechnen:
Du hast eine CPU die 1000 Instruktionen pro Sekunde machen kann.
In den Feldern steht die maximale Größe von n bei vorgegebener Rechenezeit

Laufzeit | Rechenzeit
| 0,01s 1s 1min 1h
n | 10 1000 60000 36000000
nlogn | 4 140 493 204094
n² | 3 31 244 1897
n³ | 2 10 39 153
2^n | 3 9 15 21

Also kannst du mit diesem Rechner in einer Stunde ein Sudoku-Rätsel der Größe
21 lösen.
Jetzt wirst du dir sagen: 1000 Operationen pro Sekunde, das ist ja lächerlich.
Nagut, verzehnfachen wir die Rechengeschwindigkeit

Jetzt macht dein Rechner 10000 Ops pro Sekunde und kann in einer Stunde
dennoch nur ein Sudokufeld der Größe 24 berechnen.

Wie groß müsste jetzt so ein Sudokufeld sein, dammit du damit eine normalgroße
Datei komprimieren kannst?
Und wie lange wird der PC brauchen um diese Datei wieder zu entpacken?

http://de.wikipedia.org/wiki/NP_(Komplexitätsklasse)
Die Zahlen habe ich meiner Vorleseung in Theoretischer Informatik entnommen.

edit
Da hier meine Tabellen zerhaut werden, hab ich mir mal die Mühe gemacht und das per HTML geschrieben.
http://www.hehejo.de/download/Laufzeit.html

Du hättest bei dem Verfahren ja sogar zweimal den exponentiellen Aufwand.
Einmal beim Einfügen der Daten ins Sudokufeld und dann beim Lösen durch den Computer.

Ich gebe zu, die Komprimierung wäre immens -> aber es dauert einfach viel zu lange.

Gregor

hehejo schrieb:

Ein normales Programm braucht dazu aber eine exponentielle Laufzeit, da es kein besseres Verfahren gibt. als einfach "jede mögliche Lösung ausprobieren".

Theoretisch vielleicht. ...wobei ich mir nicht sicher bin, dass es da keine intelligentere Lösung als ne Suche gibt.

Praktisch gesehen habe ich mal einen Sudoku-Löser programmiert, der auf Suche basiert. Bei den Sudokus, die ich damit gelöst habe, war es eigentlich so, dass man bei den meisten Feldern keinerlei Wahlmöglichkeiten hatte. ...kann allerdings auch daran liegen dass man den Menschen da nicht mehr zutraut: Ich weiß nicht, ob es auch viel schwerere Sudokus geben kann, die eindeutig lösbar sind. Das Programm war für klassische Sudokus mit 9*9 Feldern: Hat pro Sudoku etwa 10-40ms an Zeit benötigt. ...und war eigentlich relativ naiv und ohne besondere Optimierungen programmiert.

Jester

hehejo schrieb:

Ich will deine Idee ja nicht madig machen, aber Sudoko ist in NP.
NP ist die Klasse der Probleme die durch eine nichtdeterministische Turingmaschine in polynomieller Zeit gelöst werden kann.
Die nichtdet. TM rät eine Lösung und verifiziert diese dann.
Zufällig rät die nichtdet. TM immer die richtige Lösung.

Ein normales Programm braucht dazu aber eine exponentielle Laufzeit, da es kein besseres Verfahren gibt. als einfach "jede mögliche Lösung ausprobieren".

Hui, das sind ja ganz viele Sachen auf einmal.

Es ist in NP. Sortieren ist auch in NP. Trotzdem kann man es effizient lösen. Du meinst vermutlich, daß es NP-vollständig ist. Auch dann ist der Schluß, daß ein normales Programm exponentielle Laufzeit benötigt zumindest noch nicht richtig. Es weiß keiner, ob P=NP gilt oder nicht. Deswegen wissen wir auch nicht, ob das nun effizient lösbar ist, oder nicht.

Korbinian

...des weiteren gibt es fuer fast jedes Problem eine vernuenftige Heuristik, die dann wieder an vernuenftige Laufzeiten ranfuehrt.

@hehejo: weist was ich mein mit 'Theorie ja - aber in massen und zur richtigen Zeit'?

Gregor

Korbinian schrieb:

...des weiteren gibt es fuer fast jedes Problem eine vernuenftige Heuristik, die dann wieder an vernuenftige Laufzeiten ranfuehrt.

Ich habe es in meinem Programm folgendermaßen gemacht:

...eigentlich so, wie man Sudokus auch per Hand löst: Ich behandele immer das Feld als nächstes, für das es am wenigsten Wahlmöglichkeiten gibt. Das ist zwar nicht in dem Sinne eine klassische Heuristik, aber trotzdem eine Lösungsstrategie, die einem das Problem in der Praxis enorm vereinfacht.

hehejo

Ja scho.

Aber ich denke ihr wisst auf was ich hinauswill.

Und auch wenn man ein 9x9 Sudodu schnell lösen kann - was will man damit komprimieren?

+++Sorry, keine Antwort auf die Frage+++

@Gregor

Dein Programm würd mich interessieren. Darf ich mir das bitte mal anguggen?
Ich hab auch schon mal versucht sowas zu programmieren, bin aber noch nicht so gut.

Gregor

Interessierter schrieb:

@Gregor

Dein Programm würd mich interessieren. Darf ich mir das bitte mal anguggen?
Ich hab auch schon mal versucht sowas zu programmieren, bin aber noch nicht so gut.

Sicher. ...hab das hier eh schonmal gepostet:

import java.io.*;

public class SudokuSolver
{
   public static void main(String[] args)
   {
      if(args.length != 1)
      {
         System.out.println("Wrong number of parameters.");
         System.exit(1);
      }
      int[][] sudoku = null;
      try
      {
         sudoku = loadSudoku(args[0]);
      }
      catch(IOException e)
      {
         System.out.println(e);
      }
      if (sudoku == null)
      {
         System.out.println("Could not load Sudoku!");
         System.exit(1);
      }
      System.out.println("Eingelesenes Sudoku:");
      System.out.println();
      printSudoku(sudoku);
      System.out.println();
      long time = System.currentTimeMillis();
      int[][] outSudoku = solveSudoku(sudoku);
      time = System.currentTimeMillis() - time;
      System.out.println("Gelöstes Sudoku:");
      System.out.println();
      if (sudoku == null) System.out.println("Sudoku konnte nicht gelöst werden!");
      else printSudoku(outSudoku);
      System.out.println();
      System.out.println("Benötigte Zeit in (ms):");
      System.out.println(time);
   }

   public static int[][] loadSudoku(String filename) throws IOException
   {
      String[] lines = new String[9];
      BufferedReader reader = new BufferedReader(new FileReader(filename));
      for (int i = 0 ; i < 9 ; ++i)
      {
         if(reader.ready())
         {
            lines[i] = reader.readLine();
            if(lines[i].length() != 9) return null;
         }
         else return null;
      }
      int[][] sudoku = new int[9][9];
      for(int y = 0 ; y < 9 ; ++y)
      {
         for (int x = 0 ; x < 9 ; ++x)
         {
            final char currentChar = lines[y].charAt(x);
            if ((currentChar <= '9') && (currentChar >= '1'))
            {
               sudoku[x][y] = 1 + (int)(currentChar - '1');
            }
         }
      }
      return sudoku;
   }

   public static void printSudoku(int[][] sudoku)
   {
      for(int y = 0 ; y < 9 ; ++y)
      {
         if (y % 3 == 0) 
         {
            System.out.println(" XXXXXXXXXXXXXXXXXXX");
         }
         for (int x = 0 ; x < 9 ; ++x)
         {
            if (x % 3 == 0) System.out.print(" X ");
            if (sudoku[x][y] == 0) System.out.print("_");
            else System.out.print(sudoku[x][y]);
         }
         System.out.println(" X");
      }
      System.out.println(" XXXXXXXXXXXXXXXXXXX");
   }

   public static int[][] solveSudoku(int[][] sudoku)
   {
      boolean[][][] possibleSudoku = new boolean[9][9][];
      for (int x = 0 ; x < 9 ; ++x)
      {
         for(int y = 0 ; y < 9 ; ++y)
         {
            if (sudoku[x][y] != 0)
            {
               possibleSudoku[x][y] = null;
               continue;
            }
            possibleSudoku[x][y] = getPossibleNumbers(sudoku, x, y);
         }
      }
      int minCount = 11;
      int minX = -1;
      int minY = -1;
      for (int x = 0 ; x < 9 ; ++x)
      {
         for(int y = 0 ; y < 9 ; ++y)
         {
            if (possibleSudoku[x][y] == null) continue;
            int freeNumbers = getFreeNumberCount(possibleSudoku[x][y]);
            if (freeNumbers == 0) return null;
            if (freeNumbers < minCount)
            {
               minCount = freeNumbers;
               minX = x;
               minY = y;
            }
         }
      }
      if (minX == -1) return sudoku;
      //System.out.println("minCount : " + minCount);
      for (int i = 1 ; i < 10 ; ++i)
      {
         if (!possibleSudoku[minX][minY][i]) continue;
         sudoku[minX][minY] = i;
         int[][] outSudoku = solveSudoku(sudoku);
         if(outSudoku != null) return outSudoku;
         sudoku[minX][minY] = 0;
      }
      return null;
   }

   public static int getFreeNumberCount (boolean[] possibleNumbers)
   {
      int count = 0;
      for(int i = 1 ; i < possibleNumbers.length ; ++i)
      {
         if(possibleNumbers[i]) ++count;
      }
      return count;
   }

   public static boolean[] getPossibleNumbers(int[][] sudoku, int x, int y)
   {
      if (sudoku[x][y] != 0) return null;
      boolean[] possibleNumbers = new boolean[10];
      for (int i = 0 ; i < 10 ; ++i)
      {
         possibleNumbers[i] = true;
      }
      for (int i = 0 ; i < 9 ; ++i)
      {
         possibleNumbers[sudoku[x][i]] = false;
         possibleNumbers[sudoku[i][y]] = false;
      }
      int boxX = x / 3;
      int boxY = y / 3;
      for(int i = 0 ; i < 3 ; ++i)
      {
         for(int j = 0 ; j < 3 ; ++j)
         {
            possibleNumbers[sudoku[3*boxX+i][3*boxY+j]] = false;
         }
      }
      return possibleNumbers;
   }
}

Als Eingabe werden Textdateien in folgender Art genutzt:

Halt 9 Zeilen mit jeweils 9 Zeichen (kein Zeichen mehr oder weniger). Wenn ein Zeichen eine Ziffer zwischen 1 und 9 ist, dann ist die entsprechende Ziffer vorgegeben. Wenn es irgendetwas anderes ist, dann ist für das entsprechende Feld nichts vorgegeben.

aber wieso in java? das ist voll langsam. das kann ja nichtgut sein

Gregor

Kluger Einwand schrieb:

aber wieso in java? das ist voll langsam. das kann ja nichtgut sein

Na wenn Du meinst.

...aber das war eh nur so ne Art erstes Testprogramm. Ich hatte erwartet, dass Sudokus teilweise ziemlich lange dauern würden. ...auch für den Rechner. Deshalb habe ich dann erstmal so ein kleines Progrämmchen hingeklatscht, um das mal anzutesten. Eigentlich wollte ich da später noch mehr Aufwand reinstecken, was den Algorithmus betrifft. Aber da das Lösen der Sudokus eh nur'n paar Millisekunden dauert, hab ich das dann gelassen. Meine Einschätzung des Problems war einfach falsch. Es lohnt sich praktsich nicht, sich damit zu beschäftigen, es sei denn, man will mal irgendwas in Richtung Suche oder Backtracking ausprobieren.

Der Flaschenhals an diesem Programm ist im Übrigen die Eingabe. Es dauert vermutlich in etwa eine Minute, so eine Textdatei zu schreiben. Wenn man das Programm also beschleunigen will, dann sollte man in erster Linie ne GUI schreiben, die einem ne schnelle Eingabe ermöglicht.

Danke,

sieht nicht schlecht aus. Werd mal versuchen, ob ich das nach C++ umschreiben kann. (kann kein Java)

Ben04

Ich hatte auch mal ein Lösungsprogram geschrieben.

#include <iostream>
#include <fstream>
#include <bitset>
#include <cassert>
#include <cctype>
#include <algorithm>

typedef unsigned uint;

template<class T>
class LineAccesser{
  typedef T Data[9][9];
public:
  LineAccesser(Data&data, uint line):
    data(data), line(line){}

  T&operator()(uint i)const{
    return data[i][line];
  }
private:
  uint line;
  Data&data;
};

template<class T>
class ColumnAccesser{
  typedef T Data[9][9];
public:
  ColumnAccesser(Data&data, uint col):
    data(data), col(col){}

  T&operator()(uint i)const{
    return data[col][i];
  }
private:
  uint col;
  Data&data;
};

template<class T>
class BoxAccesser{
  typedef T Data[9][9];
public:
  BoxAccesser(Data&data, uint x, uint y):
    data(data), x(x*3), y(y*3){}

  BoxAccesser(Data&data, uint box):
    data(data), x((box/3)*3), y((box%3)*3){}

  T&operator()(uint i)const{
    return data[x+i/3][y+i%3];
  }
private:
  uint x,y;
  Data&data;
};

struct Board{
public:
  LineAccesser<std::bitset<9> > get_line(uint line){
    return LineAccesser<std::bitset<9> >(data, line);
  }

  LineAccesser<const std::bitset<9> > get_line(uint line)const{
    return LineAccesser<const std::bitset<9> >(data, line);
  }

  ColumnAccesser<std::bitset<9> > get_col(uint col){
    return ColumnAccesser<std::bitset<9> >(data, col);
  }

  ColumnAccesser<const std::bitset<9> > get_col(uint col)const{
    return ColumnAccesser<const std::bitset<9> >(data, col);
  }

  BoxAccesser<std::bitset<9> > get_box(uint box){
    return BoxAccesser<std::bitset<9> >(data, box);
  }

  BoxAccesser<const std::bitset<9> > get_box(uint box)const{
    return BoxAccesser<const std::bitset<9> >(data, box);
  }

  BoxAccesser<std::bitset<9> > get_box(uint x, uint y){
    return BoxAccesser<std::bitset<9> >(data, x, y);
  }

  BoxAccesser<const std::bitset<9> > get_box(uint x, uint y)const{
    return BoxAccesser<const std::bitset<9> >(data, x, y);
  }

  std::bitset<9>*operator[](uint i){
    return data[i];
  }

  const std::bitset<9>*operator[](uint i)const{
    return data[i];
  }

private:
  std::bitset<9>data[9][9];
};

template<class CharT>
std::basic_istream<CharT>&operator>>(std::basic_istream<CharT>&in, Board&board){
  for(uint y=0;y<9;++y)
    for(uint x=0;x<9;++x){
      char val;
      do{
				in>>std::ws;
        if((val = in.get()) == EOF)
          return in;
				if(val == '.')
					val = '0';
				/*if(!isdigit(val)){
					assert(false);
				}*/
      }while(!std::isdigit(val));

      if(val != '0'){
        board[x][y].reset();
        board[x][y].set(val-'0'-1); // non standard coversion digit => integer
      }else
        board[x][y].set();
    }
  return in;
}

template<uint size>
uint find_bit(const std::bitset<size>&bits){
  if(bits.count() == 1)
    for(uint i=0; i<size; ++i)
      if(bits.test(i))
        return i+1;
  return 0;
}

template<class CharT>
std::basic_ostream<CharT>&operator<<(std::basic_ostream<CharT>&out, LineAccesser<const std::bitset<9> >line){
  return out
    <<find_bit(line(0))<<' '<<find_bit(line(1))<<' '<<find_bit(line(2))<<'|'
    <<find_bit(line(3))<<' '<<find_bit(line(4))<<' '<<find_bit(line(5))<<'|'
    <<find_bit(line(6))<<' '<<find_bit(line(7))<<' '<<find_bit(line(8));
}

template<class CharT>
std::basic_ostream<CharT>&operator<<(std::basic_ostream<CharT>&out, const Board&board){
  return out
    <<board.get_line(0)<<'\n'<<board.get_line(1)<<'\n'<<board.get_line(2)<<'\n'
    <<"-----+-----+-----\n"
    <<board.get_line(3)<<'\n'<<board.get_line(4)<<'\n'<<board.get_line(5)<<'\n'
    <<"-----+-----+-----\n"
    <<board.get_line(6)<<'\n'<<board.get_line(7)<<'\n'<<board.get_line(8);
}

template<class Seq>
bool exclude(Seq seq,  uint bit, const std::bitset<9>*except){
  bool changed = false;
  for(uint i=0; i<9; ++i)
    if(seq(i).test(bit) && &seq(i) != except){
      changed = true;
      seq(i).reset(bit);
    }
  return changed;
}

template<class Seq>
bool find_unique_possible(Seq seq){
  bool changed = false;
  for(uint bit=0; bit<9; ++bit){
    uint unique_cell = 9;
    for(uint cell=0; cell<9; ++cell)
      if(seq(cell).test(bit))
        if(unique_cell == 9)
          unique_cell = cell;
        else{
          unique_cell = 9;
          break;
        }
    if(unique_cell != 9){
      if(find_bit(seq(unique_cell)) == 0){
        seq(unique_cell).reset();
        seq(unique_cell).set(bit);
        changed = true;
      }
    }
  }
  return changed;
}

void cross_all_impossible(Board&board)
{
  bool changed;
  do{
    changed = false;
    for(uint x=0; x<9; ++x)
      for(uint y=0; y<9; ++y){
        uint bit = find_bit(board[x][y]);
        if(bit != 0){
          if(exclude(board.get_box(x/3, y/3), bit-1, &board[x][y]))
            changed = true;
          if(exclude(board.get_line(y), bit-1, &board[x][y]))
            changed = true;
          if(exclude(board.get_col(x), bit-1, &board[x][y]))
            changed = true;
          board[x][y].set(bit-1);
        }
      }
  }while(changed);
}

bool find_all_unique_possible(Board&board)
{
  bool changed, overall_changed = false;
  do{
    changed = false;
    for(uint line=0; line<9; ++line)
      if(find_unique_possible(board.get_line(line)))
        changed = true;
    for(uint col=0; col<9; ++col)
      if(find_unique_possible(board.get_col(col)))
        changed = true;
    for(uint box=0; box<9; ++box)
      if(find_unique_possible(board.get_box(box)))
        changed = true;
    if(changed)
      overall_changed = true;
  }while(changed);
  return overall_changed;
}

template<class Seq>
bool is_correctly_solved(Seq seq){
  for(uint bit=1; bit<=9; ++bit){
    bool found = false;
    for(uint cell=0; cell<9; ++cell){
      uint bit_set = find_bit(seq(cell));
      if(!bit_set)
        return false;
      if(bit_set == bit)
        if(found)
          return false;
        else
          found = true;
    }
  }
  return true;
}

bool is_solved(Board&board)
{
  for(uint line=0; line<9; ++line)
    if(!is_correctly_solved(board.get_line(line)))
      return false;
  for(uint col=0; col<9; ++col)
    if(!is_correctly_solved(board.get_col(col)))
      return false;
  for(uint box=0; box<9; ++box)
    if(!is_correctly_solved(board.get_box(box)))
      return false;
  return true;
}

void find_optimial_back_track_cell(const Board&board, uint&min_x, uint&min_y)
{
  // sub optimal but needed rarly enough.
  min_x = 0;
  min_y = 0;
  uint min_pos = 10;
  for(uint x=0; x<9; ++x)
    for(uint y=0; y<9; ++y){
      uint pos = board[x][y].count();
      if(pos != 1 && pos < min_pos){
        min_pos = pos;
        min_x = x;
        min_y = y;
      }
    }
}

bool solve(Board&board)
{
  do{
    cross_all_impossible(board);
  }while(find_all_unique_possible(board));
  if(!is_solved(board)){
    uint x, y;
    find_optimial_back_track_cell(board, x, y);

    std::bitset<9>pos = board[x][y];
    for(uint bit=0; bit<9; ++bit)
      if(pos.test(bit)){
        Board backup(board);
        board[x][y].reset();
        board[x][y].set(bit);
        if(solve(board))
          return true;
        board = backup;
      }
    return false;
  }
  return true;
}

int main(int argc, char*argv[])
{
  Board board;
  bool loaded = false;

  if(argc == 2){
    std::ifstream in(argv[1]);
    if(!in){
      std::cerr<<"Error : Could not open file \""<<argv[1]<<"\"."<<std::endl;
      return 2;
    }
    if(!(in>>board)){
      std::cerr<<"Error : Input sudoku format is wrong."<<std::endl;
      return 2;
    }
  }else if(argc>2){
    std::cerr<<"Error : Too many commandline arguments."<<std::endl;
    return 2;
  }else{
    for(;;){
			if(!(std::cin>>board)){
				std::cerr<<"Error : Input sudoku format is wrong."<<std::endl;
				return 2;
			}
			if(!solve(board))
				std::cout<<"This sudoku has no solutions"<<std::endl;
			else
				std::cout<<board;
		}
	}

  if(!solve(board))
    std::cout<<"This sudoku has no solutions"<<std::endl;
  else
    std::cout<<board;
	return 0;
}

Geht sehr schnell und bei den meisten Sudokus muss das Program nicht einmal backtracken. Bei sehr schwierigen Sudokus ein paar mal aber immer noch beinahe nie.

Das Problem sehe ich eher bei der Kompression. Wie weiß man wieviele und vor allem welche Ziffern man fallen lassen kann?

hehejo

for(uint bit=0; bit<9; ++bit)
  if(pos.test(bit)){
    Board backup(board);
    board[x][y].reset();
    board[x][y].set(bit);
    if(solve(board))
      return true;
    board = backup;
  }
}

Tja, hier sieht man das was ich meinte.
Es gibt keine atm noch keine besserer Lösung als einfach auszuprobieren. Das hier ist jetzt nur ein Ausschnitt der Funktion solve..

Ben04

Der allerdings sehr sehr selten zum Einsatz. Ich hab noch kein Sudoku gesehen das eine Rekurionstiefe von mehr als 5 erreicht hat.

hehejo

Nun, das mag für kleine Sudokus gelten.
Aber wenn du in einem Sudoku eine große Datei reinschreiben willst, dann muss das Sudoku ja entsprechend groß werden...

Jester

Wie genau sieht denn eigentlich ein größeres Sudoku aus?

Jester schrieb:

Wie genau sieht denn eigentlich ein größeres Sudoku aus?

Na nen 15*15 Sudoku im Hexadezimalsystem z.B.

Man kann die Lösung auch schon vorher errechnen und dann in die komprimierte Datei mit einfügen. Dann geht das extrahieren natürlich sehr viel schneller, da die Berechnung nicht mehr gemacht werden müssen.

minhen

dragon90# schrieb:

Jester schrieb:

Wie genau sieht denn eigentlich ein größeres Sudoku aus?

Na nen 15*15 Sudoku im Hexadezimalsystem z.B.

Sudokus müssen nicht mit Ziffern realisiert werden. Man kann ohne Weiteres auch ein 100x100 Sudoku mit den entsprechenden Zahlen machen. Wer sagt denn, dass pro Feld immer nur eine Ziffer notiert sein darf? Genau genommen kann man Sudokus sogar mit absolut beliebigen Zeichen machen.
Dass die beiden hier vorgestellten "Löser" mit solchen Sudokus nicht umgehen können, ist eine andere Geschichte.

Jester

Was genau ist für Dich der Unterschied zwischen Zahlen und beliebigen Zeichen? Wir nummerieren einfach die Zeichen durch und fertig. Ich wollte nur wissen, wie man es sinnvoll verallgemeinert.

Damit können die beiden Löser damit schon umgehen (vielleicht müßte man noch die Schleifengrenze hochsetzen).