Sudoku zur Kompression verwenden

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

SG1

Worauf man aber achten sollte: Nehmt keine Primzahlen als Kantenlaenge. Sonst wirds langweilig.

Ben04

hehejo schrieb:

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

Wenn es um Kompression geht kann man eine Datei auch als folge mehrerer kleiner Sudokus ansehen.

Allerdings sollte es mich wundern wenn der Algorithmus für grössere Sudokus öfters Backtracken müsste. Denn der Fall wo dies nötig ist, ist ein ganz spezieller wo sich alle Kolonnen, Lininen und Kisten in den Schwanz beißen. Bei 9x9 muss man schon gut suchen um solche Sudokus zu finden und bei grösseren sollte es noch schwieriger sein da noch mehr Bedinungen gleichzeitig erfüllt sein müssen. Es kann also durchaus sein, dass die Laufzeit bei grösseren Sudokus besser wird. :p

Desweiteren muss der Algo ja gar nicht alle Sudokus lösen können. Er muss legentlich die lösen können welche der Kompressionsalgo ausgespuckt hat. Man muss also nur den so trimmen, dass der Backtrackfall nicht eintritt.

hehejo

Lösung schrieb:

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.

Naja, die Lösung ist doch grad die Komprimierung..
Wenn du die wieder mit reinsteckst, dann kannste die Datei auch gleich so nehmen.

minhen

Jester schrieb:

Was genau ist für Dich der Unterschied zwischen Zahlen und beliebigen Zeichen? Wir nummerieren einfach die Zeichen durch und fertig.

Ich rede von Bäumchen, Häuschen, Vierecken, irgendwelchen lustigen Zeichen halt. Das diese auf Zahlen abbildbar sind und es bei konkreten Implementierungen mit Rechnern zwangsläufig darauf hinausläuft, liegt schlicht in der Natur der Sache und dürfte kaum erwähnenswert sein.
Bei einem "Real-World-Sudoku" gibt es aber keinen Grund und keine Notwendigkeit irgendwas auf Zahlen oder Ziffern zurückzuführen. Dort ist es schlicht Konvention, dass man Ziffern verwendet. dragon90#s Beitrag lässt aber vermuten, dass er dem Irrtum aufsaß, dass in jedem Feld nur eine Ziffer stehen könne. Dem ist eben nicht so. Und genau darum ging's mir.

Gregor

hehejo schrieb:

Es gibt keine atm noch keine besserer Lösung als einfach auszuprobieren.

Naja. Das ist die Lösung, die man mit dem wenigsten Nachdenken realisieren kann. Ich kann mir durchaus vorstellen, dass es bessere Verfahren zum Lösen eines Sudokus gibt. Vielleicht könnte man das Lösen eines Sudokus irgendwie auf das Lösen eines Gleichungssystems reduzieren? Wenn man die Sudokus nicht eh alle so schnell lösen könnte, würde es sich direkt mal lohnen, solchen Ideen nachzugehen.

hehejo

Und am Ende arbeitest du damit am Problem P=NP.
Wenn du etwas schnellers findest als nur ausprobieren -- dann bist du reich.

Und eines noch @Threadstarter:
DU bist Schuld.
Eigentlich dachte ich, dass ich mich dem Sudokuhype entziehen kann.
Aber jetzt hab ich ein paar teilsweise gemacht und bin "begeistert".

Vielen Dank. :-þ

Gregor

hehejo schrieb:

Und am Ende arbeitest du damit am Problem P=NP.
Wenn du etwas schnellers findest als nur ausprobieren -- dann bist du reich.

Das wäre wohl ne andere Aufgabe. Die Frage ist doch, ob die Problemstellung, die man bei Sudoku hat, überhaupt in NP steckt. Es ist ja nicht so, dass kein Problem, das man irgendwie durch Suche oder ähnliches lösen kann, besser gelöst werden könnte.

yogle

Sudoku zur Kompression verwenden, klingt interessant. Könnte man dabei (falls möglich) nicht auch mehrfach komprimieren?
Ich hatte mir auch mal zum Spaß überlegt, ob man Hashes zur Komprimierung verwenden könnte. So ein MD5-Hash ist in Byteform ja 16 Bytes lang. Angenommen, also wirklich nur rein fiktiv, man hätte eine Tabelle die alle möglichen Hashs von 20 Byte Strings enthält, dann würde man pro Hash 4 Bytes sparen. So eine ganze Datei durch und man hätte einige Bytes gespart. Aber jetzt könnte man ja diese Hashs wieder Hashen usw. usw... Zum Schluss hätte man eine gigabytegroße Datei zu 16 Bytes "komprimiert" und könnte diese dann wieder entkomprimieren.
Reines Gedankenspiel

Gruß
yogle