How to save the queen?

General Usage
1

I’m looking for (but haven’t found yet) a way to save the solutions of the 8 queens problem on a chessboard into an array of some sort, without necessarily having to “print” them live.
If possible by changing the following functions. But it’s also fine with a completely different setting.

for the moment my workaround is this

function safe(queen, row)
   for i in 1:queen-1
     xriga = T[i]
        if (xriga == row||
            xriga == row- (queen- i) ||
            xriga == row+ (queen- i))
            return false
        end
    end
    return true
end

function try(k)
    if (k <= 8)
        for i in 1:8
            if (safe(k, i))
                T[k] = i
                try(k + 1)
            end
        end
    else
        for i in 1:8
            print(io,T[i],' ')
        end
        print(io,'\n')
    end
end
io=IOBuffer();
T=fill(0,8)
res=Vector{Vector{Int}}()
try(1)

sol=take!(io)

reshape(sol,17,:)'[:,1:2:16].-48
2

Hi @rocco_sprmnt21!
It may be silly of me but I think people would find it easier to help you if your code was in English?
As for storage, I would suggest an 8x8 bool (sparse) matrix for each solution?

1 Like
3

I edited the code to make it easier to read.
I found a way to overcome the problem I had: the resulting vector filled via the push!(res,T) statement had all values equal to the last T entered.
Changing to push!(res,copy(T)) seems to have overcome the problem.

function try(k)
    if (k <= 8)
        for i in 1:8
            if (safe(k, i))
                T[k] = i
                try(k + 1)
            end
        end
    else
        # for i in 1:8
        #     print(io,T[i],' ')
        # end
        # print(io,'\n')
        push!(res,copy(T))
    end
end
5

the answer is good :laughing:

6

I think this question might be a tad late (w.r.t. the queen). But here is a late answer:

function tryqueens2(k)
           if (k <= 8)
               push!(res2,0)
               for i in 1:8
                   if (safe(k, i))
                       T[k] = i
                       res2[end] = i
                       tryqueens2(k + 1)
                   end
               end
               pop!(res2)
               if length(res2)>0 && res2[end]<0 && k>1
                   res2[end] -= 1
                   push!(res2,0)
               end
           else
               push!(res2,-1)
               push!(res2,0)
           end
       end

This version stores the solutions similarly to a pre-order traversal of the search tree used to find them. It is quite compact in terms of memory, and thus would be good for speed. It is easy enough to iterate over the solutions, but randomly accessing them or sampling would be harder.

Basic operation:

julia> res2 = Vector{Int8}(); tryqueens2(1)

julia> foldl((x,y)->(y>0 ? push!(x,y) : 
  (println(x); deleteat!(x,length(x)+y+1:length(x)); x)), 
  res2; init=Int[])
[1, 5, 8, 6, 3, 7, 2, 4]
[1, 6, 8, 3, 7, 4, 2, 5]
[1, 7, 4, 6, 8, 2, 5, 3]
[1, 7, 5, 8, 2, 4, 6, 3]
[2, 4, 6, 8, 3, 1, 7, 5]
[2, 5, 7, 1, 3, 8, 6, 4]
[2, 5, 7, 4, 1, 8, 6, 3]
[2, 6, 1, 7, 4, 8, 3, 5]
:
:
7

Linking some related Rosetta code on the Eight Queens puzzle.

9

I’ll just leave this here as an example of how not to approach this: Fun "interview" question solved easily in Julia - #13 by Mason