(*
 * Copyright (c) 2007, Marco Maggesi
 * All rights reserved.
 * 
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are
 * met:
 * 
 *   1. Redistributions of source code must retain the above copyright
 *      notice, this list of conditions and the following disclaimer.
 * 
 *   2. Redistributions in binary form must reproduce the above copyright
 *      notice, this list of conditions and the following disclaimer in
 *      the documentation and/or other materials provided with the
 *      distribution.
 * 
 *   3. Neither the name of Marco Maggesi nor the names of its
 *      contributors may be used to endorse or promote products derived
 *      from this software without specific prior written permission.
 * 
 * THIS SOFTWARE IS PROVIDED BY MARCO MAGGESI "AS IS" AND ANY EXPRESS OR
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED. IN NO EVENT SHALL MARCO MAGGESI BE LIABLE FOR ANY DIRECT,
 * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
 * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
 *)

include Set.Make(struct type t = (int * int) * int let compare = compare end)

let (@) g f x = g (f x) and id x = x and sw f x y = f y x and zip x y = (x, y)

let fold9 f = let rec loop i = if i>8 then id else loop (i+1) @ f i in loop 0

let fold81 f = fold9 (fold9 @ (@) f @ zip)

let mark ((i,j),x as e) : t -> t =
  add e @ fold9 (fun k -> remove ((i/3*3 + k/3, j/3*3 + k mod 3), x) @
    remove ((i,j),k) @ remove ((i,k),x) @ remove ((k,j),x))

let search =
  let g p f s = fold (f @ sw mark s) (filter ((=) p @ fst) s) in
  fold81 g

let read () =
  let f p = Scanf.scanf "%d " (fun x -> if x>0 then mark (p,x-1) else id) in
  fold81 f (fold81 (fold9 @ ((@) add @ zip)) empty)

let print s () =
  let pr ((i,j),x) = Printf.printf "%d%c" (x+1) (if j=8 then '\n' else ' ') in
  iter pr s; print_newline ();;

search print (read ()) ()