Ondra[sej] Blog

Když jsem před časem programoval Sudoku solver v Javě, použil jsem jednoduchý, dalo by se říci až naivní, přístup k vytvoření zásobníku pro backtracking. Při řešení jednoduchých sudoku naivní implementace nevadí, protože k backtrackování dochází jen minimálně. Jak to je s (ne)efektivností tohoto řešení doopravdy se ukázalo až na opravdu těžkých zadáních z Minimum Sudoku.

Při tvorbě jsem efektivitu moc neřešil – testoval jsem hlavně na jednodušších zadáních, kde řešení nacházel poměrně rychle. Když jsem pak chtěl vyzkoušet “nejtěžší” variaty z Minimum Sudoku, tak mě doba výpočtu v řádu vteřin trochu překvapila a začal jsem do programu mírně vrtat. Vyvrtané informace shrnují následující odstavce.

Na začátek pár slov o reprezentaci dat a uložení hrací plochy. Ke každému políčku (Field) si algoritmus udržuje tři základní údaje: hodnotu políčka (0-9; 0 znamená nevyplněné políčko) a množinu hodnot, které políčku ještě jde přiřadit (jeden bit pro každou hodnotu). Stav hrací plochy je pak uložen jako dvourozměrné pole políček.

Základní myšlenka řešícího algoritmu spočívá v propagaci možných hodnot a backtrackingu, podobně jako v programování s omezujícími podmínkami. Po přiřazení hodnoty jednomu políčku je tato hodnota zakázána všem ostatním políčkům ve stejné skupině (řádku, sloupci, čtverci). Když v některém políčku zbyde jediná hodnota, pak ji tomuto políčku přiřadí (a provede další propagaci). Pokud jsou v některém poli zakázány všechny možné hodnoty, prohledávání v této větvi končí neúspěchem.
Pokud po skončení propagace hodot jsou některá políčka stále nepřiřazená, algoritmus zkusí do takového pole dosadit jednu z povolených hodnot (to, že políčko zůstalo po propagaci volné znamená, že na základě dostupných informací je do něj možné dosadit více než jednu hodnotu) a provádí backtracking.

Naivní řešení

Naivní řešení používá pro uložení zásobníku java.util.Stack<T>. Při každém sestupu při backtrackování se alokuje nová reprezentace hrací plochy a zařadí na zásobník. O staré stavy ze zásobníku, pro které prohledávání selhalo se stará garbage collector. Jednoduché, ale funkční.

private Stack gameStateStack;

private static Field[][] cloneGameState(Field[][] _source) {
  Field[][] clone = new Field[GAME_SIZE][];
  for(int i=0; i < GAME_SIZE; i++)
    clone[i] = new Field[GAME_SIZE];
  for(int x=0; x < GAME_SIZE; x++)
    for(int y=0; y < GAME_SIZE; y++)
      clone[x][y] = new Field(_source[x][y]);
  return clone;
}

private void popGameState() {
  currentGameState = gameStateStack.pop();
}

private void pushGameState() {
  Field[][] new_state = cloneGameState(currentGameState);
  gameStateStack.push(currentGameState);
  currentGameState = new_state;
}


Zlepšení s předalokováním

Teď se nad problémem zamyslíme trochu víc. Je snadné si uvědomit, že při řešení Sudoku 9×9 nikdy nebude hloubka zanoření backtrackingu vyšší než 81 – podle počtu polí na hrací ploše. Ve skutečnosti bude ještě nižší, protože některá pole jsou obsazená již v zadání. 81 je poměrně málo. Dost málo na to, aby šlo všech 81 stavů hrací plochy na zásobníku předalokovat a při backtrackingu do nich jen zkopírovat aktuální stav hry.

// alokováno při inicializaci
private Field[][][] gameStateStack = null;
private int stackPosition = 0;

private void cloneGameState() {
  Field[][] source = gameStateStack[stackPosition - 1];
  Field[][] clone = gameStateStack[stackPosition];
  for(int x=0; x < GAME_SIZE; x++)
    for(int y=0; y < GAME_SIZE; y++)
      clone[x][y].assign(source[x][y]);
}

private void popGameState() {
  stackPosition−−;
  currentGameState = gameStateStack[stackPosition];
}

private void pushGameState() {
  stackPosition++;
  cloneGameState();
  currentGameState = gameStateStack[stackPosition];
}

Výsledky

Efektivitu obou verzí kódu jsem testoval na následujícím zadání (těžké sudoku se sedmnácti podporami):

- - -|- - -|- 1 3
- - -|- 3 -|- 8 -
- 7 -|- - -|- - -
-----+-----+-----
- - -|2 - 6|- - -
- 3 -|- - -|9 - -
- - -|- 1 -|- - -
-----+-----+-----
6 - -|5 - -|2 - 4
- - -|4 - -|7 - -
1 - -|- - -|- - -

Naměřené časy shrnuje tabulka níže. Jde o průměrné časy ze 100 pokusů, aby měl JVM dost času se zahřát. Při řešení jednoho zadání solver provedl vždy 174844 rekurzivních sestupů a tedy i “alokací” nového pole.

Naivní verze:	3140,3 ms (± 30 ms)
Verze bez alokací:	2940,3 ms (± 35 ms)

Časy jsem měřil na počítači s procesorem Intel Core2Duo 1800MHz, spoustou paměti, Gentoo Linuxem a Javou 1.6 (nicméně výsledky na Javě 1.5 jsou obdobné). Rozdíl je sice viditelný (cca 7%), přesto je o dost menší, než jsem čekal. Je vidět, že se v Sunu opravdu snaží o co nejefektivnější JVM a na jejich tvrzení, že nemá smysl optimalizovat na počet alokací opravdu něco bude

This entry was posted on Saturday, January 5th, 2008 at 02:41 and is filed under Java. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.