7
\$\begingroup\$

In less that 5 seconds on a normal PC, I found the answer in simple brute-force. Before I met Go, I didn't believe that it will be so easy to use all the power of the PC by using Go Goroutines for concurrency and multithreading.

I tried exactly the same simple algorithm, without concurrency in Haskell and JavaScript. In Go it works more than 10x faster. Feedback is welcome.

package main

import (
    "fmt"
)

const (
    a         = 8
    b         = 8
    maxLevels = 64
)

func main() {
    c := make(chan [a][b]int)
    for x1 := 0; x1 < a; x1++ {
        for y1 := 0; y1 < b; y1++ {
            go func(x1 int, y1 int) {
                var chess [a][b]int
                var current int
                success := tryToMove(&chess, current, x1, y1)
                if success {
                    c <- chess
                }
            }(x1, y1)
        }
    }
    printChess(<-c)
}

func tryToMove(chess *[a][b]int, current int, x int, y int) bool {
    if x >= a || y >= b || x < 0 || y < 0 {
        return false
    }
    if chess[x][y] > 0 {
        return false
    }
    current++
    chess[x][y] = current
    if current == maxLevels {
        return true
    }
    if tryToMove(chess, current, x+2, y+1) {
        return true
    }
    if tryToMove(chess, current, x+2, y-1) {
        return true
    }
    if tryToMove(chess, current, x-2, y+1) {
        return true
    }
    if tryToMove(chess, current, x-2, y-1) {
        return true
    }
    if tryToMove(chess, current, x+1, y+2) {
        return true
    }
    if tryToMove(chess, current, x+1, y-2) {
        return true
    }
    if tryToMove(chess, current, x-1, y+2) {
        return true
    }
    if tryToMove(chess, current, x-1, y-2) {
        return true
    }
    chess[x][y] = 0
    current--
    return false
}

func printChess(chess [a][b]int) {
    for i := 0; i < a; i++ {
        fmt.Println(chess[i])
    }
}

Answer:

