طراحی سایت و برنامه نویسی

آموزش طراحی سایت و برنامه نویسی

طراحی سایت و برنامه نویسی

آموزش طراحی سایت و برنامه نویسی

رویدادهای سفارشی (Custom Events) در لاراول — راهنمای کاربردی

در این مقاله قصد داریم به بررسی مبانی مدیریت رویداد (Event) در فریمورک وب لاراول بپردازیم. این یکی از قابلیت‌هایی است که شما به عنوان یک توسعه‌دهنده باید در فریمورک مورد نظر خود به آن تسلط داشته باشید. ما در این مسیر با روش ایجاد یک مثال واقعی از رویدادهای سفارشی در لاراول نیز آشنا خواهیم شد. همچنین یک شنونده برای رویداد خود می‌سازیم.

مفهوم رویدادها در لاراول مبتنی بر الگوی طراحی نرم‌افزار بسیار رایجی به نام الگوی مشاهده‌گر (observer) است. در این الگو، تصور می‌شود که سیستم به رویدادها گوش می‌دهد و بر همین مبنا واکنش می‌دهد. این قابلیتی بسیار مفید است، زیرا امکان جداسازی کامپوننت‌ها را در یک سیستم فراهم می‌سازد و بدین ترتیب از ایجاد یک کد به شدت درهم‌تنیده و پیچیده جلوگیری می‌کند.

برای نمونه تصور کنید، می‌خواهید وقتی فردی وارد وب‌سایت شما می‌شود، این واقعه را به همه ماژول‌ها در یک سیستم اطلاع دهید. بدین ترتیب، ماژول‌ها می‌توانند به این رویداد لاگین کردن واکنش نشان دهند. این واکنش می‌تواند از ارسال ایمیل یا نوتیفیکیشن درون اپلیکیشن یا هر چیزی که قرار است در پاسخ به آن رویداد اتفاق بیفتد متفاوت باشد.

مفاهیم مقدماتی رویدادها و شنونده‌ها

در این بخش، به بررسی روش مورد استفاده از سوی لاراول برای پیاده‌سازی رویدادها و شنونده‌ها در هسته مرکزی فریمورک می‌پردازیم. اگر با معماری لاراول آشنا باشید، احتمالاً می‌دانید که لاراول مفهوم یک ارائه‌دهنده سرویس را پیاده‌سازی می‌کند و بدین ترتیب می‌توان سرویس‌های متفاوتی را به اپلیکیشن تزریق کرد. به طور مشابه، لاراول یک کلاس داخلی به نام EventServiceProvider.php دارد که امکان تعریف کردن نگاشت شنونده رویداد برای یک اپلیکیشن را فراهم می‌سازد. در ادامه فایل app/Providers/EventServiceProvider.php را باز کنید:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
<?php
namespace App\Providers;
use Illuminate\Support\Facades\Event;
use Illuminate\Foundation\Support\Providers\EventServiceProvider as ServiceProvider;
class EventServiceProvider extends ServiceProvider
{
    /**
     * The event listener mappings for the application.
     *
     * @var array
     */
    protected $listen = [
        'App\Events\SomeEvent' => [
        'App\Listeners\EventListener',
        ],
    ];
    /**
     * Register any events for your application.
     *
     * @return void
     */
    public function boot()
    {
        parent::boot();
        //
    }
}

اگر نگاهی دقیق به مشخصه listen$ داشته باشید، می‌بینید که این مشخصه امکان تعریف یک آرایه از رویدادها و شنونده‌های مرتبط را فراهم می‌سازد. کلید آرایه متناظر با رویدادها در سیستم است و مقادیر آن متناظر با شنونده‌هایی است که در زمان رخ دادن رویداد متناظر در سیستم تحریک می‌شوند. در ادامه از یک مثال دنیای واقعی برای توضیح بیشتر این مفهوم استفاده می‌کنیم. چنان که شاید بدانید، لاراول یک سیستم احراز هویت داخلی دارد که قابلیت‌هایی مانند ثبت نام، لاگین کردن و غیره را تسهیل می‌کند.

مثالی از ارسال نوتیفیکیشن به عنوان معیار امنیتی

فرض کنید می‌خواهید وقتی فردی وارد اپلیکیشن می‌شود، به عنوان معیار امنیتی، یک نوتیفیکیشن ایمیل برای وی ارسال کنید. اگر لاراول از قابلیت شنونده رویداد پشتیبانی نمی‌کرد، در نهایت مجبور بودید کلاس مرکزی لاراول را ویرایش کنید و یا این که نوعی کد دیگر را برای ارسال ایمیل مورد استفاده قرار دهید. در واقع، ما خوش‌شانس هستیم که لاراول از طریق استفاده از شنونده رویداد به حل این مشکل کمک می‌کند. در ادامه فایل app/Providers/EventServiceProvider.php را طوری تغییر می‌دهیم که به صورت زیر درآید:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
<?php
namespace App\Providers;
use Illuminate\Support\Facades\Event;
use Illuminate\Foundation\Support\Providers\EventServiceProvider as ServiceProvider;
class EventServiceProvider extends ServiceProvider
{
    /**
     * The event listener mappings for the application.
     *
     * @var array
     */
    protected $listen = [
        'Illuminate\Auth\Events\Login' => [
        'App\Listeners\SendEmailNotification',
        ],
    ];
    /**
     * Register any events for your application.
     *
     * @return void
     */
    public function boot()
    {
        parent::boot();
        //
    }
}

Illuminate\Auth\Events\Login رویدادی است که وقتی فردی وارد اپلیکیشن می‌شود، از سوی پلاگین Auth ایجاد می‌شود. ما این رویداد را به شنونده App\Listeners\SendEmailNotification متصل می‌کنیم به طوری که در زمان رویداد لاگین تحریک شود. البته باید کلاس شنونده App\Listeners\SendEmailNotification را نیز نوشته باشید. در این مورد هم لاراول از طریق استفاده از دستور آرتیزان زیر، امکان ایجاد یک کد قالب برای شنونده را فراهم می‌سازد:

php artisan event:generate

دستور فوق کلاس‌های رویداد و شنونده را زیر مشخصه listen$ تولید می‌کند. در این حالت، رویداد Illuminate\Auth\Events\Login از قبل موجود است، به طوری که صرفاً کلاس شونده App\Listeners\SendEmailNotification ایجاد می‌شود. در واقع، در این وضعیت باید کلاس رویداد Illuminate\Auth\Events\Login نیز در صورتی که از قبل موجود نیست، ایجاد شود.

بررسی شنونده رویداد

در ادامه شنونده‌ای که در مسیر app/Listeners/SendEmailNotification.php ایجاد شده را بررسی می‌کنیم:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
<?php
namespace App\Listeners;
use Illuminate\Auth\Events\Login;
use Illuminate\Queue\InteractsWithQueue;
use Illuminate\Contracts\Queue\ShouldQueue;
class SendEmailNotification
{
    /**
     * Create the event listener.
     *
     * @return void
     */
    public function __construct()
    {
        //
    }
    /**
     * Handle the event.
     *
     * @param  Login  $event
     * @return void
     */
    public function handle(Login $event)
    {
         
    }
}

این handle است که در زمان تحریک شدن شنونده به همراه وابستگی‌های مناسب فراخوانی می‌شود. در این مثال، آرگومان event$ باید شامل اطلاعات زمینه‌ای در مورد رویداد لاگین یعنی کاربر وارد شده به اپلیکیشن باشد.

همچنین می‌توان از شیء event$ برای اجرای پردازش بیشتر در متد handle استفاده کرد. در این مثال، ما می‌خواهیم یک نوتیفیکیشن ایمیل به کاربر لاگین کرده ارسال کنیم. متد handle پس از بازبینی موارد فوق به صورت زیر درمی‌آید:

1
2
3
4
5
6
7
8
public function handle(Login $event)
{
    // get logged in user's email and username
    $email = $event->user->email;
    $username = $event->user->name;
     
    // send email notification about login
}

بنابراین استفاده از قابلیت رویداد در لاراول به این صورت است. در بخش بعدی پا را فراتر می‌گذاریم و یک رویداد سفارشی و کلاس شنونده متناظرش را در لاراول می‌سازیم.

ایجاد رویداد سفارشی در لاراول

در سناریوی مثال بخش قبل که در مثال این بخش نیز مورد استفاده می‌دهیم، قرار است کارهای زیر را انجام دهیم:

یک اپلیکیشن در موارد به خصوصی نیاز دارد که کش سیستم خود را پاک کند. ما رویداد CacheClear را همراه با اطلاعات زمینه‌ای در مواردی که اپلیکیشن رویداد فوق را اجرا کند، تحریک می‌کنیم. در ادامه کلیدهای گروه کش را همراه با رویدادی که پاک شده است ارسال خواهیم کرد.
ماژول‌های دیگر در سیستم می‌توانند به رویداد CacheClear گوش دهند. ما کدی را پیاده‌سازی می‌کنیم که به بررسی کش های مرتبط می‌پردازد.

بنابراین در ادامه فایل app/Providers/EventServiceProvider.php را بازبینی می‌کنیم و رویداد سفارشی و نگاشت‌های شنونده‌های خود را در آن ثبت می‌کنیم:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
<?php
namespace App\Providers;
use Illuminate\Support\Facades\Event;
use Illuminate\Foundation\Support\Providers\EventServiceProvider as ServiceProvider;
class EventServiceProvider extends ServiceProvider
{
    /**
     * The event listener mappings for the application.
     *
     * @var array
     */
    protected $listen = [
        'App\Events\ClearCache' => [
        'App\Listeners\WarmUpCache',
        ],
    ];
    /**
     * Register any events for your application.
     *
     * @return void
     */
    public function boot()
    {
        parent::boot();
        //
    }
}

استفاده از دستور artisan

