There are a few different incarnations of it – some have slightly different wording, different names, or change the items in the riddle slightly. But they are all the exact same core problem.

The riddle itself is used as a benchmark in the evaluation of constraint satisfaction problems for computer algorithms.

What is the Einstein Riddle?

Even the origin of it the riddle is a little unclear. It's famously known as the Einstein Riddle because it was supposedly created by Einstein as a young man for fun. Others say it was used by Einstein to only select the smartest PhD students he would supervise.

But there are some claims online that it actually was invented by the author of Alice's Adventures in Wonderland, Lewis Carrol.

It's highly unlikely that it was written by Einstein, but that doesn't really matter. What's important is that, with a basic understanding of truth tables (and a bit of patience), you can solve it, too.

How to Solve Einstein's Riddle

I'm now going to give you a list of clues, and then you will need to answer a question at the end of the clues.

Just to be absolutely clear, all the clues are enough for you to solve it. You don't need any extra hints, and there aren't any assumptions I expect you to know.

There are 5 houses painted five different colors.
In each house lives a person with a different nationality.
These five owners drink a certain type of beverage, smoke a certain brand of cigar, and keep a certain pet.
No owners have the same pet, smoke the same brand of cigar, or drink the same beverage.

• The Brit lives in the red house
• The Swede keeps dogs as pets
• The Dane drinks tea
• The green house is on the left of the white house
• The person who smokes Pall Malls rears birds
• The owner of the yellow house smokes Dunhill
• The green house’s owner drinks coffee
• The man living in the center house drinks milk
• The Norwegian lives in the first (leftmost) house
• The man who smokes Blends lives next to the one who keeps cats
• The man who keeps horses lives next to the man who smokes Dunhill
• The owner who smokes BlueMaster drinks beer
• The German smokes Princes
• The Norwegian lives next to the blue house
• The man who smokes Blends has a neighbor who drinks water

Now to solve, tell me who owns the fish?

I solved it, but it did take me a couple attempts and a bit of scribbling on paper.

How I Approached the Problem

To solve the problem, the first thing I did was to try and group together the clues. There are two references to the green house in the clues, so I tried to "solve" and consider those two clues together when I was able to.

I then also filled out the center house's beverage as one clue immediately tells you, and I was also able to immediately fill out the leftmost house's nationality.

I essentially drew a really basic grid and eliminated and filled in possibilities based initially just on the clues. Then as I filled in more, I was able to fill in more details on other houses.

I don't want to keep going with the hints if you want to solve this for yourself, but that's a starting point.

A screenshot of part of a 5x5 table with every different possibility of Nationality, Color, Beverage, Pet and Smoking Cigar that can be removed on click.

To try and make it easier for anyone who wants to solve it or check their answer, I have made a basic site you can find here: http://einsteins-riddle.com/ – the screenshot from above is a part of the grid on the site.

On that site, you'll find a table with all the options laid out as clickable buttons. The grid is initially filled out with all the possibilities, and as you learn more you can remove possibilities until eventually there is only one option left.

At the bottom is a "Check Answer" button that will evaluate what you have left on your grid.

Try and solve it and see how you get on! If you prefer to do it via paper please do so.

I wish you luck 😊

If it stumps you, and you want to know how to solve it, you can find the solution here.

Why are Truth Tables Helpful?

I enjoy trying to work through these truth table problems, as it helps improve my clarity of thought.

Sometimes when I'm coding and need to carefully consider some complex Boolean states in my code (not this, and not that OR this and that (and not those)) I think that these puzzles help me reason more clearly to simplify my code.

They also help me technically plan out my approach to a problem, from the very beginning to the eventual solution.

I start from a basic set of requirements and no idea how all they fit together. But as I move along, I can go through a process of fact finding, checking edge cases, verifying/testing my logic against the requirements and finally submitting my work. All of these steps translate exactly to software development.

Whenever you have a complicated set of states you are confused by, draw a basic truth table. Or however you want to represent the problem. Breaking it down into smaller and smaller problems will allow you to solve almost anything.

Conclusion

I hope this has been an enjoyable brain teaser, and that you solved as much or as little as was fun for you.

I share my writing on Twitter if you enjoyed this article and want to see more.

In this article, we are going to create a sudoku solver with the help of Azure Form Recognizer, an AI-powered document extraction service.

The application will allow users to upload an image of the sudoku table. We will extract the data from the image, and then implement the sudoku solving algorithm on it.

We will use .NET for the backend, Angular for the front end, and Angular material for styling the application.

You can see a working demo of the application below.

Prerequisites

• Install the latest LTS version of Node.JS from https://nodejs.org/en/download/
• Install the Angular CLI from https://cli.angular.io/
• An Azure subscription account. You can create a free Azure account at https://azure.microsoft.com/en-in/free/
• Install the .NET Core 5.0 SDK from https://dotnet.microsoft.com/download/dotnet/5.0
• Install the latest version of Visual Studio 2019 from https://visualstudio.microsoft.com/downloads/

Source Code

You can get the source code from GitHub.

What is Azure Form Recognizer Cognitive Service?

The Azure Form Recognizer cognitive service allows us to build automated data processing software using machine learning technology. It lets us extract text, key/value pairs, selection marks, tables, and structure from our documents.

We can easily invoke the Form Recognizer models with the help of a REST API or client library SDKs.

The Form Recognizer cognitive service provides the following features:

• Prebuilt models: We can use the prebuilt models to extract data from the unique document type such as invoices, receipts, IDs, and business cards.
• Custom models: we can extract text, key/value pairs, selection marks, and table data from forms using the custom models. However, we need to train the custom models using our data so that it suits our custom needs.
• Layout API: It allows us to extract text, selection marks, and table structures from the documents.

In this article, we are going to use the layout API to extract content from the image of the sudoku table that the user uploads.

How to Create the Azure Form Recognizer Cognitive Service Resource

Login to the Azure portal and search for the cognitive services in the search bar and click on the result. On the next screen, click on the Create button. It will open the cognitive services marketplace page. Search for the Form Recognizer in the search bar and click on the “Form Recognizer” card from the search result.

This will open the Form Recognizer API page. Click on the Create button to create a new Form Recognizer resource. Refer to the image shown below.

On the Create Form Recognizer page, fill in the details as indicated below.

• Subscription: Select the subscription type from the dropdown.
• Resource group: Select an existing resource group or create a new one.
• Region: Choose the region which is right for you.
• Name: Give a unique name to your resource.
• Pricing tier: Select the pricing tier you want.

Click on the “Review +Create” button. Refer to the image shown below.

On the next page, check the terms of use, verify the information which you have provided, and then click on the “Create” button.

After your resource is successfully deployed, click on the “Go to resource” button. Click on the “Keys and the endpoint” link on the menu on the left. Refer to the image shown below.

Make a note of the endpoint and any one of the keys provided. We will be using these in the latter part of this article to invoke the Layout API of the Form recognizer service from the .NET code.

How to Create the ASP.NET Core Application

Open Visual Studio 2019 and click on “Create a new Project”. A “Create a new Project” dialog will open. Select “ASP.NET Core with Angular” and click on Next. Refer to the image shown below.

Now you will be at the “Configure your new project” screen. Provide the name for your application as ngSudokuSolver, and click on Next. Refer to the image shown below.

On the additional information page, select the target framework as .NET 5.0 and set the authentication type to none as shown in the image below.

This will create our project. The folder structure of the application looks like this:

The ClientApp folder contains the Angular code for our application. The Controllers folders will contain our API controllers. The angular components are present inside the ClientApp\src\app folder.

The default template contains few Angular components. These components will not affect our application, but for the sake of simplicity, we will delete fetchdata and counter folders from ClientApp/src/app folder. Also, remove the reference for these two components from the app.module.ts file.

How to Install the Required NuGet Packages

To install the package, navigate to Tools >> NuGet Package Manager >> Package Manager Console. It will open the Package Manager Console inside Visual Studio.

