Smap

Choose the version you want to view.

Current version:Version message:

Program created.

Click on the badge to open the comment window for viewing and writing comments.

No comments yet.

Created by antoy on July 21, 2020

0 users favorited this

Description: Solves the N-queens puzzle using the Concurrent Distinct Choices pattern.

Source code (Latest version):

-- N-queens puzzle 
-- Sergio Antoy, Mon 20 Jul 2020 03:16:05 PM PDT
-- 
-- The algorithm is from: The Art of Computer Programming, Volume 4,
-- Fascicle 5B: 7.2.2, Algorithm B, three arrays version.
--
-- The code is an adaption of the following pattern:
--
--   Sergio Antoy and Michael Hanus
--   Concurrent Distinct Choices
--   Journal of Functional Programming
--   Vol. 14, no. 6, pages 657-668, 2004, 
--   http://dx.doi.org/10.1017/S095679680400509X
--
-- Using Pakcs to compute all the solutions with 8 queens, this algorithm
-- is 1-2 orders of magnitude faster than most other algorithms.

queens N | equations = a
  where
     a = array N
     b = array (2*N-1)
     c = array (2*N-1)

-- place each queen on the board
     -- the numbers [0..N-1] are distinct arbitrary tokens
     -- for convenience, each can be thought as the board column of a queen
     equations = foldr (\ x y -> place x & y) True [0..N-1]

-- col and row are the column and row of a queen on the board
     -- col is given, row is non-deterministically guessed
     -- array a ensures no two queens are on the same row
     -- arrays b and c ensure no two queens are on the same diagonal
     place col = a !! row == col 
             & b !! (col + row) == col
             & c !! (col - row + N - 1) == col
             where row = anyOf [0..N-1]

-- a list of n free variables used as a write-once array
array n = map (\ _ -> _) [1..n]

-- Execute
main = queens 8

Options

Versions

1 version

Tags

5 tags

Comments

0 comments »

queens_concur_dist_choices

implemented in Curry