چنان که می‌بینید، ما رویداد App\Events\ClearCache و کلاس شنونده‌های مرتبط App\Listeners\WarmUpCache را زیر مشخصه listen$ تعریف می‌کنیم. سپس باید فایل‌های کلاس مرتبط را ایجاد کنیم. به خاطر داشته باشید که همواره می‌توانید از دستور artisan استفاده کنید و یک کد قالب مبنا تولید کنید.

php artisan event:generate

دستور فوق کلاس رویدادی را در فایل app/Events/ClearCache.php ایجاد کرده و کلاس شنونده را در فایل app/Listeners/WarmUpCache.php قرار می‌دهد. کلاس app/Events/ClearCache.php با چند تغییر به صورت زیر درمی‌آید:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
<?php
namespace App\Events;
use Illuminate\Broadcasting\Channel;
use Illuminate\Queue\SerializesModels;
use Illuminate\Broadcasting\PrivateChannel;
use Illuminate\Broadcasting\PresenceChannel;
use Illuminate\Foundation\Events\Dispatchable;
use Illuminate\Broadcasting\InteractsWithSockets;
use Illuminate\Contracts\Broadcasting\ShouldBroadcast;
class ClearCache
{
    use Dispatchable, InteractsWithSockets, SerializesModels;
     
    public $cache_keys = [];
    /**
     * Create a new event instance.
     *
     * @return void
     */
    public function __construct(Array $cache_keys)
    {
        $this->cache_keys = $cache_keys;
    }
    /**
     * Get the channels the event should broadcast on.
     *
     * @return Channel|array
     */
    public function broadcastOn()
    {
        return new PrivateChannel('channel-name');
    }
}

چنان که احتمالاً متوجه شده‌اید، ما مشخصه جدیدی به نام cache_keys$ اضافه کرده‌ایم که از آن برای نگهداری اطلاعات ارسال شده به همراه یک رویداد استفاده خواهیم کرد. در این مثال، گروه‌های کش را که پاک شده‌اند ارسال می‌کنیم. سپس نگاهی به کلاس شنونده‌ای خواهیم داشت که دارای یک متد handle به‌روزرسانی شده در فایل app/Listeners/WarmUpCache.php است.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
<?php
namespace App\Listeners;
use App\Events\ClearCache;
use Illuminate\Queue\InteractsWithQueue;
use Illuminate\Contracts\Queue\ShouldQueue;
class WarmUpCache
{
    /**
     * Create the event listener.
     *
     * @return void
     */
    public function __construct()
    {
        //
    }
    /**
     * Handle the event.
     *
     * @param  ClearCache  $event
     * @return void
     */
    public function handle(ClearCache $event)
    {
        if (isset($event->cache_keys) && count($event->cache_keys)) {
            foreach ($event->cache_keys as $cache_key) {
                // generate cache for this key
                // warm_up_cache($cache_key)
            }
        }
    }
}

تست شنونده رویداد (Event Listener)

زمانی که شنونده فراخوانی می‌شود، متد handle به همراه وهله‌ای از رویداد مرتبط ارسال می‌شود. در این مثال، این مورد باید وهله‌ای از رویداد ClearCache باشد که به عنوان آرگومان اول متد handle ارسال می‌شود. سپس کافی است روی همه کلیدهای کش، حلقه‌ای تعریف کنیم و کش های مرتبط را آماده‌سازی کنیم.

اکنون همه چیز را آماده تست ساخته‌ایم. در ادامه نگاهی به فایل کنترلر در مسیر app/Http/Controllers/EventController.php می‌اندازیم تا نشان دهیم که یک رویداد چگونه تحریک می‌شود.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
<?php
namespace App\Http\Controllers;
use App\Http\Controllers\Controller;
use App\Library\Services\Contracts\CustomServiceInterface;
use App\Post;
use Illuminate\Support\Facades\Gate;
use App\Events\ClearCache;
class EventController extends Controller
{
    public function index()
    {
        // ...
         
        // you clear specific caches at this stage
        $arr_caches = ['categories', 'products'];
         
        // want to raise ClearCache event
        event(new ClearCache($arr_caches));
         
        // ...
    }
}

قبل از هر چیز یک آرایه از کلیدهای کش در زمان ایجاد یک وهله از رویداد ClearCache به عنوان آرگومان نخست ارسال می‌شود. تابع کمکی رویداد برای تحریک یک رویداد از هر کجا درون یک اپلیکیشن مورد استفاده قرار می‌گیرد. زمانی که یک رویداد تحریک می‌شود، لاراول همه شنونده‌ها را فرامی‌خواند تا به آن رویداد خاص گوش دهند.

در مورد مثال خودمان، شنونده App\Listeners\WarmUpCache طوری تنظیم شده است که به رویداد App\Events\ClearCache گوش دهد. از این رو متد handle شنونده App\Listeners\WarmUpCache زمانی که یک رویداد از کنترلر تحریک می‌شود، فراخوانی خواهد شد. باقی کد برای آماده‌سازی کش ها جهت پاکسازی استفاده می‌شود. بنابراین اینک شما با روش ایجاد رویدادهای سفارشی در اپلیکیشن خود آشنا شده‌اید و می‌توانید با آن‌ها کار کنید.

اشتراک رویداد چیست؟

«اشتراک رویداد» (Event Subscriber) امکان ثبت نام در چند شنونده رویداد را در یک مکان منفرد فراهم می‌سازد. چه بخواهید از نظر منطقی شنونده‌های رویداد را گروه‌بندی کنید و چه بخواهید رویدادهای زیادی را در یک مکان منفرد گرد هم آورید، اشتراک رویداد گزینه مناسبی برای استفاده خواهد بود.

اگر بخواهیم مثال‌هایی را که تا به اینجا مورد بررسی قرار دادیم، با استفاده از اشتراک رویداد پیاده‌سازی کنیم، چیزی مانند زیر خواهد بود:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
<?php
// app/Listeners/ExampleEventSubscriber.php
namespace App\Listeners;
class ExampleEventSubscriber
{
    /**
     * Handle user login events.
     */
    public function sendEmailNotification($event) {
        // get logged in username
        $email = $event->user->email;
        $username = $event->user->name;
         
        // send email notification about login...
    }
    /**
     * Handle user logout events.
     */
    public function warmUpCache($event) {
        if (isset($event->cache_keys) && count($event->cache_keys)) {
            foreach ($event->cache_keys as $cache_key) {
                // generate cache for this key
                // warm_up_cache($cache_key)
            }
        }
    }
    /**
     * Register the listeners for the subscriber.
     *
     * @param  Illuminate\Events\Dispatcher  $events
     */
    public function subscribe($events)
    {
        $events->listen(
            'Illuminate\Auth\Events\Login',
            'App\Listeners\ExampleEventSubscriber@sendEmailNotification'
        );
         
        $events->listen(
            'App\Events\ClearCache',
            'App\Listeners\ExampleEventSubscriber@warmUpCache'
        );
    }
}

متد subscribe مسئول ثبت شنونده‌ها است. آرگومان اول متد subscribe وهله‌ای از کلاس Illuminate\Events\Dispatcher است که می‌توان برای اتصال رویدادها به شنونده‌ها با استفاده از متد listen استفاده کرد. آرگومان اول متد listen رویدادی است که می‌خواهید به آن گوش دهید و آرگومان دوم شنونده‌ای است که هنگام تحریک رویداد فراخوانی خواهد شد.

به این ترتیب می‌توانید چندین رویداد و شنونده را در خود کلاس اشتراک تعریف کنید. کلاس اشتراک رویداد به صورت خودکار انتخاب نمی‌شود. شما باید آن را در کلاس EventServiceProvider.php زیر مشخصه subscriber$ چنان که در قطعه کد زیر می‌بینید ثبت کنید.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
<?php
namespace App\Providers;
use Illuminate\Support\Facades\Event;
use Illuminate\Foundation\Support\Providers\EventServiceProvider as ServiceProvider;
class EventServiceProvider extends ServiceProvider
{
    /**
     * The subscriber classes to register.
     *
     * @var array
     */
    protected $subscribe = [
        'App\Listeners\ExampleEventSubscriber',
    ];
    /**
     * Register any events for your application.
     *
     * @return void
     */
    public function boot()
    {
        parent::boot();
        //
    }
}

بنابراین کلاس اشتراک رویداد در اختیار شما قرار دارد و بدین ترتیب به پایان این مقاله می‌رسیم.

سخن پایانی

در این مقاله به بررسی چند قابلیت جالب لاراول پرداختیم که شامل رویدادها و شنونده‌ها است. این قابلیت‌ها مبتنی بر الگوی طراحی مشاهده‌گر هستند که امکان تحریک رویدادها در تمام نقاط اپلیکیشن را فراهم می‌سازد و به ماژول‌های دیگر امکان می‌دهد که به این رویدادها گوش دهند و بر همین مبنا واکنش نشان دهند.

منبع: فرادرس

مشاوره چهارشنبه 26 تیر 1398 ساعت 15:40

0 نظر

روش های برقراری ارتباط بین کلاس ها در سوئیفت ۵ — به زبان ساده

زمانی که یک اپلیکیشن iOS ایجاد می‌کنید، در اغلب موارد نیاز است که بین کلاس‌های Model ،View و Controller ارتباط‌هایی برقرار کنید. در این مقاله به بررسی روش‌های مختلف برای برقراری ارتباط بین کلاس ها در سوئیفت 5 می‌پردازیم. تصویر زیر الگوی معماری مشهور به MVC را نمایش می‌دهد که روشی برای طراحی کردن یک گردش داده در پروژه‌ها محسوب می‌شود.

یکی از مزایای استفاده از یک الگوی معماری این است که کد شما به سادگی درک خواهد شد، ماژولار می‌شود و قابلیت نگهداری آن ارتقا می‌یابد. با تجزیه کلاس‌ها به دسته‌های مختلف نیازمند یک روش مؤثر برای برقراری ارتباط در مسیر model -> controller -> view و برعکس خواهیم بود. ما در ادامه 3 روشی که برای نیل به این مقصود مورد نیاز است را مورد بررسی قرار داده‌ایم. این سه روش به صورت خلاصه شامل موارد زیر هستند:

