187 lines
6.8 KiB
Awk
187 lines
6.8 KiB
Awk
# syntax: GAWK -f SUDOKU_RC.AWK
|
|
BEGIN {
|
|
# row1 row2 row3 row4 row5 row6 row7 row8 row9
|
|
# puzzle = "111111111 111111111 111111111 111111111 111111111 111111111 111111111 111111111 111111111" # NG duplicate hints
|
|
# puzzle = "1........ ..274.... ...5....4 .3....... 75....... .....96.. .4...6... .......71 .....1.30" # NG can't use zero
|
|
# puzzle = "1........ ..274.... ...5....4 .3....... 75....... .....96.. .4...6... .......71 .....1.39" # no solution
|
|
# puzzle = "1........ ..274.... ...5....4 .3....... 75....... .....96.. .4...6... .......71 .....1.3." # OK
|
|
puzzle = "123456789 456789123 789123456 ......... ......... ......... ......... ......... ........." # OK
|
|
gsub(/ /,"",puzzle)
|
|
if (length(puzzle) != 81) { error("length of puzzle is not 81") }
|
|
if (puzzle !~ /^[1-9\.]+$/) { error("only 1-9 and . are valid") }
|
|
if (gsub(/[1-9]/,"&",puzzle) < 17) { error("too few hints") }
|
|
if (errors > 0) {
|
|
exit(1)
|
|
}
|
|
plot(puzzle,"unsolved")
|
|
if (dup_hints_check(puzzle) == 1) {
|
|
if (solve(puzzle) == 1) {
|
|
dup_hints_check(sos)
|
|
plot(sos,"solved")
|
|
printf("\nbef: %s\naft: %s\n",puzzle,sos)
|
|
exit(0)
|
|
}
|
|
else {
|
|
error("no solution")
|
|
}
|
|
}
|
|
exit(1)
|
|
}
|
|
function dup_hints_check(ss, esf,msg,Rarr,Carr,Barr,i,r_row,r_col,r_pos,r_hint,c_row,c_col,c_pos,c_hint,box) {
|
|
esf = errors # errors so far
|
|
for (i=0; i<81; i++) {
|
|
# row
|
|
r_row = int(i/9) + 1 # determine row: 1..9
|
|
r_col = i%9 + 1 # determine column: 1..9
|
|
r_pos = i + 1 # determine hint position: 1..81
|
|
r_hint = substr(ss,r_pos,1) # extract 1 character; the hint
|
|
Rarr[r_row,r_hint]++ # save row
|
|
# column
|
|
c_row = i%9 + 1 # determine row: 1..9
|
|
c_col = int(i/9) + 1 # determine column: 1..9
|
|
c_pos = (c_row-1) * 9 + c_col # determine hint position: 1..81
|
|
c_hint = substr(ss,c_pos,1) # extract 1 character; the hint
|
|
Carr[c_col,c_hint]++ # save column
|
|
# box (there has to be a better way)
|
|
if ((r_row r_col) ~ /[123][123]/) { box = 1 }
|
|
else if ((r_row r_col) ~ /[123][456]/) { box = 2 }
|
|
else if ((r_row r_col) ~ /[123][789]/) { box = 3 }
|
|
else if ((r_row r_col) ~ /[456][123]/) { box = 4 }
|
|
else if ((r_row r_col) ~ /[456][456]/) { box = 5 }
|
|
else if ((r_row r_col) ~ /[456][789]/) { box = 6 }
|
|
else if ((r_row r_col) ~ /[789][123]/) { box = 7 }
|
|
else if ((r_row r_col) ~ /[789][456]/) { box = 8 }
|
|
else if ((r_row r_col) ~ /[789][789]/) { box = 9 }
|
|
else { box = 0 }
|
|
Barr[box,r_hint]++ # save box
|
|
}
|
|
dup_hints_print(Rarr,"row")
|
|
dup_hints_print(Carr,"column")
|
|
dup_hints_print(Barr,"box")
|
|
return((errors == esf) ? 1 : 0)
|
|
}
|
|
function dup_hints_print(arr,rcb, hint,i) {
|
|
# rcb - Row Column Box
|
|
for (i=1; i<=9; i++) { # "i" is either the row, column, or box
|
|
for (hint=1; hint<=9; hint++) { # 1..9 only; don't care about "." place holder
|
|
if (arr[i,hint]+0 > 1) { # was a digit specified more than once
|
|
error(sprintf("duplicate hint in %s %d",rcb,i))
|
|
}
|
|
}
|
|
}
|
|
}
|
|
function plot(ss,text1,text2, a,b,c,d,ou) {
|
|
# 1st call prints the unsolved puzzle.
|
|
# 2nd call prints the solved puzzle
|
|
printf("| - - - + - - - + - - - | %s\n",text1)
|
|
for (a=0; a<3; a++) {
|
|
for (b=0; b<3; b++) {
|
|
ou = "|"
|
|
for (c=0; c<3; c++) {
|
|
for (d=0; d<3; d++) {
|
|
ou = sprintf("%s %1s",ou,substr(ss,1+d+3*c+9*b+27*a,1))
|
|
}
|
|
ou = ou " |"
|
|
}
|
|
print(ou)
|
|
}
|
|
printf("| - - - + - - - + - - - | %s\n",(a==2)?text2:"")
|
|
}
|
|
}
|
|
function solve(ss, a,b,c,d,e,r,co,ro,bi,bl,nss) {
|
|
i = 0
|
|
# first, use some simple logic to fill grid as much as possible
|
|
do {
|
|
i++
|
|
didit = 0
|
|
delete nr
|
|
delete nc
|
|
delete nb
|
|
delete ca
|
|
for (a=0; a<81; a++) {
|
|
b = substr(ss,a+1,1)
|
|
if (b == ".") { # construct row, column and block at cell
|
|
c = a % 9
|
|
r = int(a/9)
|
|
ro = substr(ss,r*9+1,9)
|
|
co = ""
|
|
for (d=0; d<9; d++) { co = co substr(ss,d*9+c+1,1) }
|
|
bi = int(c/3)*3+(int(r/3)*3)*9+1
|
|
bl = ""
|
|
for (d=0; d<3; d++) { bl = bl substr(ss,bi+d*9,3) }
|
|
e = 0
|
|
# count non-occurrences of digits 1-9 in combined row, column and block, per row, column and block, and flag cell/digit as candidate
|
|
for (d=1; d<10; d++) {
|
|
if (index(ro co bl, d) == 0) {
|
|
e++
|
|
nr[r,d]++
|
|
nc[c,d]++
|
|
nb[bi,d]++
|
|
ca[c,r,d] = bi
|
|
}
|
|
}
|
|
if (e == 0) { # in case no candidate is available, give up
|
|
return(0)
|
|
}
|
|
}
|
|
}
|
|
# go through all cell/digit candidates
|
|
# hidden singles
|
|
for (crd in ca) {
|
|
# a candidate may have been deleted after the loop started
|
|
if (ca[crd] != "") {
|
|
split(crd,spl,SUBSEP)
|
|
c = spl[1]
|
|
r = spl[2]
|
|
d = spl[3]
|
|
bi = ca[crd]
|
|
a = c + r * 9
|
|
# unique solution if at least one non-occurrence counter is exactly 1
|
|
if ((nr[r,d] == 1) || (nc[c,d] == 1) || (nb[bi,d] == 1)) {
|
|
ss = substr(ss,1,a) d substr(ss,a+2,length(ss))
|
|
didit = 1
|
|
# remove candidates from current row, column, block
|
|
for (e=0; e<9; e++) {
|
|
delete ca[c,e,d]
|
|
delete ca[e,r,d]
|
|
}
|
|
for (e=0; e<3; e++) {
|
|
for (b=0; b<3; b++) {
|
|
delete ca[int(c/3)*3+b,int(r/3)*3+e,d]
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|
|
} while (didit == 1)
|
|
# second, pick a viable solution for the next empty cell and see if it leads to a solution
|
|
a = index(ss,".")-1
|
|
if (a == -1) { # no more empty cells, done
|
|
sos = ss
|
|
return(1)
|
|
}
|
|
else {
|
|
c = a % 9
|
|
r = int(a/9)
|
|
# concatenate current row, column and block
|
|
# row
|
|
co = substr(ss,r*9+1,9)
|
|
# column
|
|
for (d=0; d<9; d++) { co = co substr(ss,d*9+c+1,1) }
|
|
# block
|
|
c = int(c/3)*3+(int(r/3)*3)*9+1
|
|
for (d=0; d<3; d++) { co = co substr(ss,c+d*9,3) }
|
|
for (b=1; b<10; b++) { # get a viable digit
|
|
if (index(co,b) == 0) { # check if candidate digit already exists
|
|
# is viable, put in cell
|
|
nss = substr(ss,1,a) b substr(ss,a+2,length(ss))
|
|
d = solve(nss) # try to solve
|
|
if (d == 1) { # if successful, return
|
|
return(1)
|
|
}
|
|
}
|
|
}
|
|
}
|
|
return(0) # no digits viable, no solution
|
|
}
|
|
function error(message) { printf("error: %s\n",message) ; errors++ }
|