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])
}
}
