examples/pir/queens_r.pir

   1 # Copyright (C) 2005-2009, Parrot Foundation.
   2 # $Id$
   3
   4 # recursive queens placement
   5 # prints all 92 solutions in chess notation
   6 # by leo
   7
   8 .sub main :main
   9     .local pmc queen_row, queen_state
  10     queen_row = new 'ResizableIntegerArray'
  11     queen_state = new 'ResizableIntegerArray'
  12     solve(0, queen_row, queen_state)
  13 .end
  14
  15 .sub solve
  16     .param int row
  17     .param pmc queen_row
  18     .param pmc queen_state
  19     .local int col, is_free
  20     col = 0
  21 loop:
  22     is_free = check_free(col, row, queen_state)
  23     unless is_free goto not_free
  24         place_queen(col, row, queen_row, queen_state)
  25         if row < 7 goto not_fin
  26             print_solution(queen_row)
  27         goto fin
  28 not_fin:
  29         $I0 = row + 1
  30         solve($I0, queen_row, queen_state)
  31 fin:
  32         remove_queen(col, row, queen_row, queen_state)
  33 not_free:
  34     inc col
  35     if col < 8 goto loop
  36 .end
  37
  38 # queen_state
  39 # 0..7 columns
  40 # 8..14 first diagonal  := col + row
  41 # 24..  second diagonal := col - row
  42 .sub check_free
  43     .param int col
  44     .param int row
  45     .param pmc queen_state
  46     $I0 = queen_state[col]
  47     if $I0 goto ret_0
  48     $I1 = col + row
  49     $I1 += 8
  50     $I0 = queen_state[$I1]
  51     if $I0 goto ret_0
  52     $I1 = col - row
  53     $I1 += 32
  54     $I0 = queen_state[$I1]
  55     if $I0 goto ret_0
  56     .return(1)
  57 ret_0:
  58     .return(0)
  59 .end
  60
  61 .sub place_queen
  62     .param int col
  63     .param int row
  64     .param pmc queen_row
  65     .param pmc queen_state
  66     $I0 = row + 1
  67     set_queen(col, row, queen_row, queen_state, $I0)
  68 .end
  69
  70 .sub remove_queen
  71     .param int col
  72     .param int row
  73     .param pmc queen_row
  74     .param pmc queen_state
  75     set_queen(col, row, queen_row, queen_state, 0)
  76 .end
  77
  78 .sub set_queen
  79     .param int col
  80     .param int row
  81     .param pmc queen_row
  82     .param pmc queen_state
  83     .param int val
  84     queen_row[col] = val
  85     queen_state[col] = val
  86     $I1 = col + row
  87     $I1 += 8
  88     queen_state[$I1] = val
  89     $I1 = col - row
  90     $I1 += 32
  91     queen_state[$I1] = val
  92 .end
  93
  94 .sub print_solution
  95     .param pmc queen_row
  96     .local int c, r
  97     c = 0
  98 loop:
  99         $I0 = 65 + c
 100         $S0 = chr $I0
 101         print $S0
 102         r = queen_row[c]
 103         r += 48
 104         $S0 = chr r
 105         print $S0
 106         print " "
 107         inc c
 108     if c < 8 goto loop
 109     print "\n"
 110 .end
 111
 112 # Local Variables:
 113 #   mode: pir
 114 #   fill-column: 100
 115 # End:
 116 # vim: expandtab shiftwidth=4 ft=pir: