using Permutations using Base.Threads const tableau_shape = [3, 3] const num_tableau_entries = sum(tableau_shape) function create_2d_to_1d_lookup_table() lookup_table = Vector{Int}[] index = 1 for i = 1:length(tableau_shape) push!(lookup_table, Int[]) for j in 1:tableau_shape[i] push!(lookup_table[i], index) index += 1 end end return lookup_table end # Returns the 1D index of a given 2D coordinate const lookup_table_2d_to_1d = create_2d_to_1d_lookup_table() function create_1d_to_2d_lookup_table() lookup_table = Vector{Int}[] for i = 1:length(tableau_shape) for j in 1:tableau_shape[i] push!(lookup_table, [i, j]) end end return lookup_table end # Returns the 1D index of a given 2D coordinate const lookup_table_1d_to_2d = create_1d_to_2d_lookup_table() const good_2x2::Vector{Vector{Vector{UInt8}}} = Vector{Vector{UInt8}}[ [[1, 2, 3, 4], [1, 3, 2, 4]], [[1, 3, 2, 4], [1, 2, 3, 4]], [[1, 3, 4, 2], [1, 4, 3, 2]], [[1, 3, 4, 2], [2, 3, 4, 1]], [[1, 4, 3, 2], [1, 3, 4, 2]], [[1, 4, 3, 2], [2, 4, 3, 1]], [[2, 1, 4, 3], [3, 1, 4, 2]], [[2, 3, 4, 1], [1, 3, 4, 2]], [[2, 3, 4, 1], [2, 4, 3, 1]], [[2, 4, 1, 3], [3, 4, 1, 2]], [[2, 4, 3, 1], [1, 4, 3, 2]], [[2, 4, 3, 1], [2, 3, 4, 1]], [[3, 1, 2, 4], [3, 2, 1, 4]], [[3, 1, 2, 4], [4, 1, 2, 3]], [[3, 1, 4, 2], [2, 1, 4, 3]], [[3, 2, 1, 4], [3, 1, 2, 4]], [[3, 2, 1, 4], [4, 2, 1, 3]], [[3, 4, 1, 2], [2, 4, 1, 3]], [[4, 1, 2, 3], [3, 1, 2, 4]], [[4, 1, 2, 3], [4, 2, 1, 3]], [[4, 2, 1, 3], [3, 2, 1, 4]], [[4, 2, 1, 3], [4, 1, 2, 3]], [[4, 2, 3, 1], [4, 3, 2, 1]], [[4, 3, 2, 1], [4, 2, 3, 1]] ] const good_3x2::Vector{Vector{Vector{UInt8}}} = Vector{Vector{UInt8}}[ [[1, 2, 3, 4, 5, 6], [1, 4, 2, 5, 3, 6]], [[1, 3, 4, 5, 6, 2], [1, 5, 3, 6, 4, 2]], [[1, 3, 5, 2, 4, 6], [1, 5, 4, 3, 2, 6]], [[1, 4, 2, 5, 3, 6], [1, 2, 3, 4, 5, 6]], [[1, 4, 2, 5, 6, 3], [2, 3, 4, 5, 6, 1]], [[1, 4, 2, 6, 5, 3], [2, 3, 4, 6, 5, 1]], [[1, 4, 5, 3, 2, 6], [2, 3, 5, 1, 4, 6]], [[1, 4, 6, 3, 2, 5], [2, 3, 6, 1, 4, 5]], [[1, 4, 6, 3, 5, 2], [1, 6, 5, 4, 3, 2]], [[1, 5, 3, 2, 6, 4], [3, 5, 4, 1, 6, 2]], [[1, 5, 3, 6, 4, 2], [1, 3, 4, 5, 6, 2]], [[1, 5, 4, 3, 2, 6], [1, 3, 5, 2, 4, 6]], [[1, 6, 3, 2, 5, 4], [3, 6, 4, 1, 5, 2]], [[1, 6, 5, 4, 3, 2], [1, 4, 6, 3, 5, 2]], [[2, 1, 4, 3, 6, 5], [4, 1, 5, 2, 6, 3]], [[2, 3, 4, 5, 6, 1], [1, 4, 2, 5, 6, 3]], [[2, 3, 4, 5, 6, 1], [2, 5, 3, 6, 4, 1]], [[2, 3, 4, 6, 5, 1], [1, 4, 2, 6, 5, 3]], [[2, 3, 5, 1, 4, 6], [1, 4, 5, 3, 2, 6]], [[2, 3, 6, 1, 4, 5], [1, 4, 6, 3, 2, 5]], [[2, 4, 6, 3, 5, 1], [2, 6, 5, 4, 3, 1]], [[2, 5, 1, 4, 3, 6], [3, 4, 1, 2, 5, 6]], [[2, 5, 1, 4, 6, 3], [4, 5, 2, 3, 6, 1]], [[2, 5, 3, 1, 6, 4], [3, 4, 5, 1, 6, 2]], [[2, 5, 3, 6, 1, 4], [3, 4, 5, 6, 1, 2]], [[2, 5, 3, 6, 4, 1], [2, 3, 4, 5, 6, 1]], [[2, 5, 6, 4, 3, 1], [3, 4, 6, 2, 5, 1]], [[2, 6, 1, 4, 5, 3], [4, 6, 2, 3, 5, 1]], [[2, 6, 4, 3, 1, 5], [4, 6, 5, 2, 1, 3]], [[2, 6, 5, 4, 3, 1], [2, 4, 6, 3, 5, 1]], [[3, 1, 2, 5, 6, 4], [5, 1, 3, 4, 6, 2]], [[3, 1, 5, 4, 2, 6], [5, 1, 6, 3, 2, 4]], [[3, 2, 1, 5, 6, 4], [4, 1, 3, 5, 6, 2]], [[3, 2, 1, 6, 5, 4], [4, 1, 3, 6, 5, 2]], [[3, 2, 5, 4, 1, 6], [4, 1, 5, 2, 3, 6]], [[3, 2, 5, 4, 1, 6], [5, 2, 6, 3, 1, 4]], [[3, 2, 6, 4, 1, 5], [4, 1, 6, 2, 3, 5]], [[3, 4, 1, 2, 5, 6], [2, 5, 1, 4, 3, 6]], [[3, 4, 5, 1, 6, 2], [2, 5, 3, 1, 6, 4]], [[3, 4, 5, 6, 1, 2], [2, 5, 3, 6, 1, 4]], [[3, 4, 6, 2, 5, 1], [2, 5, 6, 4, 3, 1]], [[3, 5, 4, 1, 6, 2], [1, 5, 3, 2, 6, 4]], [[3, 6, 1, 5, 4, 2], [4, 5, 1, 3, 6, 2]], [[3, 6, 2, 5, 1, 4], [5, 6, 3, 4, 1, 2]], [[3, 6, 2, 5, 4, 1], [4, 5, 2, 3, 6, 1]], [[3, 6, 4, 1, 2, 5], [4, 5, 6, 1, 2, 3]], [[3, 6, 4, 1, 5, 2], [1, 6, 3, 2, 5, 4]], [[3, 6, 4, 2, 1, 5], [4, 5, 6, 2, 1, 3]], [[4, 1, 3, 5, 6, 2], [3, 2, 1, 5, 6, 4]], [[4, 1, 3, 6, 2, 5], [6, 1, 4, 5, 2, 3]], [[4, 1, 3, 6, 5, 2], [3, 2, 1, 6, 5, 4]], [[4, 1, 5, 2, 3, 6], [3, 2, 5, 4, 1, 6]], [[4, 1, 5, 2, 6, 3], [2, 1, 4, 3, 6, 5]], [[4, 1, 6, 2, 3, 5], [3, 2, 6, 4, 1, 5]], [[4, 2, 3, 6, 1, 5], [6, 2, 4, 5, 1, 3]], [[4, 3, 1, 5, 2, 6], [5, 2, 1, 3, 4, 6]], [[4, 3, 2, 1, 6, 5], [5, 2, 4, 1, 6, 3]], [[4, 3, 2, 6, 1, 5], [5, 2, 4, 6, 1, 3]], [[4, 3, 6, 5, 2, 1], [5, 2, 6, 3, 4, 1]], [[4, 5, 1, 3, 6, 2], [3, 6, 1, 5, 4, 2]], [[4, 5, 2, 3, 6, 1], [2, 5, 1, 4, 6, 3]], [[4, 5, 2, 3, 6, 1], [3, 6, 2, 5, 4, 1]], [[4, 5, 6, 1, 2, 3], [3, 6, 4, 1, 2, 5]], [[4, 5, 6, 2, 1, 3], [3, 6, 4, 2, 1, 5]], [[4, 6, 2, 3, 5, 1], [2, 6, 1, 4, 5, 3]], [[4, 6, 5, 2, 1, 3], [2, 6, 4, 3, 1, 5]], [[5, 1, 2, 3, 4, 6], [5, 3, 1, 4, 2, 6]], [[5, 1, 3, 4, 6, 2], [3, 1, 2, 5, 6, 4]], [[5, 1, 6, 3, 2, 4], [3, 1, 5, 4, 2, 6]], [[5, 2, 1, 3, 4, 6], [4, 3, 1, 5, 2, 6]], [[5, 2, 4, 1, 3, 6], [5, 4, 3, 2, 1, 6]], [[5, 2, 4, 1, 6, 3], [4, 3, 2, 1, 6, 5]], [[5, 2, 4, 6, 1, 3], [4, 3, 2, 6, 1, 5]], [[5, 2, 6, 3, 1, 4], [3, 2, 5, 4, 1, 6]], [[5, 2, 6, 3, 4, 1], [4, 3, 6, 5, 2, 1]], [[5, 3, 1, 4, 2, 6], [5, 1, 2, 3, 4, 6]], [[5, 4, 1, 6, 3, 2], [6, 3, 1, 4, 5, 2]], [[5, 4, 2, 6, 3, 1], [6, 3, 2, 4, 5, 1]], [[5, 4, 3, 1, 2, 6], [6, 3, 5, 1, 2, 4]], [[5, 4, 3, 2, 1, 6], [5, 2, 4, 1, 3, 6]], [[5, 4, 3, 2, 1, 6], [6, 3, 5, 2, 1, 4]], [[5, 6, 3, 4, 1, 2], [3, 6, 2, 5, 1, 4]], [[6, 1, 2, 3, 4, 5], [6, 3, 1, 4, 2, 5]], [[6, 1, 4, 5, 2, 3], [4, 1, 3, 6, 2, 5]], [[6, 2, 3, 4, 5, 1], [6, 4, 2, 5, 3, 1]], [[6, 2, 4, 1, 3, 5], [6, 4, 3, 2, 1, 5]], [[6, 2, 4, 5, 1, 3], [4, 2, 3, 6, 1, 5]], [[6, 3, 1, 4, 2, 5], [6, 1, 2, 3, 4, 5]], [[6, 3, 1, 4, 5, 2], [5, 4, 1, 6, 3, 2]], [[6, 3, 2, 4, 5, 1], [5, 4, 2, 6, 3, 1]], [[6, 3, 5, 1, 2, 4], [5, 4, 3, 1, 2, 6]], [[6, 3, 5, 2, 1, 4], [5, 4, 3, 2, 1, 6]], [[6, 3, 5, 2, 4, 1], [6, 5, 4, 3, 2, 1]], [[6, 4, 2, 5, 3, 1], [6, 2, 3, 4, 5, 1]], [[6, 4, 3, 2, 1, 5], [6, 2, 4, 1, 3, 5]], [[6, 5, 4, 3, 2, 1], [6, 3, 5, 2, 4, 1]], ] const good_3x3::Vector{Vector{Vector{UInt8}}} = Vector{Vector{UInt8}}[ [[1, 2, 3, 4, 5, 6, 7, 8, 9], [1, 4, 7, 2, 5, 8, 3, 6, 9]], [[1, 2, 3, 7, 8, 9, 4, 5, 6], [1, 4, 7, 3, 6, 9, 2, 5, 8]], [[1, 3, 2, 4, 6, 5, 7, 9, 8], [1, 7, 4, 2, 8, 5, 3, 9, 6]], [[1, 3, 2, 7, 9, 8, 4, 6, 5], [1, 7, 4, 3, 9, 6, 2, 8, 5]], [[1, 3, 4, 5, 6, 7, 8, 9, 2], [1, 5, 8, 3, 6, 9, 4, 7, 2]], [[1, 3, 4, 8, 9, 2, 5, 6, 7], [1, 5, 8, 4, 7, 2, 3, 6, 9]], [[1, 3, 6, 7, 9, 4, 8, 2, 5], [1, 7, 8, 3, 9, 2, 6, 4, 5]], [[1, 3, 6, 8, 2, 5, 7, 9, 4], [1, 7, 8, 6, 4, 5, 3, 9, 2]], [[1, 4, 3, 5, 7, 6, 8, 2, 9], [1, 8, 5, 3, 9, 6, 4, 2, 7]], [[1, 4, 3, 8, 2, 9, 5, 7, 6], [1, 8, 5, 4, 2, 7, 3, 9, 6]], [[1, 4, 7, 2, 5, 8, 3, 6, 9], [1, 2, 3, 4, 5, 6, 7, 8, 9]], [[1, 4, 7, 3, 6, 9, 2, 5, 8], [1, 2, 3, 7, 8, 9, 4, 5, 6]], [[1, 4, 7, 8, 2, 5, 9, 3, 6], [1, 8, 9, 4, 2, 3, 7, 5, 6]], [[1, 4, 7, 9, 3, 6, 8, 2, 5], [1, 8, 9, 7, 5, 6, 4, 2, 3]], [[1, 5, 8, 3, 6, 9, 4, 7, 2], [1, 3, 4, 5, 6, 7, 8, 9, 2]], [[1, 5, 8, 4, 7, 2, 3, 6, 9], [1, 3, 4, 8, 9, 2, 5, 6, 7]], [[1, 6, 3, 7, 4, 9, 8, 5, 2], [1, 8, 7, 3, 2, 9, 6, 5, 4]], [[1, 6, 3, 8, 5, 2, 7, 4, 9], [1, 8, 7, 6, 5, 4, 3, 2, 9]], [[1, 7, 4, 2, 8, 5, 3, 9, 6], [1, 3, 2, 4, 6, 5, 7, 9, 8]], [[1, 7, 4, 3, 9, 6, 2, 8, 5], [1, 3, 2, 7, 9, 8, 4, 6, 5]], [[1, 7, 4, 8, 5, 2, 9, 6, 3], [1, 9, 8, 4, 3, 2, 7, 6, 5]], [[1, 7, 4, 9, 6, 3, 8, 5, 2], [1, 9, 8, 7, 6, 5, 4, 3, 2]], [[1, 7, 8, 3, 9, 2, 6, 4, 5], [1, 3, 6, 7, 9, 4, 8, 2, 5]], [[1, 7, 8, 6, 4, 5, 3, 9, 2], [1, 3, 6, 8, 2, 5, 7, 9, 4]], [[1, 8, 5, 3, 9, 6, 4, 2, 7], [1, 4, 3, 5, 7, 6, 8, 2, 9]], [[1, 8, 5, 4, 2, 7, 3, 9, 6], [1, 4, 3, 8, 2, 9, 5, 7, 6]], [[1, 8, 7, 3, 2, 9, 6, 5, 4], [1, 6, 3, 7, 4, 9, 8, 5, 2]], [[1, 8, 7, 6, 5, 4, 3, 2, 9], [1, 6, 3, 8, 5, 2, 7, 4, 9]], [[1, 8, 9, 4, 2, 3, 7, 5, 6], [1, 4, 7, 8, 2, 5, 9, 3, 6]], [[1, 8, 9, 7, 5, 6, 4, 2, 3], [1, 4, 7, 9, 3, 6, 8, 2, 5]], [[1, 9, 8, 4, 3, 2, 7, 6, 5], [1, 7, 4, 8, 5, 2, 9, 6, 3]], [[1, 9, 8, 7, 6, 5, 4, 3, 2], [1, 7, 4, 9, 6, 3, 8, 5, 2]], [[2, 1, 8, 5, 4, 3, 9, 7, 6], [6, 3, 8, 7, 4, 1, 9, 5, 2]], [[2, 1, 8, 9, 7, 6, 5, 4, 3], [6, 3, 8, 9, 5, 2, 7, 4, 1]], [[2, 1, 9, 5, 4, 3, 8, 7, 6], [6, 3, 9, 7, 4, 1, 8, 5, 2]], [[2, 1, 9, 8, 7, 6, 5, 4, 3], [6, 3, 9, 8, 5, 2, 7, 4, 1]], [[2, 3, 4, 5, 6, 7, 8, 9, 1], [2, 5, 8, 3, 6, 9, 4, 7, 1]], [[2, 3, 4, 8, 9, 1, 5, 6, 7], [2, 5, 8, 4, 7, 1, 3, 6, 9]], [[2, 4, 3, 5, 7, 6, 8, 1, 9], [2, 8, 5, 3, 9, 6, 4, 1, 7]], [[2, 4, 3, 8, 1, 9, 5, 7, 6], [2, 8, 5, 4, 1, 7, 3, 9, 6]], [[2, 4, 7, 8, 1, 5, 9, 3, 6], [2, 8, 9, 4, 1, 3, 7, 5, 6]], [[2, 4, 7, 9, 3, 6, 8, 1, 5], [2, 8, 9, 7, 5, 6, 4, 1, 3]], [[2, 5, 8, 1, 4, 7, 9, 3, 6], [6, 7, 8, 3, 4, 5, 9, 1, 2]], [[2, 5, 8, 3, 6, 9, 4, 7, 1], [2, 3, 4, 5, 6, 7, 8, 9, 1]], [[2, 5, 8, 4, 7, 1, 3, 6, 9], [2, 3, 4, 8, 9, 1, 5, 6, 7]], [[2, 5, 8, 9, 3, 6, 1, 4, 7], [6, 7, 8, 9, 1, 2, 3, 4, 5]], [[2, 5, 9, 1, 4, 7, 8, 3, 6], [6, 7, 9, 3, 4, 5, 8, 1, 2]], [[2, 5, 9, 8, 3, 6, 1, 4, 7], [6, 7, 9, 8, 1, 2, 3, 4, 5]], [[2, 7, 4, 8, 5, 1, 9, 6, 3], [2, 9, 8, 4, 3, 1, 7, 6, 5]], [[2, 7, 4, 9, 6, 3, 8, 5, 1], [2, 9, 8, 7, 6, 5, 4, 3, 1]], [[2, 8, 1, 5, 3, 4, 9, 6, 7], [6, 8, 3, 7, 1, 4, 9, 2, 5]], [[2, 8, 1, 9, 6, 7, 5, 3, 4], [6, 8, 3, 9, 2, 5, 7, 1, 4]], [[2, 8, 5, 1, 7, 4, 9, 6, 3], [6, 8, 7, 3, 5, 4, 9, 2, 1]], [[2, 8, 5, 3, 9, 6, 4, 1, 7], [2, 4, 3, 5, 7, 6, 8, 1, 9]], [[2, 8, 5, 4, 1, 7, 3, 9, 6], [2, 4, 3, 8, 1, 9, 5, 7, 6]], [[2, 8, 5, 9, 6, 3, 1, 7, 4], [6, 8, 7, 9, 2, 1, 3, 5, 4]], [[2, 8, 9, 4, 1, 3, 7, 5, 6], [2, 4, 7, 8, 1, 5, 9, 3, 6]], [[2, 8, 9, 7, 5, 6, 4, 1, 3], [2, 4, 7, 9, 3, 6, 8, 1, 5]], [[2, 9, 1, 5, 3, 4, 8, 6, 7], [6, 9, 3, 7, 1, 4, 8, 2, 5]], [[2, 9, 1, 8, 6, 7, 5, 3, 4], [6, 9, 3, 8, 2, 5, 7, 1, 4]], [[2, 9, 5, 1, 7, 4, 8, 6, 3], [6, 9, 7, 3, 5, 4, 8, 2, 1]], [[2, 9, 5, 8, 6, 3, 1, 7, 4], [6, 9, 7, 8, 2, 1, 3, 5, 4]], [[2, 9, 8, 4, 3, 1, 7, 6, 5], [2, 7, 4, 8, 5, 1, 9, 6, 3]], [[2, 9, 8, 7, 6, 5, 4, 3, 1], [2, 7, 4, 9, 6, 3, 8, 5, 1]], [[3, 1, 2, 6, 4, 5, 9, 7, 8], [7, 1, 4, 8, 2, 5, 9, 3, 6]], [[3, 1, 2, 9, 7, 8, 6, 4, 5], [7, 1, 4, 9, 3, 6, 8, 2, 5]], [[3, 1, 6, 2, 8, 5, 9, 7, 4], [7, 1, 8, 4, 6, 5, 9, 3, 2]], [[3, 1, 6, 9, 7, 4, 2, 8, 5], [7, 1, 8, 9, 3, 2, 4, 6, 5]], [[3, 2, 1, 6, 5, 4, 9, 8, 7], [7, 4, 1, 8, 5, 2, 9, 6, 3]], [[3, 2, 1, 9, 8, 7, 6, 5, 4], [7, 4, 1, 9, 6, 3, 8, 5, 2]], [[3, 2, 9, 1, 8, 7, 6, 5, 4], [7, 4, 9, 1, 6, 3, 8, 5, 2]], [[3, 2, 9, 6, 5, 4, 1, 8, 7], [7, 4, 9, 8, 5, 2, 1, 6, 3]], [[3, 6, 1, 2, 5, 8, 9, 4, 7], [7, 8, 1, 4, 5, 6, 9, 2, 3]], [[3, 6, 1, 9, 4, 7, 2, 5, 8], [7, 8, 1, 9, 2, 3, 4, 5, 6]], [[3, 6, 9, 1, 4, 7, 2, 5, 8], [7, 8, 9, 1, 2, 3, 4, 5, 6]], [[3, 6, 9, 2, 5, 8, 1, 4, 7], [7, 8, 9, 4, 5, 6, 1, 2, 3]], [[3, 9, 2, 1, 7, 8, 6, 4, 5], [7, 9, 4, 1, 3, 6, 8, 2, 5]], [[3, 9, 2, 6, 4, 5, 1, 7, 8], [7, 9, 4, 8, 2, 5, 1, 3, 6]], [[3, 9, 6, 1, 7, 4, 2, 8, 5], [7, 9, 8, 1, 3, 2, 4, 6, 5]], [[3, 9, 6, 2, 8, 5, 1, 7, 4], [7, 9, 8, 4, 6, 5, 1, 3, 2]], [[4, 1, 3, 2, 8, 9, 7, 5, 6], [8, 1, 5, 2, 4, 7, 9, 3, 6]], [[4, 1, 3, 7, 5, 6, 2, 8, 9], [8, 1, 5, 9, 3, 6, 2, 4, 7]], [[4, 1, 7, 2, 8, 5, 3, 9, 6], [8, 1, 9, 2, 4, 3, 5, 7, 6]], [[4, 1, 7, 3, 9, 6, 2, 8, 5], [8, 1, 9, 5, 7, 6, 2, 4, 3]], [[4, 2, 3, 1, 8, 9, 7, 5, 6], [8, 2, 5, 1, 4, 7, 9, 3, 6]], [[4, 2, 3, 7, 5, 6, 1, 8, 9], [8, 2, 5, 9, 3, 6, 1, 4, 7]], [[4, 2, 7, 1, 8, 5, 3, 9, 6], [8, 2, 9, 1, 4, 3, 5, 7, 6]], [[4, 2, 7, 3, 9, 6, 1, 8, 5], [8, 2, 9, 5, 7, 6, 1, 4, 3]], [[4, 3, 1, 2, 9, 8, 7, 6, 5], [8, 5, 1, 2, 7, 4, 9, 6, 3]], [[4, 3, 1, 7, 6, 5, 2, 9, 8], [8, 5, 1, 9, 6, 3, 2, 7, 4]], [[4, 3, 2, 1, 9, 8, 7, 6, 5], [8, 5, 2, 1, 7, 4, 9, 6, 3]], [[4, 3, 2, 7, 6, 5, 1, 9, 8], [8, 5, 2, 9, 6, 3, 1, 7, 4]], [[4, 7, 1, 2, 5, 8, 3, 6, 9], [8, 9, 1, 2, 3, 4, 5, 6, 7]], [[4, 7, 1, 3, 6, 9, 2, 5, 8], [8, 9, 1, 5, 6, 7, 2, 3, 4]], [[4, 7, 2, 1, 5, 8, 3, 6, 9], [8, 9, 2, 1, 3, 4, 5, 6, 7]], [[4, 7, 2, 3, 6, 9, 1, 5, 8], [8, 9, 2, 5, 6, 7, 1, 3, 4]], [[6, 3, 8, 7, 4, 1, 9, 5, 2], [2, 1, 8, 5, 4, 3, 9, 7, 6]], [[6, 3, 8, 9, 5, 2, 7, 4, 1], [2, 1, 8, 9, 7, 6, 5, 4, 3]], [[6, 3, 9, 7, 4, 1, 8, 5, 2], [2, 1, 9, 5, 4, 3, 8, 7, 6]], [[6, 3, 9, 8, 5, 2, 7, 4, 1], [2, 1, 9, 8, 7, 6, 5, 4, 3]], [[6, 7, 8, 3, 4, 5, 9, 1, 2], [2, 5, 8, 1, 4, 7, 9, 3, 6]], [[6, 7, 8, 9, 1, 2, 3, 4, 5], [2, 5, 8, 9, 3, 6, 1, 4, 7]], [[6, 7, 9, 3, 4, 5, 8, 1, 2], [2, 5, 9, 1, 4, 7, 8, 3, 6]], [[6, 7, 9, 8, 1, 2, 3, 4, 5], [2, 5, 9, 8, 3, 6, 1, 4, 7]], [[6, 8, 3, 7, 1, 4, 9, 2, 5], [2, 8, 1, 5, 3, 4, 9, 6, 7]], [[6, 8, 3, 9, 2, 5, 7, 1, 4], [2, 8, 1, 9, 6, 7, 5, 3, 4]], [[6, 8, 7, 3, 5, 4, 9, 2, 1], [2, 8, 5, 1, 7, 4, 9, 6, 3]], [[6, 8, 7, 9, 2, 1, 3, 5, 4], [2, 8, 5, 9, 6, 3, 1, 7, 4]], [[6, 9, 3, 7, 1, 4, 8, 2, 5], [2, 9, 1, 5, 3, 4, 8, 6, 7]], [[6, 9, 3, 8, 2, 5, 7, 1, 4], [2, 9, 1, 8, 6, 7, 5, 3, 4]], [[6, 9, 7, 3, 5, 4, 8, 2, 1], [2, 9, 5, 1, 7, 4, 8, 6, 3]], [[6, 9, 7, 8, 2, 1, 3, 5, 4], [2, 9, 5, 8, 6, 3, 1, 7, 4]], [[7, 1, 4, 8, 2, 5, 9, 3, 6], [3, 1, 2, 6, 4, 5, 9, 7, 8]], [[7, 1, 4, 9, 3, 6, 8, 2, 5], [3, 1, 2, 9, 7, 8, 6, 4, 5]], [[7, 1, 8, 4, 6, 5, 9, 3, 2], [3, 1, 6, 2, 8, 5, 9, 7, 4]], [[7, 1, 8, 9, 3, 2, 4, 6, 5], [3, 1, 6, 9, 7, 4, 2, 8, 5]], [[7, 4, 1, 8, 5, 2, 9, 6, 3], [3, 2, 1, 6, 5, 4, 9, 8, 7]], [[7, 4, 1, 9, 6, 3, 8, 5, 2], [3, 2, 1, 9, 8, 7, 6, 5, 4]], [[7, 4, 9, 1, 6, 3, 8, 5, 2], [3, 2, 9, 1, 8, 7, 6, 5, 4]], [[7, 4, 9, 8, 5, 2, 1, 6, 3], [3, 2, 9, 6, 5, 4, 1, 8, 7]], [[7, 8, 1, 4, 5, 6, 9, 2, 3], [3, 6, 1, 2, 5, 8, 9, 4, 7]], [[7, 8, 1, 9, 2, 3, 4, 5, 6], [3, 6, 1, 9, 4, 7, 2, 5, 8]], [[7, 8, 9, 1, 2, 3, 4, 5, 6], [3, 6, 9, 1, 4, 7, 2, 5, 8]], [[7, 8, 9, 4, 5, 6, 1, 2, 3], [3, 6, 9, 2, 5, 8, 1, 4, 7]], [[7, 9, 4, 1, 3, 6, 8, 2, 5], [3, 9, 2, 1, 7, 8, 6, 4, 5]], [[7, 9, 4, 8, 2, 5, 1, 3, 6], [3, 9, 2, 6, 4, 5, 1, 7, 8]], [[7, 9, 8, 1, 3, 2, 4, 6, 5], [3, 9, 6, 1, 7, 4, 2, 8, 5]], [[7, 9, 8, 4, 6, 5, 1, 3, 2], [3, 9, 6, 2, 8, 5, 1, 7, 4]], [[8, 1, 2, 3, 4, 5, 6, 7, 9], [8, 3, 6, 1, 4, 7, 2, 5, 9]], [[8, 1, 2, 6, 7, 9, 3, 4, 5], [8, 3, 6, 2, 5, 9, 1, 4, 7]], [[8, 1, 5, 2, 4, 7, 9, 3, 6], [4, 1, 3, 2, 8, 9, 7, 5, 6]], [[8, 1, 5, 9, 3, 6, 2, 4, 7], [4, 1, 3, 7, 5, 6, 2, 8, 9]], [[8, 1, 9, 2, 4, 3, 5, 7, 6], [4, 1, 7, 2, 8, 5, 3, 9, 6]], [[8, 1, 9, 5, 7, 6, 2, 4, 3], [4, 1, 7, 3, 9, 6, 2, 8, 5]], [[8, 2, 1, 3, 5, 4, 6, 9, 7], [8, 6, 3, 1, 7, 4, 2, 9, 5]], [[8, 2, 1, 6, 9, 7, 3, 5, 4], [8, 6, 3, 2, 9, 5, 1, 7, 4]], [[8, 2, 5, 1, 4, 7, 9, 3, 6], [4, 2, 3, 1, 8, 9, 7, 5, 6]], [[8, 2, 5, 6, 9, 3, 7, 1, 4], [8, 6, 7, 2, 9, 1, 5, 3, 4]], [[8, 2, 5, 7, 1, 4, 6, 9, 3], [8, 6, 7, 5, 3, 4, 2, 9, 1]], [[8, 2, 5, 9, 3, 6, 1, 4, 7], [4, 2, 3, 7, 5, 6, 1, 8, 9]], [[8, 2, 9, 1, 4, 3, 5, 7, 6], [4, 2, 7, 1, 8, 5, 3, 9, 6]], [[8, 2, 9, 5, 7, 6, 1, 4, 3], [4, 2, 7, 3, 9, 6, 1, 8, 5]], [[8, 3, 6, 1, 4, 7, 2, 5, 9], [8, 1, 2, 3, 4, 5, 6, 7, 9]], [[8, 3, 6, 2, 5, 9, 1, 4, 7], [8, 1, 2, 6, 7, 9, 3, 4, 5]], [[8, 5, 1, 2, 7, 4, 9, 6, 3], [4, 3, 1, 2, 9, 8, 7, 6, 5]], [[8, 5, 1, 9, 6, 3, 2, 7, 4], [4, 3, 1, 7, 6, 5, 2, 9, 8]], [[8, 5, 2, 1, 7, 4, 9, 6, 3], [4, 3, 2, 1, 9, 8, 7, 6, 5]], [[8, 5, 2, 6, 3, 9, 7, 4, 1], [8, 7, 6, 2, 1, 9, 5, 4, 3]], [[8, 5, 2, 7, 4, 1, 6, 3, 9], [8, 7, 6, 5, 4, 3, 2, 1, 9]], [[8, 5, 2, 9, 6, 3, 1, 7, 4], [4, 3, 2, 7, 6, 5, 1, 9, 8]], [[8, 6, 3, 1, 7, 4, 2, 9, 5], [8, 2, 1, 3, 5, 4, 6, 9, 7]], [[8, 6, 3, 2, 9, 5, 1, 7, 4], [8, 2, 1, 6, 9, 7, 3, 5, 4]], [[8, 6, 7, 2, 9, 1, 5, 3, 4], [8, 2, 5, 6, 9, 3, 7, 1, 4]], [[8, 6, 7, 5, 3, 4, 2, 9, 1], [8, 2, 5, 7, 1, 4, 6, 9, 3]], [[8, 7, 6, 2, 1, 9, 5, 4, 3], [8, 5, 2, 6, 3, 9, 7, 4, 1]], [[8, 7, 6, 5, 4, 3, 2, 1, 9], [8, 5, 2, 7, 4, 1, 6, 3, 9]], [[8, 9, 1, 2, 3, 4, 5, 6, 7], [4, 7, 1, 2, 5, 8, 3, 6, 9]], [[8, 9, 1, 5, 6, 7, 2, 3, 4], [4, 7, 1, 3, 6, 9, 2, 5, 8]], [[8, 9, 2, 1, 3, 4, 5, 6, 7], [4, 7, 2, 1, 5, 8, 3, 6, 9]], [[8, 9, 2, 5, 6, 7, 1, 3, 4], [4, 7, 2, 3, 6, 9, 1, 5, 8]], [[9, 1, 2, 3, 4, 5, 6, 7, 8], [9, 3, 6, 1, 4, 7, 2, 5, 8]], [[9, 1, 2, 6, 7, 8, 3, 4, 5], [9, 3, 6, 2, 5, 8, 1, 4, 7]], [[9, 2, 1, 3, 5, 4, 6, 8, 7], [9, 6, 3, 1, 7, 4, 2, 8, 5]], [[9, 2, 1, 6, 8, 7, 3, 5, 4], [9, 6, 3, 2, 8, 5, 1, 7, 4]], [[9, 2, 3, 4, 5, 6, 7, 8, 1], [9, 4, 7, 2, 5, 8, 3, 6, 1]], [[9, 2, 3, 7, 8, 1, 4, 5, 6], [9, 4, 7, 3, 6, 1, 2, 5, 8]], [[9, 2, 5, 6, 8, 3, 7, 1, 4], [9, 6, 7, 2, 8, 1, 5, 3, 4]], [[9, 2, 5, 7, 1, 4, 6, 8, 3], [9, 6, 7, 5, 3, 4, 2, 8, 1]], [[9, 3, 2, 4, 6, 5, 7, 1, 8], [9, 7, 4, 2, 8, 5, 3, 1, 6]], [[9, 3, 2, 7, 1, 8, 4, 6, 5], [9, 7, 4, 3, 1, 6, 2, 8, 5]], [[9, 3, 6, 1, 4, 7, 2, 5, 8], [9, 1, 2, 3, 4, 5, 6, 7, 8]], [[9, 3, 6, 2, 5, 8, 1, 4, 7], [9, 1, 2, 6, 7, 8, 3, 4, 5]], [[9, 3, 6, 7, 1, 4, 8, 2, 5], [9, 7, 8, 3, 1, 2, 6, 4, 5]], [[9, 3, 6, 8, 2, 5, 7, 1, 4], [9, 7, 8, 6, 4, 5, 3, 1, 2]], [[9, 4, 7, 2, 5, 8, 3, 6, 1], [9, 2, 3, 4, 5, 6, 7, 8, 1]], [[9, 4, 7, 3, 6, 1, 2, 5, 8], [9, 2, 3, 7, 8, 1, 4, 5, 6]], [[9, 5, 2, 6, 3, 8, 7, 4, 1], [9, 7, 6, 2, 1, 8, 5, 4, 3]], [[9, 5, 2, 7, 4, 1, 6, 3, 8], [9, 7, 6, 5, 4, 3, 2, 1, 8]], [[9, 6, 3, 1, 7, 4, 2, 8, 5], [9, 2, 1, 3, 5, 4, 6, 8, 7]], [[9, 6, 3, 2, 8, 5, 1, 7, 4], [9, 2, 1, 6, 8, 7, 3, 5, 4]], [[9, 6, 3, 7, 4, 1, 8, 5, 2], [9, 8, 7, 3, 2, 1, 6, 5, 4]], [[9, 6, 3, 8, 5, 2, 7, 4, 1], [9, 8, 7, 6, 5, 4, 3, 2, 1]], [[9, 6, 7, 2, 8, 1, 5, 3, 4], [9, 2, 5, 6, 8, 3, 7, 1, 4]], [[9, 6, 7, 5, 3, 4, 2, 8, 1], [9, 2, 5, 7, 1, 4, 6, 8, 3]], [[9, 7, 4, 2, 8, 5, 3, 1, 6], [9, 3, 2, 4, 6, 5, 7, 1, 8]], [[9, 7, 4, 3, 1, 6, 2, 8, 5], [9, 3, 2, 7, 1, 8, 4, 6, 5]], [[9, 7, 6, 2, 1, 8, 5, 4, 3], [9, 5, 2, 6, 3, 8, 7, 4, 1]], [[9, 7, 6, 5, 4, 3, 2, 1, 8], [9, 5, 2, 7, 4, 1, 6, 3, 8]], [[9, 7, 8, 3, 1, 2, 6, 4, 5], [9, 3, 6, 7, 1, 4, 8, 2, 5]], [[9, 7, 8, 6, 4, 5, 3, 1, 2], [9, 3, 6, 8, 2, 5, 7, 1, 4]], [[9, 8, 7, 3, 2, 1, 6, 5, 4], [9, 6, 3, 7, 4, 1, 8, 5, 2]], [[9, 8, 7, 6, 5, 4, 3, 2, 1], [9, 6, 3, 8, 5, 2, 7, 4, 1]] ] # Returns true if the order and labels extend the 2x2 pattern in all possible slices. function extends_2x2(order::Vector{UInt8}, labels::Vector{UInt8}) # Loop over all places the bottom-right corner can go for i = 2:length(tableau_shape) for j = 2:tableau_shape[i] index_1 = lookup_table_2d_to_1d[i - 1][j - 1] index_2 = index_1 + 1 index_3 = lookup_table_2d_to_1d[i][j - 1] index_4 = index_3 + 1 order_corner = standardize_word( UInt8[order[index_1], order[index_2], order[index_3], order[index_4]] ) labels_corner = standardize_word( UInt8[labels[index_1], labels[index_2], labels[index_3], labels[index_4]] ) if !([order_corner, labels_corner] in good_2x2) return false end end end return true end # Returns an iterator for a range of permutations of n, useful for multithreading. function get_perm_slice(n, start_idx, end_idx) pg = PermGen(n) slice = Iterators.take(Iterators.drop(pg, start_idx - 1), end_idx - start_idx + 1) return collect(slice) end # Multithreaded function that tests every possible order-label pair for a tableau of shape tableau_shape. function test_all_pairs(max_entry::Int) num_tested = 0 num_good = 0 num_orders = factorial(num_tableau_entries) nthreads = Threads.nthreads() if (nthreads != Sys.CPU_THREADS) println("[WARNING] Multithreading incorrectly set: using $nthreads threads instead of your CPU's $(Sys.CPU_THREADS). You should enable the correct number of threads for Julia on the command line.") end orders_per_thread = ceil(Int, num_orders / nthreads) # Each entry is separate thread's list of good order-label pairs, # each of which is a 2-tuple of permutations. good_pairs = Vector{Vector{Vector{Vector{Int}}}}(undef, nthreads) Threads.@threads for thread in 1:nthreads start_idx = (thread - 1) * orders_per_thread + 1 end_idx = min(thread * orders_per_thread, num_orders) perm_slice = get_perm_slice(num_tableau_entries, start_idx, end_idx) local_good_pairs = Vector{Vector{Int}}[] for i in perm_slice order = convert(Vector{UInt8}, i.data) print_order = convert(Vector{Int}, order) for j in PermGen(num_tableau_entries) labels = convert(Vector{UInt8}, j.data) if !extends_2x2(order, labels) continue end inv_order = convert(Vector{UInt8}, inv(i).data) if garver_patrias_stress_test(inv_order, labels, max_entry) print_labels = convert(Vector{Int}, labels) # print_pair([print_order, print_labels]) push!(local_good_pairs, [print_order, print_labels]) num_good += 1 end end num_tested += 1 println("$print_order - $num_tested / $num_orders ($num_good successful)") end # print(local_good_pairs) good_pairs[thread] = local_good_pairs end combined_good_pairs = reduce(vcat, good_pairs) println("Done! ($(length(combined_good_pairs)) successful)") for line in combined_good_pairs println(line) end return combined_good_pairs end function test_pair(order::Vector{UInt8}, labels::Vector{UInt8}, max_entry::Int) orderPerm = Permutation(order) inv_order = convert(Vector{UInt8}, inv(orderPerm).data) return garver_patrias_stress_test(inv_order, labels, max_entry) end # Runs GP^O_L with the given order and labels on a bunch of tableaux, # and returns true if the results are all unique. inverse_order is a lookup for which cell is next. # For example, [3, 1, 2] means look at cell 3 first, then 1, then 2 --- not 2, then 3, then 1. function garver_patrias_stress_test(inverse_order::Vector{UInt8}, labels::Vector{UInt8}, max_entry::Int) numbers = zeros(UInt8, (num_tableau_entries)) outputs = Vector{UInt8}[] for i in 1:(max_entry ^ (num_tableau_entries)) set_numbers!(i, numbers, max_entry) output = garver_patrias(numbers, inverse_order, labels) if output == nothing return false end push!(outputs, output) end return allunique(outputs) end function set_numbers!(i::Int, numbers::Vector{UInt8}, max_entry::Int) temp = i for j = 1:(num_tableau_entries) numbers[j] = temp % max_entry temp = floor(temp / max_entry) end end # inverse_order is a lookup for which cell is next. # For example, [3, 1, 2] means look at cell 3 first, then 1, then 2 --- not 2, then 3, then 1. function garver_patrias(numbers::Vector{UInt8}, inverse_order::Vector{UInt8}, labels::Vector{UInt8}) rpp = zeros(UInt8, num_tableau_entries) for d = (-length(tableau_shape) + 1):(tableau_shape[1] - 1) # Find the bottom-right box in this diagonal. end_box = UInt8[1, 1] if d < 0 end_box[1] = -d + 1 else end_box[2] = d + 1 end while end_box[1] < length(tableau_shape) && end_box[2] < tableau_shape[end_box[1] + 1] end_box[1] += 1 end_box[2] += 1 end # Look up and left to find all the labels in this rectangle. word = UInt8[] for cell in inverse_order coordinates = lookup_table_1d_to_2d[cell] if coordinates[1] <= end_box[1] && coordinates[2] <= end_box[2] for i = 1:numbers[cell] push!(word, labels[cell]) end end end row_lengths = rskShape(word) if length(row_lengths) > min(end_box[1], end_box[2]) return nothing end row = end_box[1] col = end_box[2] j = 1 for j = 1:length(row_lengths) row = end_box[1] - (j - 1) col = end_box[2] - (j - 1) rpp[lookup_table_2d_to_1d[row][col]] = row_lengths[j] end end return rpp end # It turns out this is faster without caching. function rskShape(input_word::Vector{UInt8}) word = standardize_word(input_word) ssyt = Vector{UInt8}[UInt8[]] for letter in word row = 1 while true if length(ssyt[row]) == 0 || ssyt[row][end] <= letter push!(ssyt[row], letter) break end #Look from the right until we find a place this thing can go. j = length(ssyt[row]) while j > 1 && ssyt[row][j - 1] > letter j -= 1 end temp = ssyt[row][j] ssyt[row][j] = letter letter = temp row += 1 if length(ssyt) < row push!(ssyt, UInt8[]) end end end return length.(ssyt) end function standardize_word(word::Vector{UInt8}) word_sorted = sort(word) map!(a -> UInt8(findfirst(b -> b == a, word_sorted)), word, word) increases = zeros(UInt8, length(word)) for i in eachindex(word) word[i] += increases[word[i]] increases[word[i]] += 1 end return word end function print_pair(pair) index1 = 1 index2 = 1 for i = 1:length(tableau_shape) for j = 1:tableau_shape[i] print("$(convert(Int, pair[1][index1])) ") index1 += 1 end for j = (tableau_shape[i] + 1):tableau_shape[1] print(" ") end print(" ") for j = 1:tableau_shape[i] print("$(convert(Int, pair[2][index2])) ") index2 += 1 end print("\n") end print("\n") end function print_all(pairs) for pair in pairs print_pair(pair) end end @time test_all_pairs(2)