Run the following command to install the Polly library. This library allows you to express resilience and transient fault handling policies such as Retry, Circuit Breaker, Timeout, Bulkhead Isolation, and Fallback in a fluent and thread-safe manner.

Install-Package Polly -Version 7.2.1

Run the following command to install the Newtonsoft.Json package.

Install-Package Newtonsoft.Json -Version 13.0.1

How to Create the RetryMessage Handler

Right-click on the ngSudokuSolver project and select Add >> New Folder. Name the folder Models.

Again, right-click on the Models folder and select Add >> Class to add a new class file. Put the name of your class as HttpRetryMessageHandler.cs and click "Add".

Put the following code inside this class.

using Newtonsoft.Json;
using Polly;
using System;
using System.Net.Http;
using System.Threading;
using System.Threading.Tasks;

namespace ngSudokuSolver.Models
{
    public class HttpRetryMessageHandler : DelegatingHandler
    {
        public HttpRetryMessageHandler(HttpClientHandler handler) : base(handler) { }

        protected override Task<HttpResponseMessage> SendAsync(
            HttpRequestMessage request,
            CancellationToken cancellationToken) =>
            Policy
                .Handle<HttpRequestException>()
                .Or<TaskCanceledException>()
                .OrResult<HttpResponseMessage>(x =>
                {
                    string result = x.Content.ReadAsStringAsync().GetAwaiter().GetResult();
                    dynamic array = JsonConvert.DeserializeObject(result);

                    if (array["status"] == "running")
                    {
                        return true;
                    }
                    else
                    {
                        return false;
                    }
                })
                .WaitAndRetryAsync(7, retryAttempt => TimeSpan.FromSeconds(Math.Pow(2, retryAttempt)))
                .ExecuteAsync(() => base.SendAsync(request, cancellationToken));
    }
}

We will use the RetryMessageHandler to retry the sendAsync call. We will retry the HTTP call if the status of the HttpResponseMessage is “running”.

The maximum retry attempts is set to 7. On each retry, we will increase the duration of wait time by a power of 2. If the maximum number of retries has been exhausted and the HttpResponseMessage is not successful yet, we will return false.

How to Add the FormRecognizer Controller

Now we will add a new controller to our application.

Right-click on the Controllers folder and select Add >> New Item. An “Add New Item” dialog box will open.

Select “Visual C#” from the left panel, then select “API Controller-Empty” from the templates panel and put the name as FormRecognizerController.cs. Click on Add. Refer to the image below.

Put the following code inside this class.

using Microsoft.AspNetCore.Mvc;
using Newtonsoft.Json;
using Newtonsoft.Json.Linq;
using ngSudokuSolver.Models;
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Net.Http;
using System.Net.Http.Headers;
using System.Threading.Tasks;

namespace ngSudokuSolver.Controllers
{
    [Produces("application/json")]
    [Route("api/[controller]")]
    public class FormRecognizerController : ControllerBase
    {
        static string endpoint;
        static string apiKey;

        public FormRecognizerController()
        {
            endpoint = "https://sudokusolver.cognitiveservices.azure.com/";
            apiKey = "a9f75796b3ba49bdade48eb3b905cb0e";
        }

        [HttpPost, DisableRequestSizeLimit]
        public async Task<string[][]> Post()
        {
            try
            {
                string[][] sudokuArray = GetNewSudokuArray();

                if (Request.Form.Files.Count > 0)
                {
                    var file = Request.Form.Files[Request.Form.Files.Count - 1];

                    if (file.Length > 0)
                    {
                        var memoryStream = new MemoryStream();
                        file.CopyTo(memoryStream);
                        byte[] imageFileBytes = memoryStream.ToArray();
                        memoryStream.Flush();

                        string SudokuLayoutJSON = await GetSudokuBoardLayout(imageFileBytes);
                        if (SudokuLayoutJSON.Length > 0)
                        {
                            sudokuArray = GetSudokuBoardItems(SudokuLayoutJSON);
                        }
                    }
                }

                return sudokuArray;
            }
            catch
            {
                throw;
            }
        }

        static async Task<string> GetSudokuBoardLayout(byte[] byteData)
        {
            HttpClient client = new();
            client.DefaultRequestHeaders.Add("Ocp-Apim-Subscription-Key", apiKey);
            string uri = endpoint + "formrecognizer/v2.1-preview.3/layout/analyze";
            string LayoutJSON = string.Empty;

            using (ByteArrayContent content = new(byteData))
            {
                HttpResponseMessage response;
                content.Headers.ContentType = new MediaTypeHeaderValue("image/png");
                response = await client.PostAsync(uri, content);

                if (response.IsSuccessStatusCode)
                {
                    HttpHeaders headers = response.Headers;

                    if (headers.TryGetValues("Operation-Location", out IEnumerable<string> values))
                    {
                        string OperationLocation = values.First();
                        LayoutJSON = await GetJSON(OperationLocation);
                    }
                }
            }
            return LayoutJSON;
        }

        static async Task<string> GetJSON(string endpoint)
        {
            using var client = new HttpClient(new HttpRetryMessageHandler(new HttpClientHandler()));
            var request = new HttpRequestMessage();
            request.Method = HttpMethod.Get;
            request.RequestUri = new Uri(endpoint);

            client.DefaultRequestHeaders.Add("Ocp-Apim-Subscription-Key", apiKey);

            var response = await client.SendAsync(request);
            var result = response.Content.ReadAsStringAsync().GetAwaiter().GetResult();

            return result;
        }

        static string[][] GetSudokuBoardItems(string LayoutData)
        {
            string[][] sudokuArray = GetNewSudokuArray();
            dynamic array = JsonConvert.DeserializeObject(LayoutData);
            int countOfCells = ((JArray)array?.analyzeResult?.pageResults[0]?.tables[0]?.cells).Count;

            for (int i = 0; i < countOfCells; i++)
            {
                int rowIndex = array.analyzeResult.pageResults[0].tables[0].cells[i].rowIndex;
                int columnIndex = array.analyzeResult.pageResults[0].tables[0].cells[i].columnIndex;

                sudokuArray[rowIndex][columnIndex] = array.analyzeResult.pageResults[0].tables[0].cells[i]?.text;
            }
            return sudokuArray;
        }

        static string[][] GetNewSudokuArray()
        {
            string[][] sudokuArray = new string[9][];

            for (int i = 0; i < 9; i++)
            {
                sudokuArray[i] = new string[9];
            }

            return sudokuArray;
        }
    }
}

In the constructor of the class, we have initialized the key and the endpoint URL for the formrecognizer API.

The Post method will receive the image data as a file collection in the request body and return a two-dimensional array. We will convert the image data to a byte array and invoke the GetSudokuBoardLayout method. If we get a successful response and the JSON result is not empty, we will invoke the GetSudokuBoardItems method.

Inside the GetSudokuBoardLayout method, we will instantiate a new HttpClient. We will pass the subscription key in the header of the request.

When we use the formrecognizer API, we will get a status code as 202. This indicates that the service has accepted the request and will start processing later.

The response includes an "Operation-Location" header. The "Operation-Location" field contains the URL that we should use to get the result of the formrecognizer operation. The URL mentioned in the header will expire in 48 hours.

For the result of the formrecognizer service to be available, it requires a certain amount of time that depends on the length of the text.

This is where our RetryMessageHandler will be utilized. We will fetch the URL from the header and invoke the GetJSON method to fetch the JSON result.

Inside the GetJSON method, we create the HttpClient and initialize it with our custom HttpRetryMessageHandler. This method will return the JSON response as a string.

The GetSudokuBoardItems method will accept the JSON string. It will then iterate over the tables property of the JSON string to prepare the two-dimensional sudokuArray.

Now Let's Work on the Client Side of the Application

The code for the client-side is available in the ClientApp folder. We will use Angular CLI to work with the client code.

Using Angular CLI is not mandatory. I am using Angular CLI here as it is user-friendly and straightforward. If you do not want to use CLI then you can create the files for components and services manually.

Navigate to the ngSudokuSolver\ClientApp folder in your machine and open a command window. We will execute all our Angular CLI commands in this window.

