Problém osmi dam

Problém osmi dam je šachový kombinatorický problém (uveřejněn 1848), jehož cílem je umístit 8 dam na šachovnici takovým způsobem, aby se navzájem neohrožovaly. Zobecněním tohoto problému je problém dam (uveřejněn 1850), jehož cílem je rozmístit dam na šachovnici velikosti $n \times n$ .

Řešení za pomoci backtrackingu

Problém osmi je klasickou algoritmickou úlohou, na níž se ukazuje technika backtrackingu. V backtrackingu se prochází stavový prostor do hloubky takovým způsobem, že si algoritmus pamatuje všechna dosud učiněná rozhodnutí a v případě, že se ukáže, že daná cesta nevede k výsledku, tak se algoritmus vrátí na místo posledního rozhodnutí a změní ho. Tímto vylepšením se vyloučí značné množství potenciálních řešení, které by musel projít algoritmus řešící problém hrubou silou.

Počet řešení problému

N	1	2	3	4	5	6	7	8	9	10	11	12	13	14
Počet	1	0	0	2	10	4	40	92	352	724	2680	14200	73712	365596

/**
 * Problem n dam
 * @author Pavel Micka
 */
public class QueensProblem {
    private int solutionsCount = 0;
    /**
     * Vyresi a vypise na konzoli reseni problemu n dam
     * @param size velikost problemu
     */
    public void solve(int size) {
        boolean[][] array = new boolean[size][size];
        solveQueensProblem(array, 0, 0, true, 0);
        solveQueensProblem(array, 0, 0, false, 0);
    }
    /**
     * Resi problem n dam
     * @param array pole
     * @param x souradnice x, kam se ma vlozit dalsi (tato) dama
     * @param y souradnice y, kam se ma vlozit dalsi (tato) dama
     * @param set zda-li se ma dama vlozit @true - ano, @false - ne
     * @param queensCount kolik dam je jiz v poli vlozeno
     */
    private void solveQueensProblem(boolean[][] array, int x, int y, boolean set, int queensCount) {
        array[y][x] = set;
        if (set && !checkConsistency(array, x, y)) {
            return;
        }
        if (set) {
            queensCount++;
        }

        if (queensCount == array.length) {
            solutionsCount++;
            printArray(array);
            return; //reseni nalezeno
        }
        x = x + 1;//zvysime x
        int overflow = x == array[y].length ? 1 : 0;
        if (overflow == 1) {//pokud x preteklo
            x = 0; //snizime ho na 0
            y += 1; //zvysime y
        }

        if (y >= array.length) {
            return; //konec ulohy, prosli jsme stavovy prostor
        }
        //ucinime obe rozhodnuti
        solveQueensProblem(array, x, y, true, queensCount);
        solveQueensProblem(array, x, y, false, queensCount);

    }
    /**
     * Provede kontrolu ohrozeni damy na diagonalach, vodorovne a svisle ose
     * @param array pole dam
     * @param x kam bude nova dama vlozena na ose x
     * @param y kam bude nova dama vlozena na ose y
     * @return
     */
    private boolean checkConsistency(boolean[][] array, int x, int y) {
        //vodorovne
        for (int i = 0; i < array[y].length; i++) {
            if (i != x && array[y][i] == true) {
                return false;
            }
        }
        //svisle
        for (int i = 0; i < array.length; i++) {
            if (i != y && array[i][x] == true) {
                return false;
            }
        }
        //diagonala leva dolni, prava horni
        int i = 1;
        //vpravo nahoru
        while (x + i < array[y].length && y - i >= 0) {
            if (array[y - i][x + i]) {
                return false;
            }
            i++;
        }
        i = 1;
        //vlevo dolu
        while (x - i >= 0 && y + i < array.length) {
            if (array[y + i][x - i]) {
                return false;
            }
            i++;
        }
        //diagonala leva horni, prava dolni
        i = 1;
        //vlevo nahoru
        while (x - i >= 0 && y - i >= 0) {
            if (array[y - i][x - i]) {
                return false;
            }
            i++;
        }
        i = 1;
        //vpravo dolu
        while (x + i < array[y].length && y + i < array.length) {
            if (array[y + i][x + i]) {
                return false;
            }
            i++;
        }
        return true;
    }
    /**
     * Vypise pole dam
     * @param array pole
     */
    private void printArray(boolean[][] array) {
        System.out.println("Reseni #" + solutionsCount);
        for (int i = 0; i < array.length; i++) {
            System.out.print("\n|");
            for (int j = 0; j < array[i].length; j++) {
                if (array[i][j]) {
                    System.out.print("Q|");
                } else {
                    System.out.print(" |");
                }
            }
        }
        System.out.println("\n---------------------");
    }

    /**
     * @return the solutionsCount
     */
    public int getSolutionsCount() {
        return solutionsCount;
    }
}

/**
 * Problem n dam
 * @author Pavel Micka
 */
