[Answer and Winners] Mathematics × Programming Competition #5 [答案及得獎名單] 數學 × 程式編寫比賽 (第五回)

Mathematics × Programming Competition #5
Announcement of Answer and Winners

^{Designed by @nicolemoker}

For Chinese version please scroll to the bottom. 中文版請見文末。

Question

Complete the 4 × 4 puzzle above using the numbers 1 to 16 without repetition, subject to the following constraints:

A, B, J, K can only be filled with the numbers 2, 4, 6 or 8
E + F = 26
K + O = 9
B + K = 14
A + L = 9
C + I = 25
A + G = 13
C + P = 24
B + M = 9
A + K = 12
D + E = 25
| E - N | = 4

Answer: 4,6,13,15,10,16,9,7,12,2,8,5,3,14,1,11

Solving by hand

There are many possible ways to solve this problem by logical reasoning. Here is one of my preferred way.

The 12 constraints can actually be broken down into 3 closed loops which can be solved one by one.

We can find out that the first closed loop can be solved independently. Then we can list out all possible combinations of the second and third loops, and also note that cell H is not in any of the loops. After some cross-checking between the second and third loops, we should be able to find out the unique solution.

I will keep the explanation short here. If you wish to study in detail, please take a look at the article written by @jubi .

Programming approach

We can use depth-first search to test for every possible combination, and then list out the correct answer(s). Here is an implementation using JavaScript:

var arr = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0];

function solve(i){
    // if the array has been filled completely, we have found the answer
    if (i==16){
        console.log(arr);
    } else {
        // otherwise try to fill in 1 to 16 in the current position
        for (var j=1; j<=16; j++){
            arr[i]=j;
            if (okay(i)) solve(i+1);
        }
    }
}

function okay(i){
    var temp = true;
    // checking uniqueness of the array
    for (var j=0; j<i; j++){
        if (arr[j]==arr[i]) temp = false;
    }
    // checking other rules
    temp = temp && (arr[0] == 2 || arr[0] == 4 || arr[0] == 6 || arr[0] == 8);
    temp = temp && (i < 1 || arr[1] == 2 || arr[1] == 4 || arr[1] == 6 || arr[1] == 8);
    temp = temp && (i < 9 || arr[9] == 2 || arr[9] == 4 || arr[9] == 6 || arr[9] == 8);
    temp = temp && (i < 5 || arr[4] + arr[5] == 26);
    temp = temp && (i < 14 || arr[10] + arr[14] == 9);
    temp = temp && (i < 10 || arr[1] + arr[10] == 14);
    temp = temp && (i < 11 || arr[0] + arr[11] == 9);
    temp = temp && (i < 8 || arr[2] + arr[8] == 25);
    temp = temp && (i < 6 || arr[0] + arr[6] == 13);
    temp = temp && (i < 15 || arr[2] + arr[15] == 24);
    temp = temp && (i < 12 || arr[1] + arr[12] == 9);
    temp = temp && (i < 10 || arr[0] + arr[10] == 12);
    temp = temp && (i < 4 || arr[3] + arr[4] == 25);
    temp = temp && (i < 13 || Math.abs(arr[4] - arr[13]) == 4);
    return temp;
}

solve(0);

Output: [4, 6, 13, 15, 10, 16, 9, 7, 12, 2, 8, 5, 3, 14, 1, 11]

Another version of JavaScript program written by @justyy can be found here.

This problem may be more easily solved by logic programming languages such as Prolog. Feel free to take a look at this post written by @armandocat !

If you want to learn JavaScript, visit @adnanrahic 's blog to learn JavaScript!

Winners

Among 37 participants, there are 33 people who got the correct answers. Thank you for your participation!

@philipheihei @challk @shirlam @kona @arkoko @kitcat @carinewhy @jamhuery @yenipaola @firstamendment @tensaix2j @daut44 @tking77798 @ratticus @tzs @livinguktaiwan @doughtaker @me-shell @cauchycauchy @justyy @superbing @dailyfortune @alanman @wilkinshui @ryanfan11 @rayccy @ghasemkiani @susankiani @marziehshahabi @ariak @megii @mindthought @armandocat @chunyinau3 @misalen @osmanbugra @etzel

Prize pool = Prize pool balance carried forward (0 SBD) + SBD payout of the the question post (52.565 SBD) = 52.565 SBD

Besides, @steemstem has generously sponsored 7.5 SP, 5 SP and 2.5 SP for the first, second and third prizes!

The winners and prizes are tabulated below:

Winner	Prize	SBD
@philipheihei	First prize	52.565 / 8 = 6.571 SBD + 7.5 SP
@challk	Second prize	52.565 / 8 = 6.571 SBD + 5 SP
@shirlam	Third prize	52.565 / 8 = 6.571 SBD + 2.5 SP
@misalen	Consolation prize	52.565 / 8 = 6.571 SBD
@yenipaola	Consolation prize	52.565 / 8 = 6.571 SBD
@ghasemkiani	Consolation prize	52.565 / 8 = 6.571 SBD
@armandocat	Consolation prize	52.565 / 8 = 6.571 SBD
@dailyfortune	Consolation prize	52.565 / 8 = 6.571 SBD

Prize carried forward = 0 SBD

Congratulations to the winners!

The steemSTEM project (@steemstem) is a community-supported project aiming to increase the quality and the visibility of STEM (STEM is the acronym for Science, Technology, Engineering and Mathematics) articles on Steemit. Please support steemSTEM by following @steemstem, joining the chat channel and following the curation trail on Streemian! In order to further promote the use of the chat channel, I will stop announcing the time of next competition via a post. Instead I will announce the time in advance in the chat channel!