How to Install Angular Material

Run the following command to add Angular Material to the project.

ng add @angular/material

This command will install Angular Material to your project and then ask the following questions to determine which features to include:

• Choose a prebuilt theme name, or "custom" for a custom theme: We will select the Indigo/Pink theme.
• Set up global Angular Material typography styles? (Y/n): Y
• Set up browser animations for Angular Material? (Y/n): Y

Refer to the image shown below:

How to Add the Module for Angular Material

Run the following command to create a new module.

ng g m ng-material

Open the src\app\ng-material\ng-material.module.ts file and put the following code inside it.

import { NgModule } from '@angular/core';
import { CommonModule } from '@angular/common';
import { MatButtonModule } from '@angular/material/button';
import { MatCardModule } from '@angular/material/card';
import { MatInputModule } from '@angular/material/input';
import { MatToolbarModule } from '@angular/material/toolbar';
import { MatDividerModule } from '@angular/material/divider';
import { MatIconModule } from '@angular/material/icon';

const materialModules = [
  MatButtonModule,
  MatCardModule,
  MatInputModule,
  MatToolbarModule,
  MatDividerModule,
  MatIconModule,
];

@NgModule({
  declarations: [],
  imports: [CommonModule, ...materialModules],
  exports: [...materialModules],
})
export class NgMaterialModule {}

We are importing all the required modules for Angular material components that we'll use in this application. A separate module for Angular material will make the application easy to maintain.

Import the NgMaterialModule in the app.module.ts file as shown below:

import { NgMaterialModule } from './ng-material/ng-material.module';

@NgModule({
    ...
    imports: [
        ...
        NgMaterialModule,
    ],
})

How to Configure the Nav-bar of the App

Open nav-menu.component.html and put the following code inside it.

<mat-toolbar color="primary" class="mat-elevation-z2">
  <mat-toolbar-row>
    <div>
      <button mat-button [routerLink]='["/"]'>
        <mat-icon>book</mat-icon> Sudoku Solver
      </button>
    </div>
  </mat-toolbar-row>
</mat-toolbar>

We have added the material toolbar and a button that will link to the base route of the application.

How to Create the Form Recognizer Service

We will create an Angular service that will invoke the Web API endpoints and pass the response to our component. Run the following command.

ng g s services\form-recognizer

This command will create a folder name as services and then create the following two files inside it:

• form-recognizer.service.ts — the service class file.
• form-recognizer.service.spec.ts — the unit test file for service.

Open the form-recognizer.service.ts file and put the following code inside it.

import { Injectable } from '@angular/core';
import { HttpClient } from '@angular/common/http';

@Injectable({
  providedIn: 'root',
})
export class FormRecognizerService {
  baseURL: string;

  constructor(private http: HttpClient) {
    this.baseURL = '/api/FormRecognizer';
  }

  getSudokuTableFromImage(image: FormData) {
    return this.http.post(this.baseURL, image);
  }
}

We have defined a variable baseURL that will hold the endpoint URL of our API. We will initialize the baseURL in the constructor and set it to the endpoint of the FormRecognizerController.

The getSudokuTableFromImage method will send a Post request to the FormRecognizerController and supply the parameter of type FormData. It will fetch a two-dimensional array that denotes the items in the sudoku table.

How to Update the Home Component

Open home.component.html and put the following code in it.

<div class="container">
  <h1 class="display-4">Solve Sudoku using Azure AI</h1>
  <mat-divider></mat-divider>
  <div class="row mt-3">
    <div class="col-md-6">
      <mat-card class="mat-elevation-z4">
        <mat-card-content>
          <table>
            <tr *ngFor="let row of gameBoard">
              <td *ngFor="let col of gameBoard">
                {{game[row][col]}}
              </td>
            </tr>
          </table>
        </mat-card-content>
        <mat-card-actions>
          <button type="button" mat-raised-button color="primary" (click)="SolveSudoku()"> Solve Sudoku </button>
        </mat-card-actions>
      </mat-card>
    </div>
    <div class="col-md-6">
      <div class="image-container">
        <img class="preview-image" src={{imagePreview}}>
      </div>
      <input type="file" (change)="uploadImage($event)" />
      <hr />
      <button mat-raised-button color="accent" (click)="GetSudokuTable()">
        <span *ngIf="loading" class="spinner-border spinner-border-sm mr-1"></span>Extract Sudoku Table
      </button>
    </div>
  </div>
