Nonogram solver: Difference between revisions
→{{header|Phix}}
Line 1,217:
. . . . . . . . . . . . . . . . . # # # # # # # #
. . . . . . . . . . . . . . . . . . # # # # # # #</pre>
=={{header|Phix}}==
Deduction only, no exhaustive search.
<lang Phix>sequence x, y, grid
integer unsolved
function count_grid()
integer res = length(x)*length(y)
for i=1 to length(x) do
for j=1 to length(y) do
res -= grid[i][j]!='?'
end for
end for
return res
end function
function match_mask(string neat, string mask, integer ms, integer me)
for i=ms to me do
if mask[i]!='?' then
if mask[i]!=neat[i] then return 0 end if
end if
end for
return 1
end function
function innr(string mask, sequence blocks, integer mi=1, string res="", string neat=mask)
if length(blocks)=0 then
for i=mi to length(neat) do
neat[i] = ' '
end for
if match_mask(neat,mask,mi,length(mask)) then
if length(res)=0 then
res = neat
else
for i=1 to length(neat) do
if neat[i]!=res[i] then
res[i] = '?'
end if
end for
end if
end if
else
integer b = blocks[1]
blocks = blocks[2..$]
integer l = (sum(blocks)+length(blocks)-1),
e = length(neat)-l-b
for i=mi to e do
for j=i to i+b-1 do
neat[j] = '#'
end for
if i+b<=length(neat) then
neat[i+b] = ' '
end if
if match_mask(neat,mask,mi,min(i+b,length(mask))) then
res = innr(mask,blocks,i+b+1,res,neat)
end if
neat[i] = ' '
end for
end if
return res
end function
function inner(string mask, sequence blocks)
string res = innr(mask,blocks)
return iff(length(res)?res:mask)
end function
global function vmask(sequence source, integer column)
string res = repeat(' ',length(source))
for i=1 to length(source) do
res[i] = source[i][column]
end for
return res
end function
function logic()
integer wasunsolved = unsolved
for i=1 to length(x) do
grid[i] = inner(grid[i],x[i])
end for
for j=1 to length(y) do
string tmp = inner(vmask(grid,j),y[j])
for i=1 to length(tmp) do
grid[i][j] = tmp[i]
end for
end for
unsolved = count_grid()
return wasunsolved!=unsolved
end function
sequence tests=split("""
C BA CB BB F AE F A B
AB CA AE GA E C D C
F CAC ACAC CN AAA AABB EBB EAA ECCC HCCC
D D AE CD AE A DA BBB CC AAB BAA AAB DA AAB AAA BAB AAA CD BBA DA
CA BDA ACC BD CCAC CBBAC BBBBB BAABAA ABAD AABB BBH BBBD ABBAAA CCEA AACAAB BCACC ACBH DCH ADBE ADBB DBE ECE DAA DB CC
BC CAC CBAB BDD CDBDE BEBDF ADCDFA DCCFB DBCFC ABDBA BBF AAF BADB DBF AAAAD BDG CEF CBDB BBB FC
E BCB BEA BH BEK AABAF ABAC BAA BFB OD JH BADCF Q Q R AN AAN EI H G
E CB BAB AAA AAA AC BB ACC ACCA AGB AIA AJ AJ ACE AH BAF CAG DAG FAH FJ GJ ADK ABK BL CM""",'\n')
--Alternatively:
--integer fn = open("nonogram_problems.txt","r")
--tests = get_text(fn,GT_LF_STRIPPED)
--close(fn)
function unpack(string s)
sequence res = split(s)
for i=1 to length(res) do
string ri = res[i]
sequence r = {}
for j=1 to length(ri) do
r &= ri[j]-'A'+1
end for
res[i] = r
end for
return res
end function
for i=1 to length(tests) by 3 do
x = unpack(tests[i])
y = unpack(tests[i+1])
grid = repeat(repeat('?',length(y)),length(x))
unsolved = length(x)*length(y)
while unsolved do
if not logic() then
?"partial"
exit
end if
end while
puts(1,join(grid,"\n")&"\n")
end for</lang>
{{out}}
<pre style="float:left">
###
## #
### ##
## ##
######
# #####
######
#
##
</pre>
<pre style="float:left">
######
### # ###
# ### # ###
### ##############
# # #
# # ## ##
##### ## ##
##### # #
##### ### ### ###
######## ### ### ###
</pre>
<pre style="font-size: 10px; float:left">
### #
## #### #
# ### ###
## ####
### ### # ###
### ## ## # ###
## ## ## ## ##
## # # ## # #
# ## # ####
# # ## ##
## ## ########
## ## ## ####
# ## ## # # #
### ### ##### #
# # ### # # ##
## ### # ### ###
# ### ## ########
#### ### ########
# #### ## #####
# #### ## ##
#### ## #####
##### ### #####
#### # #
#### ##
### ###
</pre>
<pre>
#####
## ### ##
## ##### #
## ########
## ##### ###########
# # ## # ######
# ## # ###
## # #
## ###### ##
############### ####
########## ########
## # #### ### ######
#################
#################
##################
# ##############
# # ##############
##### #########
########
#######
</pre>
=={{header|Prolog}}==
| |||