I've been working on the n-queens problem as a way to learn arc. What I have so far is listed below.

However, I have a problem where a variable's value lower in the function reverts to an initial value when I loop back up to the top of the while statement. And I'm not sure how that should be handled.

Any comments?

Thanks, Steve

---

(def nqueens (board-size)
(with (diagonals nil finished nil jsg 0 result '(0) row nil total 0)
(while (~ finished)
(prn "1: diagonals " diagonals " result " result)
(let (diagonals result row)
(get-next-row board-size diagonals result)
(prn "2: diagonals " diagonals " result " result)
(if (> (++ jsg) 2) (= finished t))
(if row
(if (is (len result) board-size)
(let (diagonals result total)
(print-result diagonals result total))
(do
(prn "3: diagonals " diagonals " result " result)
(= result (goto-next-column result))
(prn "4: diagonals " diagonals " result " result)))
(if (is (len result) 1)
(= finished t)
(let (diagonals result)
(goto-previous-column diagonals result))))))
(prn "Number of results: " total)))

---

print out:

arc> (nqueens 4)
1: diagonals nil result (0)
2: diagonals (1 -4) result (1)
3: diagonals (1 -4) result (1)
4: diagonals (1 -4) result (1 0)
1: diagonals nil result (0)
2: diagonals (1 -4) result (1)
3: diagonals (1 -4) result (1)
4: diagonals (1 -4) result (1 0)
...
Number of results: 0
"Number of results: "
arc>

Yeah, I should have explained more. I'd planned the results to be in the form:

((row col) (row col) (row col) ...)

Your version works just as well :) but the variable names might make a little more sense this way.

a) (o queens) means that queens is an optional argument. If I don't pass in a value it's nil by default. I could also have given it an explicit default by saying (o queens 42). You can read more about this in the tutorial: http://www.arclanguage.org/tut.txt. Worth a reread if it's been a while.

b) queens.0.0 expands to ((queens 0) 0). Which is the same as (car (car queens)). Just a quick way to pull out the first row, the row of the most recently added queen (since I'm adding queens on the left using cons).

c) col is just a variable name for the column in the above representation of queens. But perhaps you were asking about up. Try this out at your Anarki prompt:

arc> (help up) ; only in Anarki
arc> (up col 0 8 (prn col))

d) some takes a predicate (function) and a list, and returns true if any of the elements of the list is satisfied by the predicate (function returns true). Check out (help some), as well as the tutorial above. One twist is that you can pass in any number/character/boolean as a predicate, and it's as if you're comparing with it. So I'm asking "have we already seen this column?" in this line:

(some curr-column (map [_ 1] rest))

e) Yes, no is like ~ though not quite the same. It's just simple boolean negation. (no nil) is t, no on anything else is nil. ~ (complement) is slightly different, it operates on functions and makes them return their negation. So this relation always holds:

(no f.x) <=> (~f x)

I could have written (no conflicts.new-queens) as (~conflicts new-queens).

I'm pretty sure that what's going on is that you never set the top binding of result to anything else, so it's always the original value at the beginning of each while loop.

Consider this code:

arc> (let result 0 (let result 2 (= result 3)) result)
0

The top-level result is never updated. What part of your code are you expecting to update the value of result?

Ah, you're right. I think jsgrahamus might be expecting result to be modified by this line:

(let (diagonals result row) (get-next-row board-size diagonals result)
..)

But it just creates a new shadowing binding for result, which exists only for the lifetime of the let, and is lost once the let is finished. Think of let as pushing a new value for its variable(s) on a stack before running its body, then popping the new values off, leaving behind any preexisting values.

Thanks, I'm familiar with that practice. I'm also used to passing by reference so that changes made to the variable in the newer function get passed back to the calling function.

Yeah, makes sense. However, let always creates a new binding and never modifies existing bindings. That's why it makes you indent its body to the right. Compare:

(= x 3 y 4)
(+ x y)

with:

(let (x y) '(3 4)
(+ x y))

The indentation is a hint that these are new x and y variables, compared to any earlier x and y variables.

Besides let there are indeed functions in Arc where you can pass lists or tables by reference (though not primitives like numbers or characters). However, it's usually a good idea to try to avoid these, again so you can practice a less imperative style of programming (http://arclanguage.org/item?id=19709). My usual approach is to first build a program with promiscuous copying everywhere, and then if it turns out to be too slow pick the 2% of cases that can speed it up a lot and make them destructive/call-by-reference, because the cost of doing so is that it makes the program harder to understand.

Here's a newer view. A number of variables (diagonals, result, row, total) get modified lower in the function. There must be a better way of updating those variables.

(do
(let (diagonals2 result2 total2)
(print-result diagonals2 result2 total2)
(= diagonals diagonals2 result result2 total total2)))

There must be a way for the system to realize I expect (print-result) to update diagonals, result and total, so it automatically creates diagonals2/result2/total2, puts them in a let statement as the receivers of the return value of (print-result) and upon coming back from (print-result) automatically the system automatically sets diagonals/result/total to each element of the return list.

Whenever you see an error message complain about an undefined identifier named "_R", that's because of a long-standing issue with the Racket reader in Windows terminals. If you paste multiple lines into the terminal, what you paste needs to have a blank line at the end already or else Racket will think it sees an R somewhere in the middle of your code.

It's not your fault. It's a bummer to have to work around this.

BTW, you can always simplify (if <expression> nil t) to just (no <expression>).

Also, what's that i variable doing in valid?? I don't understand how valid? works..

You _really_ don't want to be making pass-by-reference changes like incrementing i inside some, since there's no guarantee about the order in which it'll run. If you want imperative updates, just use an explicit loop like each.

There's still other functions that are missing, such as goto-next-column, goto-previous-column, etc.

Anyways, I think you've gotten me to work on this problem as well :) I found it super hard when I solved it in C back in '97. Perhaps I should go back and see if I've gotten any better at programming.

So if two results were (2 4 1 3) and (3 1 2 4), both of them sort to (1 2 3 4) so delete one of them? Of course all of the results will sort to (1 2 3 4) for a 4x4 board.

Thanks! I think I'll try to solve it on my own without looking at yours in depth first. That might take me a few days. But feel free to keep asking questions in the meantime.

This took me too many hours in my work language to solve. Initially I next just translated it to arc, but that didn't seem to work, so I started again in arc from scratch. I sure learned a lot about arc and debugging in it.

It took me a while to wrap my mind around this problem. Sure is different than CRUD work, reports and interfaces.