// 15 Puzzle Solver
//https://rosettacode.org/wiki/15_puzzle_solver
// Requires FutureBasic 7.0.30 or later

begin globals
  int Nr(15), Nc(15), n, un, N0(99), N3(99), N4(99)
  UInt64 N2(99)
end globals

def fn fY as BOOL
void def fn fI
void def fn fG
void def fn fE
void def fn fL

local fn fN1 as BOOL
  if ( N3(n) != _"u" && N0(n) / 4 < 3 )
    fn fI
    n++
    if ( fn fY ) then return YES
    n--
  end if

  if ( N3(n) != _"d" && N0(n) / 4 > 0 )
    fn fG
    n++
    if ( fn fY ) then return YES
    n--
  end if

  if ( N3(n) != _"l" && N0(n) % 4 < 3 )
    fn fE
    n++
    if ( fn fY ) then return YES
    n--
  end if

  if ( N3(n) != _"r" && N0(n) %4 > 0 )
    fn fL
    n++
    if ( fn fY ) then return YES
    n--
  end if
end fn = NO

void local fn fI
  int g = ( 11 - N0(n)) * 4
  UInt64 a = N2(n) & ((UInt64)15 << g)
  N0(n + 1) = N0(n) + 4
  N2(n + 1) = N2(n) - a + (a << 16)
  N3(n + 1) = _"d"
  if ( Nr(a >> g) <= N0(n) / 4 )
    N4(n + 1) = N4(n)
  else
    N4(n + 1) = N4(n) + 1
  end if
end fn

void local fn fG
  int g = (19 - N0(n)) * 4
  UInt64 a = N2(n) & ((UInt64)15 << g)
  N0(n + 1) = N0(n) - 4
  N2(n + 1) = N2(n) - a + (a >> 16)
  N3(n + 1) = _"u"
  if ( Nr(a >> g) >= N0(n) / 4 )
    N4(n + 1) = N4(n)
  else
    N4(n + 1) = N4(n) + 1
  end if
end fn

void local fn fE
  int g = (14 - N0(n)) * 4
  UInt64 a = N2(n) & ((UInt64)15 << g)
  N0(n + 1) = N0(n) + 1
  N2(n + 1) = N2(n) - a + (a << 4)
  N3(n + 1) = _"r"
  if ( Nc(a >> g) <= N0(n) % 4 )
    N4(n + 1) = N4(n)
  else
    N4(n + 1) = N4(n) + 1
  end if
end fn

void local fn fL
  int g = (16 - N0(n)) * 4
  UInt64 a = N2(n) & ((UInt64)15 << g)
  N0(n + 1) = N0(n) - 1
  N2(n + 1) = N2(n) - a + (a >> 4)
  N3(n + 1) = _"l"
  if ( Nc(a >> g) >= N0(n) % 4 )
    N4(n + 1) = N4(n)
  else
    N4(n + 1) = N4(n) + 1
  end if
end fn

local fn fY as BOOL
  if ( N4(n) < un ) then return fn fN1
  if ( N2(n) == 0x123456789abcdef0 )
    printf @"Solution found in %d moves:",n
    for int g = 1 to n
      printf @"%c\b",N3(g)
    next
    print
    return YES
  end if
  if ( N4(n) == un ) then return fn fN1
end fn = NO

void local fn Solve( initN as int, initG as UInt64 )
  int tempNr(15) = {3,0,0,0,0,1,1,1,1,2,2,2,2,3,3,3}
  int tempNc(15) = {3,0,1,2,3,0,1,2,3,0,1,2,3,0,1,2}

  fn memcpy(@Nr(0),@tempNr(0),sizeof(int)*16)
  fn memcpy(@Nc(0),@tempNc(0),sizeof(int)*16)

  n = 0
  un = 0

  N0(0) = initN
  N2(0) = initG

  while ( !fn fY )
    un++
  wend
end fn


window 1, @"15 Puzzle Solver"
windowcenter(1)
WindowSetBackgroundColor(1,fn ColorBlack)

text ,14,fn colorWhite
Print "Puzzle: "; "fe169b4c0a73d852"

text ,14,fn colorYellow
print
print @"15 14 1  6"
print @" 9 11 4 12"
print @" 0 10 7  3"
print @"13  8 5  2"
print
text ,14,fn colorWhite

CFStringRef ComputerChip = unix @"sysctl -n machdep.cpu.brand_string"

CFTimeInterval t : t = fn CACurrentMediaTime
fn Solve( 8, 0xfe169b4c0a73d852 )
CFTimeInterval CurrentTime = fn CACurrentMediaTime-t

print
text ,14,fn colorYellow
print
print @" 1  2  3  4"
print @" 5  6  7  8"
print @" 9 10 11 12"
print @"13 14 15  0"
print
text ,14,fn colorWhite

print : printf @"Compute time: %.3f seconds",(CurrentTime)
print ComputerChip

HandleEvents