- 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

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.

   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 m

That will produce challenging boards ?

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.

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.

   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 1

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