[СКРИПТ] Решение СУДОКУ

[TolikCorp]

Всем привет, на просторах интернета нашел необычное применение BASH, а именно решение СУДОКУ.

#!/usr/bin/env bash
# Execution time stamp 1
res1=$(date +%s.%N)
################################################################################
#                                                                              #
# SudoKiller 1.0 - Bash SuDoku solver                                          #
#                                                                              #
# NAME        : sudokiller.sh                                                  #
# VERSION     : 1.0                                                            #
# CREATED DATE: 19/09/2005                                                     #
# LAST UPDATE : 20/09/2005                                                     #
# AUTHOR      : Daniele Mazzocchio                                             #
#                                                                              #
# Fill the 'board' array with the SuDoku table, replacing the empty cells with #
# zeroes, and run this script.                                                 #
#                                                                              #
# Download sources                                                             #
################################################################################

# This is the game board. Fill it with the puzzle you want to solve
board=(8 0 0 0 0 0 0 0 0
       0 0 3 6 0 0 0 0 0
       0 7 0 0 9 0 2 0 0
       0 5 0 0 0 7 0 0 0
       0 0 0 0 4 5 7 0 0
       0 0 0 1 0 0 0 3 0
       0 0 1 0 0 0 0 6 8
       0 0 8 5 0 0 0 1 0
       0 9 0 0 0 0 4 0 0)


################################################################################
# Constants definition                                                         #
################################################################################
SIZE=9                                   # Width of the SuDoku board
BOX_W=3                                  # Width of the inner boxes
BOX_H=3                                  # Height of the inner boxes
EMPTY=0                                  # Empty cells marker

RET_OK=0                                 # Return value upon success
RET_FAIL=1                               # Return value upon failure


################################################################################
# Functions                                                                    #
################################################################################
function guess () {
    # Test all candidate numbers for current cell until board is complete
    local index=$1                       # Index of the cell to guess

    local row=$((index / SIZE ))         # Row index of current cell
    local col=$((index % SIZE ))         # Column index of current cell
    local i                              # Local counter variable

    # Check if $index is out of array bounds
    [[ $index -eq ${#board[@]} ]] && return $RET_OK

    # If the cell isn't empty, go on to the next one
    if [[ ${board[index]} -ne $EMPTY ]]; then
        guess $(( index + 1 ))
        return $?
    fi

    # Test all numbers from 1 to 9
    for ((i=1; i <= SIZE; i++)); do
        check $i $row $col && {
            # Assign $i to cell and go on to the next cell
            board[index]=$i
            guess $(( index + 1 )) && return $RET_OK
        }
    done

    # If all numbers fail, empty the cell and return RET_FAIL
    board[index]=$EMPTY
    return $RET_FAIL
}

function check () {
    # Check if a number is, according to Sudoku rules, a legal candidate for the
    #   cell identified by its row and column indexes
    local num=$1                         # Number to check
    local row=$2                         # Cell's row index
    local col=$3                         # Cell's column index

    local i                              # Local counter variable

    # Check if the cell's row contains num
    for i in ${board[@]:$(( row * SIZE )):SIZE}; do
        [[ $num -eq $i ]] && return $RET_FAIL
    done

    # Check if the cell's column contains num
    for (( i=col; i < ${#board[@]}; i+=SIZE )); do
        [[ $num -eq ${board[i]} ]] && return $RET_FAIL
    done

    # Get the top left corner indexes of the cell's 3x3 box
    local box_row=$(( $row - $row % BOX_H ))
    local box_col=$(( $col - $col % BOX_W ))

    # Check if the box contains num
    for (( r = 0; r < BOX_H; r++ )); do
        for i in ${board[@]:$(( box_col + (box_row + r) * SIZE )):BOX_W}; do
            [[ $num -eq $i ]] && return $RET_FAIL
        done
    done

    # If all previous tests have been passed, return RET_OK
    return $RET_OK
}


################################################################################
# Main                                                                         #
################################################################################

guess 0
rc=$?

if [[ $rc -eq $RET_OK ]]; then
    # Print the resulting board
    for i in ${!board[@]}; do
        [[ $(( i % SIZE )) -eq 0 ]] && \
            echo -n $'\n+---+---+---+---+---+---+---+---+---+\n|'
        echo -n " ${board[i]} |"
    done
    echo $'\n+---+---+---+---+---+---+---+---+---+\n'
else
    echo "Sorry, solution not found..."
fi

# Execution time stamp 2
res2=$(date +%s.%N)
dt=$(echo "$res2 - $res1" | bc)
dd=$(echo "$dt/86400" | bc)
dt2=$(echo "$dt-86400*$dd" | bc)
dh=$(echo "$dt2/3600" | bc)
dt3=$(echo "$dt2-3600*$dh" | bc)
dm=$(echo "$dt3/60" | bc)
ds=$(echo "$dt3-60*$dm" | bc)

printf "Total runtime: %d:%02d:%02d:%02.4f\n" $dd $dh $dm $ds

exit $rc

В комплекте уже задачка от математика Арто Инкала.
(http://pikabu.ru/story/a_vyi_smozhete_reshit_1509399)
Ответ:

+---+---+---+---+---+---+---+---+---+
| 8 | 1 | 2 | 7 | 5 | 3 | 6 | 4 | 9 |
+---+---+---+---+---+---+---+---+---+
| 9 | 4 | 3 | 6 | 8 | 2 | 1 | 7 | 5 |
+---+---+---+---+---+---+---+---+---+
| 6 | 7 | 5 | 4 | 9 | 1 | 2 | 8 | 3 |
+---+---+---+---+---+---+---+---+---+
| 1 | 5 | 4 | 2 | 3 | 7 | 8 | 9 | 6 |
+---+---+---+---+---+---+---+---+---+
| 3 | 6 | 9 | 8 | 4 | 5 | 7 | 2 | 1 |
+---+---+---+---+---+---+---+---+---+
| 2 | 8 | 7 | 1 | 6 | 9 | 5 | 3 | 4 |
+---+---+---+---+---+---+---+---+---+
| 5 | 2 | 1 | 9 | 7 | 4 | 3 | 6 | 8 |
+---+---+---+---+---+---+---+---+---+
| 4 | 3 | 8 | 5 | 2 | 6 | 9 | 1 | 7 |
+---+---+---+---+---+---+---+---+---+
| 7 | 9 | 6 | 3 | 1 | 8 | 4 | 5 | 2 |
+---+---+---+---+---+---+---+---+---+

Total runtime: 0:00:03:14.7672

Решение было найдено за 3 минуты на VPS.

Добавил подсчет времени решения задачи. У кого меньше? (Маркировку процессора не забудьте указать, или VPS)