alg-visualizer/Nqueens.lua

love.window.setMode(150, 40)  -- Input box
love.keyboard.setKeyRepeat(true)

local bit = require 'bit'

-- Validation function for numeric input
local function numeric(t)
  return type(t) == "string" and t >= "0" and t <= "9"
end

-- Validation function for UTF-8 text input
local function text(t)
  local L, U, b2, b3, b4 = #t, t:byte(1, 4)
  if L <= 1 then
    return U and U < 128
  end
  -- Check correctness of bit encoding and length
  if b2 < 128 or b2 > 191
    or L ~= 2 and (b3 < 128 or b3 > 191)
    or L == 2 and (U < 0xC2 or U > 0xDF)
    or L == 3 and (U < 0xE0 or U > 0xEF)
    or L == 4 and (U < 0xF0 or U > 0xF4 or b4 < 128 or b4 > 191)
  then
    return false
  end
  -- Basic encoding/length validation test passed - decode the bits
  U = bit.lshift(U - 192, 6) + (b2 - 128)
  if L >= 3 then
    U = bit.lshift(U - 0x800, 6) + (b3 - 128)
    if L >= 4 then
      U = bit.lshift(U - 0x10000, 6) + (b4 - 128)
    end
  end

  if L == 3 and U < 0x800 or L == 4 and U < 0x10000  -- overlong
    or U > 0x10FFFD  -- out of range
    or U >= 0xD800 and U <= 0xDFFF  -- surrogate
    or U >= 0xFDD0 and U <= 0xFDEF  -- invalid range
  then
    return false
  end
  local low = bit.band(U, 0xFFFF)
  return low ~= 0xFFFE and low ~= 0xFFFF
end

-- Input function that allows entering any text:
local function simpleInput(x, y, maxlen, validFn)
  local r_save, g_save, b_save, a_save = love.graphics.getColor()
  local font = love.graphics.getFont()
  local H = font:getHeight()
  local W = font:getWidth("M")  -- hopefully the thickest letter in the font
  local str = ''
  repeat
    poll()
    love.graphics.setColor(love.graphics.getBackgroundColor())
    love.graphics.rectangle("fill", x, y, (maxlen + 1) * W, H)
    love.graphics.setColor(r_save, g_save, b_save, a_save)
    love.graphics.print(str .. "_", x, y)
    local ret, k = peek.keypressed()
    local t = ""
    if peek.textinput() then
      ret, t = peek.textinput()
    end

    if k == "escape" then
      quit()
    end
    if k == "backspace" and str ~= "" then
      str = str:sub(1, -2)
    elseif validFn(t) then
      str = str .. t
    end
    if #str > maxlen then
      str = str:sub(1, maxlen)
    end
  until k == 'kpenter' or k == 'return'
  love.graphics.setColor(r_save, g_save, b_save, a_save)
  return str
end

do
  local text = "Enter N (4-16): "
  love.graphics.print(text, 20, 10)
  local w = love.graphics.getFont():getWidth(text)
  repeat
    N = tonumber(simpleInput(w + 20, 10, 2, numeric))
  until N and N >= 4 and N <= 16
end

local size = 40

love.window.setMode((N + 1) * size, (N + 1.5) * size, {vsync = false})
-- Work around problem where a new keypress event is sent to the new window
-- if it was pressed, by ignoring the keypressed events for 1 frame
wait.update() -- wait for this update
wait.update() -- wait for the *next* uppate

local img = love.graphics.newImage('queen-black-40x40.png')

local function clear(x, y)
  if (x + y) % 2 == 1 then
    love.graphics.setColor(0, 0, 0)
  else
    love.graphics.setColor(255, 255, 255)
  end
  love.graphics.rectangle("fill", x*size, y*size, size, size)
  love.graphics.setColor(255, 255, 255)
end

-- Set origin to top left of board
love.graphics.translate(size/2, size)

-- Draw border
love.graphics.rectangle("fill", -4, -4, N*size+8, N*size+8)
for y = 0, N-1 do
  for x = 0, N-1 do
    clear(x, y)
  end
end

local board = {}
local nSolutions = 0

local function printSolution()
  for i = 1, N do
    print(("*"):rep(board[i]) .. "Q" .. ("*"):rep(N - 1 - board[i]))
  end
  print(("-"):rep(N))
  nSolutions = nSolutions + 1
  -- Erase background before printing
  for i = 1, 3 do
    love.graphics.setColor(love.graphics.getBackgroundColor())
    love.graphics.rectangle("fill", 10, -30, N*size, 14)
    sleep(0.2)
    love.graphics.setColor(255, 255, 255)
    love.graphics.print("Number of solutions: " .. nSolutions, 10, -30)
    sleep(0.2)
  end
  pause(1.5)
end
love.graphics.print("Number of solutions: 0", 10, -30)

local function tryQueen(row)
  for x = 0, N - 1 do
    love.graphics.draw(img, x*size, row*size)
    pause(0)
    local failed = false
    for i = 1, row do
      if board[i] == x or board[i] - x == row - (i - 1) or x - board[i] == row - (i - 1) then
        failed = true
        break
      end
    end
    if not failed then
      board[row + 1] = x
      if row == N - 1 then
        printSolution()
      else
        tryQueen(row + 1)
      end
    end
    clear(x, row)
  end
end

tryQueen(0)

love.graphics.setColor(255, 0, 0)
love.graphics.print("No more solutions\nPress a key", 10, 40)
print("No more solutions")

wait.keypressed()
quit()