استفاده از نوتیفیکیشن
استفاده از نمایندگی
استفاده از callback

با ما همراه باشید تا با بررسی این موارد درکی مقدماتی از مزایا و معایب هر روش پیدا کنید و بتوانید راه‌حل مناسب خود را انتخاب نمایید.

نوتیفیکیشن

استفاده از نوتیفیکیشن زمانی مناسب خواهد بود که مشاهده‌گرهای زیادی داشته باشیم که برای به‌روزرسانی نیازمند «شنیدن» باشند. برای نمونه اگر 5 کلاس دارید که همگی داده‌های ذخیره شده را بارگذاری می‌کنند می‌توانید به یکباره به هر 5 کلاس هشدار دهید که یک درخواست موفق شبکه برقرار شده است.

ساختار مقدماتی چنین است:

1
2
3
4
5
6
7
8
9
//Posting a notification
NotificationCenter.default.post(name:  
NSNotification.Name("hello"), object: nil)
//Receiving a notification
NotificationCenter.default.addObserver(self, selector: #selector(helloReceived), name: NSNotification.Name("hello"), object: nil)
//Calling a function using #selector
@objc private func helloReceived() {
    print("hello world!")
}

نکته: تگ obj@ در ابتدای هر تابعی که از طریق selector# فراخوانی شود، ضروری خواهد بود.

گرچه امکان ارسال داده از طریق نوتیفیکیشن وجود دارد، اما به این منظور ابزار بهینه‌ای محسوب نمی‌شوند. در هر حال، بهترین کاربرد آن‌ها برای هشدار به یک کلاس است که داده‌های جدیدی موجود شده‌اند. فرض کنید مدل داده‌ای دارید که در آن داده‌هایی را از شبکه دانلود می‌کنید، زمانی که این داده‌ها در حافظه ذخیره شدند، به کنترلرهای «نما» (View) هشدار می‌دهید تا این داده‌های اخیراً ذخیره شده را در نما وارد کنند. در ادامه مثالی از طرز کار ساختار نوتیفیکیشن را می‌بینید:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class ViewController: UIViewController {
    let model = Model()
    
    override func viewDidLoad() {
        super.viewDidLoad()
        //post notification
        NotificationCenter.default.post(name: NSNotification.Name("viewLoaded"), object: nil)
    }
}
class Model {
    init() {
        //init notification receiver
        NotificationCenter.default.addObserver(self, selector: #selector(viewWasLoaded), name: NSNotification.Name("viewLoaded"), object: nil)
    }
    //function that handles notification
    @objc private func viewWasLoaded() {
        print("Model was alerted about viewDidLoad!")
    }
}

نمایندگی

«نمایندگی» (Delegation) روشی است که در اغلب موارد برای برقراری ارتباط بین کلاس‌های مدل، نما و کنترلر مورد استفاده قرار می‌گیرد. در الگوی طراحی نمایندگی از یک پروتکل برای تعریف متدها، مشخصه‌ها و دیگر الزامات مورد نیاز برای پیاده‌سازی یک کلاس استفاده می‌شود. پروتکل را می‌توان به عنوان یک قرارداد تصور کرد که با اجرای قرارداد موجود در پروتکل متعهد می‌شویم الزامات آن را پیاده‌سازی کنیم.

برای پیاده‌سازی الگوی نمایندگی باید یک پروتکل را راه‌اندازی کنیم:

1
2
3
protocol ModelDelegate: class {
    func didReceiveData(_ data: String)
}

در کلاس متد، یعنی کلاسی که این نمایندگی را بر عهده دارد، باید یک ارجاع ضعیف به ModelDelegate داشته باشید.

نکته: ارجاع به نماینده باید ضعیف یا unowned باشد. با استفاده از یک ارجاع قوی، ممکن است متوجه شوید در حال ایجاد یک چرخه هستید که در آن نماینده ارجاعی به کلاس والد نگه می‌دارد و کلاس والد نیز به نماینده ارجاع دارد. با ایجاد چنین حلقه ارجاع قوی، هر دو شیء در حافظه به همدیگر ارجاع می‌دهند و از این رو ARC به محض «مقدارزدایی» (de-initialization) از شیء نمایندگی شده آن را تخصیص‌زدایی می‌کند.

1
2
3
4
5
6
7
class Model {
    weak var delegate: ModelDelegate?
    func downloadData() {
        let data = "Network request information."
        delegate?.didReceiveData(data)
    }
}

اکنون یک وهله از Model در کلاس Controller ایجاد می‌کنیم و نماینده آن را به Self انتساب می‌دهیم.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class ViewController: UIViewController {
    let model = Model()
    
    override func viewDidLoad() {
        super.viewDidLoad()
        model.delegate = self
        model.downloadData()
    }
}
extension ViewController: ModelDelegate {
    func didReceiveData(_ data: String) {
        print(data)
    }
}

برای انتساب نماینده مدل به Self، باید ViewController با پروتکل ModelDelegate هماهنگ باشد و توجه داشته باشید که در این مثال Self همان کلاس ModelDelegate است. ما می‌توانیم این هماهنگی را بدین طریق به دست آوریم که یک بسط از کنترل نما که از این پروتکل استفاده می‌کند به طرح‌بندی تعریف‌شده در ModelDelegate اضافه کنیم. زمانی که مدل با موفقیت داده‌ها را دانلود کرد، تابع didReceiveData را درون ViewController فراخوانی خواهد کرد. زمانی که این تابع فراخوانی شد، می‌توانید کلاس View را درون ViewController به‌روزرسانی کنید.

Callback

راه‌اندازی Callback-ها ساده است. برخی برنامه نویسان از این روش کمتر استفاده می‌کنند چون پایداری الگوی نمایندگی را بیشتر می‌پسندند. با این حال، Callback-ها برای ایجاد ارتباط‌های ساده مفید هستند.

تصور کنید در یک کلاس نما تابعی داریم که یک انیمیشن را اجرا می‌کند. ما می‌خواهیم به محض تکمیل شدن انیمیشن به ViewController خود هشدار دهیم که انیمیشن به پایان رسیده است.

1
2
3
4
5
6
class View {
    func runAnimation(completion: @escaping() -> ()) {
        //run animation, upon completion send callback
        completion()
    }
}

به این منظور در ViewController یک وهله از کلاس View ایجاد می‌کنیم که تابع ()runAnimation را فراخوانی می‌کند:

1
2
3
4
5
6
7
8
9
10
11
12
13
class ViewController: UIViewController {
    let view = View()
    override func viewDidLoad() {
        super.viewDidLoad()
   
        view.runAnimation { [weak self] in
            self?.animationFinished()
        }
    }
    private func animationFinished() {
        print("Animation in View was finished!")
    }
}

نکته: به «weak self in» درون بستار روی ()runAnimation توجه خاصی داشته باشید. با تعیین این self به صورت یک ارجاع ضعیف ما از ایجاد چرخه‌های پایدار جلوگیری می‌کنیم. اگر self را به صورت قوی در اختیار بگیریم، آن گاه بستار یک ارجاع قوی به self می‌گیرد و بنابراین امکان تخصیص‌زدایی از آن در حافظه از دست می‌رود.

همچنین امکان ارسال داده‌ها به صورت مستقیم از طریق Callback وجود دارد:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Model {
    func getData(completion: ((_ data: String) -> Void)) {
        let data = "Network data!"
        completion(data)
    }
}
class ViewController: UIViewController {
    let model = Model()
    override func viewDidLoad() {
        super.viewDidLoad()
        model.getData { [weak self] (data: String) in
            self?.updateView(data)
        }
    }
    private func updateView(_ data: String) {
        print(data)
    }
}

نکته: کاراکتر زیرخط درون تعریف تابع به آن معنی است که نیازی به گنجاندن نام پارامتر در زمان فراخوانی یک متد نداریم.

سخن پایانی

شما با مطالعه این مقاله با برخی از گزینه‌های برقراری ارتباط در سوئیفت آشنا شدید. اغلب برنامه‌نویسان در پروژه‌های خود از انواع مختلفی از این روش‌های برقراری ارتباط بین کلاس‌ها استفاده می‌کنند، چون هر کدام از آن‌ها کاربردهای خاص خود را دارند. از نمایندگی برای طرح‌بندی پایدار بین کلاس‌ها و اجرای ارتباط‌های زیاد استفاده می‌شود. از Callback برای کارکردهای ساده‌ای مانند ارسال Callback در زمان پایان یافتن یک اکشن استفاده می‌شود. همچنین از نوتیفیکیشن برای ارسال هشدار به چند کلاس جهت اطلاع دادن دانلود شدن داده‌ها یا تغییر یافتن آن‌ها استفاده می‌کنیم.

منبع: فرادرس

مشاوره چهارشنبه 26 تیر 1398 ساعت 15:40

0 نظر

رویدادهای سفارشی (Custom Events) در لاراول — راهنمای کاربردی

مفاهیم مقدماتی رویدادها و شنونده‌ها

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
<?php
namespace App\Providers;
use Illuminate\Support\Facades\Event;
use Illuminate\Foundation\Support\Providers\EventServiceProvider as ServiceProvider;
class EventServiceProvider extends ServiceProvider
{
    /**
     * The event listener mappings for the application.
     *
     * @var array
     */
    protected $listen = [
        'App\Events\SomeEvent' => [
        'App\Listeners\EventListener',
        ],
    ];
    /**
     * Register any events for your application.
     *
     * @return void
     */
    public function boot()
    {
        parent::boot();
        //
    }
}

مثالی از ارسال نوتیفیکیشن به عنوان معیار امنیتی

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
<?php
namespace App\Providers;
use Illuminate\Support\Facades\Event;
use Illuminate\Foundation\Support\Providers\EventServiceProvider as ServiceProvider;
class EventServiceProvider extends ServiceProvider
{
    /**
     * The event listener mappings for the application.
     *
     * @var array
     */
    protected $listen = [
        'Illuminate\Auth\Events\Login' => [
        'App\Listeners\SendEmailNotification',
        ],
    ];
    /**
     * Register any events for your application.
     *
     * @return void
     */
    public function boot()
    {
        parent::boot();
        //
    }
}

php artisan event:generate

بررسی شنونده رویداد

در ادامه شنونده‌ای که در مسیر app/Listeners/SendEmailNotification.php ایجاد شده را بررسی می‌کنیم:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
<?php
namespace App\Listeners;
use Illuminate\Auth\Events\Login;
use Illuminate\Queue\InteractsWithQueue;
use Illuminate\Contracts\Queue\ShouldQueue;
class SendEmailNotification
{
    /**
     * Create the event listener.
     *
     * @return void
     */
    public function __construct()
    {
        //
    }
    /**
     * Handle the event.
     *
     * @param  Login  $event
     * @return void
     */
    public function handle(Login $event)
    {
         
    }
}

1
2
3
4
5
6
7
8
public function handle(Login $event)
{
    // get logged in user's email and username
    $email = $event->user->email;
    $username = $event->user->name;
     
    // send email notification about login
}

ایجاد رویداد سفارشی در لاراول

در سناریوی مثال بخش قبل که در مثال این بخش نیز مورد استفاده می‌دهیم، قرار است کارهای زیر را انجام دهیم:

یک اپلیکیشن در موارد به خصوصی نیاز دارد که کش سیستم خود را پاک کند. ما رویداد CacheClear را همراه با اطلاعات زمینه‌ای در مواردی که اپلیکیشن رویداد فوق را اجرا کند، تحریک می‌کنیم. در ادامه کلیدهای گروه کش را همراه با رویدادی که پاک شده است ارسال خواهیم کرد.
ماژول‌های دیگر در سیستم می‌توانند به رویداد CacheClear گوش دهند. ما کدی را پیاده‌سازی می‌کنیم که به بررسی کش های مرتبط می‌پردازد.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
<?php
namespace App\Providers;
use Illuminate\Support\Facades\Event;
use Illuminate\Foundation\Support\Providers\EventServiceProvider as ServiceProvider;
class EventServiceProvider extends ServiceProvider
{
    /**
     * The event listener mappings for the application.
     *
     * @var array
     */
    protected $listen = [
        'App\Events\ClearCache' => [
        'App\Listeners\WarmUpCache',
        ],
    ];
    /**
     * Register any events for your application.
     *
     * @return void
     */
    public function boot()
    {
        parent::boot();
        //
    }
}

استفاده از دستور artisan

php artisan event:generate

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
<?php
namespace App\Events;
use Illuminate\Broadcasting\Channel;
use Illuminate\Queue\SerializesModels;
use Illuminate\Broadcasting\PrivateChannel;
use Illuminate\Broadcasting\PresenceChannel;
use Illuminate\Foundation\Events\Dispatchable;
use Illuminate\Broadcasting\InteractsWithSockets;
use Illuminate\Contracts\Broadcasting\ShouldBroadcast;
class ClearCache
{
    use Dispatchable, InteractsWithSockets, SerializesModels;
     
    public $cache_keys = [];
    /**
     * Create a new event instance.
     *
     * @return void
     */
    public function __construct(Array $cache_keys)
    {
        $this->cache_keys = $cache_keys;
    }
    /**
     * Get the channels the event should broadcast on.
     *
     * @return Channel|array
     */
    public function broadcastOn()
    {
        return new PrivateChannel('channel-name');
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
<?php
namespace App\Listeners;
use App\Events\ClearCache;
use Illuminate\Queue\InteractsWithQueue;
use Illuminate\Contracts\Queue\ShouldQueue;
class WarmUpCache
{
    /**
     * Create the event listener.
     *
     * @return void
     */
    public function __construct()
    {
        //
    }
    /**
     * Handle the event.
     *
     * @param  ClearCache  $event
     * @return void
     */
    public function handle(ClearCache $event)
    {
        if (isset($event->cache_keys) && count($event->cache_keys)) {
            foreach ($event->cache_keys as $cache_key) {
                // generate cache for this key
                // warm_up_cache($cache_key)
            }
        }
    }
}

تست شنونده رویداد (Event Listener)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
<?php
namespace App\Http\Controllers;
use App\Http\Controllers\Controller;
use App\Library\Services\Contracts\CustomServiceInterface;
use App\Post;
use Illuminate\Support\Facades\Gate;
use App\Events\ClearCache;
class EventController extends Controller
{
    public function index()
    {
        // ...
         
        // you clear specific caches at this stage
        $arr_caches = ['categories', 'products'];
         
        // want to raise ClearCache event
        event(new ClearCache($arr_caches));
         
        // ...
    }
}

اشتراک رویداد چیست؟

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
<?php
// app/Listeners/ExampleEventSubscriber.php
namespace App\Listeners;
class ExampleEventSubscriber
{
    /**
     * Handle user login events.
     */
    public function sendEmailNotification($event) {
        // get logged in username
        $email = $event->user->email;
        $username = $event->user->name;
         
        // send email notification about login...
    }
    /**
     * Handle user logout events.
     */
    public function warmUpCache($event) {
        if (isset($event->cache_keys) && count($event->cache_keys)) {
            foreach ($event->cache_keys as $cache_key) {
                // generate cache for this key
                // warm_up_cache($cache_key)
            }
        }
    }
    /**
     * Register the listeners for the subscriber.
     *
     * @param  Illuminate\Events\Dispatcher  $events
     */
    public function subscribe($events)
    {
        $events->listen(
            'Illuminate\Auth\Events\Login',
            'App\Listeners\ExampleEventSubscriber@sendEmailNotification'
        );
         
        $events->listen(
            'App\Events\ClearCache',
            'App\Listeners\ExampleEventSubscriber@warmUpCache'
        );
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
<?php
namespace App\Providers;
use Illuminate\Support\Facades\Event;
use Illuminate\Foundation\Support\Providers\EventServiceProvider as ServiceProvider;
class EventServiceProvider extends ServiceProvider
{
    /**
     * The subscriber classes to register.
     *
     * @var array
     */
    protected $subscribe = [
        'App\Listeners\ExampleEventSubscriber',
    ];
    /**
     * Register any events for your application.
     *
     * @return void
     */
    public function boot()
    {
        parent::boot();
        //
    }
}

بنابراین کلاس اشتراک رویداد در اختیار شما قرار دارد و بدین ترتیب به پایان این مقاله می‌رسیم.

سخن پایانی

منبع: فرادرس

مشاوره چهارشنبه 26 تیر 1398 ساعت 15:40

0 نظر

ساخت برنامه حل سودوکو در جاوا — از صفر تا صد

در این مقاله قصد داریم به بررسی یک برنامه حل سودوکو و الگوریتم‌های مورد استفاده از سوی آن بپردازیم. سپس این راه‌حل‌ها را در جاوا پیاده‌سازی می‌کنیم. نخستین راه‌حل یک حمله «تهاجم کور» (brute-force) است. راه‌حل دوم استفاده از تکنیک «لینک‌های رقصان» (Dancing Links) است. توجه داشته باشید که در این مقاله، نقطه توجه ما روی الگوریتم‌ها است و طراحی برنامه‌نویسی شیءگرا چندان موضوع توجه نیست.

معمای سودوکو

سودوکو به بیان ساده یک معمای ترکیبی جایگشت اعداد با شبکه‌ای از سلول‌های 9 × 9 است که بخشی از آن با اعدادی از 1 تا 9 پر شده است. هدف این است که سلول‌های خالیِ باقیمانده را با بقیه اعداد طوری پر کنیم که هر ردیف و هر ستون تنها یک رقم از هر نوع داشته باشد. علاوه بر آن هر زیر بخش 3 × 3 نیز شبکه مستقلی است که نباید رقم تکراری در آن باشد. سطح دشواری سودوکو به طور طبیعی با افزایش تعداد سلول‌های خالی افزایش می‌یابد.

تخته تست

برای این که راه‌حل خود را جالب‌تر کرده و الگوریتم را اعتبارسنجی کنیم از یک تخته به نام «دشوارترین سودوکوی دنیا» استفاده می‌کنیم که به صورت زیر است:

1
2
3
4
5
6
7
8
9
8 . . . . . . . . 
. . 3 6 . . . . . 
. 7 . . 9 . 2 . . 
. 5 . . . 7 . . . 
. . . . 4 5 7 . . 
. . . 1 . . . 3 . 
. . 1 . . . . 6 8
. . 8 5 . . . 1 . 
. 9 . . . . 4 . .

تخته حل‌ شده

برای این که راه‌حل را نیز به سرعت افشا کرده باشیم، باید بیان کنیم که معمای به درستی حل‌ شده نتیجه زیر را به دست می‌دهد:

1
2
3
4
5
6
7
8
9
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

الگوریتم پس‌گرد

در این بخش به بررسی الگوریتم پس‌گرد برای حل معمای سودوکو می‌پردازیم.

مقدمه

الگوریتم «پس‌گرد» (Backtracking) تلاش می‌کند که معما را از طریق تست کردن همه سلول‌ها برای یک راه‌حل معتبر حل کند. اگر هیچ کدام از قیدهای مسئله نقض نشود، الگوریتم به سلول بعدی می‌رود و آن را با راه‌حل‌های ممکن پر کرده و همه بررسی‌ها را تکرار می‌کند.

اگر یک نقض قید وجود داشته باشد، در این صورت مقدار سلول را یک واحد افزایش می‌دهد. زمانی که مقدار سلول به 9 برسد، و همچنان راه‌حل معتبری یافت نشود، الگوریتم به عقب بازمی‌گردد و در سلول قبلی عدد مربوطه را یک واحد افزایش می‌دهد و این فرایند تکرار می‌شود. بدین ترتیب همه راه‌حل‌های ممکن تست می‌شوند.

برای یادگیری بیشتر راجع به الگوریتم پس‌گرد، می‌توانید سه مطلبی که در ادامه آمده‌اند را نیز مطالعه کنید:

راه‌حل

قبل از هر چیز باید تخته خود را به صورت آرایه‌ای دوبعدی از اعداد صحیح تعریف کنیم. ما از مقدار 0 برای نمایش سلول خالی خود استفاده می‌کنیم.

1
2
3
4
5
6
7
8
9
10
11
int[][] 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 } 
};

در ادامه متد ()solve را ایجاد می‌کنیم که board را به عنوان پارامتر ورودی می‌گیرد و روی ردیف‌ها و ستون‌ها حلقه‌ای تعریف می‌کند و مقادیر مختلف را برای یافتن راه‌حل معتبر تست می‌کند.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
private boolean solve(int[][] board) {
    for (int row = BOARD_START_INDEX; row < BOARD_SIZE; row++) {
        for (int column = BOARD_START_INDEX; column < BOARD_SIZE; column++) {
            if (board[row][column] == NO_VALUE) {
                for (int k = MIN_VALUE; k <= MAX_VALUE; k++) {
                    board[row][column] = k;
                    if (isValid(board, row, column) && solve(board)) {
                        return true;
                    }
                    board[row][column] = NO_VALUE;
                }
                return false;
            }
        }
    }
    return true;
}

متد دیگر که نیاز داریم متد ()isValid است که به بررسی قیدهای سودوکو می‌پردازد، یعنی بررسی می‌کند آیا ردیف ستون و شبکه 3 × 3 معتبر هستند یا نه.

1
2
3
4
5
private boolean isValid(int[][] board, int row, int column) {
    return (rowConstraint(board, row)
      && columnConstraint(board, column) 
      && subsectionConstraint(board, row, column));
}

این سه بررسی نسبتاً مشابه هستند. ابتدا شروع به بررسی ردیف‌ها می‌کنیم:

1
2
3
4
5
private boolean rowConstraint(int[][] board, int row) {
    boolean[] constraint = new boolean[BOARD_SIZE];
    return IntStream.range(BOARD_START_INDEX, BOARD_SIZE)
      .allMatch(column -> checkConstraint(board, row, constraint, column));
}

سپس از کد نسبتاً مشابهی برای اعتبارسنجی ستون استفاده می‌کنیم:

1
2
3
4
5
private boolean columnConstraint(int[][] board, int column) {
    boolean[] constraint = new boolean[BOARD_SIZE];
    return IntStream.range(BOARD_START_INDEX, BOARD_SIZE)
      .allMatch(row -> checkConstraint(board, row, constraint, column));
}

به علاوه باید زیربخش 3 × 3 را نیز بررسی کنیم:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
private boolean subsectionConstraint(int[][] board, int row, int column) {
    boolean[] constraint = new boolean[BOARD_SIZE];
    int subsectionRowStart = (row / SUBSECTION_SIZE) * SUBSECTION_SIZE;
    int subsectionRowEnd = subsectionRowStart + SUBSECTION_SIZE;
 
    int subsectionColumnStart = (column / SUBSECTION_SIZE) * SUBSECTION_SIZE;
    int subsectionColumnEnd = subsectionColumnStart + SUBSECTION_SIZE;
 
    for (int r = subsectionRowStart; r < subsectionRowEnd; r++) {
        for (int c = subsectionColumnStart; c < subsectionColumnEnd; c++) {
            if (!checkConstraint(board, r, constraint, c)) return false;
        }
    }
    return true;
}

در نهایت به یک متد ()checkConstraint نیاز داریم:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
boolean checkConstraint(
  int[][] board, 
  int row, 
  boolean[] constraint, 
  int column) {
    if (board[row][column] != NO_VALUE) {
        if (!constraint[board[row][column] - 1]) {
            constraint[board[row][column] - 1] = true;
        } else {
            return false;
        }
    }
    return true;
}

زمانی که همه این موارد بررسی شدند، متد ()isValid مقدار true بازگشت می‌دهد. اینک ما تقریباً آماده تست راه‌حل هستیم. کار نوشتن الگوریتم به پایان رسیده است. اما فعلاً الگوریتم صرفاً مقادیر true یا false بازگشت می‌دهد.

بنابراین باید به صورت چشمی تخته را بررسی کنیم تا ببینیم آیا باید نتیجه را نمایش دهیم یا نه. به ظاهر این بخشی از الگوریتم نیست.

1
2
3
4
5
6
7
8
private void printBoard() {
    for (int row = BOARD_START_INDEX; row < BOARD_SIZE; row++) {
        for (int column = BOARD_START_INDEX; column < BOARD_SIZE; column++) {
            System.out.print(board[row][column] + " ");
        }
        System.out.println();
    }
}

بدین ترتیب ما موفق شدیم الگوریتم پس‌گرد را که به حل معمای سودوکو می‌پردازد پیاده‌سازی کنیم. بدیهی است که جا برای بهینه‌سازی وجود دارد، چون الگوریتم به روشی خام‌دستانه همه ترکیب‌های ممکن را بارها و بارها بررسی می‌کند و ما می‌دانیم که برخی راه‌حل‌ها اساساً نمی‌توانند معتبر باشند.

لینک‌های رقصنده

در این بخش به بررسی روش لینک‌های رقصنده برای حل معمای سودوکو و پیاده‌سازی آن در جاوا می‌پردازیم.

پوشش دقیق

در این بخش راه‌حل دیگری را بررسی می‌کنیم. سودوکو را می‌توان یک مسئله «پوشش دقیق» (Exact Cover) توصیف کرد که می‌تواند از طریق ماتریس وقوع نمایش یابد. این ماتریس روابط بین دو شیء را نمایش می‌دهد.

برای نمونه اگر اعداد 1 تا 7 را انتخاب کنیم و مجموعه‌هایی به صورت {S = {A, B, C, D, E, F داشته باشیم که:

A = {1, 4, 7}
B = {1, 4}
C = {4, 5, 7}
D = {3, 5, 6}
E = {2, 3, 6, 7}
F = {2, 7}

هدف ما این است که چنان زیرمجموعه‌هایی را انتخاب کنیم که هر عدد تنها یک بار وجود داشته باشد و بنا به تعریف هیچ تکراری نداشته باشد. می‌توان مسئله را با استفاده از یک ماتریس نمایش داد که در آن ستون‌ها عدد و ردیف‌ها مجموعه هستند.

1
2
3
4
5
6
7
  | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 
A | 1 | 0 | 0 | 1 | 0 | 0 | 1 |
B | 1 | 0 | 0 | 1 | 0 | 0 | 0 |
C | 0 | 0 | 0 | 1 | 1 | 0 | 1 |
D | 0 | 0 | 1 | 0 | 1 | 1 | 0 |
E | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
F | 0 | 1 | 0 | 0 | 0 | 0 | 1 |

زیرمجموعه {S* = {B, D, F یک پوشش دقیق است:

1
2
3
4
  | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 
B | 1 | 0 | 0 | 1 | 0 | 0 | 0 |
D | 0 | 0 | 1 | 0 | 1 | 1 | 0 |
F | 0 | 1 | 0 | 0 | 0 | 0 | 1 |

هر ستون دقیقاً یک عدد 1 در همه ردیف‌های منتخب دارد.

الگوریتم X

الگوریتم X یک رویکرد آزمون‌وخطا برای یافتن همه راه‌حل‌ها برای مسئله پوشش دقیق است. یعنی اگر از مجموعه مثال {S = {A, B, C, D, E, F آغاز کنیم، باید زیرمجموعه {S* = {B, D, F را بیابیم.

طرز کار الگوریتم X چنین است:

اگر ماتریس A هیچ ستونی نداشته باشد، راه‌حل جزئی فعلی یک راه‌حل معتبر است.
با موفقیت کار را خاتمه می‌دهیم، در غیر این صورت یک ستون C را انتخاب کنید (رویکرد قطعیتی).
یک ردیف r را چنان انتخاب کنید که Ar, c = 1 (غیر قطعیتی) یعنی همه احتمال‌ها را بررسی کنید.
ردیف r را در راه‌حل جزئی بگنجانید.
برای هر ستون j که رابطه Ar, j = 1 برقرار باشد، برای هر ردیف r که Ai, j = 1 برقرار باشد:
ردیف i را از ماتریس A حذف کنید و ستون j را از ماتریس A حذف کنید.
الگوریتم را به صورت بازگشتی روی ماتریس کاهش یافته A تکرار کنید.

یک پیاده‌سازی مؤثر از الگوریتم X الگوریتم لینک‌های رقصنده (به اختصار DLX) است که از سوی دکتر «دونالد نات» (Donald Knuth) پیشنهاد شده است.

بخش عمده راه‌حل زیر از این پیاده‌سازی جاوا (+) الهام گرفته است.

مسئله پوشش دقیق

ابتدا باید یک ماتریس ایجاد کنیم که معمای سودوکو را به صورت یک مسئله پوشش دقیق نمایش دهد. این ماتریس 3^9 ردیف خواهد داشت یعنی برای هر موقعیت منفرد ممکن (9 ردیف × 9 ستون) از هر عدد ممکن (9 عدد) یک ردیف هست.

ستون‌ها نماینده تخته هستند (9 × 9) که در تعداد قیدها ضرب شده‌اند. همچنین سه قید نیز تعریف کرده‌ایم:

هر ردیف تنها یک عدد از یک نوع خواهد داشت.
هر ستون تنها یک عدد از یک نوع خواهد داشت.
هر زیرمجموعه تنها یک عدد از یک نوع خواهد داشت.

به علاوه قید صریح چهارمی نیز وجود دارد:

در هر سلول تنها یک عدد می‌تواند قرار بگیرد.

بدین ترتیب در مجموع چهار قید داریم و از این رو در ماتریس پوشش دقیق، 4 × 9 × 9 ستون وجود دارند:

1
2
3
4
5
6
7
private static int BOARD_SIZE = 9;
private static int SUBSECTION_SIZE = 3;
private static int NO_VALUE = 0;
private static int CONSTRAINTS = 4;
private static int MIN_VALUE = 1;
private static int MAX_VALUE = 9;
private static int COVER_START_INDEX = 1;

1
2
3
4
private int getIndex(int row, int column, int num) {
    return (row - 1) * BOARD_SIZE * BOARD_SIZE 
      + (column - 1) * BOARD_SIZE + (num - 1);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
private boolean[][] createExactCoverBoard() {
    boolean[][] coverBoard = new boolean
      [BOARD_SIZE * BOARD_SIZE * MAX_VALUE]
      [BOARD_SIZE * BOARD_SIZE * CONSTRAINTS];
 
    int hBase = 0;
    hBase = checkCellConstraint(coverBoard, hBase);
    hBase = checkRowConstraint(coverBoard, hBase);
    hBase = checkColumnConstraint(coverBoard, hBase);
    checkSubsectionConstraint(coverBoard, hBase);
     
    return coverBoard;
}
 
private int checkSubsectionConstraint(boolean[][] coverBoard, int hBase) {
    for (int row = COVER_START_INDEX; row <= BOARD_SIZE; row += SUBSECTION_SIZE) {
        for (int column = COVER_START_INDEX; column <= BOARD_SIZE; column += SUBSECTION_SIZE) {
            for (int n = COVER_START_INDEX; n <= BOARD_SIZE; n++, hBase++) {
                for (int rowDelta = 0; rowDelta < SUBSECTION_SIZE; rowDelta++) {
                    for (int columnDelta = 0; columnDelta < SUBSECTION_SIZE; columnDelta++) {
                        int index = getIndex(row + rowDelta, column + columnDelta, n);
                        coverBoard[index][hBase] = true;
                    }
                }
            }
        }
    }
    return hBase;
}
 
private int checkColumnConstraint(boolean[][] coverBoard, int hBase) {
    for (int column = COVER_START_INDEX; column <= BOARD_SIZE; c++) {
        for (int n = COVER_START_INDEX; n <= BOARD_SIZE; n++, hBase++) {
            for (int row = COVER_START_INDEX; row <= BOARD_SIZE; row++) {
                int index = getIndex(row, column, n);
                coverBoard[index][hBase] = true;
            }
        }
    }
    return hBase;
}
 
private int checkRowConstraint(boolean[][] coverBoard, int hBase) {
    for (int row = COVER_START_INDEX; row <= BOARD_SIZE; r++) {
        for (int n = COVER_START_INDEX; n <= BOARD_SIZE; n++, hBase++) {
            for (int column = COVER_START_INDEX; column <= BOARD_SIZE; column++) {
                int index = getIndex(row, column, n);
                coverBoard[index][hBase] = true;
            }
        }
    }
    return hBase;
}
 
private int checkCellConstraint(boolean[][] coverBoard, int hBase) {
    for (int row = COVER_START_INDEX; row <= BOARD_SIZE; row++) {
        for (int column = COVER_START_INDEX; column <= BOARD_SIZE; column++, hBase++) {
            for (int n = COVER_START_INDEX; n <= BOARD_SIZE; n++) {
                int index = getIndex(row, column, n);
                coverBoard[index][hBase] = true;
            }
        }
    }
    return hBase;
}

سپس باید تخته ذخیره ایجاد شده را به‌روزرسانی کنیم تا طرح‌بندی اولیه معما ایجاد شود:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
private boolean[][] initializeExactCoverBoard(int[][] board) {
    boolean[][] coverBoard = createExactCoverBoard();
    for (int row = COVER_START_INDEX; row <= BOARD_SIZE; row++) {
        for (int column = COVER_START_INDEX; column <= BOARD_SIZE; column++) {
            int n = board[row - 1][column - 1];
            if (n != NO_VALUE) {
                for (int num = MIN_VALUE; num <= MAX_VALUE; num++) {
                    if (num != n) {
                        Arrays.fill(coverBoard[getIndex(row, column, num)], false);
                    }
                }
            }
        }
    }
    return coverBoard;
}

اینک آماده هستیم که به مرحله بعد برویم. در ادامه دو کلاس ایجاد می‌کنیم که سلول‌های ما را به همدیگر لینک می‌کنند.

گره رقصان

الگوریتم لینک‌های رقصان بر مبنای این مشاهده ابتدایی عمل می‌کند که عملیات زیر روی لیست‌های لینک شده دوطرفه از گره‌ها:

1
2
node.prev.next = node.next
node.next.prev = node.prev

گره را حذف می‌کند و همزمان:

1
2
node.prev = node
node.next = node

گره را بازیابی می‌کند.

هر گره در DLX به گره سمت چپ، راست، بالا و پایین خود لینک شده است. کلاس DancingNode همه عملیات مورد نیاز برای افزودن و حذف گره‌ها را در خود دارد:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class DancingNode {
    DancingNode L, R, U, D;
    ColumnNode C;
 
    DancingNode hookDown(DancingNode node) {
        assert (this.C == node.C);
        node.D = this.D;
        node.D.U = node;
        node.U = this;
        this.D = node;
        return node;
    }
 
    DancingNode hookRight(DancingNode node) {
        node.R = this.R;
        node.R.L = node;
        node.L = this;
        this.R = node;
        return node;
    }
 
    void unlinkLR() {
        this.L.R = this.R;
        this.R.L = this.L;
    }
 
    void relinkLR() {
        this.L.R = this.R.L = this;
    }
 
    void unlinkUD() {
        this.U.D = this.D;
        this.D.U = this.U;
    }
 
    void relinkUD() {
        this.U.D = this.D.U = this;
    }
 
    DancingNode() {
        L = R = U = D = this;
    }
 
    DancingNode(ColumnNode c) {
        this();
        C = c;
    }
}

گره ستون

کلاس ColumnNode ستون‌ها را به هم لینک می‌کند:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class ColumnNode extends DancingNode {
    int size;
    String name;
 
    ColumnNode(String n) {
        super();
        size = 0;
        name = n;
        C = this;
    }
 
    void cover() {
        unlinkLR();
        for (DancingNode i = this.D; i != this; i = i.D) {
            for (DancingNode j = i.R; j != i; j = j.R) {
                j.unlinkUD();
                j.C.size--;
            }
        }
    }
 
    void uncover() {
        for (DancingNode i = this.U; i != this; i = i.U) {
            for (DancingNode j = i.L; j != i; j = j.L) {
                j.C.size++;
                j.relinkUD();
            }
        }
        relinkLR();
    }
}

حل‌ کننده

در این مرحله باید یک شبکه متشکل از اشیای DancingNode و ColumnNode خود بسازیم:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
private ColumnNode makeDLXBoard(boolean[][] grid) {
    int COLS = grid[0].length;
 
    ColumnNode headerNode = new ColumnNode("header");
    List<ColumnNode> columnNodes = new ArrayList<>();
 
    for (int i = 0; i < COLS; i++) {
        ColumnNode n = new ColumnNode(Integer.toString(i));
        columnNodes.add(n);
        headerNode = (ColumnNode) headerNode.hookRight(n);
    }
    headerNode = headerNode.R.C;
 
    for (boolean[] aGrid : grid) {
        DancingNode prev = null;
        for (int j = 0; j < COLS; j++) {
            if (aGrid[j]) {
                ColumnNode col = columnNodes.get(j);
                DancingNode newNode = new DancingNode(col);
                if (prev == null) prev = newNode;
                col.U.hookDown(newNode);
                prev = prev.hookRight(newNode);
                col.size++;
            }
        }
    }
 
    headerNode.size = COLS;
 
    return headerNode;
}

ما از جستجوی شهودی برای یافتن ستون‌ها استفاده می‌کنیم و زیرمجموعه‌ای از ماتریس را بازگشت می‌دهیم:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
private ColumnNode selectColumnNodeHeuristic() {
    int min = Integer.MAX_VALUE;
    ColumnNode ret = null;
    for (
      ColumnNode c = (ColumnNode) header.R; 
      c != header; 
      c = (ColumnNode) c.R) {
        if (c.size < min) {
            min = c.size;
            ret = c;
        }
    }
    return ret;
}

در نهایت می‌توانیم به صورت بازگشتی به دنبال پاسخ بگردیم:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
private void search(int k) {
    if (header.R == header) {
        handleSolution(answer);
    } else {
        ColumnNode c = selectColumnNodeHeuristic();
        c.cover();
 
        for (DancingNode r = c.D; r != c; r = r.D) {
            answer.add(r);
 
            for (DancingNode j = r.R; j != r; j = j.R) {
                j.C.cover();
            }
 
            search(k + 1);
 
            r = answer.remove(answer.size() - 1);
            c = r.C;
 
            for (DancingNode j = r.L; j != r; j = j.L) {
                j.C.uncover();
            }
        }
        c.uncover();
    }
}

اگر ستون دیگری باقی نمانده باشد، در این صورت می‌توانیم تخته سودوکوی حل‌شده را در خروجی نمایش دهیم.

مقایسه راه‌ حل‌ها

می‌توانیم دو الگوریتم مختلف را با اجرا روی رایانه یکسان با هم مقایسه کنیم. بدین ترتیب از تأثیرگذاری تفاوت اجزای محاسباتی رایانه مانند CPU یا RAM جلوگیری می‌کنیم، چون زمان‌های واقعی روی رایانه‌های مختلف متفاوت خواهد بود. با این حال، اینک می‌توانیم نتایج نسبی را ببینیم و بدین ترتیب می‌توان گفت که کدام الگوریتم سریع‌تر بود است. روی رایانه‌ای که ما تست کردیم، اجرای الگوریتم پس‌گرد برای حل معما به حدود 250 میلی‌ثانیه زمان نیاز داشت.

اگر این زمان را با زمان مورد نیاز از سوی الگوریتم لینک‌های رقصان یعنی 50 میلی‌ثانیه مقایسه کنیم، می‌بینیم که الگوریتم اخیر برنده این رقابت است. لینک‌های رقصان در زمان حل این مثال خاص در حدود پنج بار سریع‌تر عمل کرده است.

سخن پایانی

در این راهنما، به بررسی دو راه‌حل معمای سودوکو با استفاده از توابع داخلی جاوا پرداختیم. الگوریتم پس‌گرد که یک الگوریتم حمله کور است می‌تواند معمای استاندارد 9 × 9 سودوکو را به سادگی حل کند. در ادامه الگوریتم نسبتاً پیچیده‌تر لینک‌های رقصان نیز مورد بررسی قرار گرفت. هر دو الگوریتم می‌توانند معماهای سودوکو را در کسری از ثانیه حل کنند. در نهایت باید اشاره کنیم که کد کامل الگوریتم‌های بررسی شده در این مقاله را می‌توانید در این صفحه (+) مشاهده کن

منبع: فرادرس

مشاوره چهارشنبه 26 تیر 1398 ساعت 15:37

0 نظر

ساخت برنامه حل سودوکو در جاوا — از صفر تا صد

معمای سودوکو

تخته تست

1
2
3
4
5
6
7
8
9
8 . . . . . . . . 
. . 3 6 . . . . . 
. 7 . . 9 . 2 . . 
. 5 . . . 7 . . . 
. . . . 4 5 7 . . 
. . . 1 . . . 3 . 
. . 1 . . . . 6 8
. . 8 5 . . . 1 . 
. 9 . . . . 4 . .

تخته حل‌ شده

1
2
3
4
5
6
7
8
9
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

الگوریتم پس‌گرد

در این بخش به بررسی الگوریتم پس‌گرد برای حل معمای سودوکو می‌پردازیم.

مقدمه

برای یادگیری بیشتر راجع به الگوریتم پس‌گرد، می‌توانید سه مطلبی که در ادامه آمده‌اند را نیز مطالعه کنید:

راه‌حل

1
2
3
4
5
6
7
8
9
10
11
int[][] 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 } 
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
private boolean solve(int[][] board) {
    for (int row = BOARD_START_INDEX; row < BOARD_SIZE; row++) {
        for (int column = BOARD_START_INDEX; column < BOARD_SIZE; column++) {
            if (board[row][column] == NO_VALUE) {
                for (int k = MIN_VALUE; k <= MAX_VALUE; k++) {
                    board[row][column] = k;
                    if (isValid(board, row, column) && solve(board)) {
                        return true;
                    }
                    board[row][column] = NO_VALUE;
                }
                return false;
            }
        }
    }
    return true;
}

1
2
3
4
5
private boolean isValid(int[][] board, int row, int column) {
    return (rowConstraint(board, row)
      && columnConstraint(board, column) 
      && subsectionConstraint(board, row, column));
}

این سه بررسی نسبتاً مشابه هستند. ابتدا شروع به بررسی ردیف‌ها می‌کنیم:

1
2
3
4
5
private boolean rowConstraint(int[][] board, int row) {
    boolean[] constraint = new boolean[BOARD_SIZE];
    return IntStream.range(BOARD_START_INDEX, BOARD_SIZE)
      .allMatch(column -> checkConstraint(board, row, constraint, column));
}

سپس از کد نسبتاً مشابهی برای اعتبارسنجی ستون استفاده می‌کنیم:

1
2
3
4
5
private boolean columnConstraint(int[][] board, int column) {
    boolean[] constraint = new boolean[BOARD_SIZE];
    return IntStream.range(BOARD_START_INDEX, BOARD_SIZE)
      .allMatch(row -> checkConstraint(board, row, constraint, column));
}

به علاوه باید زیربخش 3 × 3 را نیز بررسی کنیم:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
private boolean subsectionConstraint(int[][] board, int row, int column) {
    boolean[] constraint = new boolean[BOARD_SIZE];
    int subsectionRowStart = (row / SUBSECTION_SIZE) * SUBSECTION_SIZE;
    int subsectionRowEnd = subsectionRowStart + SUBSECTION_SIZE;
 
    int subsectionColumnStart = (column / SUBSECTION_SIZE) * SUBSECTION_SIZE;
    int subsectionColumnEnd = subsectionColumnStart + SUBSECTION_SIZE;
 
    for (int r = subsectionRowStart; r < subsectionRowEnd; r++) {
        for (int c = subsectionColumnStart; c < subsectionColumnEnd; c++) {
            if (!checkConstraint(board, r, constraint, c)) return false;
        }
    }
    return true;
}

در نهایت به یک متد ()checkConstraint نیاز داریم:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
boolean checkConstraint(
  int[][] board, 
  int row, 
  boolean[] constraint, 
  int column) {
    if (board[row][column] != NO_VALUE) {
        if (!constraint[board[row][column] - 1]) {
            constraint[board[row][column] - 1] = true;
        } else {
            return false;
        }
    }
    return true;
}

1
2
3
4
5
6
7
8
private void printBoard() {
    for (int row = BOARD_START_INDEX; row < BOARD_SIZE; row++) {
        for (int column = BOARD_START_INDEX; column < BOARD_SIZE; column++) {
            System.out.print(board[row][column] + " ");
        }
        System.out.println();
    }
}

لینک‌های رقصنده

در این بخش به بررسی روش لینک‌های رقصنده برای حل معمای سودوکو و پیاده‌سازی آن در جاوا می‌پردازیم.

پوشش دقیق

برای نمونه اگر اعداد 1 تا 7 را انتخاب کنیم و مجموعه‌هایی به صورت {S = {A, B, C, D, E, F داشته باشیم که:

A = {1, 4, 7}
B = {1, 4}
C = {4, 5, 7}
D = {3, 5, 6}
E = {2, 3, 6, 7}
F = {2, 7}

1
2
3
4
5
6
7
  | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 
A | 1 | 0 | 0 | 1 | 0 | 0 | 1 |
B | 1 | 0 | 0 | 1 | 0 | 0 | 0 |
C | 0 | 0 | 0 | 1 | 1 | 0 | 1 |
D | 0 | 0 | 1 | 0 | 1 | 1 | 0 |
E | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
F | 0 | 1 | 0 | 0 | 0 | 0 | 1 |

زیرمجموعه {S* = {B, D, F یک پوشش دقیق است:

1
2
3
4
  | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 
B | 1 | 0 | 0 | 1 | 0 | 0 | 0 |
D | 0 | 0 | 1 | 0 | 1 | 1 | 0 |
F | 0 | 1 | 0 | 0 | 0 | 0 | 1 |

هر ستون دقیقاً یک عدد 1 در همه ردیف‌های منتخب دارد.

الگوریتم X

طرز کار الگوریتم X چنین است:

اگر ماتریس A هیچ ستونی نداشته باشد، راه‌حل جزئی فعلی یک راه‌حل معتبر است.
با موفقیت کار را خاتمه می‌دهیم، در غیر این صورت یک ستون C را انتخاب کنید (رویکرد قطعیتی).
یک ردیف r را چنان انتخاب کنید که Ar, c = 1 (غیر قطعیتی) یعنی همه احتمال‌ها را بررسی کنید.
ردیف r را در راه‌حل جزئی بگنجانید.
برای هر ستون j که رابطه Ar, j = 1 برقرار باشد، برای هر ردیف r که Ai, j = 1 برقرار باشد:
ردیف i را از ماتریس A حذف کنید و ستون j را از ماتریس A حذف کنید.
الگوریتم را به صورت بازگشتی روی ماتریس کاهش یافته A تکرار کنید.

بخش عمده راه‌حل زیر از این پیاده‌سازی جاوا (+) الهام گرفته است.

مسئله پوشش دقیق

ستون‌ها نماینده تخته هستند (9 × 9) که در تعداد قیدها ضرب شده‌اند. همچنین سه قید نیز تعریف کرده‌ایم:

هر ردیف تنها یک عدد از یک نوع خواهد داشت.
هر ستون تنها یک عدد از یک نوع خواهد داشت.
هر زیرمجموعه تنها یک عدد از یک نوع خواهد داشت.

به علاوه قید صریح چهارمی نیز وجود دارد:

در هر سلول تنها یک عدد می‌تواند قرار بگیرد.

بدین ترتیب در مجموع چهار قید داریم و از این رو در ماتریس پوشش دقیق، 4 × 9 × 9 ستون وجود دارند:

1
2
3
4
5
6
7
private static int BOARD_SIZE = 9;
private static int SUBSECTION_SIZE = 3;
private static int NO_VALUE = 0;
private static int CONSTRAINTS = 4;
private static int MIN_VALUE = 1;
private static int MAX_VALUE = 9;
private static int COVER_START_INDEX = 1;

1
2
3
4
private int getIndex(int row, int column, int num) {
    return (row - 1) * BOARD_SIZE * BOARD_SIZE 
      + (column - 1) * BOARD_SIZE + (num - 1);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
private boolean[][] createExactCoverBoard() {
    boolean[][] coverBoard = new boolean
      [BOARD_SIZE * BOARD_SIZE * MAX_VALUE]
      [BOARD_SIZE * BOARD_SIZE * CONSTRAINTS];
 
    int hBase = 0;
    hBase = checkCellConstraint(coverBoard, hBase);
    hBase = checkRowConstraint(coverBoard, hBase);
    hBase = checkColumnConstraint(coverBoard, hBase);
    checkSubsectionConstraint(coverBoard, hBase);
     
    return coverBoard;
}
 
private int checkSubsectionConstraint(boolean[][] coverBoard, int hBase) {
    for (int row = COVER_START_INDEX; row <= BOARD_SIZE; row += SUBSECTION_SIZE) {
        for (int column = COVER_START_INDEX; column <= BOARD_SIZE; column += SUBSECTION_SIZE) {
            for (int n = COVER_START_INDEX; n <= BOARD_SIZE; n++, hBase++) {
                for (int rowDelta = 0; rowDelta < SUBSECTION_SIZE; rowDelta++) {
                    for (int columnDelta = 0; columnDelta < SUBSECTION_SIZE; columnDelta++) {
                        int index = getIndex(row + rowDelta, column + columnDelta, n);
                        coverBoard[index][hBase] = true;
                    }
                }
            }
        }
    }
    return hBase;
}
 
private int checkColumnConstraint(boolean[][] coverBoard, int hBase) {
    for (int column = COVER_START_INDEX; column <= BOARD_SIZE; c++) {
        for (int n = COVER_START_INDEX; n <= BOARD_SIZE; n++, hBase++) {
            for (int row = COVER_START_INDEX; row <= BOARD_SIZE; row++) {
                int index = getIndex(row, column, n);
                coverBoard[index][hBase] = true;
            }
        }
    }
    return hBase;
}
 
private int checkRowConstraint(boolean[][] coverBoard, int hBase) {
    for (int row = COVER_START_INDEX; row <= BOARD_SIZE; r++) {
        for (int n = COVER_START_INDEX; n <= BOARD_SIZE; n++, hBase++) {
            for (int column = COVER_START_INDEX; column <= BOARD_SIZE; column++) {
                int index = getIndex(row, column, n);
                coverBoard[index][hBase] = true;
            }
        }
    }
    return hBase;
}
 
private int checkCellConstraint(boolean[][] coverBoard, int hBase) {
    for (int row = COVER_START_INDEX; row <= BOARD_SIZE; row++) {
        for (int column = COVER_START_INDEX; column <= BOARD_SIZE; column++, hBase++) {
            for (int n = COVER_START_INDEX; n <= BOARD_SIZE; n++) {
                int index = getIndex(row, column, n);
                coverBoard[index][hBase] = true;
            }
        }
    }
    return hBase;
}

سپس باید تخته ذخیره ایجاد شده را به‌روزرسانی کنیم تا طرح‌بندی اولیه معما ایجاد شود:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
private boolean[][] initializeExactCoverBoard(int[][] board) {
    boolean[][] coverBoard = createExactCoverBoard();
    for (int row = COVER_START_INDEX; row <= BOARD_SIZE; row++) {
        for (int column = COVER_START_INDEX; column <= BOARD_SIZE; column++) {
            int n = board[row - 1][column - 1];
            if (n != NO_VALUE) {
                for (int num = MIN_VALUE; num <= MAX_VALUE; num++) {
                    if (num != n) {
                        Arrays.fill(coverBoard[getIndex(row, column, num)], false);
                    }
                }
            }
        }
    }
    return coverBoard;
}

گره رقصان

1
2
node.prev.next = node.next
node.next.prev = node.prev

گره را حذف می‌کند و همزمان:

1
2
node.prev = node
node.next = node

گره را بازیابی می‌کند.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class DancingNode {
    DancingNode L, R, U, D;
    ColumnNode C;
 
    DancingNode hookDown(DancingNode node) {
        assert (this.C == node.C);
        node.D = this.D;
        node.D.U = node;
        node.U = this;
        this.D = node;
        return node;
    }
 
    DancingNode hookRight(DancingNode node) {
        node.R = this.R;
        node.R.L = node;
        node.L = this;
        this.R = node;
        return node;
    }
 
    void unlinkLR() {
        this.L.R = this.R;
        this.R.L = this.L;
    }
 
    void relinkLR() {
        this.L.R = this.R.L = this;
    }
 
    void unlinkUD() {
        this.U.D = this.D;
        this.D.U = this.U;
    }
 
    void relinkUD() {
        this.U.D = this.D.U = this;
    }
 
    DancingNode() {
        L = R = U = D = this;
    }
 
    DancingNode(ColumnNode c) {
        this();
        C = c;
    }
}

گره ستون

کلاس ColumnNode ستون‌ها را به هم لینک می‌کند:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class ColumnNode extends DancingNode {
    int size;
    String name;
 
    ColumnNode(String n) {
        super();
        size = 0;
        name = n;
        C = this;
    }
 
    void cover() {
        unlinkLR();
        for (DancingNode i = this.D; i != this; i = i.D) {
            for (DancingNode j = i.R; j != i; j = j.R) {
                j.unlinkUD();
                j.C.size--;
            }
        }
    }
 
    void uncover() {
        for (DancingNode i = this.U; i != this; i = i.U) {
            for (DancingNode j = i.L; j != i; j = j.L) {
                j.C.size++;
                j.relinkUD();
            }
        }
        relinkLR();
    }
}

حل‌ کننده

در این مرحله باید یک شبکه متشکل از اشیای DancingNode و ColumnNode خود بسازیم:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
private ColumnNode makeDLXBoard(boolean[][] grid) {
    int COLS = grid[0].length;
 
    ColumnNode headerNode = new ColumnNode("header");
    List<ColumnNode> columnNodes = new ArrayList<>();
 
    for (int i = 0; i < COLS; i++) {
        ColumnNode n = new ColumnNode(Integer.toString(i));
        columnNodes.add(n);
        headerNode = (ColumnNode) headerNode.hookRight(n);
    }
    headerNode = headerNode.R.C;
 
    for (boolean[] aGrid : grid) {
        DancingNode prev = null;
        for (int j = 0; j < COLS; j++) {
            if (aGrid[j]) {
                ColumnNode col = columnNodes.get(j);
                DancingNode newNode = new DancingNode(col);
                if (prev == null) prev = newNode;
                col.U.hookDown(newNode);
                prev = prev.hookRight(newNode);
                col.size++;
            }
        }
    }
 
    headerNode.size = COLS;
 
    return headerNode;
}

ما از جستجوی شهودی برای یافتن ستون‌ها استفاده می‌کنیم و زیرمجموعه‌ای از ماتریس را بازگشت می‌دهیم:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
private ColumnNode selectColumnNodeHeuristic() {
    int min = Integer.MAX_VALUE;
    ColumnNode ret = null;
    for (
      ColumnNode c = (ColumnNode) header.R; 
      c != header; 
      c = (ColumnNode) c.R) {
        if (c.size < min) {
            min = c.size;
            ret = c;
        }
    }
    return ret;
}

در نهایت می‌توانیم به صورت بازگشتی به دنبال پاسخ بگردیم:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
private void search(int k) {
    if (header.R == header) {
        handleSolution(answer);
    } else {
        ColumnNode c = selectColumnNodeHeuristic();
        c.cover();
 
        for (DancingNode r = c.D; r != c; r = r.D) {
            answer.add(r);
 
            for (DancingNode j = r.R; j != r; j = j.R) {
                j.C.cover();
            }
 
            search(k + 1);
 
            r = answer.remove(answer.size() - 1);
            c = r.C;
 
            for (DancingNode j = r.L; j != r; j = j.L) {
                j.C.uncover();
            }
        }
        c.uncover();
    }
}

اگر ستون دیگری باقی نمانده باشد، در این صورت می‌توانیم تخته سودوکوی حل‌شده را در خروجی نمایش دهیم.

مقایسه راه‌ حل‌ها

سخن پایانی

منبع: فرادرس

مشاوره چهارشنبه 26 تیر 1398 ساعت 15:37

0 نظر

140
1
...
11
12
صفحه 13
14
15
...
28

طراحی سایت و برنامه نویسی

ابر برجسب

جدیدترین یادداشت‌ها

بایگانی

جستجو

رویدادهای سفارشی (Custom Events) در لاراول — راهنمای کاربردی

مفاهیم مقدماتی رویدادها و شنونده‌ها

مثالی از ارسال نوتیفیکیشن به عنوان معیار امنیتی

بررسی شنونده رویداد

ایجاد رویداد سفارشی در لاراول

استفاده از دستور artisan

تست شنونده رویداد (Event Listener)

اشتراک رویداد چیست؟

سخن پایانی

روش های برقراری ارتباط بین کلاس ها در سوئیفت ۵ — به زبان ساده

نوتیفیکیشن

نمایندگی

Callback

سخن پایانی

رویدادهای سفارشی (Custom Events) در لاراول — راهنمای کاربردی

مفاهیم مقدماتی رویدادها و شنونده‌ها

مثالی از ارسال نوتیفیکیشن به عنوان معیار امنیتی

بررسی شنونده رویداد

ایجاد رویداد سفارشی در لاراول

استفاده از دستور artisan

تست شنونده رویداد (Event Listener)

اشتراک رویداد چیست؟

سخن پایانی

ساخت برنامه حل سودوکو در جاوا — از صفر تا صد

معمای سودوکو

تخته تست

تخته حل‌ شده

الگوریتم پس‌گرد

مقدمه

راه‌حل

لینک‌های رقصنده

پوشش دقیق

الگوریتم X

مسئله پوشش دقیق

گره رقصان

گره ستون

حل‌ کننده

مقایسه راه‌ حل‌ها

سخن پایانی

ساخت برنامه حل سودوکو در جاوا — از صفر تا صد

معمای سودوکو

تخته تست

تخته حل‌ شده

الگوریتم پس‌گرد

مقدمه

راه‌حل

لینک‌های رقصنده

پوشش دقیق

الگوریتم X

مسئله پوشش دقیق

گره رقصان

گره ستون

حل‌ کننده

مقایسه راه‌ حل‌ها

سخن پایانی