The 3x3 Hexa Prime Square Puzzle

Introduction

We consider 3x3 squares of hexadecimal digits (from 0 to F) such as:

2 E 3    1 F 3
8 1 5    7 2 7
D D 5    B B 9


We define a 3x3 Hexa Prime Square (HPS3) as such a square for which all hexadecimal numbers read from left to right and from top to bottom are odd primes (i.e. primes greater than 2).

This is true for the left square and false for the right square:

2 E 3 --> 0x2E3 = 739       1 F 3 --> 0x1F3 = 499
8 1 5 --> 0x815 = 2069      7 2 7 --> 0x727 = 1831
D D 5 --> 0xDD5 = 3541      B B 9 --> 0xBB9 = 3001
| | |                       | | |
| | +---> 0x355 = 853       | | +---> 0x379 = 889 = 7 x 127
| +-----> 0xE1D = 3613      | +-----> 0xF2B = 3883 = 11 x 353
+-------> 0x28D = 653       +-------> 0x17B = 379


Goal

Given a list of 9 hexadecimal digits, your goal is to find an arrangement that forms a HPS3.

Example:

Input: 123558DDE
Possible output: 2E3815DD5 (a flattened representation of the above left example)


Input / Output

Input and output formats are flexible. The only requirement is that output digits are ordered from left to right and from top to bottom. Below are some possible options:

"2E3815DD5"
[ 0x2, 0xE, 0x3, 0x8, 0x1, 0x5, 0xD, 0xD, 0x5 ]
[ "2", "E", "3", "8", "1", "5", "D", "D", "5" ]
[
[ 0x2, 0xE, 0x3 ],
[ 0x8, 0x1, 0x5 ],
[ 0xD, 0xD, 0x5 ]
]
[ "2E3", "815", "DD5" ]
etc.


Using the same format for both input and output is not required.

Rules

• This is code-golf, so the shortest answer in bytes wins. Standard loopholes are forbidden.
• Your algorithm must be deterministic
• You can't just bogosort the array until it's valid, even in a deterministic way (by using a constant random seed).
• You may list all possible solutions for a given input, but this is neither required nor subject to a bonus.
• You're not required to support inputs that do not admit any solution. (It's perfectly fine if your code is looping forever or crashing in that case.)

Test cases

Input       Possible output
---------------------------
123558dde   2e3815dd5
1155578ab   a7b851551
03bddffff   ffd0dfb3f
35899beff   8f99e3bf5
15899bbdf   581bb9fd9
14667799f   6f1469779
13378bcdd   78d1cd33b
24577bbdd   7274bd5db
1118bbddd   11b18dbdd
223556cdd   623c25dd5
12557899a   8a5295971
113579bbd   5b3db7191

• "You can't just bogosort the array until it's valid, even in a deterministic way (by using a constant random seed)." What if I simply check all permutations of the input? At no more than 362880 permutations, this isn't even going to be particularly slow. Oct 15, 2016 at 19:46
• @MartinEnder Trying all permutations (only once each) is perfectly fine. Any random method that would potentially try several times the same permutation is prohibited. Oct 15, 2016 at 19:52
• It took me like 10 minutes just to understand the logic. To make a post about it... from now #1 on my ToNotDo list :) Oct 15, 2016 at 20:09

05AB1E, 23 21 bytes

Uses CP-1252 encoding.

œJvy3ôD€SøJìHDps2›*P—


Too slow for TIO.

Explanation

