related:
- with SMT (11 days ago, 47 comments) https://news.ycombinator.com/item?id=44259476
- with APL (10 days ago, 1 comment) https://news.ycombinator.com/item?id=44273489 and (8 days ago, 20 comments) https://news.ycombinator.com/item?id=44275900
- with MiniZinc (1 day ago, 0 comment) https://news.ycombinator.com/item?id=44353731
I set this as part of a Scala programming assignment for my second year undergraduate class at UNE (Australia) last term. However, during the working a square is not Queen | Eliminated but Set[Queen | NotQueen]
Largely so from a programming perspective it becomes a simplified version of Einstein's Riddle that I showed the class, doing in a similar way.
https://theintelligentbook.com/willscala/#/decks/einsteinPro...
Where at each step, you're just eliminating one or more possibilities from a cell that starts out containing all of them.
Queens has fewer rules to code, making it more amenable for students.
Solving Queens using J and brute force all permutations.
randomboard =: 3 : '? (y,y) $ y'
testsolution =: 4 : 0 NB. solution is a list of columns.
m =. x
n =. #x
solution =. y A. i. n
regions =. ({&m) <"1 (i. n) ,. solution
distinctregions =. n -: # ~. regions
adjacentregions =. 1 e. |2-/\solution
distinctregions * -. adjacentregions
)
findsolution =:3 : 0
board =: y
ns =. 1 i.~ (board & testsolution)"0 i. !#y
if. (ns = !#y) do. 'No solution found'
else.
echo 'Solution index is ', ": ns
ns A. i. #y end.
)
regions =: 4 : 0
({&x) <"1 (i. #x) ,. y
)
number2solution =: 4 : 0
y A. i. #x
)
writesolution =: 4 : 0
board =. x
sol =.y
m1 =. m
n1 =. #x
count =. 0
for_a. sol do.
m1 =. n1 (< count , a) } m1
count =. count + 1
end.
m1
)
writewithsolution=: 4 : 0
m1 =: x writesolution y
(":"1 x) ,. '|' ,. ":"1 m1
)
m =: randomboard 9
echo m writewithsolution findsolution mJust when I start thinking I am smart, someone drops this :) Haskell certainly looks graceful but is imposing! I feel pretty good if I can do functional stuff in Rust, but this is next level.
I believe I first encountered this problem while working through SICP. Was confused why it's called Linkedin queens, since this problem is a classical one in CS that definitely pre-dated the existence of Linkedin.
Does anyone know of any algorithms for generating these game boards ?
That will produce challenging boards ?
Awesome, I'm writing a "logical solver" just like this - I'll hopefully also have something to post here when I'm done.
I'm trying to use it during the generation process to evaluate the difficulty a basic heuristic I'm trying to work with is counting the number of times a particular colour is eliminated - the higher the count the harder the problem since it requires more iteration of the rules to solve. (A counter example to this would be a board with 1 colour covering everything except the cells a queen of the other colours needs to be placed on)
Also I'm trying to evaluate the efficacy of performing colour swaps but it's proving more challenging than I thought. The basic idea is you can swap the colours of neighbouring cells to line up multiple colours so there are less obvious "single cells" which contains the queen. The problem with this is it can introduce other solutions and it's difficult to tell whether a swap makes the puzzle harder or simpler to solve.
Does anyone know of a way to transpile monadic logic to quantum logic?
https://en.wikipedia.org/wiki/Monad_(functional_programming)
https://en.wikipedia.org/wiki/Quantum_programming
Conceptually they are similar, but the math is way over my head. I have trouble grokking each one actually.
But it's pretty easy for a beginner to start with a list of true/false (or true/null) monads as inputs to a pure function. Imagine the monads occupying nodes in a tree structure like JSON, or merging through NAND/NOR gates to reduce to fewer outputs.
From the outside, we can toggle the inputs to feed them examples like 0101 and see how that affects the outputs. This is basically how a spreadsheet works.
Then we can extend the monads to contain a set of values. Or even a range of values, like a floating point number from 0 to 1 or 0 to pi/2, etc, more like imaginary numbers for use in quantum programming (not sure if this is still a monad).
Functional programming can lazily evaluate the inputs and eliminate don't-cares to calculate all possible outputs within the limits of their computing power and time. Quantum gates can do something similar using the interference patterns between the inputs and logic somehow (the hand wavy part nobody seems to be able to explain).
Maybe this approach could be used as a bridge to eliminate the hand wavy part and give us something tractable in layman's terms. This might be considered quantized or simulated quantum programming.
-
Note: monads are similar to futures/promises and async/await in imperative programming, like using the imaginary number i in algebra. Except that we are generally only concerned with a handful of expected results, so often miss the failure modes by not stress-testing the logic with fuzzing and similar techniques. Which tends to make async code nondeterministic and brittle. So I'm also interested in transpiling async/nonblocking <-> sync/blocking and state machine <-> coroutine.
Clean, thoughtful, and practical. Curious, have you tried benchmarking your Haskell solver against an SMT solver (like Z3 or CVC5) to compare performance or expressiveness?
I'm curious how this would look using an exact covering algorithm. I'm also vaguely curious to see the various solutions that have been explored lately benchmarked. For that matter, a table that gives the stats on the code and execution would almost certainly lead to some amusing fights.
Kinda off topic but I had some much fun solving n queens in SQL: https://gist.github.com/seisvelas/952185983a625cd16e1ed4d901...
Hmm, an interesting pattern is that every queen is a knight's move away. I haven't thought about this problem since I started dabbling in chess but now looks like a simple pattern.
Solving Queens in J from a novice J programmer:
randomboard =: 3 : '? (y,y) $ y'
testsolution =: 4 : 0
m =. x
n =. #x
n -: # ~. ({&m) <"1 (i. n) ,. y A. (i. n)
)
findsolution =:3 : 0
board =: y
ns =. 1 i.~ (board & testsolution)"0 i. !#y
if. (ns = !#y) do. 'No solution found' else. ns A. i. #y end.
)
writesolution =: 4 : 0
board =. x
sol =.y
m1 =. m
n1 =. #x
count =. 0
for_a. sol do.
m1 =. n1 (< count , a) } m1
count =. count + 1
end.
m1
)
writewithsolution=: 4 : 0
m1 =: x writesolution y
(":"1 x) ,. '|' ,. ":"1 m1
)
m =: randomboard 9
echo m writewithsolution findsolution m
load 'queens.ijs'
5 2 8 0 3 3 0 5 2|9 2 8 0 3 3 0 5 2
8 2 3 6 7 7 4 5 1|8 9 3 6 7 7 4 5 1
6 1 5 8 3 5 8 7 6|6 1 5 9 3 5 8 7 6
8 4 8 8 7 5 1 1 1|8 4 8 8 9 5 1 1 1
2 6 7 6 5 4 7 3 1|2 6 7 6 5 4 7 9 1
6 8 1 4 1 4 3 2 7|6 8 1 4 1 9 3 2 7
6 0 5 6 5 5 8 5 0|6 0 5 6 5 5 8 5 9
1 7 5 5 8 1 1 0 1|1 7 5 5 8 1 9 0 1
8 4 6 2 2 4 6 4 1|8 4 9 2 2 4 6 4 1how would you encode a constraint system where the generator must yield exactly one solution and that solution remains unique under all transformations in the problem’s symmetry group, without relying on post-solution filtering or external isomorphism checks?
So you're the co-worker playing Queens according to my LinkedIn notifications!
Anything similar with Zip? That's the one I enjoy in the mornings.
A simpler approach uses mixed-integer LP (MIP) and a mathematical programming DSL like julia/JuMP or python/pyomo.
Here's a trivial and fast MIP solution using python/pulp, which would be essentially the same in any mathematical programming DSL:
from collections import defaultdict
import pulp
board = [
["P", "P", "P", "P", "P", "P", "P", "P", "P"],
["P", "P", "R", "S", "S", "S", "L", "L", "L"],
["P", "R", "R", "W", "S", "L", "L", "L", "L"],
["P", "R", "W", "W", "S", "O", "O", "L", "L"],
["P", "R", "W", "Y", "Y", "Y", "O", "O", "L"],
["P", "R", "W", "W", "Y", "O", "O", "L", "L"],
["P", "R", "R", "W", "Y", "O", "B", "L", "L"],
["P", "R", "R", "G", "G", "G", "B", "B", "L"],
["P", "P", "R", "R", "G", "B", "B", "L", "L"],
]
# group by color for color constraint
def board_to_dict(board):
nr = len(board)
res = defaultdict(list)
for i, row in enumerate(board):
if len(row) != nr:
raise ValueError("Input must be a square matrix")
for j, color in enumerate(row):
res[color].append((i, j))
return res
color_regions = board_to_dict(board)
N = len(color_regions)
prob = pulp.LpProblem("Colored_N_Queens", pulp.LpMinimize)
x = [[pulp.LpVariable(f"x_{i}_{j}", cat="Binary") for j in range(N)] for i in range(N)]
# Row constraints
for i in range(N):
prob += pulp.lpSum(x[i][j] for j in range(N)) == 1
# Column constraints
for j in range(N):
prob += pulp.lpSum(x[i][j] for i in range(N)) == 1
# Color region constraints
for positions in color_regions.values():
prob += pulp.lpSum(x[i][j] for (i, j) in positions) == 1
# No diagonal adjacency
for i in range(N):
for j in range(N):
for di, dj in [(-1, -1), (-1, 1), (1, -1), (1, 1)]:
ni, nj = i + di, j + dj
if 0 <= ni < N and 0 <= nj < N:
prob += x[i][j] + x[ni][nj] <= 1
# Trivial objective
prob += 0
res = prob.solve()
print(f"Solver status: {pulp.LpStatus[prob.status]}")
if pulp.LpStatus[prob.status] == "Optimal":
for i in range(N):
row = ""
for j in range(N):
row += ("#" if pulp.value(x[i][j]) > 0.5 else " ") + board[i][j] + " "
print(row)
#P P P P P P P P P
P P R S S #S L L L
P R R W S L L L #L
P R #W W S O O L L
P R W Y Y Y O #O L
P R W W #Y O O L L
P #R R W Y O B L L
P R R #G G G B B L
P P R R G B #B L L
Reminds me of this classic: https://aphyr.com/posts/342-typing-the-technical-interview