Help with Puzzle Solver Program

Hi!

I’m new to Julia but I’ve had years of experience using Python and some Javascript too. I wrote a puzzle solving program in Python and got a big speedup when I translated it to Javascript. I’ve taken a bash at a Julia version. It’s to solve a mini-sudoku puzzle (6x6 instead of 9x9) and it works recursively, filling a solution array and solving for a growing “position” variable and backtracking when it hits a conflict. The original puzzle is linked to at the beginning of the program.

I’ve tested all the other functions, but the “solve” function is giving me only a partial solution. The “7” is the correct value that’s first in the solution, but then the program doesn’t go any further? I don’t know what it’s doing since my Jupyter program won’t print out all the boards, it stops at a certain point. The Visual Studio Code won’t even run it, and I have no idea what the error message is all about. It doesn’t even reference my program!

https://github.com/hackingmath/jupyter/blob/master/Julia%20Puzzle%20Solver.ipynb

The identical code, just in one place:
https://github.com/hackingmath/jupyter/blob/master/numoku_solver.jl

Any input would be appreciated!

Thanks,

Peter Farrell (twitter: hackingmath)

A programming friend of mine found the bug. The Jupyter Notebook now reflects the correction, and once the standard Numoku worked I adapted it to solve a harder puzzle with more numbers to check.

My vanilla Python program (using lists, not Numpy arrays) took 50 minutes to crank through it, a literally-tranlated Javascript program took 50 seconds and Julia took under 7 seconds! I’m really looking seriously at Julia!

Peter Farrell

4 Likes

Looking at your code and the timing result
3.185998 seconds (49.77 M allocations: 2.293 GiB, 6.27% gc time)
I see that you have written code that allocates a lot of temporary arrays. While this style of coding works and is common in python, you can do faster in Julia.
Things like
board[6*n-5:6*n]
allocates a slice, i.e., a new vector. Try replacing it with
@view board[6*n-5:6*n]

This variable

q = [[1,2,3,7,8,9,13,14,15],[4,5,6,10,11,12,16,17,18],[19,20,21,25,26,27,31,32,33],[22,23,24,28,29,30,34,35,36]]

can be made global and const (const is important).

Variables like these (that appear in many places)

[board[i] for i in q[n]]

are allocated in every call to the function, you can either create a global vector and write to that in-place to save those allocations, or send in vectors to the functions that are used to store the results.

Reducing allocations in allocation heavy code can lead to dramatic improvements in performance.

5 Likes

Thanks so much for the feedback! I copied and pasted from Python a lot so there’s no doubt the program could benefit from using better Julia tools. Even more impressive that my newbie code could speed up things as fast as it did. I’ll learn more about allocations like you suggested.

Peter

1 Like

I think you might be able to get away with using tuples instead of vectors, I have not tried the functions below, but something like this might work

function row(board,n)
    #returns values in row n of board
    return @view board[6*n-5:6*n]
end

function col(board,n)
    #returns values in col n of board
    ct = n:6:36
    ntuple(i->board[ct[i]], 6)
end

const q = [[1,2,3,7,8,9,13,14,15],[4,5,6,10,11,12,16,17,18],[19,20,21,25,26,27,31,32,33],[22,23,24,28,29,30,34,35,36]]
function quadrant(board,n)
    qn = q[n]
    return ntuple(i->board[qn[i]], 9)
end

Tuples will not be heap allocated if the compiler can infer their full type, which I think it should be able to do for the functions above

EDIT: I tried, it cuts my timing from

  4.051498 seconds (49.68 M allocations: 2.288 GiB, 5.94% gc time)
# to
  2.548475 seconds (27.07 M allocations: 866.295 MiB, 3.59% gc time)

and making the global variables, such as BOARD const reduces the timing to

0.875207 seconds (5.90 M allocations: 543.259 MiB, 6.83% gc time)

allocating the output variable as a global const and assigning into this instead of output = deepcopy(BOARD) reduced the timing to

 436.036 ms (3453748 allocations: 158.10 MiB)

A solid factor of 10x improvement from reducing the amount of allocations :slight_smile:

2 Likes

Full code available here

Click to expand!
function row(board,n)
    #returns values in row n of board
    return @view board[6*n-5:6*n]
end

function col(board,n)
    #returns values in col n of board
        ct = n:6:36
        ntuple(i->board[ct[i]], 6)
end

const q = ((1,2,3,7,8,9,13,14,15),(4,5,6,10,11,12,16,17,18),(19,20,21,25,26,27,31,32,33),(22,23,24,28,29,30,34,35,36))
function quadrant(board,n)
    qn = q[n]
    return ntuple(i->board[qn[i]], 9)
end


# function row(board,n)
#     #returns values in row n of board
#     return board[6*n-5:6*n]
# end
#
# function col(board,n)
#     #returns values in col n of board
#     if n == 6
#         return [board[i] for i in [6,12,18,24,30,36]]
#     else
#         return [board[i] for i in 1:36 if i%6 == n]
#     end
# end
#
# function quadrant(board,n)
#     q = [[1,2,3,7,8,9,13,14,15],[4,5,6,10,11,12,16,17,18],[19,20,21,25,26,27,31,32,33],[22,23,24,28,29,30,34,35,36]]
#     return [board[i] for i in q[n]]
# end


#Solving Numoku Puzzle 20002
#https://twitter.com/1to9puzzle/status/1212782433612861441
const BOARD = [4,2,8,0,0,0,0,0,0,9,0,0,0,0,7,0,0,0,0,0,0,4,0,0,0,0,5,0,0,0,0,0,0,5,6,2]

function count(mylist,thing)
    output = 0
    for i in mylist
        if i == thing
            output += 1
            end
    end
    output
end

const NUMS = 1:9
const NUMBLANKS = count(BOARD,0)
#print(NUMBLANKS)

const output = copy(BOARD)

function populate_board(solution_board)
    copyto!(output, BOARD)
    ind = 1
    for i in 1:36
        if output[i] == 0
            output[i] = solution_board[ind]
            ind +=1
        end
    end
    output
end


function repeat(mylist)
    for n in mylist
        if n != 0 && count(mylist,n)>1
            return true
        end
    end
    return false

end

function print_board(solution_board)
    #board = populate_board(solution_board)

    print()
    for i in 1:36
        if i % 6 == 0
            println(solution_board[i])
        else
            print(solution_board[i])
            print(' ')
        end
    end
    println() #blank line
end

# rboard = rand(1:9,1,36)
# print_board(rboard)
# println(row(rboard,2))
#println(col(rboard,6))
# println(sum(quadrant(rboard,2)))

function check_no_conflicts(solution_board)
    #Returns False if there ARE conflicts
    for j in 1:6
        this_row = row(solution_board,j)
        if repeat(this_row)
            #println("repeat row",j)
            return false
        end
        if count(this_row,0) == 0 && sum(this_row) != 30
            return false
        end
        this_col = col(solution_board,j)
        #println("col count 0's ",count(this_col,0))
        if repeat(this_col)
            #println("repeat col",j)
            return false
        end
        if (count(this_col,0) == 0) && (sum(this_col) != 30)
            #println("col sum",j)
            return false
        end
    end
    for i in 1:4
        this_quad = quadrant(solution_board,i)
        if repeat(this_quad)
            return false
        end
        for j in 1:9
            if count(this_quad,0) == 0 && count(this_quad,j) != 1
                #println("quad",n)
                return false
            end
        end
    end
    return true
end

# rboard = rand(1:9,1,36)
# print_board(rboard)
# println(check_no_conflicts(rboard))
const board = [4, 2, 8, 7, 3, 6, 1, 5, 3, 9, 8, 4, 6, 9, 7, 2, 5, 1, 2, 3, 6, 4, 7, 8, 8, 4, 5, 3, 1, 9, 9, 7, 1, 5, 6, 2]
println(check_no_conflicts(board))

function solve(values, size)
    solution_list = zeros(size)

    function extend_solution(position)
        for value in values
            solution_list[position] = value
            solution = populate_board(solution_list)
            #print_board(solution)
            if check_no_conflicts(solution)
                #This change was the key. It wasn't returning the
                #solution up to the end.
                if position >= size
                    return solution
                end
                new_solution = extend_solution(position+1)
                if new_solution != nothing
                    return new_solution
                end
            else
                solution_list[position] = 0
                if position < size
                    solution_list[position+1] = 0
                end
                if value == values[length(values)]
                    #println("end of values")
                    if position > 1
                        solution_list[position-1] = 0
                    end
                end

            end
        end

        nothing
    end
    extend_solution(1)
end

#board1 = create_board(BOARD)
#print_board(board1)

function main()
    soln = solve(NUMS,NUMBLANKS)
    # print_board(soln)
end

main()

using BenchmarkTools
@btime main()
5 Likes