Pasted

#!/usr/bin/awk -f 
#
# GLOBAL VARIABLES:
#   grid        - Game grid
#   row     - Horizontal slice through the grid
#   col     - Vertical slice through the grid
#   sector      - solved numbers per sector
#   setorMap    - map of sector for each cell
#   solutions   - grid of all possible solutions per unsolved cell
#   solutionsCnt    - count of possible solutions for each unsolved number per sector
#
 
BEGIN { 
    for (i=1; i <= 9; i++ ) {
        for (j=1; j <= 9; j++ ) {
            grid[i,j]=0
            sectorMap[i,j]=toSector(i,j)
        }
    }
 
 
    "tput smso" | getline SMSO
    "tput bold" | getline BOLD
    "tput rmso" | getline RMSO
    "tput clear"    | getline CLEAR
    "tput cup 0 0"  | getline HOME
    "tput cup 20 0" | getline LINE20
 
    PROMPT = ">>"
    printf "%s ", PROMPT
}
 
$1 == "help" {
    print "help, load, loadFile, step, dumpsolutions, dumpSector, dumpSectorMap, dump"
}
 
$1 == "list" {
    LIST="ls puzzle.*"
    while ( LIST | getline listing >0 ) {
        print listing
    }
    close(LIST)
}
 
####################################################################
#
#   load puzzle from a file
#
####################################################################
$1 == "loadFile" {
    fileName = $2
    print "loading " fileName
 
    clearSector()
    delete grid
    delete row
    delete col
 
    r=0;
    while ( (getline < fileName) > 0 ) {
        r++
        for (c=1; c<=NF; c++)
        {
            if ( $c != ".")
                load(r, c, $c)
        }
    }
 
    close(fileName)
}
 
####################################################################
#
#   load puzzle from command line 
#
####################################################################
$1 == "load" {
    fileName=""
    for (i=2; i<=NF; i++)
    {
        split($i,fields,",")
        load(fields[1], fields[2], fields[3])
    }
}
 
####################################################################
#
#   step through automated solution of the puzzle
#
####################################################################
$1 == "step" {
    if (solveStep()==0)
        print "no solution"
    
}
 
####################################################################
#
#   automatically solve the entire puzzle
#
####################################################################
$1 == "solve" {
    
    printf "%s", CLEAR
 
    do {
        if ( $2 != "" ) {
            system("sleep " $2)
        }
        printf "%s", HOME
 
    } while (solveStep() != 0 ) 
 
    dump()
    print "Solution Stopped"
}
 
####################################################################
#
#   validate the currently solved puzzle against a solution
#   in a file
#
####################################################################
$1 == "check" {
 
    fileName=$2
    print "checking solution against " fileName
 
    r=0
 
    while ( (getline < fileName) > 0 ) {
        r++
 
        for (c=1; c<=NF; c++)
        {
            # print "grid["r","c"]("grid[r,c]")=" $c  ## DEBUG
            if (grid[r,c] != $c) {
                dump(r,c)
                print "Error @ cell " r","c
                close(fileName)
                next
            }
        }
    }
 
    print "Congradulations, your solution is correct!"
 
    close(fileName)
}
 
####################################################################
#
#   save the current puzzle in a file
#
####################################################################
$1 == "save"        {
    for (r=1; r<=9; r++) {
        for (c=1; c<=9; c++) {
            v = grid[r,c]
            if ( v <=0 )
                v="."
            printf "%s ", v  > $2
        }
        print "" > $2
    }
    close($2)
}
 
$1 == "dumpSolution"    { dumpSolutions() }     # dump the list of solutions to output
$1 == "dumpSectorMap"   { dumpSectorMap() }     # dump the sector map to output
$1 == "dumpSector"  { dumpSectors() }       # dump all solved numbers per sector to output
$1 == "dump"        { C=$3; dump($2, $3) }      # dump the puzzle grid to output
$1 == "quit"        { exit 0 }          # exit the game
            { printf "%s ", PROMPT }
 
####################################################################
#
#   load a value into a (r)ow and (c)olumn of the puzzle grid
#
####################################################################
function load( r, c, value) {
    grid[r,c]=value
    solutions[r,c]="C"
    row[r,value]=1
    col[c,value]=1
    addToSector(sectorMap[r, c],value)
}
 
####################################################################
#
#   attempt to find the first solvable cell in the grid.
#   print the grid with the solved cell highlighted.
#
####################################################################
function solveStep() {
    plotSolutions()
 
    for ( r=1; r<=9; r++ ) {
        for ( c=1; c<=9; c++ ) {
            for ( i=1; i <= 9; i++ ) {
                if(solutions[r,c] != "C" && solutions[r,c] ~ i && solutions[r,c] !~ /,/) {
                    load(r,c,i)
                    dump(r,c)
                    print "                                   "
                    return 1
                }
        
                if ( solutions[r,c]!="C" && solutions[r,c] ~ i && solutionsCnt[sectorMap[r,c],i]==1)
                {
                    load(r,c,i)
                    dump(r,c)
                    print "                                   "
                    return 1
                }
            }
        }
    }
    
        if ( !gridSolved() ) {
        plotSolutions()
        plotTwins()
        for ( r=1; r<=9; r++ ) {
            for ( c=1; c<=9; c++ ) {
                for ( i=1; i <= 9; i++ ) {
                    if(solutions[r,c] != "C" && solutions[r,c] ~ i && solutions[r,c] !~ /,/) {
                        load(r,c,i)
                        dump(r,c)
                        print "Solved using twins..."
                        return 1
                    }
            
                    if ( solutions[r,c]!="C" && solutions[r,c] ~ i && solutionsCnt[sectorMap[r,c],i]==1)
                    {
                        load(r,c,i)
                        dump(r,c)
                        print "Solved using twins..."
                        return 1
                    }
                }
            }
        }
    }
 
    return 0
}
 
####################################################################
#
#   plot all possible solutions for all unsolved cells
#
####################################################################
function plotSolutions() {
    delete solutions
    delete solutionsCnt
 
    ############################################################
    #
    #   Mark solved cells in the solution space
    #
    ############################################################
    for ( r=1; r<=9; r++ ) {
        for (c=1; c<=9; c++) {
            if ( grid[r,c] != 0 ) {
                solutions[r,c]="C"
            }
        }
    }
 
 
    ############################################################
    #
    #   plot all possible solutions for the current
    #   puzzle grid
    #
    ############################################################
    for (i=1; i<=9; i++ ) {
        for ( r=1; r<=9; r++ ) {
            for ( c=1; c<=9; c++ ) {
                if ( solutions[r,c] != "C" ) {
                    if ( row[r,i] != 1 && col[c,i] != 1 && sector[sectorMap[r,c]] !~ i) {
                        if ( solutions[r,c] == 0 )
                            solutions[r,c]=i
                        else
                            solutions[r,c]=solutions[r,c]","i
 
                        solutionsCnt[sectorMap[r,c],i]= solutionsCnt[sectorMap[r,c],i]+1
                    }
                }
            }
        }
    }
}
 
function plotTwins() {
    ############################################################
    #
    #   look for "twins" in the solutions space
    #
    ############################################################
 
    for ( r=1; r<=9; r++) {
        for ( c=1; c<=9; c++ ) {
            if (split(solutions[r,c],a,",") == 2 ) {
                if (matchTwinCol(r,c,a)) {
                    extractTwinValuesFromCol(c,a)
                }
 
                if (matchTwinRow(r,c,a)) {
                    extractTwinValuesFromRow(r,a)
                }
            }
        }
    }
}
 
function matchTwinCol(R,C,A){
    twinCount=0
    ############################################################
    #
    #   look for "twins" across column in the solutions space
    #
    ############################################################
    for ( ; C<=9; C++ ) {
        if (split(solutions[R,C],b,",") == 2 ) {
            if( isTwin(A,b) ) {
                twinCount++
            }
        }
    }
 
    if ( twinCount == 1 )
        return 1
    else
        return 0 #  false
}
 
function matchTwinRow(R,C,A){
    twinCount=0
    
    ############################################################
    #
    #   look for "twins" across Row in the solutions space
    #
    ############################################################
    for ( ; R<=9; R++ ) {
        if (split(solutions[R,C],b,",") == 2 ) {
            if( isTwin(A,b) ) {
                twinCount++
            }
        }
    }
 
    if ( twinCount == 1 )
        return 1
    else
        return 0 #  false
}
 
function extractTwinValuesFromCol(C, A) {
    for ( R=1; R<=9; R++ ) {
        if ( solutions[R,C] != "C" ) {
            split(solutions[R,C],B,",")
 
            if ( length(B) > 1 && !isTwin(A,B)) {
                solutions[R,C]=""
 
                for ( i=1; i<= length(B); i++ ) {
                    if ( B[i] != A[1] && B[i] != A[2] ) {
                        if ( solutions[R,C]=="" ) {
                            solutions[R,C]=B[i]
                        }else{
                            solutions[R,C]=solutions[R,C]","B[i]
                        }
                    }
                }
            }
        }
    }
}
 
function extractTwinValuesFromRow(R, A) {
    for ( C=1; C<=9; C++ ) {
        if ( solutions[R,C] != "C" ) {
            split(solutions[R,C],B,",")
 
            if ( length(B) > 1 && !isTwin(A,B)) {
                solutions[R,C]=""
 
                for ( i=1; i<= length(B); i++ ) {
                    if ( B[i] != A[1] && B[i] != A[2] ) {
                        if ( solutions[R,C]=="" ) {
                            solutions[R,C]=B[i]
                        }else{
                            solutions[R,C]=solutions[R,C]","B[i]
                        }
                    }
                }
            }
        }
    }
}
 
function isTwin(A, B) {
    if (  length(A) == 2 && length(B) == 2 && A[1] == B[1] && A[2] == B[2] ) {
        return 1
    }
 
    return 0
}
 
function gridSolved() {
    for ( r=1 ; r<=9; r++ ) {
        for ( c=1; c<=9; c++ ) {
            if ( solutions[r,c]!="C" )
                return 0
        }
    }
    return 1
}
 
####################################################################
#
#   dump the list of all currently plotted solutions for 
#   unsolved cells
#
####################################################################
function dumpSolutions() {
    for ( r=1; r<=9; r++ ) {
        for ( c=1; c<=9; c++ ) {
            printf "solutions[%d,%d]=%s\n", r, c, solutions[r,c]
        }
    }
}
 
####################################################################
#
#   dump all solved numbers per sector
#
####################################################################
function dumpSectors() {
    print "SECTORS {"
    for ( i=1; i <=9; i++ ) {
        printf "    Sector[%d]: %s\n", i, sector[i]
    }
    print "}"
}
 
####################################################################
#
#   map a cell to a sector
#
####################################################################
function toSector(r, c) {
    if ( r <= 3 && c <=3 ) {
        return 1
    } else if ( r <= 3 && c <=6 ) {
        return 2
    } else if ( r <= 3 && c <=9 ) {
        return 3
    } else if ( r <= 6 && c <=3 ) {
        return 4
    } else if ( r <= 6 && c <=6 ) {
        return 5
    } else if ( r <= 6 && c <=9 ) {
        return 6
    } else if ( r <= 9 && c <=3 ) {
        return 7
    } else if ( r <= 9 && c <=6 ) {
        return 8
    } else if ( r <= 9 && c <=9 ) {
        return 9
    }
}
 
####################################################################
#
#   dump the puzzle grid to output, highlight the cell 
#   designated by the (r)ow and (c)olumn arguments
#
####################################################################
function dump(r, c) {
    print fileName
    printf "===================\n"
    for (i=1; i<=9; i++ ) {
        printf "|"
        for ( j=1; j<=9; j++) {
 
            if( i==r && j==c) {
                SM=SMSO
                RM=RMSO
            }else{
                SM=""
                RM=""
            }
 
            if (grid[i,j]!=0) {
                printf "%s%d%s",SM,grid[i,j],RM
            }else{
                printf " "
            }
 
            if ( j%3 == 0 ) {
                printf "|"
            }else{
                printf ":"
            }
        }
        if ( i%3 == 0 ) {
            printf "\n|=====|=====|=====|\n"
        }else{
            printf "\n|-----|-----|-----|\n"
        }
    }
}
 
####################################################################
#
#   dump the pregenerated sector map to output
#
####################################################################
function dumpSectorMap() {
    printf "SECTOR MAP {\n  ===================\n   "
    for (i=1; i<=9; i++ ) {
        printf "|"
        for ( j=1; j<=9; j++) {
 
            printf "%d", sectorMap[i,j]
 
            if ( j%3 == 0 ) {
                printf "|"
            }else{
                printf ":"
            }
        }
        if ( i%3 == 0 ) {
            printf "\n  |=====|=====|=====|\n   "
        }else{
            printf "\n  |-----|-----|-----|\n   "
        }
    }
    printf "\n}\n"
}
 
####################################################################
#
#   clear sector solutions
#
####################################################################
function clearSector() {
    delete sector
    delete sectorCnt
}
 
####################################################################
#
#   add a solution (v)alue to a (s)ector
#
####################################################################
function addToSector(s,v) {
    if ( sector[s]==0 ) {
        sector[s]=v
    } else{
        sector[s]=sector[s]","v
    }
    sectorCnt[s,v]=sectorCnt[s,v]+1
}
 
####################################################################
#
#   Program Exit
#
####################################################################
END { print ">> GOODBYE!" }