3
\$\begingroup\$

I wrote a solution to a problem based on the N-Queens problem which should use more pieces than just queens. Problem is it's very slow, it probably has to do with how I modeled data and my lack of knowledge on how to compare boards without the possibility of extending from an interface compareTo as I would do in a language like Java.

This is the algorithm:

func Solution(board b.Board, pieces []rune, solutions *[]b.Board, testedConfigurations *[]b.Board) *[]b.Board {
    if len(pieces) != 0 {
        for i := 1; i < board.M; i++ {
            for j := 1; j < board.N; j++ {
                c := p.CreatePiece(pieces[0], i, j)
                if b.IsSafe(board, c) {
                    modifiedBoard := b.Place(board, c)
                    if len(pieces) != 1 {
                        if !contains(modifiedBoard, *testedConfigurations) {
                            *testedConfigurations = append(*testedConfigurations, modifiedBoard)
                            Solution(modifiedBoard, pieces[1:], solutions, testedConfigurations)
                        }
                    } else {
                        if !contains(modifiedBoard, *solutions) {
                            *solutions = append(*solutions, modifiedBoard)
                            println("Found Solutions", len(*solutions))
                        }
                    }
                }
            }
        }
    }
    return solutions
}

This is how I represent a piece in the board:

type Piece struct {
    Name rune
    Row  int
    Col  int
}

This is how I represent the board

type Board struct {
    M     int
    N     int
    Board [][]rune
    Used  []primitives.Attacks
}

This is the Attacks interface (I use it to check if a piece attacks another):

type Attacks interface {
    Attacks(piece Attacks) bool
    Row() int
    Col() int
    Name() rune
    ToString() string
}

This is what I use to check if a solution is already been used:

func contains(boardContains b.Board, testedConfigurations []b.Board) bool {
    for _, k := range testedConfigurations {
        if len(k.Used) == len(boardContains.Used) && EqualBoards(k.Board, boardContains.Board, k.M, k.N) {
            return true
        }
    }
    return false
}

And this is what I use to check if two boards are equal:

func EqualBoards(board1 [][]rune, board2 [][]rune, M, N int) bool{
    for i:=1; i< M; i++ {
        for j:=1; j< N; j++ {
            if board1[i][j]!=board2[i][j] {
                return false
            }
        }
    }
    return true
}

Here's the code

\$\endgroup\$
3
  • \$\begingroup\$ Welcome to Code Review, Is it possible to post more of the code here? There is not enough code here to show the context and usage of this function. It might be considered off-topic to some users of the site, please see codereview.stackexchange.com/help/how-to-ask and codereview.stackexchange.com/help/dont-ask. \$\endgroup\$ – pacmaninbw Apr 29 '19 at 17:34
  • \$\begingroup\$ Sure. I think this time I provided enough information. \$\endgroup\$ – Ignacio Mosca Apr 29 '19 at 18:13
  • \$\begingroup\$ Maybe I'm missing something, but it seems to me there are no generics here... If so, I suggest removing the generics tag. Also, the Github link is not working. \$\endgroup\$ – kyrill May 4 '19 at 23:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.