數學 × 程式編寫比賽 (第五回)
答案及得獎名單公佈

^{Designed by @nicolemoker}

問題

以1至16完成以上之4 × 4 拼圖，數字不能重覆，並需符合以下限制：

A, B, J, K 只可由 2, 4, 6, 8 四個數字填上
E + F = 26
K + O = 9
B + K = 14
A + L = 9
C + I = 25
A + G = 13
C + P = 24
B + M = 9
A + K = 12
D + E = 25
| E - N | = 4

答案: 4,6,13,15,10,16,9,7,12,2,8,5,3,14,1,11

筆算解題

讓我們嘗試透過邏輯推理來解決這個問題。以下是其中一個可行的思路。

12項限制實際上可以分解成3個閉環，並且可以逐個解決。

我們可以發現，第一個閉環可以獨立解決。然後我們可以列出第二個和第三個閉環的所有可能的組合，並且同時注意到H並不在任何閉環之中。在第二和第三循環進行交叉檢查後，我們應能找出唯一的可行組合。

如果你想查看詳細解釋的話，可以到這裡看看由 @jubi 所寫的解說。

編程方法

我們可以利用深度優先搜索來測試每個組合的可能性。以下是利用入javascript寫成的程式：

var arr = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0];

function solve(i){
    // if the array has been filled completely, we have found the answer
    if (i==16){
        console.log(arr);
    } else {
        // otherwise try to fill in 1 to 16 in the current position
        for (var j=1; j<=16; j++){
            arr[i]=j;
            if (okay(i)) solve(i+1);
        }
    }
}

function okay(i){
    var temp = true;
    // checking uniqueness of the array
    for (var j=0; j<i; j++){
        if (arr[j]==arr[i]) temp = false;
    }
    // checking other rules
    temp = temp && (arr[0] == 2 || arr[0] == 4 || arr[0] == 6 || arr[0] == 8);
    temp = temp && (i < 1 || arr[1] == 2 || arr[1] == 4 || arr[1] == 6 || arr[1] == 8);
    temp = temp && (i < 9 || arr[9] == 2 || arr[9] == 4 || arr[9] == 6 || arr[9] == 8);
    temp = temp && (i < 5 || arr[4] + arr[5] == 26);
    temp = temp && (i < 14 || arr[10] + arr[14] == 9);
    temp = temp && (i < 10 || arr[1] + arr[10] == 14);
    temp = temp && (i < 11 || arr[0] + arr[11] == 9);
    temp = temp && (i < 8 || arr[2] + arr[8] == 25);
    temp = temp && (i < 6 || arr[0] + arr[6] == 13);
    temp = temp && (i < 15 || arr[2] + arr[15] == 24);
    temp = temp && (i < 12 || arr[1] + arr[12] == 9);
    temp = temp && (i < 10 || arr[0] + arr[10] == 12);
    temp = temp && (i < 4 || arr[3] + arr[4] == 25);
    temp = temp && (i < 13 || Math.abs(arr[4] - arr[13]) == 4);
    return temp;
}

solve(0);

Output: [4, 6, 13, 15, 10, 16, 9, 7, 12, 2, 8, 5, 3, 14, 1, 11]

另一個由 @justyy 撰寫的JavaScript版本可以在這裡找到。

這道問題亦能輕易以邏輯編程語言例如Prolog來解決。歡迎到這裡看一看由 @armandocat 所寫的Prolog程式！

如果你想學習JavaScript，不妨參閱 @adnanrahic 的文章！

得獎者

在37個參加者之中，有33人答對。多謝大家的熱烈參與！

@rayccy @arkoko @victorier @krischy @pizzachain @jubi @justyy @nationalpark @tensaix2j @firstamendment @apsu @hansenator @misko @nocturnal @doughtaker @jeffreytong @wilkinshui @mrkool @davor27 @tking77798 @daut44 @carobetc @jstoddard @tvb @kelkoo

是次獎池 = 上回比賽剩餘獎金 (0 SBD) + 比賽題目帖文的SBD收入 (52.565 SBD) = 52.565 SBD

另外，@steemstem 慷慨贊助了7.5 SP、5 SP以及2.5 SP予是次比賽的第一、二及三等獎！

下表顯示得獎者及其所得獎金：

得獎者	獎項	SBD
@philipheihei	一等獎	52.565 / 8 = 6.571 SBD + 7.5 SP
@challk	二等獎	52.565 / 8 = 6.571 SBD + 5 SP
@shirlam	三等獎	52.565 / 8 = 6.571 SBD + 2.5 SP
@misalen	安慰獎	52.565 / 8 = 6.571 SBD
@yenipaola	安慰獎	52.565 / 8 = 6.571 SBD
@ghasemkiani	安慰獎	52.565 / 8 = 6.571 SBD
@armandocat	安慰獎	52.565 / 8 = 6.571 SBD
@dailyfortune	安慰獎	52.565 / 8 = 6.571 SBD

下回比賽獎池現有 = 0 SBD

恭喜所有得獎者！

steemSTEM（@steemstem）是一個由steemit社群支持的項目，旨在宣傳STEM（STEM是科學，技術，工程和數學的首字母縮略詞）。請通過以下方式來支持steemSTEM：追蹤@steemSTEM，加入聊天頻道和加入Streemian！為了進一步推廣聊天頻道的使用，我將不再透過發文來宣布下一場比賽的時間，我會在聊天頻道中提前公佈比賽時間！