Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

In this Discussion

8 Queens or 1 to 50

dave1707dave1707 Mod
in Code Sharing Posts: 9,730

I had nothing better to do so I thought I’d write an 8 queens program. If you don’t know about it, you’re supposed to place 8 queens on an 8x8 board so that none of the queens can capture any other queen. There’s nothing fancy about the code or display. I was more curious as to how long or how many solutions there were per board. Once I had the 8 Queens going, I expanded it to do boards from sizes of 1 to 50. There are options to do single step, or change the speed from 1 step per draw cycle (default), up to 2,000,001 steps per draw cycle. You can select to print the solutions without stopping until it’s done or stop after each solution. You can play around with the selections to see how they work. This was more of just a hack job which I normally do with a lot of my code. When I can’t find anything better to do, I usually go back and rewrite the code to make it smaller and look better. But until then this will find the solutions, at least on the smaller boards, unless you want to wait awhile.

n=1 # of solutions = 1
n=2 # of solutions = 0
n=3 # of solutions = 0
n=4 # of solutions = 2
n=5 # of solutions = 10
n=6 # of solutions = 4
n=7 # of solutions = 40
n=8 # of solutions = 92
n=9 # of solutions = 352
n=10 # of solutions = 724
n=11 # of solutions = 2680
n=12 # of solutions = 14200

viewer.mode=STANDARD

function setup()
    rectMode(CENTER)
    parameter.integer("board",1,50,8,setup1)
    parameter.integer("speed",0,20,0)
    parameter.boolean("stop_on_solution",true)
    parameter.boolean("single_step",false)
    setup1()
end

function setup1()
    output.clear()
    check=false
    count,count1=0,0
    n=board
    size=WIDTH/(n+3)
    offset=1
    queens={}
    for z=1,n do
        queens[z]=0
    end  
end

function draw()
    background()
    fontSize(size-5)
    textMode(CENTER)
    if check then
        for t=1,100000*speed+1 do   
            addOne()
            if offset<1 then
                return
            end
            if single_step then
                speed=0
                check=false
            end 
            count1=count1+1
            if checkRow() then
                if checkDownDiag() then
                    if checkUpDiag() then
                        offset=offset+1
                        if offset>n then    -- solution
                            count=count+1
                            print(count.."="..table.concat(queens," "))
                            offset=offset-1
                            if stop_on_solution then
                                t=100000*speed+1
                                check=false
                            end
                            return
                        end
                    end
                end
            end 
        end       
    end
    fill(255)    
    if stop_on_solution then
        for x=1,n do
            for y=1,n do
                fill(255,0,0)
                rect(x*size,y*size,size)
                fill(255)
                if queens[x]==y then
                    fill(0,0,255)
                    rect(x*size,y*size,size)
                    fill(255)
                    text(queens[x],x*size,y*size)
                end
            end
        end
    else
        single_step=false
    end

    fontSize(20)
    if not check then
        text("Tap screen to continue",WIDTH/2,HEIGHT/2)
    end
    textMode(CORNER)
    text("Draw Speed  "..speed*100000+1,10,HEIGHT-30)
    text("Tries "..count1,WIDTH/2-60,HEIGHT-30)
    text("Solutions "..count,WIDTH-150,HEIGHT-30)    

end

function touched(t)
    if t.state==BEGAN then
        check=true
        if offset<1 then
            offset,count,count1=1,0,0
        end
    end    
end

function addOne()   -- add 1 to column and zero columns to right
    if offset<1 then
        check=false
        print("solutions complete")
        return
    end
    queens[offset]=queens[offset]+1
    if queens[offset]>n then
        offset=offset-1
        addOne()
    end
    for z=offset+1,n do
        queens[z]=0
    end
end

function checkRow()
    v=queens[offset]
    for z=offset-1,1,-1 do
        if v==queens[z] then
            return false    -- another queen found
        end
    end
    return true -- no other queens found
end

function checkDownDiag()    -- down and left
    v=queens[offset]
    b=1
    if v==1 then    -- nothing to check
        return true
    end
    for z=offset-1,1,-1 do
        if v-b==queens[z] then
            return false    -- another queen found
        else
            b=b+1
            if v-b<1 then
                return true
            end
        end
    end
    return true -- no other queens found
end

function checkUpDiag()  -- up and left
    v=queens[offset]
    b=1
    if v==n then    -- nothing to check
        return true
    end
    for z=offset-1,1,-1 do
        if v+b==queens[z] then
            return false    -- another queen found
        else
            b=b+1
            if v+b>n then
                return true
            end
        end
    end
    return true -- no other queens found
end

Comments

Sign In or Register to comment.