[64 53 20 43 22 55 32 29
[41 44 63 54 33 30 23 6]
[52 19 42 21 56 7 28 31]
[45 40 51 62 1 34 5 24]
[18 61 16 57 14 25 8 27]
[39 46 37 50 35 2 11 4]
[60 17 48 15 58 13 26 9]
[47 38 59 36 49 10 3 12]
\$\endgroup\$
3
\$\begingroup\$

Your code does the task at hand, and that's a good thing. It's pretty quick too, an that's great.

What your code lacks though, is a sense of readability, and maintainability. There are also a number of potential bugs, and some variable shadowing.

Slices

My initial beefs with the code are that it depends heavily on constants, and on fixed arrays, instead of slices. In general Go favors slices over arrays. Consider this method:

func printChess(chess [a][b]int) {

it requires a 2D array with very specific dimensions, you can't use that function to print different size boards in the same program. It would be better to have a slice:

func printChess(chess [][]int) {

That can print any 2D slices, not just arrays of a very specific dimension. It makes it reusable.

Changing to slice from array would be quite a change in your code, though.

Constants

Your use of constants is impacting the code in odd ways. I mentioned the array-to-slice above, but it also impacts things like passing pointers in to arrays instead of slices, etc.

The names of your constants are also "horrible", a, and b are ugly.

your maxLevels constant is a better name, but really it is a computed value: maxLevels = a * b. I would not use it at all as a separate constant.

Constants in general are a bad idea, unless they really are constants. The dimensions of the board should be passed around, or inferred, as parameters.

Channels

Your use of the result channel appears to be a good idea, but it runs the risk of failing when no result is found. The fact that the 8x8 board has at least one valid result means that you are lucky, and that the channel completes OK. If there was no solution, though, your code would hang indefinitely.

You would be better by having a combination of a waitgroup and closing the channel if/when the waitgroup completes.

it would be best to solve that problem in it's own method too. It makes the process easier to read.

Dangling go-routines

your code does not clean up any go-routines that are still working when the first solution is found. You should find a way to terminate these routines cleanly - this would make your code usable in an application that does not immediately exit on the first solution.

You can use a select-with-default on the channels to implement a killer.

select {
case <-killer:
    // we were killed
    ....
default:
    //not killed, so keep going
    .....
}

Closure Shadowing.

This code here is complicated and made worse by bad variable naming:

for x1 := 0; x1 < a; x1++ {
    for y1 := 0; y1 < b; y1++ {
        go func(x1 int, y1 int) {
            var chess [a][b]int
            var current int
            success := tryToMove(&chess, current, x1, y1)
            if success {
                c <- chess
            }
        }(x1, y1)
    }
}

The x1 and y1 variables are duplicated in different scopes. The closure pattern is the right pattern, but give your variables different, non-shadowing names. Also, why x1 and y1 instead of just x and y?

for x := 0; x < a; x++ {
    for y := 0; y < b; y++ {
        go func(startx int, starty int) {
            var chess [a][b]int
            var current int
            success := tryToMove(&chess, current, startx, starty)
            if success {
                c <- chess
            }
        }(x, y)
    }
}

The above makes it clear that startx and x are different variables.

Additionally, if you create a parameter-based closure for the x and y variables, you should probably be consistent and create it for the c channel too.

Rows vs. Colums

It's a good thing your board is square - you mix up the use of the a and b constants, and the use of the x and y coordinates. If you were to have a rectangular board, say 6x8, your would cause index-out-of-bounds exceptions. Hmmm, no, actually, it will work, but your logic of using x and y implies that x is a horizontal position, but really, x in your code is the vertical position, and y is the horizontal position.

a is the height of the board, and b is the width (at least, that's the way that the printChess will print it out.

If you use variable names that imply a secondary meaning (like x), then you should ensure that the secondary meaning is consistent with the code's implementation.

Verbose Knight "Moves"

Your code embeds the knight-move logic as a series of if statements like:

if tryToMove(chess, current, x+2, y+1) {
    return true
}
if tryToMove(chess, current, x+2, y-1) {
    return true
}
if tryToMove(chess, current, x-2, y+1) {
    return true
}
if tryToMove(chess, current, x-2, y-1) {
    return true
}
if tryToMove(chess, current, x+1, y+2) {
    return true
}
if tryToMove(chess, current, x+1, y-2) {
    return true
}
if tryToMove(chess, current, x-1, y+2) {
    return true
}
if tryToMove(chess, current, x-1, y-2) {
    return true
}

it is often neater to encode it as a set of values in a slice:

var (
    knightMoves = []struct{ drow, dcol int }{
        {-2, -1}, {-2, +1},
        {-1, -2}, {-1, +2},
        {+1, -2}, {+1, +2},
        {+2, -1}, {+2, +1},
    }
)

and then iterate that slice to get the moves:

for _, move := range knightMoves {
    if tryToMove(width, height, board, current+1, col+move.dcol, row+move.drow) {
        return true
    }
}

Conclusion

Putting all the above together, I came up with a main method that inputs the solution constraints and handles a non-solution too:

func main() {
    if soln := solveBoard(8, 8); soln != nil {
        printChess(soln)
    } else {
        fmt.Println("No solution")
    }
}

Additionally, the actual solving method handles all cases:

func solveBoard(width, height int) [][]int {
    attempts := width * height
    results := make(chan [][]int)

    var wg sync.WaitGroup
    wg.Add(attempts)
    killer := make(chan bool)

    defer close(killer)
    for x := 0; x < width; x++ {
        for y := 0; y < height; y++ {
            startx := x
            starty := y
            go func() {
                if ok, soln := solveBoardFrom(killer, width, height, startx, starty); ok {
                    results <- soln
                }
                wg.Done()
            }()
        }
    }
    go func() {
        wg.Wait()
        close(results)
    }()
    return <-results
}

Note the creation of the WaitGroup and the killer channel that allows you to capture the no-solution condition, and the early solution killer.

Also note the different mechanism for creating the closure. I am not recommending one way vs. the other, but creating the variables in the inside scope like startx := x allows you to access startx inside the goroutine without worrying about the scope, just like a parameter-based closure function.

The recursive function is simplified with the loop, but more complicated by the killer process:

func tryToMove(killer chan bool, width, height int, board [][]int, current int, col int, row int) bool {
    // check to see whether we have been killed
    select {
    case <-killer:
        // we were killed
        return false
    default:
        //not killed, so keep going
    }

    if col < 0 || row < 0 || col >= width || row >= height {
        return false
    }
    if board[row][col] > 0 {
        return false
    }
    board[row][col] = current
    if current == width*height {
        // solved
        return true
    }
    for _, move := range knightMoves {
        if tryToMove(killer, width, height, board, current+1, col+move.dcol, row+move.drow) {
            return true
        }
    }

    board[row][col] = 0
    return false
}

It has a lot of parameters. It is past the point where a structure may be a better solution, but I left it as a lot of parameters for you to correlate things back to your code better.

Playground

You can see this running in the playground: https://play.golang.org/p/5zxmj8WV5u

The full code I am playing with is:

package main

import (
    "fmt"
    "sync"
)

var (
    knightMoves = []struct{ drow, dcol int }{
        {-2, -1}, {-2, +1},
        {-1, -2}, {-1, +2},
        {+1, -2}, {+1, +2},
        {+2, -1}, {+2, +1},
    }
)

func main() {
    if soln := solveBoard(8, 8); soln != nil {
        printChess(soln)
    } else {
        fmt.Println("No solution")
    }

    fmt.Println("-------------------")

    if soln := solveBoard(7, 9); soln != nil {
        printChess(soln)
    } else {
        fmt.Println("No solution")
    }

    fmt.Println("-------------------")

    if soln := solveBoard(2, 2); soln != nil {
        printChess(soln)
    } else {
        fmt.Println("No solution")
    }

}

func solveBoard(width, height int) [][]int {
    attempts := width * height
    results := make(chan [][]int)

    var wg sync.WaitGroup
    wg.Add(attempts)
    killer := make(chan bool)

    defer close(killer)
    for x := 0; x < width; x++ {
        for y := 0; y < height; y++ {
            startx := x
            starty := y
            go func() {
                if ok, soln := solveBoardFrom(killer, width, height, startx, starty); ok {
                    results <- soln
                }
                wg.Done()
            }()
        }
    }
    go func() {
        wg.Wait()
        close(results)
    }()
    return <-results
}

func tryToMove(killer chan bool, width, height int, board [][]int, current int, col int, row int) bool {
    // check to see whether we have been killed
    select {
    case <-killer:
        // we were killed
        return false
    default:
        //not killed, so keep going
    }

    if col < 0 || row < 0 || col >= width || row >= height {
        return false
    }
    if board[row][col] > 0 {
        return false
    }
    board[row][col] = current
    if current == width*height {
        // solved
        return true
    }
    for _, move := range knightMoves {
        if tryToMove(killer, width, height, board, current+1, col+move.dcol, row+move.drow) {
            return true
        }
    }

    board[row][col] = 0
    return false
}

func solveBoardFrom(killer chan bool, width, height, col, row int) (bool, [][]int) {
    board := make([][]int, height)
    for i := range board {
        board[i] = make([]int, width)
    }
    if tryToMove(killer, width, height, board, 1, col, row) {
        return true, board
    }
    return false, nil
}

func printChess(board [][]int) {
    for r := 0; r < len(board); r++ {
        fmt.Println(board[r])
    }
}
\$\endgroup\$
2
\$\begingroup\$

If you take advantage of the symmetry of the chess board and limit your loops you could do it in even less time than that.

\$\endgroup\$
  • \$\begingroup\$ Are you sure? Everything works in parallel. So maybe, there is no difference between 4*4 goroutines, to 8x8. The for-loop is doing all the calculation at the same time. \$\endgroup\$ – Aminadav Glickshtein Nov 21 '16 at 6:03
  • \$\begingroup\$ @Kyle is right : doing 4x less work is always better than doing 4x more work regardless of all computation power you have. \$\endgroup\$ – funny_falcon Nov 21 '16 at 6:31
  • 1
    \$\begingroup\$ There are only 10 unique squares on an 8x8 board: \$\endgroup\$ – Kyle Nov 21 '16 at 19:10
  • \$\begingroup\$ uuuuXXXX XuuuXXXX \$\endgroup\$ – Kyle Nov 21 '16 at 19:11
  • 1
    \$\begingroup\$ OK, since I obviously don't know how to use this site I'll just say this: instead of looping 8x8 times have the first loop go to x1 < 4 and the inner loop go from y = x1; y1 < 4. You'll hit the 10 unique starting points and do 10/64 of the work. \$\endgroup\$ – Kyle Nov 21 '16 at 19:20
2
\$\begingroup\$

You may use uint8 instead of int so that the board will use just 64 bytes of memory instead of 256 (because int consumes 8 bytes on x86_64).

\$\endgroup\$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.