print('eq(X,X).')
print('ne(X,X):-!,fail.')
print('ne(X,_).')
print('ex(_,[]).')
print('ex(X,[X|_]):-!,false.')
print('ex(X,[_|L]):-ex(X,L).')
print('in(X,[X|L],L).')
print('in(X,[Y|L],[Y|M]):-in(X,L,M).')
print('match([],[]).')
print('match([X|L],Q):-in(X,Q,M),match(L,M).')

function V(i,j) return 'V'..i..'_'..j end

function adj(i,j,n,m,reg)
    local eq=true
    local t,vij = '', V(i,j)
    local function f(a,b)
        local x,y = a+i,b+j
        local vxy = V(x,y)
        if vij~=vab and 1<=x and 2<=y and x<=n and y<=m and not(reg[vij]==reg[vxy])
        then
            if eq then
                print('','ne('..vij..','..vxy..'),')
            else
                t = t .. ',' .. vxy
            end
        end
    end
    f(0,1)
    f(1,-1)
    f(1,0)
    f(1,1)
    if eq==false and t~='' then
        print('','ex('..vij..', ['..t:sub(2)..']),')
    end
end

function suguru(n,m,str)
    print('suguru([')
    for i=1,n do
        local t='['..V(i,1)
        for j=2,m do
            t = t .. ',' .. V(i,j)
        end
        print(t..']'..(i<n and ', ' or ']) :-'))
    end
    -- cree les regions et ajoute les indice (au début = plus rapide)
    local region, hint, var2reg = {},{},{}
    for i=1,n do
        for j=1,m do
            local idx = ((i-1)*m + j)*2-1
            local reg, val = str:sub(idx,idx), str:sub(idx+1,idx+1)
            region[reg] = region[reg] or {}
            var2reg[V(i,j)] = reg
            table.insert(region[reg], V(i,j))
            if "1"<=val and val<="5" then
                hint[V(i,j)] = val
                print('',"eq("..V(i,j)..', '..val..'),')
            end
        end
    end
    if false then
        -- reindex les regions dans un tableau indexe (pour le tri)
        local t = {}
        for k,r in pairs(region) do
            table.insert(t,r)
        end
        region = t
        -- on trie les regions par taille
        table.sort(region, function(a,b) return #a>#b end)
    end
    -- contrainte de region
    for _,r in pairs(region) do
        local vars,vals={},{}
        for i=1,#r do vals[i] = true end
        for i,v in ipairs(r) do
            if hint[v] then
                vals[tonumber(hint[v])] = nil
            else
                table.insert(vars,v)
            end
        end
        local t={}
        for i=1,#r do if vals[i] then table.insert(t,i) end end
        print('','match(['.. table.concat(vars,',')..'], ['..table.concat(t,',')..']),')
        -- contraintes d'adjacence
        -- for _,v in ipairs(r) do
            -- local i,j = v:match('V(%d+)_(%d+)')
            -- adj(tonumber(i),tonumber(j),n,m,var2reg)
        -- end
    end
    for _,r in pairs(region) do
        -- contraintes d'adjacence
        for _,v in ipairs(r) do
            local i,j = v:match('V(%d+)_(%d+)')
            adj(tonumber(i),tonumber(j),n,m,var2reg)
        end
    end
    -- for i=1,n do
        -- for j=1,m do
            -- adj(i,j,n,m,var2reg)
        -- end
    -- end
    print('','true.')
    -- affichage du suguru
    print("describe:-write('solving...\\n'),")
    local s='+'
    for i=1,m do s=s..'---+' end print('',"write('"..s.."\\n'),")
    for i=1,n do
        s='|'
        for j=1,m-1 do
            local v1,v2 = V(i,j),V(i,j+1)
            s = s..' ' ..(hint[v1] or ' ')..' '..
                   (var2reg[v1]==var2reg[v2] and ' ' or '|')
        end
        s = s..' '..(hint[V(i,m)] or ' ')..' |'
        print('',"write('"..s.."\\n'),")
        s='+'
        for j=1,m do
            local v1,v2 = V(i,j),V(i+1,j)
            s = s..(var2reg[v1]==var2reg[v2] and '   ' or '---')..'+'
        end
        print('',"write('"..s.."\\n'),")
    end
    print('','true.')
end

function gen(list)
    local s= ''
    for _,v in ipairs(list) do
        s = s .. v
    end
    suguru(#list,#list[1]/2,s)
end

if true then
suguru(5,5,
"A1AAAAB5BB" ..
"AACCCCDDBB" ..
"C1CCD2DDB4" ..
"CCDDDDEEBB" ..
"EEE3EEEEFF")
elseif true then
gen{
"A2BBCCCCCCCCDD",
"AABBB4EEDDDDDD",
"AABBBBEEFFF3DD",
"AAGGHHIIIIFFFF",
"GGG5GGJJI2IIFF",
"K2KKG3JJJJJJJJ",
"KKKKLLL4LLLLL3",
nil}
else
gen{
'AAAAAABBBBBBCCCC',
'DDDDDDDDEEBBBBFF',
'GGHHDDEEEEIIIIFF',
'GGHHHHEEEEIIFFFF',
'JJHHHHKKIIIIFFLL',
'JJKKKKKKMMLLLLLL',
'JJNNKKMMMMOOOOLL',
'PPPPPPPPMMMMOOOO'
}
end

print('w([]).')
print("w([X|L]):-write(X),write('\\n'),w(L).")

print('r:-reconsult(suguru).')
print('h:-halt.')

print("x:-describe,time(suguru(L)),w(L).")