The Hyper Programming Language

Eight Queens Example

This program looks for a solution to the eight queens problem and prints the result on standard output.

Disclaimer: I haven't been able to actually compile and run this code yet, so if you find an error please let me know.

The program should print the following:

X-------
------X-
----X---
-------X
-X------
---X----
-----X--
--X-----

Source Code

import system.stdio

class EightQueens
public:
	
	static procedure main()
		placeQueen(0)  # place queens 0 to 7
		
		# now print the board with the solution we found
		iterate y : nat from 0 count 8
			iterate x : nat from 0 count 8
				system.Out.print(board[x, y] ? "X" : "-")
			end
			system.Out.line
		end
	end
	
private:
	# try to put a queen on column x
	static procedure placeQueen(x : nat) : bool
		iterate y : nat from 0 count 8
			# see if we can place a queen on position y in column x
			if canPlaceQueen(x, y) then
				# queen doesn't interfere with those already placed
				
				# put the queen on the board
				board[x, y] = true
				
				# try to place more queens...
				if (placeQueen(x + 1)) then
					# placement of others was successfull
					return true
				else
					# deadlock situation -> take our queen back off the board
					board[x, y] = false
				end
			end
		end
		
		# could not place a queen in the current board
		return false
	end
	
	# Check if we can put a queen on the given position.
	# We know that there can only be queens on the board
	# to the left of this position.
	static procedure canPlaceQueen(x & y : nat) : bool
		# horizontally (the left side)
		iterate ix : nat from 0 to --x
			if (board[ix, y]) then
				return false
			end
		end
		
		# north-west
		var ix : nat = x
		var iy : nat = y
		loop when ix > 0 & iy > 0
			ix --
			iy --
			if (board[ix, iy]) then
				return false
			end
		end
		
		# south-west
		ix = x
		iy = y
		loop when ix > 0 & iy < (8 - 1)
			ix --
			iy ++
			if (board[ix, iy]) then
				return false
			end
		end
		
		return true
	end
	
	static var board : [8, 8] bool  # board to place queens on
end

More Information

For information about the language, go to the language reference. The following links provide information about some things used in the example above:

Other examples