Pomoc s algoritmem - Backtracking – Java – Fórum – Programujte.com

Dobrý den,

chtěl bych vás poprosit, zda - li byste mi prosím pomohli vytvořit finální fázi mého úkolu do algoritmizace. Nevím si už rady... :smile10:

Dostaneme zadanoý obdelník M*N prvků a několik tetrisových kostiček. Naším úkolem je najít všechna řešení, jakými se dají tyto tetrisové kostičky nacpat do zadané šachovnice. Tyto kostičky lze otočit o 90°, 180° a 270°.

Zpracování velmi krkolomného vstupu už mám za sebou, mám

    public static List<int[][]> uloziste = new ArrayList<int[][]>();

    public static List<int[][]> uloziste1 = new ArrayList<int[][]>();

    public static List<int[][]> uloziste2 = new ArrayList<int[][]>();

    public static List<int[][]> uloziste3 = new ArrayList<int[][]>();

int[][] podklad

Zde přidávám zdroják :o)

Je samozřejmě několik možností, jak to řešit. Problém je totiž v tom, že nezáleží jenom na tom, kde se začne, ale i s jakou a jak natočenou kostičkou. Řešení by se tedy dalo rozdělit na 2 části: výběr kostiček (v daném pořadí a rotaci) a umisťování do hracího pole. Vytvořit si algoritmus na získání sady kostiček (pořadí + rotace - ne všechny jsou rozdílné v rotaci), tj. postupně vygenerovat všechny možnosti. A v druhé části je postupně umísťovat, stačí tupě zkoušet pozici po pozici (kolize jsou neperspektivní větve atd.).

Když budu mít zadané velké hrací pole a pouze jednu kostičku, tak vlastně všechny možnosti jsou i řešení. To je potřeba mít na paměti než začneš svoje řešení (až ho budeš mít) optimalizovat.

To liborb :

Děkuji za odpověď!

Momentálně jsem ve stavu, kdy mám toto:

