Nhf1

NHF1.livemd

@DeNeSSS

Elixir_projekt_NHF

Share to X

Share to Bluesky

More notebooks

Nhf1

Mix.install([
  {:benchee, "~> 1.3"},
  {:benchee_html, "~> 1.0"},
  {:kino, "~> 0.12"} # ha még nincs
])

MRV + LVC

Backtracking + Forward Checking + MRV + LCV

MRV (Minimum Remaining Values): mindig azt a cellát választod, ahol a legkevesebb érték engedett még → minimális ágmélység.
LCV (Least Constraining Value): ha több érték közül választhatsz, próbáld azt, ami a legkevesebb más cellát zárja ki.
Komplexitás: Exponenciális worst-case, de gyakorlatilag ~O(N²) kis–közepes mátrixokra. Előny: Sokkal kevesebb visszalépés → 10–100× gyorsabb lehet.

Adat szerkezetek:

allowed values: map(key=y, value = map(key=x, value = {[allowed values], lenght}))
csak ezt a kell tárolni és leszűkíteni, hogy mindehol egy érték legyen

Segéd függvények:

[ ] convert_solution(result): a megoldást a megfelelő formátumúra konvertálja
Return: [megoldás[sor[oszlop]]]
[x] prepare_allowed_values(size, cycle, constraints): Megépíti az adatszerkezetet, és constraintok megkötései szerint szűkíti azt
Return: map(y, map(x, {[values], lenght}))
[x] forward_checking(allowed_values, size, {{y, x}, value}): Megnézi és kiveszi a már nem lehetséges értékeket a mátrixból
Return: allowed_values
[x] find_MRV(allowed_values): Megkeresi a legkevesebb, nem 1 lehetséges értékkel rendelkező mezők cordinátáját.
Return: list({y, x})
[ ] find_LCV(mrv, allowed_values): Megnézi, hogy melyik MVR mező és érték zárja ki a legkevesebb lehetséges értéket
Return: {y, x, value}

defmodule Auxiliary_func do
  def prepare_allowed_values(size, cycle, constraints) do
    values = for v <- 1..cycle, do: v 
    allowed_values = 
      for y <- 1..size, into: %{} do
        inner_map =
          for x <- 1..size, into: %{} do
            {x, {values, cycle}}
          end
        {y, inner_map}
      end

    Enum.reduce(constraints, allowed_values, fn {{y, x}, v}, acc ->
      forward_checking(acc, size, {{y, x}, v})
    end)
  end

  def forward_checking(allowed_values, size, {{y, x}, value}) do
    allowed_values = Enum.reduce(1..size, allowed_values, fn index, acc ->
      {values, lenght} = allowed_values[y][index]
      acc =
        if lenght != 1 and value in values do
          new_values = List.delete(values, value)
          Map.put(acc, y, Map.put(acc[y], index, {new_values, lenght-1}))
        else
          acc
        end
    
      {values, lenght} = allowed_values[index][x]
      acc =
        if lenght != 1 and value in values do
          new_values = List.delete(values, value)
          Map.put(acc, index, Map.put(acc[index], x, {new_values, lenght-1}))
        else
          acc
        end
    
      acc
    end)

    Map.put(allowed_values, y, Map.put(allowed_values[y], x, {[value], 1}))
  end

  def find_MRV(allowed_values, size, cycle) do
    Enum.reduce(1..size, {[], cycle}, fn y, acc ->
      Enum.reduce(1..size, acc, fn x, {vs, lenght} = acc2 ->
        {values, len} = allowed_values[y][x]
        if len < 2 do acc2
        else
          cond do
            len == lenght -> {[{y, x} | vs], lenght}
            len < lenght -> {[{y, x}], len}
            len > lenght -> acc2
          end
        end
      end)
    end)
  end

  def findLCV(mrv, allowed_values) do
    
  end

end

size = 3
cycle = 2
matrix = Auxiliary_func.prepare_allowed_values(size, cycle, [{{1, 1,}, 1}, {{3, 3}, 1}])
IO.inspect(matrix)
IO.inspect(Auxiliary_func.find_MRV(matrix, size, cycle))
# new_matrix = Auxiliary_func.forward_checking(matrix, size, {{1, 2}, 2})
# IO.inspect(new_matrix)

defmodule Auxiliary_func_v2 do
  def map_to_nested_list(map) do
    # Határozzuk meg a mátrix méretét a legnagyobb koordináta alapján
    max_y = map |> Map.keys() |> Enum.map(&amp;elem(&amp;1, 0)) |> Enum.max()
    max_x = map |> Map.keys() |> Enum.map(&amp;elem(&amp;1, 1)) |> Enum.max()

    matrix =
    for y <- 1..max_y do
      for x <- 1..max_x do
        case Map.get(map, {y, x}) do
          {values, _} -> MapSet.to_list(values)
          nil -> nil  # ha hiányzik az elem, tehetsz ide 0-t vagy -1-et is
        end
      end
    end

    Enum.each(matrix, fn row ->
      row
      |> IO.inspect()
    end)
  end
 
  def prepare_allowed_values(size, cycle, constraints) do
    values = MapSet.new(for v <- 1..cycle, do: v)
    allowed_values = 
      for y <- 1..size, x <- 1..size, into: %{} do
        {{x, y}, {values, size}}
      end

    Enum.reduce(constraints, allowed_values, fn {{y, x}, v}, acc ->
      forward_checking(acc, size, {{y, x}, v})
    end)
  end

  def forward_checking(allowed_values, size, {{y, x}, value}) do
    allowed_values = Enum.reduce(1..size, allowed_values, fn index, acc ->
      {values, lenght} = allowed_values[{y, index}]
      acc =
        if lenght != 1 and value in values do
          new_values = MapSet.delete(values, value)
          Map.put(acc, {y, index}, {new_values, lenght-1})
        else
          acc
        end
    
      {values, lenght} = allowed_values[{index, x}]
      acc =
        if lenght != 1 and value in values do
          new_values = MapSet.delete(values, value)
          Map.put(acc, {index, x}, {new_values, lenght-1})
        else
          acc
        end
    
      acc
    end)

    Map.put(allowed_values, {y, x}, {MapSet.new([value]), 1})
  end

  def find_MRV(allowed_values, size, cycle) do
    Enum.reduce(1..size, {[], cycle}, fn y, acc ->
      Enum.reduce(1..size, acc, fn x, {vs, lenght} = acc2 ->
        {_values, len} = allowed_values[{y, x}]
        if len < 2 do acc2
        else
          cond do
            len == lenght -> {[{y, x} | vs], lenght}
            len < lenght -> {[{y, x}], len}
            len > lenght -> acc2
          end
        end
      end)
    end)
  end

  # def findLCV(mrv, allowed_values) do
    
  # end

end

size = 3
cycle = 2
matrix = Auxiliary_func_v2.prepare_allowed_values(size, cycle, [{{1, 1,}, 1}, {{3, 3}, 1}])
Auxiliary_func_v2.map_to_nested_list(matrix)
# IO.inspect(Auxiliary_func_v2.find_MRV(matrix, size, cycle))
# new_matrix = Auxiliary_func.forward_checking(matrix, size, {{1, 2}, 2})
# IO.inspect(new_matrix)

Brute force V1

