Passer un tableau en argument de fonction récursive

a marqué ce sujet comme résolu.

Un zestueux salut à tous les amis !

Après avoir écrit en Java l'algorithme récursif résolvant le problème des N-Reines en utilisant du backtracking, je voulais le faire en JavaScript et étonnamment, la tâche s'avère être plus difficile que prévue…

Le problème des N-Reines

Soit un échiquier vierge de C*C cases et N reines. Le problème est le suivant : "Quelles sont toutes les dispositions possibles de ces N reines sur cet échiquier telles qu'aucune reine ne menace une autre ?".

Une reine menace une autre horizontalement, verticalement et en diagonale.

Sous-problème : N-Tours

Je me suis limité à des tours : une tour menace une autre horizontalement et verticalement.

Exemple : 2-Tours et 2*2-Echiquier

Notation utilisée :

T = présence d'une tour

<petit_tiret> = cette case de l'échiquier est vide

Première solution :

T-

-T

Seconde solution :

-T

T-

Algorithme récursif des N-Reines (valable pour les N-Tours)

Une façon de résoudre ce problème est d'écrire un algorithme récursif faisant usage du backtracking.

Explications

Pour chaque case de l'échiquier, on essaie de placer une même reine (c'est juste une boucle : N n'est pas modifié).

Dès qu'une reine est placée, on essaie de placer une autre reine (c'est l'appel récursif : N est décrémenté).

Conditions d'arrêt de la récursivité :

Quand on a placé les N reines (ie. : N = 0), le programme a trouvé une solution, celle-ci est stockée dans le tableau des solutions, et le niveau de récursivité doit faire un return.

Quand il reste des reines à placer et qu'on a fini de parcourir l'échiquier, le programme a trouvé une non-solution, celle-ci n'est pas stockée dans le tableau des solutions évidemment, et le niveau de récursivité doit faire un return.

Problème

L'algorithme que j'ai écrit semble trouver le bon nombre de solutions, mais celles-ci ne contiennent que des - et aucun T.

Il semblerait que je passe mal mon array_array_chessboard dans l'appel récursif. J'ai par ailleurs essayé de donner un nouvel array au solutions.push(...) : en effet, étant donné que je n'ai qu'un seul array sur lequel je travaille, il est possible que les modifications de ses éléments se répercutent sur le résultat final.

Source

JSFiddle : https://jsfiddle.net/btcj6uzp/

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
<body>

<script type="text/javascript">
    /**
     * Finds all the solutions to the N-Towers algorithm.
     *
     * @param number_of_towers number of towers to try to place in the chessboard
     * @param number_of_lines chessboard's ones
     * @param number_of_columns chessboard's ones
     * @returns {nTowersSolutions} array containing all the solutions
     */
    function nTowersSolutions(number_of_towers, number_of_lines, number_of_columns) {
        /*
        NB
        "T" = "Tower" = presence of a tower in this square of the chessboard
        "-" = "nothing" = no tower in this square of the chessboard
        (used for both solutions displaying and finding)
         */

        var solutions = [];
        var array_array_chessboard = []; // Represents the chessboard
        for(var i = 0; i < number_of_lines; i++) {
            array_array_chessboard[i] =  new Array(number_of_columns);
            for(var j = 0; j < number_of_columns; j++) {
                array_array_chessboard[i][j] = "-"; // We initialize the chessboard with "-"
            }
        }

        /**
         * Uses HTML to display the found solutions, in the Web page
         */
        this.displaySolutions = function() {
            var body = document.body;
            solutions.forEach((array_array_chessboard) => {
                array_array_chessboard.forEach(function(array_chessboard) {
                    array_chessboard.forEach((square) => {
                        body.innerHTML += square; // New cell
                    });
                    body.innerHTML += "<br />"; // New line
                });
                body.innerHTML += "<br /><br />"; // New solution
            });
        };

        /**
         * RECURSIVE FUNCTION. If there are still towers to place, this function tries to place them. If not, it means a
         * solution has been found : it's stored in an array (external to this function).
         * If this function can't place a tower, nothing happens.
         * Else, it places it and makes the recursive call.
         * Each recursion level does this for each next (to the placed tower) chessboard's squares.
         * @param number_of_left_towers how many remaining towers to place there are (if 0, it means a solution has been
         * found)
         * @param array_array_chessboard the chessboard
         * @returns {Number} the return is not important
         */
        function placeTower(number_of_left_towers, array_array_chessboard) {
            if (number_of_left_towers == 0) {
                return solutions.push(array_array_chessboard);
            }

            for (var current_x = 0; current_x < number_of_lines; current_x++) {
                for (var current_y = 0; current_y < number_of_columns; current_y++) {
                    if (array_array_chessboard[current_x][current_y] == "-" && canBePlaced(array_array_chessboard, current_x, current_y)) {
                        array_array_chessboard[current_x][current_y] = "T";
                        placeTower(number_of_left_towers - 1, array_array_chessboard);
                        array_array_chessboard[current_x][current_y] = "-";
                    }
                }
            }
        }

        /**
         * Can this tower be placed ?
         * @param array_array_chessboard
         * @param new_x
         * @param new_y
         * @returns {boolean}
         */
        function canBePlaced(array_array_chessboard, new_x, new_y) {
            for(var i = 0; i < array_array_chessboard.length; i++) {
                for(var z = 0; z < array_array_chessboard[i].length; z++) {
                    if(array_array_chessboard[i][z] == "T"
                            && (
                                    new_x == z || new_y == i // Horizontal and vertical checks
                            )
                    ) {
                        return false;
                    }
                }
            }
            return true;
        }

        placeTower(number_of_towers, array_array_chessboard);
        return this;
    }

    // <!-- CHANGE THESE PARAMETERS' VALUE TO TEST -->
    nTowersSolutions(2, 2, 2).displaySolutions();
</script>

</body>
</html>

Voilà voilà, avez-vous une idée de pourquoi je n'obtiens que des cases "-" ?

Merci d'avance ! :)

+0 -0

Il y a une maniere beaucoup plus simple de resoudre ce probleme de maniere recursive (en utilisant un tableau). Je l'ai code en python (ne savant pas coder en Javascript). Mais python etant un langage tres "intuitif", tu devrais comprendre sans probleme, si ca t'interesse.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def print_board(arr):
    size = len(arr)
    board = [['-' for _ in range(size)] for _ in range(size)]
    
    for i, j in enumerate(arr):
        board[i][j] = 'Q'

    for row in board:
        print(' '.join(row))
        
    print()
    
def n_tower(arr, start, available):
    if start == len(arr):
        print_board(arr)
        return

    for i in available:
        arr[start] = i
        n_tower(arr, start + 1, available - {i})


size = int(input('Enter size: '))
arr = [0] * size
n_tower(arr, 0, set(range(size)))

Output:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
~$ python test.py
Enter size: 3
Q - -
- Q -
- - Q

Q - -
- - Q
- Q -

- Q -
Q - -
- - Q

- Q -
- - Q
Q - -

- - Q
Q - -
- Q -

- - Q
- Q -
Q - -

+0 -0
Connectez-vous pour pouvoir poster un message.
Connexion

Pas encore membre ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte