# Help with Puzzle Solver Program

**URL:** <https://discourse.julialang.org/t/help-with-puzzle-solver-program/37412>\
**Category:** Modelling & Simulations\
**Tags:** puzzles\
**Created:** [April 11, 2020, 7:07pm UTC](https://discourse.julialang.org/t/help-with-puzzle-solver-program/37412 "2020-04-11T19:07:21Z")\
**Posts on this page:** 6\
**Page:** 1

<div class="post-metadata">

**Author:** ![peterfarrell66](https://avatars.discourse-cdn.com/v4/letter/p/46a35a/32.png) [@peterfarrell66](https://discourse.julialang.org/u/peterfarrell66)\
**Post date:** [April 11, 2020, 7:07pm UTC](https://discourse.julialang.org/t/help-with-puzzle-solver-program/37412/1 "2020-04-11T19:07:21Z")

</div>

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)

---

<div class="post-metadata">

**Author:** ![peterfarrell66](https://avatars.discourse-cdn.com/v4/letter/p/46a35a/32.png) [@peterfarrell66](https://discourse.julialang.org/u/peterfarrell66)\
**Post date:** [April 11, 2020, 11:58pm UTC](https://discourse.julialang.org/t/help-with-puzzle-solver-program/37412/2 "2020-04-11T23:58:11Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![baggepinnen](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/baggepinnen/32/693_2.png) [@baggepinnen](https://discourse.julialang.org/u/baggepinnen)\
**Post date:** [April 12, 2020, 2:34am UTC](https://discourse.julialang.org/t/help-with-puzzle-solver-program/37412/3 "2020-04-12T02:34:13Z")

</div>

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

```julia
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)

```julia
[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.

---

<div class="post-metadata">

**Author:** ![peterfarrell66](https://avatars.discourse-cdn.com/v4/letter/p/46a35a/32.png) [@peterfarrell66](https://discourse.julialang.org/u/peterfarrell66)\
**Post date:** [April 12, 2020, 3:33am UTC](https://discourse.julialang.org/t/help-with-puzzle-solver-program/37412/4 "2020-04-12T03:33:17Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![baggepinnen](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/baggepinnen/32/693_2.png) [@baggepinnen](https://discourse.julialang.org/u/baggepinnen)\
**Post date:** [April 12, 2020, 4:03am UTC](https://discourse.julialang.org/t/help-with-puzzle-solver-program/37412/5 "2020-04-12T04:03:31Z")

</div>

> [@peterfarrell66](#):
>
> [https://github.com/hackingmath/jupyter/blob/master/Julia%20Puzzle%20Solver.ipynb](https://github.com/hackingmath/jupyter/blob/master/Julia%20Puzzle%20Solver.ipynb)

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

```julia
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

```julia
  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

```julia
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

```julia
 436.036 ms (3453748 allocations: 158.10 MiB)

```

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

---

<div class="post-metadata">

**Author:** ![baggepinnen](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/baggepinnen/32/693_2.png) [@baggepinnen](https://discourse.julialang.org/u/baggepinnen)\
**Post date:** [April 12, 2020, 4:30am UTC](https://discourse.julialang.org/t/help-with-puzzle-solver-program/37412/6 "2020-04-12T04:30:08Z")

</div>

Full code available here

> **Click to expand!**
>
> ```julia
> 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()
> 
> ```