class QueensProblem {
private:
    int solutionsCount;
    /**
     * Resi problem n dam
     * @param array pole
     * @param x souradnice x, kam se ma vlozit dalsi (tato) dama
     * @param y souradnice y, kam se ma vlozit dalsi (tato) dama
     * @param set zda-li se ma dama vlozit @true - ano, @false - ne
     * @param queensCount kolik dam je jiz v poli vlozeno
     */
    void solveQueensProblem(bool ** a, int x, int y, bool set, int queensCount, int size) {
        a[y][x] = set;
        if (set && !checkConsistency(a, x, y, size)) {
            return;
        }
        if (set) {
            queensCount++;
        }

        if (queensCount == size) {
            solutionsCount++;
            printArray(a, size);
            return; //reseni nalezeno
        }
        x = x + 1;//zvysime x
        int overflow = x == size ? 1 : 0;
        if (overflow == 1) {//pokud x preteklo
            x = 0; //snizime ho na 0
            y += 1; //zvysime y
        }

        if (y >= size) {
            return; //konec ulohy, prosli jsme stavovy prostor
        }
        //ucinime obe rozhodnuti
        solveQueensProblem(a, x, y, true, queensCount, size);
        solveQueensProblem(a, x, y, false, queensCount, size);

    }
    /**
     * Provede kontrolu ohrozeni damy na diagonalach, vodorovne a svisle ose
     * @param array pole dam
     * @param x kam bude nova dama vlozena na ose x
     * @param y kam bude nova dama vlozena na ose y
     * @return
     */
    bool checkConsistency(bool ** a, int x, int y, int size) {
        //vodorovne
        for (int i = 0; i < size; i++) {
            if (i != x && a[y][i] == true) {
                return false;
            }
        }
        //svisle
        for (int i = 0; i < size; i++) {
            if (i != y && a[i][x] == true) {
                return false;
            }
        }
        //diagonala leva dolni, prava horni

        int j = 1;
        //vpravo nahoru
        while (x + j < size && y - j >= 0) {
            if (a[y - j][x + j]) {
                return false;
            }
            j++;
        }
        j = 1;
        //vlevo dolu
        while (x - j >= 0 && y + j < size) {
            if (a[y + j][x - j]) {
                return false;
            }
            j++;
        }
        //diagonala leva horni, prava dolni
        j = 1;
        //vlevo nahoru
        while (x - j >= 0 && y - j >= 0) {
            if (a[y - j][x - j]) {
                return false;
            }
            j++;
        }
        j = 1;
        //vpravo dolu
        while (x + j < size && y + j < size) {
            if (a[y + j][x + j]) {
                return false;
            }
            j++;
        }
        return true;
        
    }
    /**
     * Vypise pole dam
     * @param array pole
     */
    void printArray(bool ** a, int size) {
        cout << "Reseni #" << this->solutionsCount;
        for (int i = 0; i < size; i++) {
            cout << "\n" << "|";

            for (int j = 0; j < size; j++) {
                if (a[i][j]) {
                    cout << "Q|";
                } else {
                    cout << " |";
                }
            }
        }
        cout << "\n" << "---------------------\n";
    }
public:
    QueensProblem(){
        this->solutionsCount = 0;
    }
    /**
     * Vyresi a vypise na konzoli reseni problemu n dam
     * @param size velikost problemu
     */
    void solve(int size) {
        bool ** a = new bool*[size];
        for(int j = 0; j < size; j++){
            a[j] = new bool[size];
            for(int k = 0;  k < size; k++){
                a[j][k] = false;
            }
        }
        solveQueensProblem(a, 0, 0, true, 0, size);
        solveQueensProblem(a, 0, 0, false, 0, size);
        for(int i = 0; i < size; i ++) delete[] a[i];
        delete[] a;
    }

    /**
     * @return the solutionsCount
     */
    int getSolutionsCount() {
        return solutionsCount;
    }
};

{ zpětná vazba }

Tweet	Delicious
Sdílet

Hodnocení (0): 0

Přečtěte si také

Sudoku

Diskuse

Michy21.6.2010

Značné množství případů se též dá vyloučit faktem, že při umístění n dam na šachovnici velikosti nxn musí být nutně každá dáma v jiném sloupci. Tudíž stačí v cyklu umisťovat i-tou dámu jen v rámci i-tého sloupce. Rozmístění dam pak lze reprezentovat jen pomocí pole unsigned qeens[n] (a i-tá dáma bude pak na poli i,queen[i]). Test konzistence po přidání dámy do sloupce y se pak zjednoduší na
for( int i = 0; i < y; ++i){
// otestovat stejny radek
if( queens[i] == queens[y] ) return false;
// test diagonaly - i-ta dama je v radku nad nove pridanou
if( queens[i] < queens[y] && (queens[y] - queens[i] == y - i) ) return false;
// test diagonaly - i-ta dama je v radku pod nove pridanou
if( queens[i] > queens[y] && ( queens[i] - queens[y] == y - i ) ) return false;
}
return true;
Další možností zrychlení výpočtu je využití symetrie řešení:
mám-li jedno řešení, pak je rozmístění dam vertikálně obrácené též řešením. Takže stačí zkoušet umisťovat první dámu jen do prvních n/2 řádků a při nalezení řešení přidat i to symetrické (při lichém počtu řádků pozor na řešení, kde je první dáma na prostředním řádku - to symetrické bude také nalezeno, takže to dvakrát nezapočítat)