## Hello Julia!

posted on Mon, Aug 20 '18 under tags: code, julia

##### Solving the eight queens chess puzzle as a hello world program in julia

As Julia hit 1.0 this month there has been an understandable excitement about the language with even my guide and mentor Dr Anantha Kumar asking me if I will switch to Julia from R/Python.

I then read about Julia and found many of its features really interesting (like `missing`, `end`, optional typing, and others)

As I reached exercise 2.42 in SICP today I decided to program in Julia for the first time.

## Hello, world!

Julia is available in the official repository of arch linux and others. (The version in arch is now 0.7 due to technical issues and has been flagged out of date). Once installed, the REPL can be invoked with `julia` command. It is useful for interactively running things.

`julia scriptname.jl` can run scripts just like python.

Now, I had to find solutions to the eight queens puzzle. For those who don’t know, the challenge is to keep 8 queens on the chess board such that nobody is in line of sight of anyone else.

The first thing I tried to get right was representing the board and queens in a 2D array.

### Array

I would need an 8x8 array with each cell representing whether that position on the chess board has a queen or not. Boolean seems to be the right type for this.

Of course we can manually create it

``````[
false false false false false false false false;
false false false false false false false false;
false false false false false false false false;
false false false false false false false false;
false false false false false false false false;
false false false false false false false false;
false false false false false false false false;
false false false false false false false false;
]
``````

(Notice the space between each false and the `;` separating each array)

But the programmatic way to do it is much simple `falses(8,8)`. More such tricks at construction of multidimensional arrays

Interestingly these two ways of creating arrays produce two different kinds of arrays. The first method produces an array of type `8×8 Array{Bool,2}` while the latter produces `8×8 BitArray{2}`. BitArray is stored in bits compared to Bool Array and therefore saves space. There are other differences as well.

Now we can place queens by setting cells to true.

### Functions

To do anything useful, we have to start creating functions. In Julia, you create functions like thus:

``````function add(x, y)
x + y
end
``````

You can use `return` to specifically return value if you don’t want the last expression to be returned.

Though I have indented code like python, the whitespace does not really matter thanks to `end` keyword. So you could write the add function like:

``````function add(x,y);x+y;end
``````

and it would still work

### Printing

Now I wanted to be able to print the board nicely. So I created a function printboard.

``````function printboard(board)
# to print board
end
``````

For printing, we have three (actually more) commands that are useful:

• println() works like python’s print. It will print all the arguments and then a newline.
• print() is same as `println` except it won’t print a newline at the end
• @printf() is like C’s printf and supports printing formatted string. (You will need to put `using Printf` at the top to use this (like `import` in python))

Example:

``````# All the following produce the same output
julia> print(1, '\n')
1

julia> println(1)
1

julia> using Printf; Printf.@printf('%d\n', 1)
1

``````

### Looping

Both `while` and `for` loops are similar to their python counterparts except they end with `end` like most things in julia.

I used `for` for the printboard function

``````function printboard(board)
print("===============\n")
for row in 1:8
for column in 1:8
if board[row, column] == true
print("X ")
else
print("- ")
end
end
print("\n")
end
print("===============\n")
end
``````

### Conditionals

If you saw the use of if in the previous block, good, else, see. Over.

Read more in the official documentation

### Short-circuit evaluations

`&&` and `||` work just like you would expect them to. We will use `&&` for ensuring several criteria are met in the following part of the algorithm.

### Algorithm

What we have is computing power. But if we go full brute force and generate all the possible permutations of where 8 queens can be and which ones are right solutions, we would be making it very hard for the computer. Instead we can use a few properties of the chess board and queen piece to simplify this process.

Each column can have only 1 queen

This means that we can solve column by column wherein we put the first queen in any row of column 1, then move on to the second column where we place the queen in a row such that it doesn’t affect the previous queen and then repeat this process. It paves way for an iterative solution.

First, though, we need to create a few functions which will check if a queen can safely be placed in a given cell.

We need to check if the row we are going to place the queen in already has another queen.

``````function rowfree(board, cell)
for i in 1:8
if board[cell, i] == true
return false
end
end
return true
end
``````

`function rowfree(board, cell)`

Although we haven’t typed it, this function should be called with two parameters. The first is the state of the board (the 8x8 array), then the cell which we want to check for safely keeping another queen. I chose this cell to be passed in as a tuple, eg `(1,1)` is the top-left cell.

`for i in 1:8`

Let us iterate through values of i from 1 to 8

`if board[cell, i] == true`

We are checking only the row in which the cell is. And that is given by cell. We need to check each column in that row to see if there is a queen there and this is accomplished by `i` which we are iterating from 1 to 8.

If we find another queen at any point we `return false` to signal the row isn’t free. If at the end of checking 8 columns there is no queen anywhere we `return true`.

Diagonals also need to be clear

This is slightly more complicated. We need to check in four directions from any given cell. Top left, top right, bottom left, and bottom right.

(Note: Since we are going from left to right, it is enough that we check only top-left and bottom-left directions, but to enable people to place a queen anywhere as a starting point, we check all directions)

``````function diagonalsfree(board, cell)
return (
topleftfree(board, cell)
&& bottomleftfree(board, cell)
&& toprightfree(board, cell)
&& bottomrightfree(board, cell))
end
``````

