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

Тема в разделе "Linux", создана пользователем TolikCorp, 9 сен 2014.

  1. TolikCorp

    TolikCorp

    Сообщения:
    855
    Симпатии:
    271
    Всем привет, на просторах интернета нашел необычное применение BASH, а именно решение СУДОКУ.
    PHP:
    #!/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 ))
            return $?
        
    fi

        
    # Test all numbers from 1 to 9
        
    for ((i=1<= SIZEi++)); do
            
    check $i $row $col && {
                
    # Assign $i to cell and go on to the next cell
                
    board[index]=$i
                guess 
    $(( index )) && 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< ${#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 (( 0BOX_Hr++ )); 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
            [[ $(( 
    SIZE )) -eq 0 ]] && \
                echo -
    $'\n+---+---+---+---+---+---+---+---+---+\n|'
            
    echo -${board[i]} |"
        
    done
        
    echo $'\n+---+---+---+---+---+---+---+---+---+\n'
    else
        echo 
    "Sorry, solution not found..."
    fi

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

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

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

    Total runtime0:00:03:14.7672

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

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