œJ                     # all permutations of input as strings
v                    # for each permutation
# EXAMPLE: 2E3815DD5
y3ô                 # split in pieces of 3
# EXAMPLE: ['2E3','815','DD5']
D                # duplicate
# EXAMPLE: ['2E3','815','DD5'], ['2E3','815','DD5']
€SøJ            # zip the copy to swap rows and columns
# EXAMPLE: ['2E3','815','DD5'], ['28D','E1D','355']
ì           # attach them to the same list
# EXAMPLE: ['2E3','815','DD5','28D','E1D','355']
H          # convert from base 16 to base 10
# EXAMPLE: [739, 2069, 3541, 653, 3613, 853]
D         # duplicate
# EXAMPLE: [739, 2069, 3541, 653, 3613, 853],[739, 2069, 3541, 653, 3613, 853]
p        # check first copy for primality
# EXAMPLE: [739, 2069, 3541, 653, 3613, 853],[1,1,1,1,1,1]
s2›     # check that each in second copy is larger than 2
# EXAMPLE: [1,1,1,1,1,1],[1,1,1,1,1,1]
*    # pairwise multiplication
# EXAMPLE: [1,1,1,1,1,1]
P   # product (1 if all were primes larger than 2, else 0)
# EXAMPLE: 1
—  # if 1, print y
# EXAMPLE: 2E3815DD5


Python 2, 212206197 194 bytes

Requires input enclosed in quotes, like "123558dde"

from itertools import*
k,p,P=3,4,[]
while k<5e3:P+=[k][:p%k];p*=k;k+=1
print[s for s in map(''.join,permutations(input()))if all(int(s[3*i:][:3],16)in P and int(s[i::3],16)in P for i in(0,1,2))]


Saving 9 and 3 bytes thanks to Jonathan Allan

Found new prime filter from xnor (modified the square away, since we dont want 2 as prime here), old prime filter is from Bob

• How about P+=[k][:p%k] - when p%k is not 0 the slice will yield [k], when it is 0 it will yield []. Oct 15, 2016 at 21:39
• Also from itertools import* is a neat golf trick that'll save a couple of bytes. Also forgo the efficiency and do k<5e3. Oct 15, 2016 at 21:43
• @JonathanAllan The import saved only 1 byte in this case, thought it helps only if stuff was used multiple times. Oh the efficiency, it is hard for me to drop it ;) That refactor with the slice for P is great. Oct 15, 2016 at 21:54
• Couple more bytes by printing a list of strings: print[s for s in map(''.join,permutations(input()))if all(int(s[3*i:][:3],16)in P and int(s[i::3],16)in P for i in(0,1,2))] Oct 15, 2016 at 22:19

Pyth, 23 21 bytes

f*F}R-Pd2iR16sCBc3T.p


Times out online, but finishes in 1.5 minutes on my laptop. Takes input in quotes.

Explanation

f*F}R-Pd2iR16sCBc3T.p
.pQ     permutations of input (implicit Q)
f                 T        filter each T:
c3             divide into rows
CB               make pair (rows, columns)
s                 join those lists
iR16                  interpret items as hex
}R                          check if each number d is in
Pd                           its prime factors
-  2                          with twos removed
*F                            product (also known as all)
implicitly print matches


Jelly, 34 30 bytes

i@€ØH’
s3µ;ZÇ€ḅ⁴µ>2aÆPẠ
Œ!ÇÐfḢ


