Java lernen

Choco Solver,

Diskutiere Choco Solver, im Mathematik Forum; Ich knobele an folgender Aufgabe: Springerproblem: Ermittlung aller Stellungen auf einem Schachbrett (der normalen Größe 8x8), bei denen nur je...

  1. Barista
    Barista Mitglied
    Ich knobele an folgender Aufgabe:

    Springerproblem:

    Ermittlung aller Stellungen auf einem Schachbrett (der normalen Größe 8x8),
    bei denen nur je ein weißer und ein schwarzer Springer frei so positioniert sind,
    dass diese sich gegenseitig bedrohen.

    Die Visualisierung der gesuchten Stellungen kann sehr einfach gehalten sein.

    Mit einfacher Java-Programmierung habe ich es bereits gelöst.

    In JavaSpektrum 1/2018 war ein Artikel über Constraint Programming mit dem Choco Solver http://www.choco-solver.org/

    Da mir oft vorgeworfen wird, meist zu viel selbst zu programmieren, wollte ich diesen Solver mal verwenden.

    In der Eclipse muss man sich ein Maven-Projekt anlegen.

    Den Choco Solver bindet man in die pom.xml ein mit

    HTML:
      <dependencies>
        <dependency>
          <groupId>org.choco-solver</groupId>
          <artifactId>choco-solver</artifactId>
          <version>4.0.4</version>
          <scope>runtime</scope>
        </dependency>
      </dependencies>
    Code (Java):
    package de.heinerkuecker.springer_problem_choco_solver;

    import java.util.List;

    import org.chocosolver.solver.Model;
    import org.chocosolver.solver.Solution;
    import org.chocosolver.solver.Solver;
    import org.chocosolver.solver.expression.discrete.arithmetic.ArExpression;
    import org.chocosolver.solver.expression.discrete.relational.ReExpression;
    import org.chocosolver.solver.variables.IntVar;

    /**
    * <h2>Springerproblem</h2>
    *
    * Ermittlung aller Stellungen auf einem Schachbrett (der normalen Größe 8x8),
    * bei denen nur je ein weißer und ein schwarzer Springer frei so positioniert sind,
    * dass diese sich gegenseitig bedrohen.
    * <br/>
    * Die Visualisierung der gesuchten Stellungen kann sehr einfach gehalten sein.
    * </p>
    *
    * @author Barista
    */

    public final class Main {

        /**
         * @param args
         */

        public static void main(String[] args) {

            // Anzahl Zeilen und Anzahl Spalten des Spielfeldes
            final int SIZE = 8;

            // maximaler Zeilen- und Spalten-Wert
            final int MAX = SIZE - 1;

            final Model model = new Model( "All mutual threat knights playing positions" );

            // =================
            // === Variables ===
            // =================

            final IntVar white_row = model.intVar( "white row" , 0 , MAX );
            final IntVar white_col = model.intVar( "white col" , 0 , MAX );

            final IntVar black_row = model.intVar( "black row" , 0 , MAX );
            final IntVar black_col = model.intVar( "black col" , 0 , MAX );

            // ===================
            // === Constraints ===
            // ===================

            // die Positionen des weißen und des schwarzen Springer müssen unterschiedlich sein

            final ArExpression white_row_mul_SIZE = white_row.mul( SIZE );
            final ArExpression white_row_mul_SIZE_add_white_col = white_row_mul_SIZE.add( white_col );

            final ArExpression black_row_mul_SIZE = black_row.mul( SIZE );
            final ArExpression black_row_mul_SIZE_add_black_col = black_row_mul_SIZE.add( black_col );

            final ReExpression white_pos__not_equal__black_pos = white_row_mul_SIZE_add_white_col.ne( black_row_mul_SIZE_add_black_col );

            model.???keine Ahnung, wie ich die ReExpression zum Model hinzufuegen kann???

            // === Solution ===

            final Solver solver = model.getSolver();

            final List<Solution> solutions = solver.findAllSolutions();

            for (final Solution solution : solutions) {

                System.out.println( solution );

                System.out.println( "+-+-+-+-+-+-+-+-+" );

                for ( int rowIndex = 0 ; rowIndex < SIZE ; rowIndex++ ) {

                    System.out.print( "|" );

                    for ( int colIndex = 0 ; colIndex < SIZE ; colIndex++ ) {

                        if ( rowIndex == solution.getIntVal( white_row ) &&
                                colIndex == solution.getIntVal( white_col ) ) {
                            // white
                            System.out.print( "w" );
                        } else if ( rowIndex == solution.getIntVal( black_row ) &&
                                colIndex == solution.getIntVal( black_col ) ) {
                            // black
                            System.out.print( "b" );
                        } else {
                            // empty
                            System.out.print( " " );
                        }

                        System.out.print( "|" );
                    }

                    System.out.println();
                    System.out.println( "+-+-+-+-+-+-+-+-+" );
                }

                System.out.println();
            }

            System.out.println( "solution count: "+ solutions.size() );
        }

    }
     
    Leider funktioniert bereits das Constraint, welches gleiche Positionen der Springer verbietet, nicht.

    Ich habe beim Suchen im Netz nicht gefunden, wie ich die ReExpression zum Model hinzufuegen kann.
     
  2. Barista
    Barista Mitglied
    Oh, eben habe ich es doch gefunden.

    Code (Java):
    white_pos__not_equal__black_pos.post();
    Aber vielleicht habe ich heute noch mehr Fragen.
     
  3. Barista
    Barista Mitglied
    Ich habe es jetzt gelöst, eventuell möchte es jemand anderes mal verwenden.

    Code (Java):
    package de.heinerkuecker.springer_problem_choco_solver;

    import java.util.List;

    import org.chocosolver.solver.Model;
    import org.chocosolver.solver.Solution;
    import org.chocosolver.solver.Solver;
    import org.chocosolver.solver.expression.discrete.arithmetic.ArExpression;
    import org.chocosolver.solver.expression.discrete.relational.ReExpression;
    import org.chocosolver.solver.variables.IntVar;

    /**
    * <h2>Springerproblem</h2>
    *
    * Ermittlung aller Stellungen auf einem Schachbrett (der normalen Größe 8x8),
    * bei denen nur je ein weißer und ein schwarzer Springer frei so positioniert sind,
    * dass diese sich gegenseitig bedrohen.
    * <br/>
    * Die Visualisierung der gesuchten Stellungen kann sehr einfach gehalten sein.
    * </p>
      *
    * <p>
    * <h3>Lösung</h3>
    * Verwendung <a href="http://www.choco-solver.org/">Choco Solver</a>
    * </p>
    *
    * @author Barista
    */

    public final class Main {

        /**
         * @param args
         */

        public static void main(String[] args) {

            // Anzahl Zeilen und Anzahl Spalten des Spielfeldes
            final int SIZE = 8;

            // maximaler Zeilen- und Spalten-Wert
            final int MAX = SIZE - 1;

            final Model model = new Model( "All mutual threat knights playing positions" );

            // =================
            // === Variables ===
            // =================

            final IntVar white_row = model.intVar( "white row" , 0 , MAX );
            final IntVar white_col = model.intVar( "white col" , 0 , MAX );

            final IntVar black_row = model.intVar( "black row" , 0 , MAX );
            final IntVar black_col = model.intVar( "black col" , 0 , MAX );

            // ===================
            // === Constraints ===
            // ===================

            // die Positionen des weißen und des schwarzen Springer müssen unterschiedlich sein

            final ArExpression white_row_mul_SIZE = white_row.mul( SIZE );
            final ArExpression white_row_mul_SIZE_add_white_col = white_row_mul_SIZE.add( white_col );

            final ArExpression black_row_mul_SIZE = black_row.mul( SIZE );
            final ArExpression black_row_mul_SIZE_add_black_col = black_row_mul_SIZE.add( black_col );

            final ReExpression white_pos__not_equal__black_pos = white_row_mul_SIZE_add_white_col.ne( black_row_mul_SIZE_add_black_col );

            white_pos__not_equal__black_pos.post();

            // der weiße und ein schwarze Springer sich müssen gegenseitig bedrohen
            // die Idee ist, dass sich die Zeile der beiden Springer um 1 unterscheidet und die Spalte um 2 unterscheidet oder sich die Zeile der beiden Springer um 2 unterscheidet und die Spalte um 1 unterscheidet
            //
            // ( ABS( white_row - black_row ) == 1 AND ABS( white_col - black_col ) == 2 ) OR ( ABS( white_row - black_row ) == 2 AND ABS( white_col - black_col ) == 1 )
            //
            // wenn dieses Constraint zum Model hinzugefügt ist, kann die ReExpression white_pos__not_equal__black_pos entfallen, weil diese dann impliziert wird

            final ArExpression white_black_row_diff_abs = white_row.sub( black_row ).abs();
            final ArExpression white_black_col_diff_abs = white_col.sub( black_col ).abs();

            final ReExpression white_black_row_diff_abs__eq_1 = white_black_row_diff_abs.eq( 1 );
            final ReExpression white_black_col_diff_abs__eq_2 = white_black_col_diff_abs.eq( 2 );

            final ReExpression white_black_row_diff_abs__eq_1___and___white_black_col_diff_abs__eq_2 = white_black_row_diff_abs__eq_1.and( white_black_col_diff_abs__eq_2 );

            final ReExpression white_black_row_diff_abs__eq_2 = white_black_row_diff_abs.eq( 2 );
            final ReExpression white_black_col_diff_abs__eq_1 = white_black_col_diff_abs.eq( 1 );

            final ReExpression white_black_row_diff_abs__eq_2___and___white_black_col_diff_abs__eq_1 = white_black_row_diff_abs__eq_2.and( white_black_col_diff_abs__eq_1 );

            final ReExpression white_black_row_diff_abs__eq_1___and___white_black_col_diff_abs__eq_2____and____white_black_row_diff_abs__eq_2___and___white_black_col_diff_abs__eq_1 =
                    white_black_row_diff_abs__eq_1___and___white_black_col_diff_abs__eq_2.or(
                            white_black_row_diff_abs__eq_2___and___white_black_col_diff_abs__eq_1 );

            white_black_row_diff_abs__eq_1___and___white_black_col_diff_abs__eq_2____and____white_black_row_diff_abs__eq_2___and___white_black_col_diff_abs__eq_1.post();

            // ================
            // === Solution ===
            // ================

            final Solver solver = model.getSolver();

            final List<Solution> solutions = solver.findAllSolutions();

            for (final Solution solution : solutions) {

                System.out.println( solution );

                System.out.println( "+-+-+-+-+-+-+-+-+" );

                for ( int rowIndex = 0 ; rowIndex < SIZE ; rowIndex++ ) {

                    System.out.print( "|" );

                    for ( int colIndex = 0 ; colIndex < SIZE ; colIndex++ ) {

                        if ( rowIndex == solution.getIntVal( white_row ) &&
                                colIndex == solution.getIntVal( white_col ) ) {
                            // white
                            System.out.print( "w" );
                        } else if ( rowIndex == solution.getIntVal( black_row ) &&
                                colIndex == solution.getIntVal( black_col ) ) {
                            // black
                            System.out.print( "b" );
                        } else {
                            // empty
                            System.out.print( " " );
                        }

                        System.out.print( "|" );
                    }

                    System.out.println();
                    System.out.println( "+-+-+-+-+-+-+-+-+" );
                }

                System.out.println();
            }

            System.out.println( "solution count: "+ solutions.size() );
        }

    }
    Die ReExpression white_pos__not_equal__black_pos kann entfallen, wie ich im Kommentar geschrieben habe.
     
    JCODA gefällt das.
  4. mrBrown
    mrBrown Super-Moderator Mitarbeiter
    white_black_row_diff_abs__eq_1___and___white_black_col_diff_abs__eq_2____and____white_black_row_diff_abs__eq_2___and___white_black_col_diff_abs__eq_1
    Wirklich? xD
     
    CSHW89 und Flown gefällt das.
  5. Barista
    Barista Mitglied
    Verdammt, Du hast recht, es muss heissen:

    white_black_row_diff_abs__eq_1___and___white_black_col_diff_abs__eq_2____or____white_black_row_diff_abs__eq_2___and___white_black_col_diff_abs__eq_1
     
Die Seite wird geladen...

Choco Solver, - Ähnliche Themen

Lösen von Problemen - ProblemSolver
Lösen von Problemen - ProblemSolver im Forum Codeschnipsel u. Projekte
Java Sudoku Solver
Java Sudoku Solver im Forum Java Basics - Anfänger-Themen
Resolver für XML Schema Location beim Laden des Spring Application Context
Resolver für XML Schema Location beim Laden des Spring Application Context im Forum Allgemeines EE
Sudoku-Solver - Backtracking
Sudoku-Solver - Backtracking im Forum Allgemeine Java-Themen
Sudoku Solver - Sauber programmiert?
Sudoku Solver - Sauber programmiert? im Forum Hausaufgaben
Thema: Choco Solver,