
Chess coaches have been known to inflict a kind of torture on beginners by taking a chess board, placing pennies on some squares and requiring that a Knight's tour be constructed that avoids the squares with pennies.

This kind of knight's tour puzzle is similar to   Hidato.

The present task is to produce a solution to such problems. At least demonstrate your program by solving the following:



Example

  0 0 0 
  0   0 0 
  0 0 0 0 0 0 0
0 0 0     0   0
0   0     0 0 0
1 0 0 0 0 0 0
    0 0   0
      0 0 0

Note that the zeros represent the available squares, not the pennies.

Extra credit is available for other interesting examples.



Related tasks

 A* search algorithm
 Knight's tour
 N-queens problem
 Solve a Hidato puzzle
 Solve a Hopido puzzle
 Solve a Numbrix puzzle
 Solve the no connection puzzle


import sat.
 
main =>
    S = {".000....",
         ".0.00...",
         ".0000000",
         "000..0.0",
         "0.0..000",
         "1000000.",
         "..00.0..",
         "...000.."},
    MaxR = len(S),
    MaxC = len(S[1]),
    M = new_array(MaxR,MaxC),
    StartR = _,    % make StartR and StartC global
    StartC = _,   
    foreach (R in 1..MaxR)
        fill_row(R, S[R], M[R], 1, StartR, StartC)
    end,
    NZeros = len([1 : R in 1..MaxR, C in 1..MaxC, M[R,C] == 0]),
    M :: 0..MaxR*MaxC-NZeros,
    Vs = [{(R,C),1} : R in 1..MaxR, C in 1..MaxC, M[R,C] !== 0],
    Es = [{(R,C),(R1,C1),_} : R in 1..MaxR, C in 1..MaxC, M[R,C] !== 0,
                              neibs(M,MaxR,MaxC,R,C,Neibs),
                              (R1,C1) in Neibs, M[R1,C1] !== 0],
    hcp(Vs,Es),
    foreach ({(R,C),(R1,C1),B} in Es)
        B #/\ (R1 #!= StartR #\/ C1 #!= StartC) #=> M[R1,C1] #= M[R,C]+1
    end,
    solve(M),
    foreach (R in 1..MaxR)
        foreach (C in 1..MaxC)
            if M[R,C] == 0 then
                printf("%4c", '.')
            else
                printf("%4d", M[R,C])
            end
        end,
        nl
    end.
 
neibs(M,MaxR,MaxC,R,C,Neibs) =>
    Connected = [(R+1, C+2),
                 (R+1, C-2),
                 (R-1, C+2),
                 (R-1, C-2),
                 (R+2, C+1),
                 (R+2, C-1),
                 (R-2, C+1),
                 (R-2, C-1)],
    Neibs = [(R1,C1) : (R1,C1) in Connected,
                       R1 >= 1, R1 =< MaxR, C1 >= 1, C1 =< MaxC,
                       M[R1,C1] !== 0].
 
 
fill_row(_R, [], _Row, _C, _StartR, _StartC) => true.
fill_row(R, ['.'|Str], Row, C, StartR, StartC) =>
    Row[C] = 0,
    fill_row(R,Str, Row, C+1, StartR, StartC).
fill_row(R, ['0'|Str], Row, C, StartR, StartC) =>
    fill_row(R, Str, Row, C+1, StartR, StartC).
fill_row(R, ['1'|Str], Row, C, StartR, StartC) =>
    Row[C] = 1,
    StartR = R,
    StartC = C,
    fill_row(R, Str, Row, C+1, StartR, StartC).
 