[32eb06]: Tests / 8queens.sis Maximize Restore History

Download this file

8queens.sis    52 lines (42 with data), 1.2 kB

define Main 

type queen_list    = array[integer];
type solution_list = array [queen_list]


%  in_check checks to see that the (row,column) pair proposed
%  does not enter check with any of the previously assigned
%  (row,column) pairs.
%
function in_check (r, c : integer; queens : queen_list
		   returns boolean)

    for row in queens at column
    returns value of sum
      (r = row) |
      ((row + column) = (r + c)) |
      ((row - column) = (r - c))
    end for

end function


function Main(level: integer returns solution_list)

    if level = 1 then
	for row in 1,4		% 5 to 8 are same by symmetry
	    assignment := array queen_list [ 1: row ]
	returns
	    array of assignment
	end for
    else
	for partial_assignment in Main(level - 1)
	    column := 1 + array_size(partial_assignment);
	    new_assignment :=
		 for row in 1,8
		     ischeck    := in_check(row, column, partial_assignment);
		     assignment := if ischeck then
			              array queen_list []
			           else
			              array_addh(partial_assignment, row)
			           end if
		 returns
		   array of assignment unless ischeck
		 end for
	returns
	  value of catenate new_assignment
	end for
    end if

end function