Sudoku zur Kompression verwenden

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

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

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