155 lines
4.5 KiB
Text
155 lines
4.5 KiB
Text
integer w, h
|
|
|
|
string board, target
|
|
|
|
procedure new_board()
|
|
board = ""
|
|
h = prompt_number("Enter number of rows(1..9):",{1,9})
|
|
w = prompt_number("Enter number of columns(1..26):",{1,26})
|
|
string line = ""
|
|
for j=1 to w do line &= 'A'+j-1 end for
|
|
board = " "&line&"\n"
|
|
for i=1 to h do
|
|
line = '0'+i&" "
|
|
for j=1 to w do line &= '0'+rand(2)-1 end for
|
|
board &= line&"\n"
|
|
end for
|
|
end procedure
|
|
|
|
procedure show_bt()
|
|
sequence sb = split(board,'\n'),
|
|
st = split(target,'\n')
|
|
printf(1,"board:%s target:%s\n",{sb[1],st[1]})
|
|
for i=2 to length(sb)-1 do
|
|
printf(1," %s %s\n",{sb[i],st[i]})
|
|
end for
|
|
end procedure
|
|
|
|
procedure flip(integer ch, bool bShow=true)
|
|
integer k
|
|
if ch>='A' and ch<='A'+w-1 then
|
|
-- flip_column
|
|
ch = ch-'A'+1
|
|
for i=1 to h do
|
|
k = 2+ch+i*(w+3)
|
|
board[k] = '0'+'1'-board[k]
|
|
end for
|
|
k = 2+ch
|
|
elsif ch>='1' and ch<='0'+h then
|
|
-- flip_row
|
|
ch -= '0'
|
|
for i=1 to w do
|
|
k = 2+i+(ch)*(w+3)
|
|
board[k] = '0'+'1'-board[k]
|
|
end for
|
|
k = 1+(ch)*(w+3)
|
|
else
|
|
?9/0 -- sanity check
|
|
end if
|
|
if bShow then
|
|
integer wasch = board[k]
|
|
board[k] = '*'
|
|
show_bt()
|
|
board[k] = wasch
|
|
end if
|
|
end procedure
|
|
|
|
procedure scramble_board()
|
|
integer lim = 10000
|
|
while 1 do
|
|
for i=1 to lim do
|
|
if rand(2)=1 then
|
|
flip('A'-1+rand(w),false)
|
|
else
|
|
flip('0'+rand(h),false)
|
|
end if
|
|
end for
|
|
if board!=target then exit end if
|
|
lim -= 1 -- sidestep the degenerate 1x1 case
|
|
end while
|
|
end procedure
|
|
|
|
function solve_board()
|
|
-- not guaranteed optimal (the commented-out length check clogs it on larger boards)
|
|
string original = board, moves
|
|
sequence next = {{0,board,""}},
|
|
legal_moves = tagset('A'+w-1,'A')&tagset('0'+h,'1')
|
|
atom t2 = time()+2 -- in case board is illegal/unsolveable
|
|
while time()<t2 do
|
|
for lm=1 to length(legal_moves) do
|
|
integer c = legal_moves[lm]
|
|
{?,board,moves} = next[1]
|
|
flip(c,false)
|
|
moves &= c
|
|
if board = target then
|
|
board = original
|
|
return moves
|
|
end if
|
|
next = append(next,{sum(sq_eq(board,target)),board,moves})
|
|
for i=length(next) to 3 by -1 do
|
|
if next[i][1]<=next[i-1][1] then exit end if
|
|
-- if length(next[i][3])>length(next[i-1][3]) then exit end if
|
|
{next[i-1],next[i]} = {next[i],next[i-1]}
|
|
end for
|
|
end for
|
|
next = next[2..$]
|
|
end while
|
|
board = original
|
|
return 0
|
|
end function
|
|
|
|
constant ESC = #1B
|
|
|
|
procedure main()
|
|
integer moves = 0, solves = 0, ch
|
|
bool took_hint = false
|
|
new_board()
|
|
target = board
|
|
scramble_board()
|
|
show_bt()
|
|
object soln = solve_board()
|
|
while 1 do
|
|
string solve = iff(string(soln)?sprintf(" solveable in %d,",length(soln)):"")
|
|
printf(1,"moves taken %d,%s enter your move (A..%c or 1..%c) or ?:",{moves,solve,'A'+w-1,'0'+h})
|
|
while 1 do
|
|
ch = upper(wait_key())
|
|
if ch<=#FF then exit end if -- (ignore control keys)
|
|
end while
|
|
printf(1,"%c\n",ch)
|
|
if (ch>='A' and ch<='A'+w-1)
|
|
or (ch>='1' and ch<='0'+h) then
|
|
flip(ch)
|
|
if board=target then
|
|
printf(1,"\nWell %s!\n\n",{iff(took_hint?"cheated","done")})
|
|
exit
|
|
end if
|
|
moves += 1
|
|
soln = iff(string(soln) and ch=soln[1]?soln[2..$]:solve_board())
|
|
elsif string(soln) and
|
|
(ch='H' -- (nb consumed above if w>=8)
|
|
or ch='.') then
|
|
took_hint = true
|
|
printf(1,"hint: %c\n",soln[1])
|
|
elsif ch='Q' -- (nb consumed above if w>=17)
|
|
or ch=ESC then
|
|
exit
|
|
elsif string(soln) and
|
|
(ch='S' -- (nb consumed above if w>=19)
|
|
or ch='!') then
|
|
for i=1 to length(soln) do
|
|
printf(1,"auto-solving, move %d:\n",i)
|
|
flip(soln[i])
|
|
sleep(2)
|
|
end for
|
|
exit
|
|
else
|
|
puts(1,"press ")
|
|
if string(soln) then
|
|
puts(1,"'!' (or 's' if width<19) to solve the board automatically,\n")
|
|
puts(1," '.' (or 'h' if width<8) to show hint,\n")
|
|
end if
|
|
puts(1," escape (or 'q' if width<17) to quit\n")
|
|
end if
|
|
end while
|
|
end procedure
|
|
main()
|