defmodule Helper do
  def decode_from_spiral(list, size) do
    res = 
      for _ <- 1..size do
        for _ <- 1..size do
          -1
        end
      end
    iterate(list, size, size, 1, 0, 0, 1, res)
  end 

  defp iterate([], _cycle_size, _cycle, _dx, _dy, _x, _y, res), do: res
  defp iterate(list, cycle_size, 0, dx, dy, x, y, res) do 
    cond do 
      dx == 1  and dy == 0  ->
        iterate(list, cycle_size-1, cycle_size-1,  0,  1, x, y, res)
      dx == 0  and dy == 1  ->
        iterate(list, cycle_size, cycle_size, -1,  0, x, y, res)
      dx == -1 and dy == 0  ->
        iterate(list, cycle_size-1, cycle_size-1,  0, -1, x, y, res)
      dx == 0  and dy == -1 ->
        iterate(list, cycle_size, cycle_size,  1,  0, x, y, res)
      true -> 
        IO.inspect({"Hiba", dx, dy})
    end
  end
  defp iterate([value | list], cycle_size, cycle, dx, dy, x, y, res) do
    new_x = x + dx
    new_y = y + dy

    # IO.inspect({new_y, new_x})
    line = Enum.at(res, new_y-1)
    new_line = List.replace_at(line, new_x-1, value)
    new_res = List.replace_at(res, new_y-1, new_line)
    iterate(list, cycle_size, cycle-1, dx, dy, new_x, new_y, new_res)
  end
  
  def next(size, y, x) when x+1 >= y and  size+1 > x + y, do: {y, x+1}
  def next(size, y, x) when y >= x  and x + y > size+1,   do: {y, x-1}
  def next(size, y, x) when x > size/2,                   do: {y+1, x}
  def next(size, y, x) when size/2 >= x,                  do: {y-1, x} 

  def test_next(0, _size, _y, _x), do: nil
  def test_next(index, size, y, x) do
    IO.inspect({y, x})
    {new_y, new_x} = next(size, y, x)
    test_next(index-1, size, new_y, new_x)
  end
  
end

# IO.inspect(Helper.decode_from_spiral([1, 2, 3, 6, 9, 8, 7, 4, 5], 3), charlists: :as_lists)
# IO.inspect(Helper.next(5, 1, 5))
# Helper.test_next(6*6, 6, 1, 1)

defmodule Nhf1_brute_force do
@moduledoc """
Számtekercs
@author "Gödölle Dénes "
@date   "2025-10-14"
...
"""

  @type size()  :: integer() # tábla mérete (0 < n)
  @type cycle() :: integer() # ciklus hossza (0 < m <= n)
  @type value() :: integer() # mező értéke (0 < v <= m)

  @type row()   :: integer()       # sor száma (1-től n-ig)
  @type col()   :: integer()       # oszlop száma (1-től n-ig)
  @type field() :: {row(), col()}  # mező koordinátái

  @type field_value() :: {field(), value()}                 # mező és értéke
  @type puzzle_desc() :: {size(), cycle(), [field_value()]} # feladvány

  @type retval()    :: integer()    # eredménymező értéke (0 <= rv <= m)
  @type solution()  :: [[retval()]] # egy megoldás
  @type solutions() :: [solution()] # összes megoldás

  @spec helix(sd::puzzle_desc()) :: ss::solutions()
  # ss az sd feladványleíróval megadott feladvány összes megoldásának listája
  def helix({size, cycle, field_values}) do
    zero_counter = size * size - size * cycle
    solver(
      {size, cycle, field_values}, {1, 1}, {%{}, %{}},
      {size * size, zero_counter, 1}, [], []
    )
  end

  def solver({size, _cycle, _field_values}, {_y, _x}, {_v_constraints, _h_constraints},
    {0, _zero_counter, value}, result, results) do
    
    if value == 1 do
      res = Helper.decode_from_spiral(Enum.reverse(result), size)
      [res | results]
    else 
      results
    end
    
  end
    
  def solver({size, cycle, field_values}, {y, x}, {v_constraints, h_constraints},
    {index, zero_counter, value}, result, results) do

    # Van-e az adott sorban vagy oszlopban már a value száma
    allow_constraints = value not in Map.get(v_constraints, y, []) 
      and value not in Map.get(h_constraints, x, [])
        
    # Van-e már előre beírt érték a cordinátán
    fix_value = case Enum.find(field_values, fn {{fy, fx}, _} -> fy == y and fx == x end) do
      nil -> nil
      {{_, _}, v} -> v
    end

    # Lehet-e nullát beírni
    allow_zero = (fix_value == nil or fix_value == 0) and zero_counter > 0
    allow_value = allow_constraints and (fix_value == nil or fix_value == value)
    
    new_value = if value == cycle do 1 else value+1 end
    {new_y, new_x} = Helper.next(size, y, x)
    
    new_results = 
      if allow_value do
        new_v_constraints = Map.put(v_constraints, y, [value | Map.get(v_constraints, y, [])])
        new_h_constraints = Map.put(h_constraints, x, [value | Map.get(h_constraints, x, [])])    
        solver({size, cycle, field_values}, {new_y, new_x}, {new_v_constraints, new_h_constraints},
          {index-1, zero_counter, new_value}, [value | result], results) 
      else results end

    if allow_zero do
        solver({size, cycle, field_values}, {new_y, new_x}, {v_constraints, h_constraints},
          {index-1, zero_counter-1, value}, [0 | result], new_results)
    else new_results end
    
  end

  
end

# IO.inspect(Nhf1_brute_force.prepare_list(4, [{{1, 4}, 2}]))
IO.inspect(Nhf1_brute_force.helix({4, 2, [{{1, 1}, 1}, {{1, 4}, 2}]}))

Brute force V2

defmodule Nhf1_brute_force_v2 do
@moduledoc """
Számtekercs
@author "Gödölle Dénes "
@date   "2025-10-14"
...
"""

  @type size()  :: integer() # tábla mérete (0 < n)
  @type cycle() :: integer() # ciklus hossza (0 < m <= n)
  @type value() :: integer() # mező értéke (0 < v <= m)

  @type row()   :: integer()       # sor száma (1-től n-ig)
  @type col()   :: integer()       # oszlop száma (1-től n-ig)
  @type field() :: {row(), col()}  # mező koordinátái

  @type field_value() :: {field(), value()}                 # mező és értéke
  @type puzzle_desc() :: {size(), cycle(), [field_value()]} # feladvány

  @type retval()    :: integer()    # eredménymező értéke (0 <= rv <= m)
  @type solution()  :: [[retval()]] # egy megoldás
  @type solutions() :: [solution()] # összes megoldás

  @spec helix(sd::puzzle_desc()) :: ss::solutions()
  # ss az sd feladványleíróval megadott feladvány összes megoldásának listája
  def helix({size, cycle, field_values}) do
    zero_counter = size * size - size * cycle
    solver(
      {size, cycle, field_values}, {1, 1}, {%{}, %{}},
      {size * size, zero_counter, 1}, [], []
    )
  end

  def solver({size, _cycle, _field_values}, {_y, _x}, {_v_constraints, _h_constraints},
    {0, _zero_counter, value}, result, results) do
    
    if value == 1 do
      res = Helper.decode_from_spiral(Enum.reverse(result), size)
      [res | results]
    else 
      results
    end
    
  end
    
  def solver({size, cycle, field_values}, {y, x}, {v_constraints, h_constraints},
    {index, zero_counter, value}, result, results) do

    # Van-e az adott sorban vagy oszlopban már a value száma
    allow_constraints = 
      value not in elem(Map.get(v_constraints, y, {[], 0}), 0) and 
      value not in elem(Map.get(h_constraints, x, {[], 0}), 0)
        
    # Van-e már előre beírt érték a cordinátán
    fix_value = case Enum.find(field_values, fn {{fy, fx}, _} -> fy == y and fx == x end) do
      nil -> nil
      {{_, _}, v} -> v
    end

    new_value = if value == cycle do 1 else value+1 end
    {new_y, new_x} = Helper.next(size, y, x)

    {v_values, v_zeros} = Map.get(v_constraints, y, {[], size-cycle})
    {h_values, h_zeros} = Map.get(h_constraints, x, {[], size-cycle})
    
    # Lehet-e nullát beírni
    allow_value = allow_constraints and (fix_value == nil or fix_value == value)
    allow_zero = (fix_value == nil or fix_value == 0) and zero_counter > 0 and
      v_zeros > 0 and h_zeros > 0

    new_results = 
      if allow_value do
        new_v_constraints = Map.put(v_constraints, y, {[value | v_values], v_zeros})
        new_h_constraints = Map.put(h_constraints, x, {[value | h_values], h_zeros})    
        solver({size, cycle, field_values}, {new_y, new_x}, {new_v_constraints, new_h_constraints},
          {index-1, zero_counter, new_value}, [value | result], results) 
      else results end

    if allow_zero do
      new_v_constraints = Map.put(v_constraints, y, {v_values, v_zeros-1})
      new_h_constraints = Map.put(h_constraints, x, {h_values, h_zeros-1}) 
      solver({size, cycle, field_values}, {new_y, new_x}, {new_v_constraints, new_h_constraints},
        {index-1, zero_counter-1, value}, [0 | result], new_results)
    else new_results end
    
  end

  