This is where we create a general function that can go in any direction based on the direction offset we decide.

``````function checkdiagonal(board, cell, offsetx, offsety)
x = cell + offsetx
y = cell + offsety
while (0 < x && x < 9 && 0 < y && y < 9)
if board[x, y] == true
return false
end
x = x + offsetx
y = y + offsety
end
return true
end
``````

This function takes the board’s state, the cell we are checking and the direction as parameter (indicated by offset in x axis and offset in y axis)

We are using the comparison operator `<`, also `&&` to make sure all criteria are met.

Then we define all the four function calls for all directions.

``````function topleftfree(board, cell)
checkdiagonal(board, cell, -1, -1)
end

function bottomleftfree(board, cell)
checkdiagonal(board, cell, 1, -1)
end

function toprightfree(board, cell)
checkdiagonal(board, cell, -1, 1)
end

function bottomrightfree(board, cell)
checkdiagonal(board, cell, 1, 1)
end
``````

A cell is safe if row and diagonals are free

``````function cellsafe(board, cell)
return (
diagonalsfree(board, cell)
&& rowfree(board, cell)
)
end
``````

Now our final iterative function to conclude the algorithm:

``````function findRestQueens!(board, column = 1)
if column == 9
global solutions
solutions = solutions + 1
println("Solution ", solutions)
printboard(board)
println()
return true
end
if columnfree(board, column)
for row in 1:8
if(cellsafe(board, (row, column)))
guessboard = copy(board)
guessboard[row, column] = true
findRestQueens!(guessboard, column + 1)
end
end
return false
else
findRestQueens!(board, column + 1)
end
end
``````

Like in python we can give default value for argument. Here, we are assigning column to 1 unless explicitly stated so computer starts at the left-most column.

We are naming the function with a `!` because it is the prescribed style for functions that mutate their arguments.

As it is an iterative function, we need an exit condition. And if column is 9, we can exit as we have placed all the 8 queens. See the use of `global` keyword which will append to a global count of how many solutions we have discovered. Then we print the solution we have discovered.

The rest of the function is the iterative part which I hope is error-free (I have done enough trial and errors to get it to a state where it is producing all the 92 solutions).

An important line is `guessboard = copy(board)`. This is required because of this:

``````julia> a = [1, 1]
2-element Array{Int64,1}:
1
1

julia> b = a
2-element Array{Int64,1}:
1
1

julia> b = 2
2

julia> b
2-element Array{Int64,1}:
2
1

julia> a
2-element Array{Int64,1}:
2
1
``````

It is now possible to get our 92 solutions.

``````board = falses(8,8)
findRestQueens!(board)
``````

We can place a few queens manually as well

``````board = falses(8,8)
board[3, 3] = true
findRestQueens!(board)
``````

### Command line argumens

What if we need to allow placing queens from the command line?

The `ARGS` global constant becomes useful in that case. Command line parameters are passed as array of strings named ARGS. If we call our script as `julia queens.jl 1 2 3 4` the ARGS would be `String["1", "2", "3", "4"]`.

To parse numbers from this we will have to use the function `x -> parse(Int, x)`

(Note: This is another way of defining a function. As we don’t name it, it is called an “anonymous function” also known as “lambda function”)

We can map that function to the ARGS array like `map(x -> parse(Int, x), ARGS)`. This will create another array with parse applied to each element.

Putting all of it together, we have

``````arguments = map(x -> parse(Int, x), ARGS)
arglength = length(arguments)
cells = floor(Int, arglength / 2)
if arglength > 0
if arglength % 2 == 0
for i in 1:cells
cell = (arguments[i * 2 - 1], arguments[i * 2])
if(cellsafe(board, cell))
board[cell, cell] = true
println("Set a starting queen at: ", cell)
else
println("Invalid starting position. Can't set queen at ", cell)
board[cell, cell] = true
printboard(board)
println()
exit()
end
end
println("Starting position is:")
println("=====================")
printboard(board)
println()
else
print("You need to enter cells that are checked as args. Eg: `julia queens.jl 1 1 3 4` if the top left cell and the cell two rows below and 3 rows to the right of it is taken already")
exit()
end
end
``````

We have added a few conditions and operations to ensure there are the right number of arguments, check if those positions are valid, place queens in those positions, and find corresponding solutions.

The `exit()` function allows aborting the script halfway through.

We did not use our global variable solutions. Let us use it

``````if solutions > 0
if solutions == 1
printstyled("Found the only solution", color=:cyan)
else
printstyled("Found ", solutions, " solutions", color=:green)
end
else
printstyled("Unfortunately no solutions exist for this starting combination", color=:red)
end
``````

The `printstyled` function allows printing colourful output to terminal. But this works only with `--color=yes` flag on while invoking julia. We can alias julia to that `alias julia='julia --color=yes'` to avoid repeating color flag.

## Conclusion

I have put the code in a repo in julia subgroup of learnlearnin group on gitlab. (Did you know gitlab allowed subgroups of subgroups upto 20 levels deep!?). Feel free to hack around.

This was written in Julia 0.6 and then modified for 0.7, while reading manual for version 1.0. Please let me know if there are any errors.

Julia is quite interesting. It has quite a few packages for data science and others. Arrays start at 1 even. Take a look.