(I should be able to use an nfind to just fetch the first match, 1# in place of ÐfḢ, for less bytes and more speed, but I'm seeing errors when I try. EDIT: wrote some changes to possibly implement this in Jelly.)

Brute force search of all permutations, filtered for the criteria, returning first match.
Way too slow for TtyItOnline. Local output examples:

C:\Jelly\jelly-master>python jelly -fu test.txt "123558DDE"
28DE1D355
C:\Jelly\jelly-master>python jelly -fu test.txt "1155578AB"
11B8A5557


How?

i@€ØH’ - Link 1, convert from hexadecimal string to integer list: string
ØH  - yield hexadecimal characters, "0123456789ABCDEF"
i@€    - index of €ach character of s in hex chars
’ - decrement (vectorises) (from 1 based jelly index to place value)

s3µ;ZÇ€ḅ⁴µ>2aÆPẠ - Link 2, check if a flattened square is "all prime": string
s3               - split into threes (rows)
;             - concatenate with
Z            - transpose (columns)
Ç€          - call last link (1) as a monad for €ach string in the list
-> list of integer lists
ḅ⁴        - convert from base 16 (vectorises) -> list of decimals
>2     - greater than 2
a    - and
ÆP  - isPrime? -> list of 1s and 0s
Ạ - all truthy?

Œ!      - all permutations of the string
Ðf   - filter keeping entries that evaluate to truthily for
Ḣ  - head - return first entry


J, 49 bytes

[:(#~([:*/@(2&<*1&p:)@(,&dfh|:)_3]\])"{)i.@!@#A.]


Brute-force search that tests all permutations and outputs all permutations that satisfy the conditions for the puzzle.

The performance is good enough to compute each test case in about 3 seconds.

Usage

   f =: [:(#~([:*/@(2&<*1&p:)@(,&dfh|:)_3]\])"{)i.@!@#A.]
f '123558dde'
28de1d355
28de1d355
28de1d355
28de1d355
2e3815dd5
2e3815dd5
2e3815dd5
2e3815dd5
timex 'f ''123558dde'''
3.68822


Explanation

[:(#~([:*/@(2&<*1&p:)@(,&dfh|:)_3]\])"{)i.@!@#A.]  Input: string S
#     Length of S
!@      Factorial
i.@        Range [0, len(S)!)
]  Get S
A.   Find the permutations of S by index
[:(                                    )           Operate on the permutations
(                              )"{              For each permutation P
]                   Get P
_3]\                    Get sublists of size 3
[:              (       )                        Operate on the sublists
|:                           Transpose
&dfh                             Convert both the transpose and
initial from hex to decimal
,                                 Join them
(        )                                  Operate on the decimals
1&p:                                     Test each for primality
2&<                                          Test each if greater than 2
*                                         Multiply them (AND)
*/@                                            Reduce using multiplication
#~                                                Filter the permutations by those
values and return


Mathematica, 115 bytes

#<>""&@@Select[Permutations@#,And@@(PrimeQ@#&&#>2&)/@(FromDigits[#<>"",16]&/@#~Join~Transpose@#)&[#~Partition~3]&]&


The input must be a list of characters (e.g. {"1", "2", "3", "5", "5", "8", "D", "D", "E"})

Ruby, 146 bytes

Anonymous function takes an array of nine integers, returns one solution as an array of nine integers. Relies on helper function g and a require.

require'prime'
g=->x,y,z{(2<s=x<<8|y<<4|z)&&s.prime?}
->r{r.permutation{|i|a=1
3.times{|j|a&&=g[*i[j*3,3]]&&g[i[j],i[j+3],i[j+6]]}
a&&(return i)}}


This 140-byte version prints all possible solutions, with the integers as decimals (not sure if that's allowed.)

require'prime'
g=->x,y,z{(2<s=x<<8|y<<4|z)&&s.prime?}
->r{r.permutation{|i|a=1
3.times{|j|a&&=g[*i[j*3,3]]&&g[i[j],i[j+3],i[j+6]]}
a&&p(i)}}


Ungolfed in test program

require'prime'
g=->x,y,z{(2<s=x<<8|y<<4|z)&&   #combine 3 input values, check if >2
s.prime?}                     #and check if prime
h=->r{
r.permutation{|i|             #iterate over all permutations
a=1                         #a=truthy
3.times{|j|
a&&=g[*i[j*3,3]]&&        #check rows (3 consecutive integers)
g[i[j],i[j+3],i[j+6]] #and columns
}
a&&(return i)               #if a still truthy, return solution.
}
}

#test cases: uncomment to run. solutions do not always match example solution from OP.
a=10;b=11;c=12;d=13;e=14;f=15
#p h[[1,2,3,5,5,8,d,d,e]]   #2e3815dd5
#p h[[1,1,5,5,5,7,8,a,b]]   #a7b851551
#p h[[0,3,b,d,d,f,f,f,f]]   #ffd0dfb3f
#p h[[3,5,8,9,9,b,e,f,f]]   #8f99e3bf5
#p h[[1,5,8,9,9,b,b,d,f]]   #581bb9fd9
#p h[[1,4,6,6,7,7,9,9,f]]   #6f1469779
#p h[[1,3,3,7,8,b,c,d,d]]   #78d1cd33b
#p h[[2,4,5,7,7,b,b,d,d]]   #7274bd5db
#p h[[1,1,1,8,b,b,d,d,d]]   #11b18dbdd
#p h[[2,2,3,5,5,6,c,d,d]]   #623c25dd5
#p h[[1,2,5,5,7,8,9,9,a]]   #8a5295971
#p h[[1,1,3,5,7,9,b,b,d]]   #5b3db7191


Groovy, 134 Bytes

Finds all possible solutions and returns them as an array, returns [] if there isn't a solution.

{it.toList().permutations().collect{it.collate(3).every{x=Integer.parseInt(it.join(),16);(2..x**0.5).every{x%it>0};}?it.join():0}-[0]}


Example input: 123558dde
Output:

[8235d5e1d, 2dd851e35, 815e352dd, 2e3d5518d, d2d3e5581, 853de5d21, 2dd3558e1, 2dd3e5581, 2e355d18d, 2518dd3e5, dd52e3185, e1d5d5283, 823ed1d55, 28d3e515d, 28d15de35, e351258dd, e5dd21853, 851d2d3e5, ed515d283, 2dd3e5185, 85de35d21, 5d1ed5823, 8dd355e21, d2d3e5815, d2d3e5851, 251e358dd, 2dde35851, 8235d5ed1, 2dde35815, e3585dd21, d2d8153e5, 85d5d12e3, 21dd85e35, d8521de35, 21d85d3e5, e1d5d5823, e35581d2d, 3e52dd581, dd52e3851, dd52e3815, 3e5281dd5, 8dd1253e5, 3e5815d2d, 3e55d128d, ed515d823, de5853d21, e218dd355, d8d1253e5, d8d251e35, d8d5512e3, 2dde35581, 3e52dd851, 5d1ed5283, e21dd5853, 3e5d2185d, 2513e58dd, 2dd3e5815, 2dd3e5851, e1d823d55, 3e52dd815, 581d2de35, e3515d28d, 2e318dd55, ed1823d55, dd52813e5, dd52e3581, 2e3515d8d, 28d3e55d1, 82355de1d, 82355ded1, 2dde35185, 3e5d8d125, 85d21de35, 281dd53e5, d21d85e35, d21e35d85, 2dd8e1355, 28d5d1e35, 85d15d2e3, 2813e5dd5, 3e5d2d185, 5d1e5d283, 3e5d2d581, e1dd55823, 3558e12dd, d55283e1d, 15dde5283, 5d128d3e5, 5518dd2e3, e5d28315d, 5d5823ed1, d2d1853e5, 823d55e1d, de521d853, d81d552e3, 5d5823e1d, 21ded5853, 823e1dd55, 3e52dd185, 5812dde35, d85e35d21, 3e585d21d, 8512dd3e5, 3e5251d8d, d2d8513e5, e1dd55283, 2e3d81d55, 853ed5d21, 2835d1ed5, 15d2e3d85, 5d1e3528d, 15dde5823, e35851d2d, 55d283e1d, 2e3551d8d, 8dd3e5125, 85d3e5d21, 8152e3dd5, 28de1d355, e1d55d823, 8dd3e5251, 5158dd2e3, e3521dd85, e1d35528d, 2e35d185d, 21de5d853, 823d55ed1, 5813e52dd, 8153e5d2d, e1d55d283, 21de3585d, d85d21e35, 5152e3d8d, 8513e5d2d, dd5e21853, 3552dd8e1, d552e318d, e5d2835d1, 2835d1e5d, 2835d1de5, 5d1e5d823, 8dde35125, 5d52e3d81, 3e5821dd5, 28d5d13e5, e35d21d85, dd51852e3, d2d185e35, 8dde35251, 8dd2513e5, e35d2d185, 2835d5e1d, 1852e3dd5, d85d213e5, 515d8d2e3, dd53e5821, d5518d2e3, 8dd5512e3, 283d55ed1, e5d5d1823, 28d355ed1, 3e58152dd, d812e3d55, e5d85321d, d8515d2e3, d2d581e35, 3e5581d2d, 85d21d3e5, 283d55e1d, dd53e5281, 851dd52e3, e35dd5821, 3e51258dd, dd58512e3, 28d355e1d, d8d2513e5, 125e358dd, e35dd5281, e35d2d851, d8d2e3515, e35d2d815, d21853ed5, d8d2e3551, 1852dd3e5, d21853e5d, 85dd213e5, d21853de5, 5d1283e5d, 823ed155d, 5d1283de5, ed521d853, 283e1dd55, d8d355e21, d8de35251, 5d1283ed5, e35d2d581, 3e528d15d, d55283ed1, 8512dde35, 3e5851d2d, 823ed15d5, 15d28de35, 15d3e528d, 2835d5ed1, 5d12e385d, 5d185d2e3, 5d5283e1d, 55d2e3d81, d2185de35, d55e1d283, ed582315d, 2dd8513e5, 853e5d21d, e352dd581, 851e352dd, 2dd5813e5, e352dd815, 853d21e5d, e352dd851, dd5821e35, ed155d283, 3e5d8d251, d8de35125, 2e3d8d551, 3e528d5d1, e5d21d853, dd5853e21, 853d21ed5, 85de3521d, e352518dd, 2e3d8d515, 125d8de35, e352dd185, 853d21de5, 8e13552dd, 1258dde35, 581e352dd, e21d8d355, ed155d823, e21853dd5, e3528d5d1, d2d851e35, 5512e38dd, 125d8d3e5, 2e3815dd5, 2513e5d8d, 21dde5853, 355d2d8e1, d55ed1283, 815dd52e3, 283ed1d55, 8152dd3e5, 281e35dd5, 28355de1d, 355e1d28d, ed182355d, 853dd5e21, e3528d15d, ed18235d5, 15d85d2e3, e351852dd, d55e1d823, 8e12dd355, 28355ded1, 2dd815e35, 581d2d3e5, d55ed1823, 15d283ed5, 821dd53e5, 2e35d518d, 5d5283ed1, 15d283e5d, 15d283de5, e1d28355d, e5d5d1283, 251d8d3e5, e1d2835d5, dd5281e35, ed15d5823, 21de35d85, dd58152e3, 2dd1853e5, 1258dd3e5, 5d5e1d283, 1253e58dd, 3e5d8521d, 18d2e3d55, e358152dd, 5512e3d8d, e35251d8d, 853ed521d, 3e5dd5281, 5813e5d2d, ed15d5283, 18d55d2e3, 281dd5e35, 8dde21355, 1852dde35, 3e585dd21, d85e3521d, 581e35d2d, ed1283d55, d812e35d5, 2e35518dd, 5d128de35, 8153e52dd, ed55d1823, e5d82315d, e35d85d21, d812e355d, d853e521d, 8dd2e3551, 2e3581dd5, 15de5d823, 8dd2e3515, 185e35d2d, 125e35d8d, 581dd52e3, 5d5e1d823, 5812e3dd5, 5152e38dd, 3558e1d2d, 85d3e521d, 5d1d852e3, 823de55d1, 2e3d8155d, d213e585d, ed55d1283, 2e3dd5581, 2e3dd5815, 15d823ed5, 2e3dd5851, d552e3d81, 55de1d823, e5d8235d1, 21d853de5, de528315d, d21e3585d, 2e3d815d5, 21d853e5d, ed58235d1, 2e3dd5185, 21d853ed5, de52835d1, 15d823e5d, e1d28d355, 355ed128d, 5812dd3e5, 815d2d3e5, 15d823de5, 823de515d, 55de1d283, ed5853d21, 2dd8153e5, 2e3d855d1, 185dd52e3, 8e1355d2d, 2e3d55d81, d2d3558e1, d8521d3e5, e5d15d823, ed52835d1, 35528de1d, dd5e35281, 3e58dd251, 5d5ed1283, dd58213e5, e355d128d, 3e58dd125, 3e5125d8d, 8213e5dd5, 355e218dd, 2e3d8515d, 35528ded1, e5d15d283, 853e21dd5, 8dd125e35, 15ded5823, e358dd251, 2e315dd85, 851d2de35, 551d8d2e3, d2d5813e5, ed528315d, 2e3185dd5, 185d2de35, 8152dde35, e35d2185d, 15de3528d, e358dd125, 251e35d8d, 5d5ed1823, 821dd5e35, 251d8de35, 8512e3dd5, 5d1823de5, d2d815e35, 3e51852dd, 5d1823e5d, 82315dde5, 3e5dd5821, 82315de5d, 5d518d2e3, 1853e5d2d, 8dd251e35, ed128355d, e1d8235d5, 82315ded5, d21ed5853, 823ed515d, 2e38dd551, ed135528d, 2e38dd515, 5d1823ed5, 2e318d55d, 15de5d283, e1d82355d, ed1d55823, 2e3851dd5, d8d5152e3, 283de515d, 823ed55d1, 3e55812dd, dd5e35821, 15ded5283, e21355d8d, 21d85de35, 8dd5152e3, e35125d8d, e355812dd, 5d52e318d, 8e1d2d355, d8155d2e3, 3e5d21d85, 21d3e5d85, ed12835d5, de585321d, d2185d3e5, 85dd21e35, 2e318d5d5, d213e5d85, 2e385d5d1, 55d823ed1, 15d2e385d, 3e521dd85, 283de55d1, ed1d55283, d8de21355, de5d21853, 55d823e1d, d852e315d, 355d8de21, d852e35d1, 8513e52dd, 185d2d3e5, 853e5dd21, 21d3e585d, 2dd581e35, de582315d, 823e5d15d, de515d283, 185e352dd, 28de3515d, 3e5d2d815, d21de5853, 283ed155d, 3e5d2d851, 55d283ed1, 3558dde21, 283ed15d5, d815d52e3, 28de355d1, 851e35d2d, de515d823, 5d1de5823, 55dd812e3, 283e5d15d, dd55812e3, 823e5d5d1, 15dd852e3, d2de35185, 1253e5d8d, 2e35d5d81, 1853e52dd, 2e35158dd, 21dd853e5, e35185d2d, 283e5d5d1, 18dd552e3, e35281dd5, 5d13e528d, e1d283d55, 2e385d15d, 28315de5d, 85d2e35d1, 28315dde5, 2dd185e35, e3585d21d, 283ed55d1, 5d1de5283, 28315ded5, d55823ed1, 5d12e3d85, e5d853d21, e35d8d125, e358512dd, d55823e1d, 815e35d2d, e35d8d251, 18d5d52e3, 28ded1355, e3521d85d, 283ed515d, 821e35dd5, d2d3e5185, 85321de5d, d2de35815, e35d8521d, d55d812e3, e213558dd, e35815d2d, d855d12e3, 15d28d3e5, d21e5d853, 85d2e315d, 3e58512dd, d2de35851, ed128d355, 28d15d3e5, 3e52518dd, 18d2e355d, de55d1823, d2de35581, 85321ded5, d2d8e1355, d853e5d21, 18d2e35d5, 2e35d1d85, 85321dde5, 3e5185d2d, 853de521d, 355e21d8d, 5d5d812e3, 55ded1823, de55d1283, 8235d1ed5, e35821dd5, 2518dde35, 8235d1de5, 8235d1e5d, 3e521d85d, d8d125e35, 2e315d85d, ed5d21853, 55ded1283, 815d2de35, 283e1d55d, 823e1d55d, 2e355dd81, 3e5d85d21, d8d3e5125, 3e515d28d, d21d853e5, 283e1d5d5, ed585321d, 823e1d5d5, 55d2e318d, d8d3e5251, 55d18d2e3, de58235d1]


Example input: 222222222 Output: []

If anyone wants me to comment it out, holler at a brother.

• Is it also testing the vertical primes? Oct 21, 2016 at 22:06
• Gaahhh fuck good point... I thought that was too easy... Fixing expect +70 bytes. Oct 22, 2016 at 0:57