end

res1 = Nhf1_brute_force.helix({4, 2, [{{1, 1}, 1}, {{1, 4}, 2}]})
res2 = Nhf1_brute_force_v2.helix({4, 2, [{{1, 1}, 1}, {{1, 4}, 2}]})
IO.inspect({res1, res2})
IO.inspect(res1 == res2)

Brute force V3 - MapSet - worse

defmodule Nhf1_brute_force_v3 do
@moduledoc """
Számtekercs
@author "Gödölle Dénes "
@date   "2025-10-14"
...
"""

  @type size()  :: integer() # tábla mérete (0 < n)
  @type cycle() :: integer() # ciklus hossza (0 < m <= n)
  @type value() :: integer() # mező értéke (0 < v <= m)

  @type row()   :: integer()       # sor száma (1-től n-ig)
  @type col()   :: integer()       # oszlop száma (1-től n-ig)
  @type field() :: {row(), col()}  # mező koordinátái

  @type field_value() :: {field(), value()}                 # mező és értéke
  @type puzzle_desc() :: {size(), cycle(), [field_value()]} # feladvány

  @type retval()    :: integer()    # eredménymező értéke (0 <= rv <= m)
  @type solution()  :: [[retval()]] # egy megoldás
  @type solutions() :: [solution()] # összes megoldás

  @spec helix(sd::puzzle_desc()) :: ss::solutions()
  # ss az sd feladványleíróval megadott feladvány összes megoldásának listája
  def helix({size, cycle, field_values}) do
    zero_counter = size * size - size * cycle
    solver(
      {size, cycle, field_values}, {1, 1}, {%{}, %{}},
      {size * size, zero_counter, 1}, [], []
    )
  end

  def solver({size, _cycle, _field_values}, {_y, _x}, {_v_constraints, _h_constraints},
    {0, _zero_counter, value}, result, results) do
    
    if value == 1 do
      res = Helper.decode_from_spiral(Enum.reverse(result), size)
      [res | results]
    else 
      results
    end
    
  end
    
  def solver({size, cycle, field_values}, {y, x}, {v_constraints, h_constraints},
    {index, zero_counter, value}, result, results) do

    # Van-e az adott sorban vagy oszlopban már a value száma
    allow_constraints = 
      not MapSet.member?(elem(Map.get(v_constraints, y, {MapSet.new(), 0}), 0), value) and 
      not MapSet.member?(elem(Map.get(h_constraints, x, {MapSet.new(), 0}), 0), value)
        
    # Van-e már előre beírt érték a cordinátán
    fix_value = case Enum.find(field_values, fn {{fy, fx}, _} -> fy == y and fx == x end) do
      nil -> nil
      {{_, _}, v} -> v
    end

    new_value = if value == cycle do 1 else value+1 end
    {new_y, new_x} = Helper.next(size, y, x)

    {v_values, v_zeros} = Map.get(v_constraints, y, {MapSet.new(), size-cycle})
    {h_values, h_zeros} = Map.get(h_constraints, x, {MapSet.new(), size-cycle})
    
    # Lehet-e nullát beírni
    allow_value = allow_constraints and (fix_value == nil or fix_value == value)
    allow_zero = (fix_value == nil or fix_value == 0) and zero_counter > 0
      and v_zeros > 0 and h_zeros > 0
    
    new_results = 
      if allow_value do
        new_v_constraints = Map.put(v_constraints, y, {MapSet.put(v_values, value), v_zeros})
        new_h_constraints = Map.put(h_constraints, x, {MapSet.put(h_values, value), h_zeros})    
        solver({size, cycle, field_values}, {new_y, new_x}, {new_v_constraints, new_h_constraints},
          {index-1, zero_counter, new_value}, [value | result], results) 
      else results end

    if allow_zero do
      new_v_constraints = Map.put(v_constraints, y, {v_values, v_zeros-1})
      new_h_constraints = Map.put(h_constraints, x, {h_values, h_zeros-1}) 
      solver({size, cycle, field_values}, {new_y, new_x}, {new_v_constraints, new_h_constraints},
        {index-1, zero_counter-1, value}, [0 | result], new_results)
    else new_results end
    
  end

  
end

res1 = Nhf1_brute_force.helix({4, 2, [{{1, 1}, 1}, {{1, 4}, 2}]})
res2 = Nhf1_brute_force_v3.helix({4, 2, [{{1, 1}, 1}, {{1, 4}, 2}]})
IO.inspect(res1 == res2)

Brute force V4 - BitSet

defmodule BitSet do
  import Bitwise

  def member?(set, number) do
    ((set >>> (number - 1)) &amp;&amp;&amp; 1) == 1
  end
  
  def put(set, number) do
    set ||| (1 <<< (number - 1))
  end

  def remove(set, number) do
    set &amp;&amp;&amp; bnot(1 <<< (number - 1))
  end
end

bin = 0
bin = BitSet.put(bin, 3)
bin = BitSet.put(bin, 4)
# bin = BitSet.remove(bin, 3)

IO.inspect(BitSet.member?(bin, 3))
IO.inspect(BitSet.member?(bin, 4))

defmodule Nhf1_brute_force_v4 do
@moduledoc """
Számtekercs
@author "Gödölle Dénes "
@date   "2025-10-14"
...
"""

  @type size()  :: integer() # tábla mérete (0 < n)
  @type cycle() :: integer() # ciklus hossza (0 < m <= n)
  @type value() :: integer() # mező értéke (0 < v <= m)

  @type row()   :: integer()       # sor száma (1-től n-ig)
  @type col()   :: integer()       # oszlop száma (1-től n-ig)
  @type field() :: {row(), col()}  # mező koordinátái

  @type field_value() :: {field(), value()}                 # mező és értéke
  @type puzzle_desc() :: {size(), cycle(), [field_value()]} # feladvány

  @type retval()    :: integer()    # eredménymező értéke (0 <= rv <= m)
  @type solution()  :: [[retval()]] # egy megoldás
  @type solutions() :: [solution()] # összes megoldás

  @spec helix(sd::puzzle_desc()) :: ss::solutions()
  # ss az sd feladványleíróval megadott feladvány összes megoldásának listája
  def helix({size, cycle, field_values}) do
    zero_counter = size * size - size * cycle
    solver(
      {size, cycle, field_values}, {1, 1}, {%{}, %{}},
      {size * size, zero_counter, 1}, [], []
    )
  end

  def solver({size, _cycle, _field_values}, {_y, _x}, {_v_constraints, _h_constraints},
    {0, _zero_counter, value}, result, results) do
    
    if value == 1 do
      res = Helper.decode_from_spiral(Enum.reverse(result), size)
      [res | results]
    else 
      results
    end
    
  end
    
  def solver({size, cycle, field_values}, {y, x}, {v_constraints, h_constraints},
    {index, zero_counter, value}, result, results) do

    # Van-e az adott sorban vagy oszlopban már a value száma
    allow_constraints = 
      not BitSet.member?(elem(Map.get(v_constraints, y, {0, 0}), 0), value) and 
      not BitSet.member?(elem(Map.get(h_constraints, x, {0, 0}), 0), value)
        
    # Van-e már előre beírt érték a cordinátán
    fix_value = case Enum.find(field_values, fn {{fy, fx}, _} -> fy == y and fx == x end) do
      nil -> nil
      {{_, _}, v} -> v
    end

    new_value = if value == cycle do 1 else value+1 end
    {new_y, new_x} = Helper.next(size, y, x)

    {v_values, v_zeros} = Map.get(v_constraints, y, {0, size-cycle})
    {h_values, h_zeros} = Map.get(h_constraints, x, {0, size-cycle})
    
    # Lehet-e nullát beírni
    allow_value = allow_constraints and (fix_value == nil or fix_value == value)
    allow_zero = (fix_value == nil or fix_value == 0) and zero_counter > 0
      and v_zeros > 0 and h_zeros > 0
    
    new_results = 
      if allow_value do
        new_v_constraints = Map.put(v_constraints, y, {BitSet.put(v_values, value), v_zeros})
        new_h_constraints = Map.put(h_constraints, x, {BitSet.put(h_values, value), h_zeros})    
        solver({size, cycle, field_values}, {new_y, new_x}, {new_v_constraints, new_h_constraints},
          {index-1, zero_counter, new_value}, [value | result], results) 
      else results end

    if allow_zero do
      new_v_constraints = Map.put(v_constraints, y, {v_values, v_zeros-1})
      new_h_constraints = Map.put(h_constraints, x, {h_values, h_zeros-1}) 
      solver({size, cycle, field_values}, {new_y, new_x}, {new_v_constraints, new_h_constraints},
        {index-1, zero_counter-1, value}, [0 | result], new_results)
    else new_results end
    
  end

  
end

res1 = Nhf1_brute_force.helix({4, 2, [{{1, 1}, 1}, {{1, 4}, 2}]})
res2 = Nhf1_brute_force_v4.helix({4, 2, [{{1, 1}, 1}, {{1, 4}, 2}]})
IO.inspect(res1 == res2)

Brute force V5 - without global zero counter

defmodule Nhf1_brute_force_v5 do
@moduledoc """
Számtekercs
@author "Gödölle Dénes "
@date   "2025-10-14"
...
"""

  @type size()  :: integer() # tábla mérete (0 < n)
  @type cycle() :: integer() # ciklus hossza (0 < m <= n)
  @type value() :: integer() # mező értéke (0 < v <= m)

  @type row()   :: integer()       # sor száma (1-től n-ig)
  @type col()   :: integer()       # oszlop száma (1-től n-ig)
  @type field() :: {row(), col()}  # mező koordinátái

  @type field_value() :: {field(), value()}                 # mező és értéke
  @type puzzle_desc() :: {size(), cycle(), [field_value()]} # feladvány

  @type retval()    :: integer()    # eredménymező értéke (0 <= rv <= m)
  @type solution()  :: [[retval()]] # egy megoldás
  @type solutions() :: [solution()] # összes megoldás

  @spec helix(sd::puzzle_desc()) :: ss::solutions()
  # ss az sd feladványleíróval megadott feladvány összes megoldásának listája
  def helix({size, cycle, field_values}) do
    solver(
      {size, cycle, field_values}, {1, 1}, {%{}, %{}},
      {size * size, 1}, [], []
    )
  end

  def solver({size, _cycle, _field_values}, {_y, _x}, {_v_constraints, _h_constraints},
    {0, value}, result, results) do
    
    if value == 1 do
      res = Helper.decode_from_spiral(Enum.reverse(result), size)
      [res | results]
    else 
      results
    end
    
  end
    
  def solver({size, cycle, field_values}, {y, x}, {v_constraints, h_constraints},
    {index, value}, result, results) do

    # Van-e az adott sorban vagy oszlopban már a value száma
    allow_constraints = 
      value not in elem(Map.get(v_constraints, y, {[], 0}), 0) and 
      value not in elem(Map.get(h_constraints, x, {[], 0}), 0)
        
    # Van-e már előre beírt érték a cordinátán
    fix_value = case Enum.find(field_values, fn {{fy, fx}, _} -> fy == y and fx == x end) do
      nil -> nil
      {{_, _}, v} -> v
    end

    new_value = if value == cycle do 1 else value+1 end
    {new_y, new_x} = Helper.next(size, y, x)

    {v_values, v_zeros} = Map.get(v_constraints, y, {[], size-cycle})
    {h_values, h_zeros} = Map.get(h_constraints, x, {[], size-cycle})
    
    # Lehet-e nullát beírni
    allow_value = allow_constraints and (fix_value == nil or fix_value == value)
    allow_zero = (fix_value == nil or fix_value == 0) and
      v_zeros > 0 and h_zeros > 0

    new_results = 
      if allow_value do
        new_v_constraints = Map.put(v_constraints, y, {[value | v_values], v_zeros})
        new_h_constraints = Map.put(h_constraints, x, {[value | h_values], h_zeros})    
        solver({size, cycle, field_values}, {new_y, new_x}, {new_v_constraints, new_h_constraints},
          {index-1, new_value}, [value | result], results) 
      else results end

    if allow_zero do
      new_v_constraints = Map.put(v_constraints, y, {v_values, v_zeros-1})
      new_h_constraints = Map.put(h_constraints, x, {h_values, h_zeros-1}) 
      solver({size, cycle, field_values}, {new_y, new_x}, {new_v_constraints, new_h_constraints},
        {index-1, value}, [0 | result], new_results)
    else new_results end
    
  end

  
end

res1 = Nhf1_brute_force.helix({4, 2, [{{1, 1}, 1}, {{1, 4}, 2}]})
res2 = Nhf1_brute_force_v5.helix({4, 2, [{{1, 1}, 1}, {{1, 4}, 2}]})
IO.inspect({res1, res2})
IO.inspect(res1 == res2)

Brute force - V6 - Best

defmodule Helper_v2 do
  def decode_from_spiral([v | list], size) do
  {s_y, s_x} = {div(size, 2) + 1, round(size/2)}

  {map, _rest, _y, _x} =
    Enum.reduce(1..(size * size), {%{}, [v | list], s_y, s_x}, fn
      _, {acc, [v | rest], y, x} ->
        {new_y, new_x} = previous(size, y, x)
        {Map.put(acc, {y, x}, v), rest, new_y, new_x}
    end)

    # Map → rendezett nested list
    1..size
    |> Enum.map(fn y ->
      1..size
      |> Enum.map(fn x ->
        Map.fetch!(map, {y, x})
      end)
    end)
  end

  def previous(size, y, x) when x >= y and  size+1 >= x + y, do: {y, x-1}
  def previous(size, y, x) when y > x  and size+1 <= x + y,   do: {y, x+1}
  def previous(size, y, x) when x > size/2,                   do: {y-1, x}
  def previous(size, y, x) when size/2 >= x,                  do: {y+1, x} 

  def test_previous(0, _size, _y, _x), do: nil
  def test_previous(index, size, y, x) do
    IO.inspect({y, x})
    {new_y, new_x} = previous(size, y, x)
    test_previous(index-1, size, new_y, new_x)
  end
  
end

# IO.inspect(Helper.decode_from_spiral([1, 2, 3, 6, 9, 8, 7, 4, 5], 3), charlists: :as_lists)
# IO.inspect(Helper.previous(5, 1, 5))
# Helper_v2.previous(6, 3, 2)
# Helper_v2.test_previous(3*3, 3, 2, 2)
# list = for v <- 1..9, do: v
# IO.inspect(Helper_v2.decode_from_spiral(list, 3), charlists: :as_lists)

defmodule Nhf1_brute_force_v6 do
@moduledoc """
Számtekercs
@author "Gödölle Dénes "
@date   "2025-10-14"
...
"""

  @type size()  :: integer() # tábla mérete (0 < n)
  @type cycle() :: integer() # ciklus hossza (0 < m <= n)
  @type value() :: integer() # mező értéke (0 < v <= m)

  @type row()   :: integer()       # sor száma (1-től n-ig)
  @type col()   :: integer()       # oszlop száma (1-től n-ig)
  @type field() :: {row(), col()}  # mező koordinátái

  @type field_value() :: {field(), value()}                 # mező és értéke
  @type puzzle_desc() :: {size(), cycle(), [field_value()]} # feladvány

  @type retval()    :: integer()    # eredménymező értéke (0 <= rv <= m)
  @type solution()  :: [[retval()]] # egy megoldás
  @type solutions() :: [solution()] # összes megoldás

  @spec helix(sd::puzzle_desc()) :: ss::solutions()
  # ss az sd feladványleíróval megadott feladvány összes megoldásának listája
  def helix({size, cycle, field_values}) do
    solver(
      {size, cycle, field_values}, {1, 1}, {%{}, %{}},
      {size * size, 1}, [], []
    )
  end

  def solver({size, _cycle, _field_values}, {_y, _x}, {_v_constraints, _h_constraints},
    {0, value}, result, results) do
    
    if value == 1 do
      res = Helper_v2.decode_from_spiral(result, size)
      [res | results]
    else 
      results
    end
    
  end
    
  def solver({size, cycle, field_values}, {y, x}, {v_constraints, h_constraints},
    {index, value}, result, results) do

    # Van-e az adott sorban vagy oszlopban már a value száma
    allow_constraints = 
      not BitSet.member?(elem(Map.get(v_constraints, y, {0, 0}), 0), value) and 
      not BitSet.member?(elem(Map.get(h_constraints, x, {0, 0}), 0), value)
        
    # Van-e már előre beírt érték a cordinátán
    fix_value = case Enum.find(field_values, fn {{fy, fx}, _} -> fy == y and fx == x end) do
      nil -> nil
      {{_, _}, v} -> v
    end

    new_value = if value == cycle do 1 else value+1 end
    {new_y, new_x} = Helper.next(size, y, x)

    {v_values, v_zeros} = Map.get(v_constraints, y, {0, size-cycle})
    {h_values, h_zeros} = Map.get(h_constraints, x, {0, size-cycle})
    
    # Lehet-e nullát beírni
    allow_value = allow_constraints and (fix_value == nil or fix_value == value)
    allow_zero = (fix_value == nil or fix_value == 0) and
      v_zeros > 0 and h_zeros > 0

    new_results = 
      if allow_value do
        new_v_constraints = Map.put(v_constraints, y, {BitSet.put(v_values, value), v_zeros})
        new_h_constraints = Map.put(h_constraints, x, {BitSet.put(h_values, value), h_zeros})    
        solver({size, cycle, field_values}, {new_y, new_x}, {new_v_constraints, new_h_constraints},
          {index-1, new_value}, [value | result], results) 
      else results end

    if allow_zero do
      new_v_constraints = Map.put(v_constraints, y, {v_values, v_zeros-1})
      new_h_constraints = Map.put(h_constraints, x, {h_values, h_zeros-1}) 
      solver({size, cycle, field_values}, {new_y, new_x}, {new_v_constraints, new_h_constraints},
        {index-1, value}, [0 | result], new_results)
    else new_results end
    
  end

end

res1 = Nhf1_brute_force.helix({4, 2, [{{1, 1}, 1}, {{1, 4}, 2}]})
res2 = Nhf1_brute_force_v6.helix({4, 2, [{{1, 1}, 1}, {{1, 4}, 2}]})
# IO.inspect({res1, res2})
IO.inspect(res1 == res2)

Shortest unknown part first

defmodule Helper_supf do
  def sort_constraints(size, constraints) do
    total = size * size

    const_map = Map.new(constraints, fn {{y, x}, v} -> {{y, x}, v} end)
    {found_list, _} =
      Enum.reduce(1..total, {[], {1, 1}}, fn index, {acc, {y, x}} ->
        cond do
          Map.has_key?(const_map, {y, x}) ->
            v = const_map[{y, x}]
            {[{{y, x}, v, index} | acc], Helper.next(size, y, x)}

          true ->
            {acc, Helper.next(size, y, x)}
        end
      end)

    found = Enum.reverse(found_list)
    {{y, x}, end_value, index} = Enum.at(found, 0, {{0, 0}, 1, total+1})
    start = 
      if y != 1 or x != 1 do
        [{{1, 1}, {0, end_value}, 1, index-1}]
      else [] end 
    
    case found do
      [] -> start
      [{{pos, v}, idx}] -> start ++ {pos, {v, 1}, idx, total-idx}
      _ ->
        tuples_with_dist =
          found
          |> Enum.with_index()
          |> Enum.map(fn {{pos, v, idx}, i} ->
            {next_v, next_idx} =
              case Enum.at(found, i + 1) do
                nil -> {1, total+1}  # ha nincs következő, a végéhez kell hasonlítani
                {_, v, ni} -> {v, ni}
              end

            dist = next_idx - idx
            {pos, {v, next_v}, idx, dist}
          end)

        tuples_with_dist = start ++ tuples_with_dist
        Enum.sort_by(tuples_with_dist, fn {_pos, _values, _idx, dist} -> dist end)
    end
    
  end
end

IO.inspect(Helper_supf.sort_constraints(3, []))
# IO.inspect(Helper_supf.sort_constraints(3, [{{1, 1}, 1}]))
# IO.inspect(Helper_supf.sort_constraints(3, [{{1, 3}, 2}]))
# IO.inspect(Helper_supf.sort_constraints(3, [{{1, 3}, 2}, {{2, 1}, 3}]))

Adatstruktúra:

A v és h constraintek legyenek listák amikben egy {BitSet, int}

defmodule Nhf1_supf do
  @moduledoc """
  Számtekercs
  @author "Gödölle Dénes "
  @date   "2025-10-14"
  ...
  """

  # tábla mérete (0 < n)
  @type size() :: integer()
  # ciklus hossza (0 < m <= n)
  @type cycle() :: integer()
  # mező értéke (0 < v <= m)
  @type value() :: integer()

  # sor száma (1-től n-ig)
  @type row() :: integer()
  # oszlop száma (1-től n-ig)
  @type col() :: integer()
  # mező koordinátái
  @type field() :: {row(), col()}

  # mező és értéke
  @type field_value() :: {field(), value()}
  # feladvány
  @type puzzle_desc() :: {size(), cycle(), [field_value()]}

  # eredménymező értéke (0 <= rv <= m)
  @type retval() :: integer()
  # egy megoldás
  @type solution() :: [[retval()]]
  # összes megoldás
  @type solutions() :: [solution()]

  @spec helix(sd :: puzzle_desc()) :: ss :: solutions()
  # ss az sd feladványleíróval megadott feladvány összes megoldásának listája
  def helix({size, cycle, field_values}) do
    ordered_consts = Helper_supf.sort_constraints(size, field_values)

    solver(
      {size, cycle, ordered_consts},
      {-1, -1},
      {%{}, %{}},
      {size * size, 0, -1, false},
      {0, -1},
      {[], %{}, []}
    )
  end

  # Ha kész vagyunk a teljes spirállal
  def solver(
        {size, _cycle, _ordered_consts},
        {_y, _x},
        {_v_constraints, _h_constraints},
        {0, _index, value, _const_value},
        {start_index, end_value},
        {part, result, results}
      ) do
    if value == end_value do
      list_res =
        Map.to_list(Map.put(result, start_index, part))
        |> Enum.sort_by(fn {key, _value} -> key end, :desc)
        |> Enum.map(fn {_key, value} -> value end)

      list_res = List.flatten(list_res)
      res = Helper_v2.decode_from_spiral(list_res, size)
      [res | results]
    else
      results
    end
  end

  # Ha a figyelt constaintel vagyunk teljesen kész
  def solver(
        {size, cycle, [next_const | ordered_consts]},
        {_y, _x},
        {v_constraints, h_constraints},
        {whole_index, 0, value, _const_value},
        {start_index, end_value},
        {part, result, results}
      ) do
    {{n_y, n_x}, {n_v, n_end_value}, n_index, n_lenght} = next_const

    cond do
      n_v == 0 ->
        solver(
          {size, cycle, ordered_consts},
          {n_y, n_x},
          {v_constraints, h_constraints},
          {whole_index, n_lenght, 1, false},
          {n_index, n_end_value},
          {[], Map.put(result, start_index, part), results}
        )

      value == end_value ->
        solver(
          {size, cycle, ordered_consts},
          {n_y, n_x},
          {v_constraints, h_constraints},
          {whole_index, n_lenght, n_v, true},
          {n_index, n_end_value},
          {[], Map.put(result, start_index, part), results}
        )

      true ->
        results
    end
  end

  def solver(
        {size, cycle, _ordered_consts} = fix_parameters,
        {y, x},
        {v_constraints, h_constraints},
        {whole_index, index, value, const_value},
        const_parameters,
        {part, result, results}
      ) do
    # Van-e az adott sorban vagy oszlopban már a value száma
    allow_constraints =
      not BitSet.member?(elem(Map.get(v_constraints, y, {0, 0}), 0), value) and
        not BitSet.member?(elem(Map.get(h_constraints, x, {0, 0}), 0), value)

    new_value =
      if value == cycle do
        1
      else
        value + 1
      end

    {new_y, new_x} = Helper.next(size, y, x)

    {v_values, v_zeros} = Map.get(v_constraints, y, {0, size - cycle})
    {h_values, h_zeros} = Map.get(h_constraints, x, {0, size - cycle})

    # Lehet-e nullát beírni
    allow_zero = v_zeros > 0 and h_zeros > 0 and not const_value

    new_results =
      if allow_constraints do
        new_v_constraints = Map.put(v_constraints, y, {BitSet.put(v_values, value), v_zeros})
        new_h_constraints = Map.put(h_constraints, x, {BitSet.put(h_values, value), h_zeros})

        solver(
          fix_parameters,
          {new_y, new_x},
          {new_v_constraints, new_h_constraints},
          {whole_index - 1, index - 1, new_value, false},
          const_parameters,
          {[value | part], result, results}
        )
      else
        results
      end

    if allow_zero do
      new_v_constraints = Map.put(v_constraints, y, {v_values, v_zeros - 1})
      new_h_constraints = Map.put(h_constraints, x, {h_values, h_zeros - 1})

      solver(
        fix_parameters,
        {new_y, new_x},
        {new_v_constraints, new_h_constraints},
        {whole_index - 1, index - 1, value, false},
        const_parameters,
        {[0 | part], result, new_results}
      )
    else
      new_results
    end
  end
end

# res1 = Nhf1_brute_force.helix({5, 3, [{{1, 3}, 1}, {{2, 2}, 2}]})
# res2 = Nhf1_supf.helix({5, 3, [{{1, 3}, 1}, {{2, 2}, 2}]})
# IO.inspect(res1)
# IO.inspect("")
# IO.inspect(res2)
# IO.inspect(res1 == res2)

:fprof.start()
:fprof.trace([:start, {:procs, [self()]}])

Nhf1_supf.helix({3, 2, []})

:fprof.trace(:stop)
:fprof.profile()
analysis = :fprof.analyse([:totals, :details, sort: :acc])
IO.inspect(analysis, limit: :infinity)

Tests

defmodule Nhf1Kiadott do

  testcases = # %{key => {size, cycle, constraints, solutions}}
    %{
      0 => {3, 2, [], [[[0, 1, 2], [1, 2, 0], [2, 0, 1]], [[0, 1, 2], [2, 0, 1], [1, 2, 0]], [[1, 2, 0], [2, 0, 1], [0, 1, 2]]]},
      1 => {4, 2, [{{1, 1}, 1}, {{1, 4}, 2}], [[[1, 0, 0, 2], [0, 1, 2, 0], [0, 2, 1, 0], [2, 0, 0, 1]], [[1, 0, 0, 2], [2, 0, 0, 1], [0, 2, 1, 0], [0, 1, 2, 0]], [[1, 0, 0, 2], [2, 0, 1, 0], [0, 2, 0, 1], [0, 1, 2, 0]]]},
      2 => {4, 1, [{{1, 1}, 1}], [[[1, 0, 0, 0], [0, 0, 0, 1], [0, 0, 1, 0], [0, 1, 0, 0]], [[1, 0, 0, 0], [0, 0, 0, 1], [0, 1, 0, 0], [0, 0, 1, 0]], [[1, 0, 0, 0], [0, 0, 1, 0], [0, 0, 0, 1], [0, 1, 0, 0]], [[1, 0, 0, 0], [0, 0, 1, 0], [0, 1, 0, 0], [0, 0, 0, 1]], [[1, 0, 0, 0], [0, 1, 0, 0], [0, 0, 0, 1], [0, 0, 1, 0]], [[1, 0, 0, 0], [0, 1, 0, 0], [0, 0, 1, 0], [0, 0, 0, 1]]]},
      3 => {4, 3, [], []},
      4 => {5, 3, [{{1, 3}, 1}, {{2, 2}, 2}], [[[0, 0, 1, 2, 3], [0, 2, 0, 3, 1], [1, 3, 0, 0, 2], [3, 0, 2, 1, 0], [2, 1, 3, 0, 0]], [[0, 0, 1, 2, 3], [0, 2, 3, 0, 1], [1, 3, 0, 0, 2], [3, 0, 2, 1, 0], [2, 1, 0, 3, 0]]]},
      5 => {6, 3, [{{1, 5}, 2}, {{2, 2}, 1}, {{4, 6}, 1}], [[[1, 0, 0, 0, 2, 3], [0, 1, 2, 3, 0, 0], [0, 3, 1, 2, 0, 0], [0, 2, 3, 0, 0, 1], [3, 0, 0, 0, 1, 2], [2, 0, 0, 1, 3, 0]]]},
      6 => {6, 3, [{{1, 5}, 2}, {{2, 2}, 1}, {{4, 6}, 1}], [[[1, 0, 0, 0, 2, 3], [0, 1, 2, 3, 0, 0], [0, 3, 1, 2, 0, 0], [0, 2, 3, 0, 0, 1], [3, 0, 0, 0, 1, 2], [2, 0, 0, 1, 3, 0]]]},
      7 => {6, 3, [{{2, 4}, 3}, {{3, 3}, 1}, {{3, 6}, 2}, {{6, 1}, 3}], [[[0, 1, 2, 0, 3, 0], [2, 0, 0, 3, 0, 1], [0, 3, 1, 0, 0, 2], [0, 0, 3, 2, 1, 0], [1, 0, 0, 0, 2, 3], [3, 2, 0, 1, 0, 0]]]},
      8 => {7, 3, [{{1, 1}, 1}, {{2, 4}, 3}, {{3, 4}, 1}, {{4, 3}, 3}, {{6, 6}, 2}, {{7, 7}, 3}], [[[1, 0, 0, 2, 0, 3, 0], [0, 1, 2, 3, 0, 0, 0], [0, 3, 0, 1, 2, 0, 0], [0, 2, 3, 0, 0, 0, 1], [3, 0, 0, 0, 0, 1, 2], [0, 0, 1, 0, 3, 2, 0], [2, 0, 0, 0, 1, 0, 3]]]},
      9 => {8, 3, [{{1, 4}, 1}, {{1, 7}, 3}, {{2, 3}, 2}, {{2, 4}, 3}, {{3, 2}, 1}, {{4, 7}, 1}, {{7, 7}, 2}], [[[0, 0, 0, 1, 0, 2, 3, 0], [0, 0, 2, 3, 0, 0, 0, 1], [0, 1, 0, 0, 2, 3, 0, 0], [0, 3, 0, 0, 0, 0, 1, 2], [1, 2, 3, 0, 0, 0, 0, 0], [3, 0, 0, 2, 0, 1, 0, 0], [0, 0, 1, 0, 3, 0, 2, 0], [2, 0, 0, 0, 1, 0, 0, 3]], [[0, 0, 0, 1, 0, 2, 3, 0], [0, 0, 2, 3, 0, 0, 0, 1], [0, 1, 0, 0, 2, 3, 0, 0], [0, 3, 0, 0, 0, 0, 1, 2], [1, 2, 3, 0, 0, 0, 0, 0], [3, 0, 0, 2, 1, 0, 0, 0], [0, 0, 1, 0, 3, 0, 2, 0], [2, 0, 0, 0, 0, 1, 0, 3]], [[0, 0, 0, 1, 0, 2, 3, 0], [0, 0, 2, 3, 0, 0, 0, 1], [0, 1, 0, 2, 0, 3, 0, 0], [0, 3, 0, 0, 0, 0, 1, 2], [1, 2, 3, 0, 0, 0, 0, 0], [3, 0, 0, 0, 2, 1, 0, 0], [0, 0, 1, 0, 3, 0, 2, 0], [2, 0, 0, 0, 1, 0, 0, 3]], [[0, 0, 0, 1, 0, 2, 3, 0], [0, 0, 2, 3, 0, 0, 0, 1], [0, 1, 0, 2, 3, 0, 0, 0], [0, 3, 0, 0, 0, 0, 1, 2], [1, 2, 3, 0, 0, 0, 0, 0], [3, 0, 0, 0, 2, 1, 0, 0], [0, 0, 0, 0, 1, 3, 2, 0], [2, 0, 1, 0, 0, 0, 0, 3]], [[0, 0, 0, 1, 0, 2, 3, 0], [0, 0, 2, 3, 0, 0, 0, 1], [0, 1, 0, 2, 3, 0, 0, 0], [0, 3, 0, 0, 0, 0, 1, 2], [1, 2, 3, 0, 0, 0, 0, 0], [3, 0, 0, 0, 2, 1, 0, 0], [0, 0, 1, 0, 0, 3, 2, 0], [2, 0, 0, 0, 1, 0, 0, 3]]]},
      # Valami itt nem optimális
      # További vizsgálatot igényelÍ
      10 => {8, 4, [{{2, 3}, 4}, {{3, 3}, 2}, {{6, 1}, 1}, {{7, 6}, 3}], [[[0, 0, 1, 2, 3, 4, 0, 0], [0, 0, 4, 0, 1, 2, 3, 0], [0, 0, 2, 3, 0, 0, 4, 1], [3, 1, 0, 4, 0, 0, 0, 2], [2, 4, 0, 0, 0, 0, 1, 3], [1, 3, 0, 0, 0, 0, 2, 4], [0, 2, 0, 1, 4, 3, 0, 0], [4, 0, 3, 0, 2, 1, 0, 0]], [[0, 0, 1, 2, 3, 4, 0, 0], [0, 0, 4, 0, 1, 2, 3, 0], [3, 0, 2, 0, 0, 0, 4, 1], [0, 1, 3, 4, 0, 0, 0, 2], [2, 4, 0, 0, 0, 0, 1, 3], [1, 3, 0, 0, 0, 0, 2, 4], [0, 2, 0, 1, 4, 3, 0, 0], [4, 0, 0, 3, 2, 1, 0, 0]]]},
      11 => {9, 3, [{{1, 7}, 3}, {{3, 1}, 1}, {{6, 1}, 3}, {{6, 2}, 2}, {{6, 6}, 1}, {{8, 4}, 3}, {{9, 2}, 1}], [[[0, 0, 0, 0, 1, 2, 3, 0, 0], [0, 0, 2, 0, 0, 0, 0, 3, 1], [1, 3, 0, 0, 0, 0, 0, 0, 2], [0, 0, 0, 1, 2, 3, 0, 0, 0], [0, 0, 0, 2, 3, 0, 1, 0, 0], [3, 2, 0, 0, 0, 1, 0, 0, 0], [0, 0, 3, 0, 0, 0, 2, 1, 0], [0, 0, 1, 3, 0, 0, 0, 2, 0], [2, 1, 0, 0, 0, 0, 0, 0, 3]]]}
    }
  for i <- 0..map_size(testcases)-1
    do
    {size, cycle, constrains, solutions} = testcases[i]
    {time, res} = :timer.tc(fn -> Nhf1.helix({size, cycle, constrains}) end)
    {time2, res2} = :timer.tc(fn -> Nhf1_brute_force_v2.helix({size, cycle, constrains}) end)
    if res2 |> Enum.sort() === solutions and res |> Enum.sort() === solutions do
      {"Test case #{i}",
        "V1: #{time * 0.000001 |> Float.ceil(6)} V2: #{time2 * 0.000001 |> Float.ceil(6)}",
        (time2 - time) * 0.000001 |> Float.ceil(6)
      }
      |> IO.inspect
    else
      "Test case #{i} rossz megoldás" |> IO.inspect()
    end
  end

end

Beadás

defmodule Nhf1 do
  @moduledoc """
  Számtekercs
  @author "Gödölle Dénes "
  @date   "2025-10-23"
  ...
  """

  # --- Típusdefiníciók -------------------------------------------------------

  @type size() :: integer()
  @type cycle() :: integer()
  @type value() :: integer()
  @type row() :: integer()
  @type col() :: integer()
  @type field() :: {row(), col()}
  @type field_value() :: {field(), value()}
  @type puzzle_desc() :: {size(), cycle(), [field_value()]}
  @type retval() :: integer()
  @type solution() :: [[retval()]]
  @type solutions() :: [solution()]
  @type index() :: integer()
  @type length() :: integer()
  @type interval_constraints() :: {field(), {value(), integer()}, index(), length()}
  @type zero_count() :: integer()
  @type bit_set() :: integer()
  @type row_constraits() :: %{row() => {bit_set(), zero_count()}}
  @type col_constraits() :: %{col() => {bit_set(), zero_count()}}
  @type spiral_part() :: [value()]
  @type spiral_parts() :: %{index() => spiral_part()}

  # --- Fő belépési pont ------------------------------------------------------

  @spec helix(sd :: puzzle_desc()) :: ss :: solutions()
  def helix({size, cycle, field_values}) do
    ordered_consts = sort_constraints(size, field_values)

    solver(
      {size, cycle, ordered_consts},
      {-1, -1}, {%{}, %{}},
      {size * size, 0, -1, false},
      {0, -1}, {[], %{}, []}
    )
  end

  # --- Solver ---------------------------------------------------------------

  @spec solver(
          {size(), cycle(), interval_constraints()},
          {row(), col()},
          {row_constraits(), col_constraits()},
          {index(), index(), value(), boolean()},
          {index(), value()},
          {spiral_part(), spiral_parts(), solutions()}
        ) :: solutions()

  # Báziseset
  def solver(
        {size, _cycle, _ordered_consts},
        {_y, _x}, {_v_constraints, _h_constraints},
        {0, _index, value, _const_value},
        {start_index, end_value},
        {part, result, results}
      ) do
    if value == end_value do
      list_res =
        Map.to_list(Map.put(result, start_index, part))
        |> Enum.sort_by(fn {key, _value} -> key end, :desc)
        |> Enum.map(fn {_key, value} -> value end)
        |> List.flatten()

      res = decode_from_spiral(list_res, size)
      [res | results]
    else
      results
    end
  end

  # Új constraint kezdése
  def solver(
        {size, cycle, [next_const | ordered_consts]},
        {_y, _x}, {v_constraints, h_constraints},
        {whole_index, 0, value, _const_value},
        {start_index, end_value},
        {part, result, results}
      ) do
    {{n_y, n_x}, {n_v, n_end_value}, n_index, n_lenght} = next_const

    cond do
      n_v == 0 ->
        solver(
          {size, cycle, ordered_consts},
          {n_y, n_x},
          {v_constraints, h_constraints},
          {whole_index, n_lenght, 1, false},
          {n_index, n_end_value},
          {[], Map.put(result, start_index, part), results}
        )

      value == end_value ->
        solver(
          {size, cycle, ordered_consts},
          {n_y, n_x},
          {v_constraints, h_constraints},
          {whole_index, n_lenght, n_v, true},
          {n_index, n_end_value},
          {[], Map.put(result, start_index, part), results}
        )

      true ->
        results
    end
  end

  # Általános eset
  def solver(
        {size, cycle, _ordered_consts} = fix_parameters,
        {y, x}, {v_constraints, h_constraints},
        {whole_index, index, value, const_value},
        const_parameters,
        {part, result, results}
      ) do
    allow_constraints =
      not bitSet_member?(elem(Map.get(v_constraints, y, {0, 0}), 0), value) and
        not bitSet_member?(elem(Map.get(h_constraints, x, {0, 0}), 0), value)

    new_value =
      if value == cycle, do: 1, else: value + 1

    {new_y, new_x} = next(size, y, x)

    {v_values, v_zeros} = Map.get(v_constraints, y, {0, size - cycle})
    {h_values, h_zeros} = Map.get(h_constraints, x, {0, size - cycle})

    allow_zero = v_zeros > 0 and h_zeros > 0 and not const_value

    new_results =
      if allow_constraints do
        new_v_constraints = Map.put(v_constraints, y, {bitSet_put(v_values, value), v_zeros})
        new_h_constraints = Map.put(h_constraints, x, {bitSet_put(h_values, value), h_zeros})

        solver(
          fix_parameters,
          {new_y, new_x},
          {new_v_constraints, new_h_constraints},
          {whole_index - 1, index - 1, new_value, false},
          const_parameters,
          {[value | part], result, results}
        )
      else
        results
      end

    if allow_zero do
      new_v_constraints = Map.put(v_constraints, y, {v_values, v_zeros - 1})
      new_h_constraints = Map.put(h_constraints, x, {h_values, h_zeros - 1})

      solver(
        fix_parameters,
        {new_y, new_x},
        {new_v_constraints, new_h_constraints},
        {whole_index - 1, index - 1, value, false},
        const_parameters,
        {[0 | part], result, new_results}
      )
    else
      new_results
    end
  end

  # --- Segédfüggvények -------------------------------------------------------

  @spec next(size(), row(), col()) :: {row(), col()}
  def next(size, y, x) when x + 1 >= y and size + 1 > x + y, do: {y, x + 1}
  def next(size, y, x) when y >= x and x + y > size + 1, do: {y, x - 1}
  def next(size, y, x) when x > size / 2, do: {y + 1, x}
  def next(size, y, x) when size / 2 >= x, do: {y - 1, x}

  @spec previous(size(), row(), col()) :: {row(), col()}
  def previous(size, y, x) when x >= y and size + 1 >= x + y, do: {y, x - 1}
  def previous(size, y, x) when y > x and size + 1 <= x + y, do: {y, x + 1}
  def previous(size, y, x) when x > size / 2, do: {y - 1, x}
  def previous(size, y, x) when size / 2 >= x, do: {y + 1, x}

  @spec decode_from_spiral([value()], size()) :: solution()
  def decode_from_spiral([v | list], size) do
    {s_y, s_x} = {div(size, 2) + 1, round(size / 2)}

    {map, _rest, _y, _x} =
      Enum.reduce(1..(size * size), {%{}, [v | list], s_y, s_x}, fn
        _, {acc, [v | rest], y, x} ->
          {new_y, new_x} = previous(size, y, x)
          {Map.put(acc, {y, x}, v), rest, new_y, new_x}
      end)

    1..size
    |> Enum.map(fn y ->
      1..size
      |> Enum.map(fn x -> Map.fetch!(map, {y, x}) end)
    end)
  end

  @spec sort_constraints(size(), [field_value()]) :: interval_constraints()
  def sort_constraints(size, constraints) do
    total = size * size
    const_map = Map.new(constraints, fn {{y, x}, v} -> {{y, x}, v} end)

    {found_list, _} =
      Enum.reduce(1..total, {[], {1, 1}}, fn index, {acc, {y, x}} ->
        if Map.has_key?(const_map, {y, x}) do
          v = const_map[{y, x}]
          {[{{y, x}, v, index} | acc], next(size, y, x)}
        else
          {acc, next(size, y, x)}
        end
      end)

    found = Enum.reverse(found_list)
    {{y, x}, end_value, index} = Enum.at(found, 0, {{0, 0}, 1, total + 1})

    start =
      if y != 1 or x != 1 do
        [{{1, 1}, {0, end_value}, 1, index - 1}]
      else
        []
      end

    case found do
      [] ->
        start

      [{{pos, v}, idx}] ->
        start ++ {pos, {v, 1}, idx, total - idx}

      _ ->
        tuples_with_dist =
          found
          |> Enum.with_index()
          |> Enum.map(fn {{pos, v, idx}, i} ->
            {next_v, next_idx} =
              case Enum.at(found, i + 1) do
                nil -> {1, total + 1}
                {_, v, ni} -> {v, ni}
              end

            dist = next_idx - idx
            {pos, {v, next_v}, idx, dist}
          end)

        tuples_with_dist = start ++ tuples_with_dist
        Enum.sort_by(tuples_with_dist, fn {_pos, _values, _idx, dist} -> dist end)
    end
  end

  import Bitwise
  def bitSet_member?(set, number) do
    ((set >>> (number - 1)) &amp;&amp;&amp; 1) == 1
  end
  
  def bitSet_put(set, number) do
    set ||| (1 <<< (number - 1))
  end

  def bitSet_remove(set, number) do
    set &amp;&amp;&amp; bnot(1 <<< (number - 1))
  end
end

Other notebooks:

Yejun Su
@goofansu

ogp

ogp

ogp.livemd

tutorial intermediate ogp kino

2022-8-18
@TomBers

livebookNotes

Attractors

attractors.livemd

advanced data-science decimal vega_lite kino

2022-8-18
Kevin Pan
@feng19

spider_man

ElixirJobs

elixirjobs.livemd

tutorial advanced spider_man floki nimble_csv kino

2022-8-18
@TomBers

livebookNotes

Fun with Graphs

graphs.livemd

tutorial advanced intermediate vega_lite kino math

2022-8-18
Sebastian Heiden
@sehHeiden

poll_election_bavaria_202...

Bavarian Election

election_bavaria.livemd

tutorial advanced data-science algorithms testing debugging sql httpoison explorer kino_vega_lite exla kino_bumblebee bumblebee adbc tucan scholar nx

2023-8-14
Lukas Knuth
@LukasKnuth

aoc_24

Day 16: Reindeer Maze

day_16_reindeer_maze.livemd

tutorial advanced algorithms data-structures kino vega_lite kino_vega_lite

2025-4-21
Ammar Massoud
@ammar-mohamed-massoud

Dockyard-Academy

Phoenix Authentication

phoenix_authentication.livemd

tutorial advanced security jason kino youtube hidden_cell

2026-5-19

Back