</div>

We have created a 9x9 table that denotes a sudoku board. We have defined a file upload control that will allow us to upload an image. After uploading the image, the preview of the image will be displayed using an <img> element.

Clicking on the “Extract Sudoku Table” button will fetch the content of the sudoku from the image and partially fill the table. Clicking on “Solve Sudoku” will solve the sudoku and update the table with the result.

Open the home.component.ts file and put the following code inside it.

import { Component, OnDestroy, OnInit } from '@angular/core';
import { Subject } from 'rxjs';
import { FormRecognizerService } from '../services/form-recognizer.service';
import { takeUntil } from 'rxjs/operators';

@Component({
  selector: 'app-home',
  templateUrl: './home.component.html',
  styleUrls: ['./home.component.scss'],
})
export class HomeComponent implements OnDestroy {
  gameBoard = [0, 1, 2, 3, 4, 5, 6, 7, 8];
  loading = false;
  imageFile;
  imagePreview;
  maxFileSize: number;
  isValidFile = true;
  status: string;
  DefaultStatus: string;
  imageData = new FormData();
  game = new Array(9);
  private unsubscribe$ = new Subject();

  constructor(private formRecognizerService: FormRecognizerService) {
    this.DefaultStatus = 'Maximum size allowed for the image is 4 MB';
    this.status = this.DefaultStatus;
    this.maxFileSize = 4 * 1024 * 1024; // 4MB

    for (var i = 0; i < this.game.length; i++) {
      this.game[i] = new Array(9);
    }
  }

  uploadImage(event) {
    this.imageFile = event.target.files[0];
    if (this.imageFile.size > this.maxFileSize) {
      this.status = `The file size is ${this.imageFile.size} bytes, this is more than the allowed limit of ${this.maxFileSize} bytes.`;
      this.isValidFile = false;
    } else if (this.imageFile.type.indexOf('image') == -1) {
      this.status = 'Please upload a valid image file';
      this.isValidFile = false;
    } else {
      const reader = new FileReader();
      reader.readAsDataURL(event.target.files[0]);
      reader.onload = () => {
        this.imagePreview = reader.result;
      };
      this.status = this.DefaultStatus;
      this.isValidFile = true;
    }
  }

  GetSudokuTable() {
    if (this.isValidFile) {
      this.loading = true;
      this.imageData.append('imageFile', this.imageFile);

      this.formRecognizerService
        .getSudokuTableFromImage(this.imageData)
        .pipe(takeUntil(this.unsubscribe$))
        .subscribe(
          (result: any) => {
            this.game = result;
            this.loading = false;
          },
          () => {
            console.error();
            this.loading = false;
          }
        );
    }
  }

  SolveSudoku() {
    this.sudokuSolver(this.game);
  }

  ngOnDestroy() {
    this.unsubscribe$.next();
    this.unsubscribe$.complete();
  }

  private sudokuSolver(data) {
    for (let i = 0; i < 9; i++) {
      for (let j = 0; j < 9; j++) {
        if (data[i][j] == '') {
          for (let k = 1; k <= 9; k++) {
            if (this.isSudokuValid(data, i, j, k)) {
              data[i][j] = `${k}`;
              if (this.sudokuSolver(data)) {
                return true;
              } else {
                data[i][j] = '';
              }
            }
          }
          return false;
        }
      }
    }
    return true;
  }

  private isSudokuValid(board, row, col, k) {
    for (let i = 0; i < 9; i++) {
      const m = 3 * Math.floor(row / 3) + Math.floor(i / 3);
      const n = 3 * Math.floor(col / 3) + (i % 3);
      if (board[row][i] == k || board[i][col] == k || board[m][n] == k) {
        return false;
      }
    }
    return true;
  }
}

We will inject the formRecognizerService in the constructor of the HomeComponent and set a message and the value for the max image size allowed inside the constructor. We will also initialize the two-dimensional array to hold the value of the sudoku.

The uploadImage method will be invoked upon uploading an image. We will check if the uploaded file is a valid image and is within the allowed size limit. We will process the image data using a FileReader object. The readAsDataURL method will read the contents of the uploaded file.

When the read operation completes successfully, the reader.onload event will be triggered. The value of imagePreview will be set to the result returned by the fileReader object, which is of type ArrayBuffer.

Inside the GetSudokuTable method, we will append the image file to a variable for type FormData. We will invoke the getSudokuTableFromImage of the service and bind the result to the game array.

The sudokuSolver method will accept the Sudoku board as a parameter. We will then solve the sudoku board with the help of the backtracking algorithm.

Execution Demo

Press F5 to launch the application. Upload the image of a sudoku table. Click on the “Extract Sudoku Table” button. It will extract the content from the image and populate the table on the left side. Refer to the image shown below:

Click on the “Solve Sudoku” button. You can see the final result of the sudoku on the UI. Refer to the image shown below:

Summary

We have created a sudoku solver application using Angular and Azure form recognizer service. The application can extract the data from the image of a sudoku board uploaded by the user. We then implement backtracking to solve the sudoku. We have used Angular material for styling the app.

Get the Source code from GitHub and play around to get a better understanding.

See Also

• Optical Character Reader Using Angular And Azure Computer Vision
• Multi-Language Translator Using Blazor And Azure Cognitive Services
• Facebook Authentication And Authorization In Server-Side Blazor App
• Continuous Deployment For Angular App Using Heroku And GitHub
• Going Serverless With Blazor

If you like the article, please share it with your friends. You can also connect with me on Twitter and LinkedIn.

Originally published at https://ankitsharmablogs.com/

In this article, we've collected a few famous logic puzzles and their solutions. Can you solve them without peeking at the answer?

Knights and Knaves

For this logic puzzle, imagine there are two types of people, knights and knaves. Knights only tell the truth, while Knaves only tell lies.

There are many variations of this puzzle, but most involve asking a question to figure out who is the knight and who is the knave.

Red and Blue

There are two people standing in front of you, Red and Blue. Blue says, "We are both knaves." Who is really the knight and who is the knave?

Solution
It's impossible for Blue to be the knight. If Blue was a knight, the statement, "We are both knaves," would actually be a lie. Therefore, Blue is a knave as his statement is a lie, and Red must be a knight.

Two Paths

You arrive at a fork in the road and need to choose the correct path that leads to your destination. There are two people standing at the fork, and you know that one must be a knight and the other must be a knave.

What single question could you ask to one of the people to determine the correct path, A or B?

Solution
The question you can ask either person is, "What path would the other person tell me is the correct one?" The answer will always be the wrong path to take, and you can safely take the other path.

Imagine the correct path is A.

If you ask directly, "Which is the correct path?" the knave will say B is correct while the knight will say A.

However, when asked which path the other person would say is correct, the knave will lie and say that the knight would tell you path B is correct. Meanwhile, the knight will tell the truth about the knave's answer, and say that the knave will tell you that path B is the correct one.

In both cases you know that then answer, path B, is actually a lie, so you should take the other path.

The Monty Hall Problem

The Monty Hall Problem is a riddle on probability named after the host of the 70’s game show it’s based on, Let’s Make a Deal. This particular problem is a veridical paradox, which means that there is a solution that seems counter-intuitive, yet proven to be true.

Imagine you are on a game show and there are 3 doors, each with a different prize behind them. Behind one of the three doors is a car. Behind the other two doors there are goats.

You must choose one of the 3 doors to select as your prize.

Say you decide to open Door 1. The host, who knows where the car is, opens a different door, Door 2, which reveals a goat. He then asks if you would like to open Door 3 instead.

Should you choose Door 3 over your original choice? Does it even matter?

Solution
It turns out that your choice really does matter, and it is actually to your benefit to choose Door 3 instead of Door 1. Here's why.

When you chose Door 1 from the 3 closed doors, you had a 1 out of 3 chance that you picked the right one. Both Door 2 and Door 3 also have a 1 out of the 3 chance of having a car behind it.

Another way to think about it is that Doors 2 and 3 have a 2 out of 3 chance of having a car behind it combined.

But when the host opens Door 2 and reveals the goat, you suddenly have more information about the problem.

Remember that Doors 2 and 3 have a combined probability hiding the car 2/3rds of the time. When Door 2 was opened you know that there was no car behind it.

But this reveal does not change the combined probability of the two doors. That’s the key takeaway here!

Since you know that Door 2 has a 0/3 chance of hiding the car, you can now say that there's a 2/3 chance that the car is behind Door 3. Door 1 remains unchanged – there's only a 1/3 the car is behind it.

So if you decide to switch, you go from roughly a 33.33% chance to a 66.67% chance of finding the car. In other words, you are doubling your chances of success by opening Door 3 instead!

Yes, it is possible that Door 1 was hiding all along and host tricked you. That doesn’t matter. You are gambling by taking the deal, but you’re gambling smart. You should make the best decision with the information you’re given and let the dice roll.

In the long run, you'd perform better by switching than a contestant who decides to go with their first choice. Though it's not immediately obvious, the host is actually doing you a favor by offering you a better deal.

The Dining Philosophers Problem

The dining philosophers problem is a classic example in computer science to illustrate issues with synchronization. It was originally created by Edsger Dijkstra in 1965, who presented it to his students as a handful of computers competing for access to shared tape drives.

Imagine five silent philosophers sitting around a table, each with a bowl of spaghetti. There are forks on the table between each pair of adjacent philosophers.

Image courtesy of adit.io.

Each philosopher can only do one thing at a time: think and eat. However, a philosopher can only eat spaghetti when they have both the left and right forks. A fork can only be held by one philosopher at a time.

After a philosopher finishes eating, they need to put down both the left and right forks so they're available to the others. A philosopher can take a fork as soon as it's available, but can only start eating once they have both forks.

The philosophers are famous for their appetites – they can all eat endlessly and never get full. On top of that, the bowls of spaghetti magically replenish no matter how much is eaten.

The problem is, how can can you ensure that no philosopher will starve, and that they can continue eating and thinking forever?

Synchronization and Deadlock

In simple terms, the dining philosophers problem is an illustration of how synchronized access to a shared resource can result in creation of a deadlock situation.

Synchronization is used to control concurrent access to a shared resource. This is necessary in any situation where multiple independent actors may be competing for the use of one resource like the forks. Since there is only one resource available, we use synchronization to prevent confusion and chaos.

A Deadlock is a system state where no progress is possible. This situation can occur when synchronization is enforced, and many processes end up waiting for a shared resource which is being held by some other process. Like with the philosophers who are either stuck eating or thinking, the processes just keep waiting and execute no further.

Solutions

At first glance it appears like it would not be possible for a deadlock where all philosophers are stuck either eating or thinking. For example, pattern for each philosopher to follow might be:

1: think until the left fork is available; when it is, pick it up;

2: think until the right fork is available; when it is, pick it up;

3: when both forks are held, eat for a fixed amount of time;

4: then, put the right fork down;

5: then, put the left fork down;

6: repeat from the beginning.

Source: Wikipedia

There are many solutions possible to prevent deadlock. If we look closely, one problem in the algorithm above is that all philosophers have equal chance (have the same priority) of acquiring one fork. This prevents anyone from acquiring two forks and the whole system grinds to a halt.

Here are some possible solutions:

1. Priority: Some philosophers are assigned higher priority, so that the chance of acquiring both forks is increased.
2. Preemption (Politeness): Philosophers relinquish the acquired fork without eating, in case the other fork is not available.
3. Arbitration: A mediator allocates forks ensuring that two forks are given to one person, instead of one to many.

Now that you know how to solve these logic puzzles, treat yourself to an endless bowl of spaghetti. You earned it.