public static void Hledac(int indexKosticky, int[][] policko) {

        int souradniceX = 0;

        int souradniceY = 0;





        // ----

        for (int i = 0; i < policko.length - uloziste.get(indexKosticky).length + 1; i++) {

            for (int j = 0; j < policko[0].length - uloziste.get(indexKosticky)[0].length + 1; j++) {



                int zdaLi = 0;

                // overovani kosticky

                for (int k = 0; k < uloziste.get(indexKosticky).length; k++) {

                    for (int l = 0; l < uloziste.get(indexKosticky)[0].length; l++) {



                        if ((policko[i + k][j + l] == 1) || (policko[i + k][j + l] > 1 && uloziste.get(indexKosticky)[k][l] == 0) || (policko[i + k][j + l] == 0 && uloziste.get(indexKosticky)[k][l] == 0)) {

                        } else {

                            zdaLi++;

                        }

                    }

                }

                if (zdaLi == 0) {

                    souradniceY = i;

                    souradniceX = j;



                    // kopceni do pomocneho policka

                    for (int k = 0; k < policko.length; k++) {

                        for (int l = 0; l < policko[0].length; l++) {

                            copik[k][l] = policko[k][l];

                        }

                    }



                    for (int k = 0; k < uloziste.get(indexKosticky).length; k++) {

                        for (int l = 0; l < uloziste.get(indexKosticky)[0].length; l++) {

                            copik[k + souradniceY][l + souradniceX] += uloziste.get(indexKosticky)[k][l];

                        }



                    }



                    if (indexKosticky + 1 < uloziste.size()) {

                        Hledac(indexKosticky + 1, copik);

                    } else {

                        Vypisovac(copik);

                    }



                }



            }

        }







        // ---- otocene o 90

        if (uloziste1.get(indexKosticky)[0][0] != -9) {

            for (int i = 0; i < policko.length - uloziste1.get(indexKosticky).length + 1; i++) {

                for (int j = 0; j < policko[0].length - uloziste1.get(indexKosticky)[0].length + 1; j++) {



                    int zdaLi = 0;

                    // overovani kosticky

                    for (int k = 0; k < uloziste1.get(indexKosticky).length; k++) {

                        for (int l = 0; l < uloziste1.get(indexKosticky)[0].length; l++) {



                            if ((policko[i + k][j + l] == 1) || (policko[i + k][j + l] > 1 && uloziste1.get(indexKosticky)[k][l] == 0) || (policko[i + k][j + l] == 0 && uloziste1.get(indexKosticky)[k][l] == 0)) {

                            } else {

                                zdaLi++;

                            }





                        }

                    }

                    if (zdaLi == 0) {

                        souradniceY = i;

                        souradniceX = j;



                        // kopceni do pomocneho policka

                        for (int k = 0; k < policko.length; k++) {

                            for (int l = 0; l < policko[0].length; l++) {

                                copik[k][l] = policko[k][l];

                            }

                        }





                        for (int k = 0; k < uloziste1.get(indexKosticky).length; k++) {

                            for (int l = 0; l < uloziste1.get(indexKosticky)[0].length; l++) {

                                copik[k + souradniceY][l + souradniceX] += uloziste1.get(indexKosticky)[k][l];

                            }



                        }





                        if (indexKosticky + 1 < uloziste1.size()) {

                            Hledac(indexKosticky + 1, copik);

                        } else {

                            Vypisovac(copik);

                        }

                    }



                }

            }

        }











        // --- otocene o 180

        if (uloziste2.get(indexKosticky)[0][0] != -9) {

            for (int i = 0; i < policko.length - uloziste2.get(indexKosticky).length + 1; i++) {

                for (int j = 0; j < policko[0].length - uloziste2.get(indexKosticky)[0].length + 1; j++) {



                    int zdaLi = 0;

                    // overovani kosticky

                    for (int k = 0; k < uloziste2.get(indexKosticky).length; k++) {

                        for (int l = 0; l < uloziste2.get(indexKosticky)[0].length; l++) {



                            if ((policko[i + k][j + l] == 1) || (policko[i + k][j + l] > 1 && uloziste2.get(indexKosticky)[k][l] == 0) || (policko[i + k][j + l] == 0 && uloziste2.get(indexKosticky)[k][l] == 0)) {

                            } else {

                                zdaLi++;

                            }





                        }

                    }

                    if (zdaLi == 0) {

                        souradniceY = i;

                        souradniceX = j;



                        // kopceni do pomocneho policka

                        for (int k = 0; k < policko.length; k++) {

                            for (int l = 0; l < policko[0].length; l++) {

                                copik[k][l] = policko[k][l];

                            }

                        }





                        for (int k = 0; k < uloziste2.get(indexKosticky).length; k++) {

                            for (int l = 0; l < uloziste2.get(indexKosticky)[0].length; l++) {

                                copik[k + souradniceY][l + souradniceX] += uloziste2.get(indexKosticky)[k][l];

                            }



                        }









                        if (indexKosticky + 1 < uloziste2.size()) {

                            Hledac(indexKosticky + 1, copik);

                        } else {

                            Vypisovac(copik);

                        }

                    }



                }

            }

        }









        // --- otocene o 270

        if (uloziste3.get(indexKosticky)[0][0] != -9) {

            for (int i = 0; i < policko.length - uloziste3.get(indexKosticky).length + 1; i++) {

                for (int j = 0; j < policko[0].length - uloziste3.get(indexKosticky)[0].length + 1; j++) {



                    int zdaLi = 0;

                    // overovani kosticky

                    for (int k = 0; k < uloziste3.get(indexKosticky).length; k++) {

                        for (int l = 0; l < uloziste3.get(indexKosticky)[0].length; l++) {



                            if ((policko[i + k][j + l] == 1) || (policko[i + k][j + l] > 1 && uloziste3.get(indexKosticky)[k][l] == 0) || (policko[i + k][j + l] == 0 && uloziste3.get(indexKosticky)[k][l] == 0)) {

                            } else {

                                zdaLi++;

                            }





                        }

                    }

                    if (zdaLi == 0) {

                        souradniceY = i;

                        souradniceX = j;



                        // kopceni do pomocneho policka

                        for (int k = 0; k < policko.length; k++) {

                            for (int l = 0; l < policko[0].length; l++) {

                                copik[k][l] = policko[k][l];

                            }

                        }





                        for (int k = 0; k < uloziste3.get(indexKosticky).length; k++) {

                            for (int l = 0; l < uloziste3.get(indexKosticky)[0].length; l++) {

                                copik[k + souradniceY][l + souradniceX] += uloziste3.get(indexKosticky)[k][l];

                            }



                        }









                        if (indexKosticky + 1 < uloziste3.size()) {

                            Hledac(indexKosticky + 1, copik);

                        } else {

                            Vypisovac(copik);

                        }

                    }



                }

            }

        }



    }

Pokud je není možné krokování, tak doporučuji ladící výpisy, abys viděl, kde se co děje a proč. Kde to končí a proč atd.

No a pokud chceš pomoci trochu víc :smile1:, tak se hoď kompletní zdroják i popis jak se to pohání (vstup).