Misc.hs

module Misc (queens, knightsTour, knightsTo, closedKnights) where

import qualified Control.Monad as M
import qualified Data.Ix as Ix
import qualified Data.List as L
import qualified Data.Maybe as Mb
import qualified Data.Set as Set

{-
Problem 90: (**) Eight queens problem.

The objective is to place eight queens on a chessboard so that
no two queens are attacking each other; i.e., no two queens
are in the same row, the same column, or on the same diagonal.

ANSWER:
We start from the nth column and move left. Since calculating
the we length of a list is a linear time opertation in Haskell,
also keep track of the number of queens placed so far. The
rows are index by the columns, so [1, 3] means two queens
placed at (r: 1, c: 7) and (r: 3: c: 8).

At the ith iteration, where 0 <= i < n, we are trying to find a row
for the column n-i. The columns n-i+1 through n have been filled,
and the corresponding rows are available in the list 'rows'.

We observe that a (row, col) is under attack from one of the queens
if a queen is present in the same row (in the list rows), or if
(row, col) is on the same diagonal or anti-diagonal. If row - queen_row
is equal to col - queen_col, then (row, col) is under attack diagonally.
-}
queens :: Int -> [[Int]]
queens n = go 0 []
  where
    go :: Int -> [Int] -> [[Int]]
    go numPlaced rows
      | numPlaced == n = return rows
      | otherwise = do
          row <- [1 .. n]
          _ <- M.guard (canPlace numPlaced rows row)
          go (numPlaced + 1) (row : rows)

    canPlace numPlaced rows row
      | row `elem` rows = False
      | otherwise = all (\(r, c) -> abs (row - r) /= abs (col - c)) $ zip rows cols
      where
        col = n - numPlaced
        cols = [col + 1 .. n]

-- https://wiki.haskell.org/The_Knights_Tour
knightsTour :: Int -> ((Int, Int) -> Int -> Bool) -> (Int, Int) -> [(Int, Int)]
knightsTour n isDone = go Set.empty
  where
    go visited pos
      | isDone pos (Set.size visited) = [pos]
      | otherwise = Mb.maybe [] (pos :) ys
      where
        xs = filter (`Set.notMember` visited) $ moves pos
        -- Warnsdorff's rule - choose the next position
        -- with the fewest onward moves.
        nexts = L.sortOn (length . moves) xs
        ys = L.find (not . null) $ map (go (Set.insert pos visited)) nexts
        moves (i, j) =
          [ (i', j')
            | (dx, dy) <- [(1, 2), (2, 1)],
              i' <- [i + dx, i - dx],
              j' <- [j + dy, j - dy],
              Ix.inRange ((1, 1), (n, n)) (i', j')
          ]

{-
Problem 91: (**) Knight's tour.

How can a knight jump on an NxN chessboard in such a way
that it visits every square exactly once?

There are two variants of this problem:

1. find a tour ending at a particular square
2. find a circular tour, ending a knight's jump from the start
   (clearly it doesn't matter where you start, so choose (1,1))
-}
knightsTo :: Int -> (Int, Int) -> [(Int, Int)]
-- const :: a -> b -> a
-- When const f, where f is a boolean function a -> Bool ==> b -> a -> Bool
-- which means the boolean function will operate on the 2nd argument.
knightsTo n = reverse . knightsTour n (const (n * n - 1 ==))

closedKnights :: Int -> [(Int, Int)]
closedKnights n = knightsTour n isDone (1, 1)
  where
    isDone pos k = pos `elem` [(2, 3), (3, 2)] && k == n * n - 1

{-
Problem 92: (***) Von Koch's conjecture.

It has been conjectured that if graph G is a tree with n vertices, and thus n-1 edges,
then there is a graceful labeling of the tree. This means that there is a way to label
each vertex with an integer from 1 to n such that there is an edge whose difference in
vertex labels is between 1 and n-1.
There is no known counterexample, but neither is it proven that this is true for all trees.

Example:
n=7

┌──┐  6                 2    ┌──┐  1   ┌──┐
│1 ├────────┐       ┌────────┤5 ├──────┤4 │
└──┘        │       │        └──┘      └──┘
          ┌─┴┐  4  ┌┴─┐
          │ 7├─────┤3 │
          └─┬┘     └┬─┘
┌──┐  5     │       │   3    ┌──┐
│2 ├────────┘       └────────┤6 │
└──┘                         └──┘

ANSWER: TODO.
-}

{-
Problem 93: (***) An arithmetic puzzle.

Given a list of positive integer numbers, find a correct way of inserting
the arithmetic signs such that the result is a correct equation.

For example, with the list of numbers [2,3,5,7,11], we can form the equations
2-3+5+7=11 or 2=(3*5+7)/11.

The arithmetic signs to insert are:

+ : addition
- : subtraction
\* : multiplication
/ : division
= : equality
(, ) : parentheses

Arithmetic operations are only binary, e.g., -4 should not be included.
Division should be interpreted as operating on rationals, e.g., 3/5=6/10
but 3/5≠0, and division by zero should be avoided.
Parentheses should be inserted only when the default precedence rules
need to be overridden. Equality should be inserted exactly once.

ANSWER: TODO.
-}

{-
Problem 94: (***) Generate K-regular simple graphs with N nodes.

In a k-regular graph, all vertexes have a degree of k, i.e.,
the number of edges incident in each vertex is k.

How many non-isomorphic 3-regular graphs with 6 vertexes are there?

ANSWER: TODO.
-}