################################################################################
#
# Sedoku -- a sudoku (blech) solver in sed
#
# The solver works in two stages. First, row, column and square consistency is
# enforced. Then, if this does not solve the puzzle, a search is performed by
# choosing a number where there is a range of possibilities and enforcing
# consistency
#
# All the consistency work is performed in the pattern space, leaving the hold
# space free for the search.
#
# Each square is stored as 11 chars: X followed by a list of possible numbers
# in the correct position, followed by a Y. For instance, X--34--789Y indicates
# that in that square, the numbers 3,4,7,8,9 are consistent with all other
# numbers.
# As a special case, when there is only one number present, X is replaced by x
# The fixed width format of each square makes it easy to index a particluar row
# column or 3x3 square.
#
# Any squares which have only 1 allowed number (ie solved squares) are used to
# eliminate numbers from the available list in all other related squares (row
# column, square).
#
#
# See ###Elimination
#
# When an elimination is being performed, 9 squares are `active' in the
# elimination, and these have the [xX] replaced by [aA]. Then, the program looks
# for any solved numbers and removed this number from the list of all active
# but unsolved squared. After this, any solved squares are flagged by replacing
# A with a. This is looped over until no more eliminations are made.
#
# First, ranges of squares to be activated are marked between S,E pairs, and a
# state letter is added to the beginning of the buffer to mark the current
# state. After elimination on the active squares, the markers are moved to
# activate the next set of squares.
#
# See ###Search
#
# The hold space is used to maintain a <stack/queue> of puzzle solutions.
# Currently a queue is used (bredth first search) since I've never seen a
# puzzle which reaquies >1 search depth.
#
# The search is performed by replacing an incomplete cell with a complete
# one and rerunning the solver. The number to be tried is marked with a Q
# The Q is moved along one available place. Cells in which all of the
# numbers have been tried have X replaced with K. If Q goes beyond the
# last number in a cell, it is removed, the cell is changed to K and a
# new Q is put in the next place.
#
# The top of the quee is moved in to the pattern space and changed in
# to a form suitable for elimination. If is is consistent but unsolved,
# then it is put back in to the queue. Otherwise, the next thing in the
# queue is examined.
#Store as e.g. A12--5-7-9B
#Replace with lcase if number is exact
s/./X&Y/g
s/1/1--------/g
s/2/-2-------/g
s/3/--3------/g
s/4/---4-----/g
s/5/----5----/g
s/6/-----6---/g
s/7/------7--/g
s/8/-------8-/g
s/9/--------9/g
s/\./123456789/g
H
1,8 d
#Empty the hold space for later
s/.*//
x
s/\n//g
#Mark known squares
s/X\(-*[0-9]-*\)Y/x\1Y/g
s/$/Z/
#a Z$ signifies no elminiation happened. z$ signifies that they did.
#Mark active squares with aA instead of xX
#First char is the machine state
#rR means row elimination is active. R for first row, r for the rest
#cC means col elimination is active.
#defghijkl for square elimination
:search
#Start with row elimination first
s/^/R/
#Mark active regions with (S)tart (E)nd pairs
:loop
#Rows
/^r/ {
s/S//
s/E/S/
}
/^R/ s/^R/rS/
/r/ s/S.\{99\}/&E/
/r/ {
#Check to see if row elimination has finished
/E/ !{
#Yes, so do Column elimination
#Remove row markers
s/[rS]//g
#Place column markers
s/\(.\{11\}\)\(.\{88\}\)/S\1E\2/g
s/^/C/
}
}
#Move all column markers across by 1 (11 chars)
/c/ s/S\([^E]*\)E\(.\{11\}\)/\1S\2E/g
s/^C/c/
/c/ {
#Check to see if there is an S anywhere in the first row. If not, then columns are done
/^c[^S]\{99\}/ {
#Remove markers
s/[cSE]//g
#Put in first square markers
s/\(.\{33\}\)\(.\{66\}\)\(.\{33\}\)\(.\{66\}\)\(.\{33\}\)\(.\{66\}\)/S\1E\2S\3E\4S\5E\6/
#Put in state machine state
s/^/d/
}
}
#Move square markers
/^[e-m]/ {
#Start pos
#0 0
#33 33
#66 66
#297 255 + 42
#330 255 + 75
#363 255 + 108
#594 255 + 255 + 84
#627 255 + 255 + 117
#660 255 + 255 + 150
#Sed on OpenBSD requires that for \{X\}, 0 < X < 256
s/[SE]//g
s/^\(l.\{255\}.\{255\}.\{150\}\)\(.\{33\}\)\(.\{66\}\)\(.\{33\}\)\(.\{66\}\)\(.\{33\}\)/\1S\2E\3S\4E\5S\6E/
s/^\(k.\{255\}.\{255\}.\{117\}\)\(.\{33\}\)\(.\{66\}\)\(.\{33\}\)\(.\{66\}\)\(.\{33\}\)/\1S\2E\3S\4E\5S\6E/
s/^\(j.\{255\}.\{255\}.\{84\}\)\(.\{33\}\)\(.\{66\}\)\(.\{33\}\)\(.\{66\}\)\(.\{33\}\)\(.\{66\}\)/\1S\2E\3S\4E\5S\6E\7/
s/^\(i.\{255\}.\{108\}\)\(.\{33\}\)\(.\{66\}\)\(.\{33\}\)\(.\{66\}\)\(.\{33\}\)\(.\{66\}\)/\1S\2E\3S\4E\5S\6E\7/
s/^\(h.\{255\}.\{75\}\)\(.\{33\}\)\(.\{66\}\)\(.\{33\}\)\(.\{66\}\)\(.\{33\}\)\(.\{66\}\)/\1S\2E\3S\4E\5S\6E\7/
s/^\(g.\{255\}.\{42\}\)\(.\{33\}\)\(.\{66\}\)\(.\{33\}\)\(.\{66\}\)\(.\{33\}\)\(.\{66\}\)/\1S\2E\3S\4E\5S\6E\7/
s/^\(f.\{66\}\)\(.\{33\}\)\(.\{66\}\)\(.\{33\}\)\(.\{66\}\)\(.\{33\}\)\(.\{66\}\)/\1S\2E\3S\4E\5S\6E\7/
s/^\(e.\{33\}\)\(.\{33\}\)\(.\{66\}\)\(.\{33\}\)\(.\{66\}\)\(.\{33\}\)\(.\{66\}\)/\1S\2E\3S\4E\5S\6E\7/
}
#Increment the state flag
y/defghijklm/efghijklmn/
/^n/ {
#Squares have finished
s/[nSE]//g
#If no substutions have taken place...
/Z/ b done
#else, go back to elimination on rows
s/^/R/
#Reset elminiation marker
s/z/Z/
b loop
}
################################################################################
#
###Elimination loop
#
#Mark squares between SE pairs with aA insetad of xX
:markloop
t markloop
s/S\([^E]*\)X/S\1A/g
s/S\([^E]*\)x/S\1a/g
t markloop
#Perform elimination
b elim
:change
#An elimination happened, so mark it with a z
s/Z/z/
:elim
t elim
/a1/ s/\(A\)1/\1-/g
/a-2/ s/\(A.\)2/\1-/g
/a--3/ s/\(A..\)3/\1-/g
/a---4/ s/\(A...\)4/\1-/g
/a----5/ s/\(A....\)5/\1-/g
/a-----6/ s/\(A.....\)6/\1-/g
/a------7/ s/\(A......\)7/\1-/g
/a-------8/ s/\(A.......\)8/\1-/g
/a--------9/ s/\(A........\)9/\1-/g
#Check for errors
/[aA]---------/ b bork
/a1.*a1/ b bork
/a-2.*a-2/ b bork
/a--3.*a--3/ b bork
/a---4.*a---4/ b bork
/a----5.*a----5/ b bork
/a-----6.*a-----6/ b bork
/a------7.*a------7/ b bork
/a-------8.*a-------8/ b bork
/a--------9.*a--------9/ b bork
#Mark newly solved squares as solved
s/A\(-*[0-9]-*\)Y/a\1Y/g
t change
#Unmark active squares
y/aA/xX/
b loop
################################################################################
#Inconsistent state
:bork
x
#Hold space empty -- first time through -- broken puzzle
/^$/ {
s/.*/Broken1!/
q
}
#Else, just go and try the next thing
b next
###Search
:done
#No unsolved squares---puzzle is finished!
/X/ !b end
1000 {
s/.\{33\}/& /g
s/.\{108\}/&\
/g
s/.\{255\}.\{71\}/&\
/g
s/[xXY]/ /g
q
}
#Hold space seperates puzzles with #
s/z/Z/
#Append the puzzle to the queue
s/^/#/
H
x
s/\n//g
#Move the end of the queue to the beginning
#bredth first search
s/\(.*\)\(#[^#]*\)$/\2\1/
#Next number to try is marked with a Q
#Only X cells need to be tried. Fully searched
#X cells are changed to K cells.
:next
#Move the marker (if present)
s/Q\([0-9]\)\(-*\)\([0-9Y][^#]*\)$/\1\2Q\3/
#Marker reached the end of the cell, flag cell and remove marker
s/X\(.........\)QY\([^#]*\)$/K\1Y\2/
#If necessary, place marker in next unchecked cell
/Q[^#]*$/ !s/\(X-*\)\([0-9][-0-9]*Y[^#]*\)$/\1Q\2/
#Was this pattern exhausted?
/#[^X#]*$/ {
#Remove it and go again
s/#[^#]*//
/^$/ {
s/.*/Broken!/
q
}
b next
}
x
#Get the top of the stack and put it in a form for processing
g
s/.*#//g
y/K/X/
s/XQ........./x1--------/
s/X.Q......../x-2-------/
s/X..Q......./x--3------/
s/X...Q....../x---4-----/
s/X....Q...../x----5----/
s/X.....Q..../x-----6---/
s/X......Q.../x------7--/
s/X.......Q../x-------8-/
s/X........Q./x--------9/
#Now attempt to solve this version of the puzzle
b search
:end
s/X[-0-9]\{9\}Y/./g
s/x-*\([0-9]\)-*Y/\1/g
s/.\{9\}/&\
/g
s/Z//
q
#
# The End :-)
#
################################################################################
### colorized by sedsed, a debugger and code formatter for sed scripts
### original script: