A novel hybrid genetic algorithm-based firefly mating algorithm for solving Sudoku View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2021-05-24

AUTHORS

Sunanda Jana, Anamika Dey, Arnab Kumar Maji, Rajat Kumar Pal

ABSTRACT

Sudoku is an NP-complete-based mathematical puzzle, which has enormous applications in the domains of steganography, visual cryptography, DNA computing, and so on. Therefore, solving Sudoku effectively can bring revolution in various fields. Several heuristics are there to solve this interesting structure. One of the heuristics, genetic algorithm, is used by many researchers to solve Sudoku successfully, but they face various problems. Genetic algorithm has so many lacunas, and to overcome these, we have hybridised it in a novel way. In this paper, we have developed a hybrid genetic algorithm-based firefly mating algorithm, which can solve Sudoku instances with a greater success rate for easy, medium, and hard difficulty level puzzles. Our proposed method has controlled “getting stuck in local optima”, considering a smaller population and lesser generation. More... »

PAGES

261-275

References to SciGraph publications

  • 2017-11-25. Solving Sudoku Puzzles Using Evolutionary Techniques—A Systematic Survey in SOFT COMPUTING: THEORIES AND APPLICATIONS
  • 1999. Preventing Premature Convergence to Local Optima in Genetic Algorithms via Random Offspring Generation in MULTIPLE APPROACHES TO INTELLIGENT SYSTEMS
  • 2017-04-27. Harmony search based memetic algorithms for solving sudoku in INTERNATIONAL JOURNAL OF SYSTEM ASSURANCE ENGINEERING AND MANAGEMENT
  • 2019-11-25. An Empirical Analysis of Genetic Algorithm with Different Mutation and Crossover Operators for Solving Sudoku in PATTERN RECOGNITION AND MACHINE INTELLIGENCE
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s11334-021-00397-4

    DOI

    http://dx.doi.org/10.1007/s11334-021-00397-4

    DIMENSIONS

    https://app.dimensions.ai/details/publication/pub.1138301751


    Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
    Incoming Citations Browse incoming citations for this publication using opencitations.net

    JSON-LD is the canonical representation for SciGraph data.

    TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

    [
      {
        "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
        "about": [
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/06", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Biological Sciences", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0604", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Genetics", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Department of Computer Science and Engineering, Haldia Institute of Technology, 721657, Haldia, Purba Medinipur, West Bengal, India", 
              "id": "http://www.grid.ac/institutes/grid.452520.4", 
              "name": [
                "Department of Computer Science and Engineering, Haldia Institute of Technology, 721657, Haldia, Purba Medinipur, West Bengal, India"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Jana", 
            "givenName": "Sunanda", 
            "id": "sg:person.015125667372.19", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015125667372.19"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Department of Computer Science and Engineering, University of Calcutta, JD-2, Sector-III, Salt Lake, 700106, Kolkata, West Bengal, India", 
              "id": "http://www.grid.ac/institutes/grid.59056.3f", 
              "name": [
                "Department of Computer Science and Engineering, University of Calcutta, JD-2, Sector-III, Salt Lake, 700106, Kolkata, West Bengal, India"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Dey", 
            "givenName": "Anamika", 
            "id": "sg:person.010445362731.34", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010445362731.34"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Department of Information Technology, North-Eastern Hill University, Umshing Mawkynroh, 793022, Shillong, Meghalaya, India", 
              "id": "http://www.grid.ac/institutes/grid.412227.0", 
              "name": [
                "Department of Information Technology, North-Eastern Hill University, Umshing Mawkynroh, 793022, Shillong, Meghalaya, India"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Maji", 
            "givenName": "Arnab Kumar", 
            "id": "sg:person.015723247772.61", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015723247772.61"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Department of Computer Science and Engineering, University of Calcutta, JD-2, Sector-III, Salt Lake, 700106, Kolkata, West Bengal, India", 
              "id": "http://www.grid.ac/institutes/grid.59056.3f", 
              "name": [
                "Department of Computer Science and Engineering, University of Calcutta, JD-2, Sector-III, Salt Lake, 700106, Kolkata, West Bengal, India"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Pal", 
            "givenName": "Rajat Kumar", 
            "id": "sg:person.013427074010.52", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013427074010.52"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/s13198-017-0620-x", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1085081628", 
              "https://doi.org/10.1007/s13198-017-0620-x"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-981-10-5687-1_71", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1092973080", 
              "https://doi.org/10.1007/978-981-10-5687-1_71"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-030-34869-4_39", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1122857204", 
              "https://doi.org/10.1007/978-3-030-34869-4_39"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-48765-4_16", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1011141970", 
              "https://doi.org/10.1007/978-3-540-48765-4_16"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2021-05-24", 
        "datePublishedReg": "2021-05-24", 
        "description": "Sudoku is an NP-complete-based mathematical puzzle, which has enormous applications in the domains of steganography, visual cryptography, DNA computing, and so on. Therefore, solving Sudoku effectively can bring revolution in various fields. Several heuristics are there to solve this interesting structure. One of the heuristics, genetic algorithm, is used by many researchers to solve Sudoku successfully, but they face various problems. Genetic algorithm has so many lacunas, and to overcome these, we have hybridised it in a novel way. In this paper, we have developed a hybrid genetic algorithm-based firefly mating algorithm, which can solve Sudoku instances with a greater success rate for easy, medium, and hard difficulty level puzzles. Our proposed method has controlled \u201cgetting stuck in local optima\u201d, considering a smaller population and lesser generation.", 
        "genre": "article", 
        "id": "sg:pub.10.1007/s11334-021-00397-4", 
        "inLanguage": "en", 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1044675", 
            "issn": [
              "1614-5046", 
              "1614-5054"
            ], 
            "name": "Innovations in Systems and Software Engineering", 
            "publisher": "Springer Nature", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "3", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "17"
          }
        ], 
        "keywords": [
          "genetic algorithm", 
          "visual cryptography", 
          "DNA computing", 
          "algorithm", 
          "Sudoku", 
          "enormous applications", 
          "heuristics", 
          "novel way", 
          "mathematical puzzles", 
          "computing", 
          "fireflies", 
          "cryptography", 
          "less generation", 
          "NPs", 
          "interesting structures", 
          "instances", 
          "success rate", 
          "applications", 
          "researchers", 
          "domain", 
          "way", 
          "greater success rate", 
          "method", 
          "revolution", 
          "generation", 
          "puzzle", 
          "field", 
          "structure", 
          "rate", 
          "small population", 
          "lacunae", 
          "population", 
          "paper", 
          "problem", 
          "hybrid genetic algorithm-based firefly", 
          "genetic algorithm-based firefly", 
          "algorithm-based firefly", 
          "Sudoku instances", 
          "hard difficulty level puzzles", 
          "difficulty level puzzles", 
          "level puzzles", 
          "novel hybrid genetic algorithm-based firefly"
        ], 
        "name": "A novel hybrid genetic algorithm-based firefly mating algorithm for solving Sudoku", 
        "pagination": "261-275", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1138301751"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s11334-021-00397-4"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s11334-021-00397-4", 
          "https://app.dimensions.ai/details/publication/pub.1138301751"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2022-01-01T18:58", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-springernature-scigraph/baseset/20220101/entities/gbq_results/article/article_890.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://doi.org/10.1007/s11334-021-00397-4"
      }
    ]
     

    Download the RDF metadata as:  json-ld nt turtle xml License info

    HOW TO GET THIS DATA PROGRAMMATICALLY:

    JSON-LD is a popular format for linked data which is fully compatible with JSON.

    curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/s11334-021-00397-4'

    N-Triples is a line-based linked data format ideal for batch operations.

    curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/s11334-021-00397-4'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s11334-021-00397-4'

    RDF/XML is a standard XML format for linked data.

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s11334-021-00397-4'


     

    This table displays all metadata directly associated to this object as RDF triples.

    143 TRIPLES      22 PREDICATES      71 URIs      59 LITERALS      6 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s11334-021-00397-4 schema:about anzsrc-for:06
    2 anzsrc-for:0604
    3 schema:author N46cbd6e12cf6479288d92f8051442a8f
    4 schema:citation sg:pub.10.1007/978-3-030-34869-4_39
    5 sg:pub.10.1007/978-3-540-48765-4_16
    6 sg:pub.10.1007/978-981-10-5687-1_71
    7 sg:pub.10.1007/s13198-017-0620-x
    8 schema:datePublished 2021-05-24
    9 schema:datePublishedReg 2021-05-24
    10 schema:description Sudoku is an NP-complete-based mathematical puzzle, which has enormous applications in the domains of steganography, visual cryptography, DNA computing, and so on. Therefore, solving Sudoku effectively can bring revolution in various fields. Several heuristics are there to solve this interesting structure. One of the heuristics, genetic algorithm, is used by many researchers to solve Sudoku successfully, but they face various problems. Genetic algorithm has so many lacunas, and to overcome these, we have hybridised it in a novel way. In this paper, we have developed a hybrid genetic algorithm-based firefly mating algorithm, which can solve Sudoku instances with a greater success rate for easy, medium, and hard difficulty level puzzles. Our proposed method has controlled “getting stuck in local optima”, considering a smaller population and lesser generation.
    11 schema:genre article
    12 schema:inLanguage en
    13 schema:isAccessibleForFree false
    14 schema:isPartOf N01be23439e1843d0b19711dff3f7b291
    15 N24cf3e6467f7478eb068023ed6c84408
    16 sg:journal.1044675
    17 schema:keywords DNA computing
    18 NPs
    19 Sudoku
    20 Sudoku instances
    21 algorithm
    22 algorithm-based firefly
    23 applications
    24 computing
    25 cryptography
    26 difficulty level puzzles
    27 domain
    28 enormous applications
    29 field
    30 fireflies
    31 generation
    32 genetic algorithm
    33 genetic algorithm-based firefly
    34 greater success rate
    35 hard difficulty level puzzles
    36 heuristics
    37 hybrid genetic algorithm-based firefly
    38 instances
    39 interesting structures
    40 lacunae
    41 less generation
    42 level puzzles
    43 mathematical puzzles
    44 method
    45 novel hybrid genetic algorithm-based firefly
    46 novel way
    47 paper
    48 population
    49 problem
    50 puzzle
    51 rate
    52 researchers
    53 revolution
    54 small population
    55 structure
    56 success rate
    57 visual cryptography
    58 way
    59 schema:name A novel hybrid genetic algorithm-based firefly mating algorithm for solving Sudoku
    60 schema:pagination 261-275
    61 schema:productId N675fbd4abec14c8693f0c288d9eaac18
    62 N76f197cf7e99434dae5fadd4e9515d8c
    63 schema:sameAs https://app.dimensions.ai/details/publication/pub.1138301751
    64 https://doi.org/10.1007/s11334-021-00397-4
    65 schema:sdDatePublished 2022-01-01T18:58
    66 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    67 schema:sdPublisher N4daba99178844227a4e9a6dbeea4f8d9
    68 schema:url https://doi.org/10.1007/s11334-021-00397-4
    69 sgo:license sg:explorer/license/
    70 sgo:sdDataset articles
    71 rdf:type schema:ScholarlyArticle
    72 N01be23439e1843d0b19711dff3f7b291 schema:volumeNumber 17
    73 rdf:type schema:PublicationVolume
    74 N24cf3e6467f7478eb068023ed6c84408 schema:issueNumber 3
    75 rdf:type schema:PublicationIssue
    76 N2eea0cce94fb40d595abaa82b388b94d rdf:first sg:person.015723247772.61
    77 rdf:rest N87569f7254a04cd88a1b83b3c517ca42
    78 N46cbd6e12cf6479288d92f8051442a8f rdf:first sg:person.015125667372.19
    79 rdf:rest Nf0fe6d63c6584baf8ea573b8f293cb15
    80 N4daba99178844227a4e9a6dbeea4f8d9 schema:name Springer Nature - SN SciGraph project
    81 rdf:type schema:Organization
    82 N675fbd4abec14c8693f0c288d9eaac18 schema:name doi
    83 schema:value 10.1007/s11334-021-00397-4
    84 rdf:type schema:PropertyValue
    85 N76f197cf7e99434dae5fadd4e9515d8c schema:name dimensions_id
    86 schema:value pub.1138301751
    87 rdf:type schema:PropertyValue
    88 N87569f7254a04cd88a1b83b3c517ca42 rdf:first sg:person.013427074010.52
    89 rdf:rest rdf:nil
    90 Nf0fe6d63c6584baf8ea573b8f293cb15 rdf:first sg:person.010445362731.34
    91 rdf:rest N2eea0cce94fb40d595abaa82b388b94d
    92 anzsrc-for:06 schema:inDefinedTermSet anzsrc-for:
    93 schema:name Biological Sciences
    94 rdf:type schema:DefinedTerm
    95 anzsrc-for:0604 schema:inDefinedTermSet anzsrc-for:
    96 schema:name Genetics
    97 rdf:type schema:DefinedTerm
    98 sg:journal.1044675 schema:issn 1614-5046
    99 1614-5054
    100 schema:name Innovations in Systems and Software Engineering
    101 schema:publisher Springer Nature
    102 rdf:type schema:Periodical
    103 sg:person.010445362731.34 schema:affiliation grid-institutes:grid.59056.3f
    104 schema:familyName Dey
    105 schema:givenName Anamika
    106 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010445362731.34
    107 rdf:type schema:Person
    108 sg:person.013427074010.52 schema:affiliation grid-institutes:grid.59056.3f
    109 schema:familyName Pal
    110 schema:givenName Rajat Kumar
    111 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013427074010.52
    112 rdf:type schema:Person
    113 sg:person.015125667372.19 schema:affiliation grid-institutes:grid.452520.4
    114 schema:familyName Jana
    115 schema:givenName Sunanda
    116 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015125667372.19
    117 rdf:type schema:Person
    118 sg:person.015723247772.61 schema:affiliation grid-institutes:grid.412227.0
    119 schema:familyName Maji
    120 schema:givenName Arnab Kumar
    121 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015723247772.61
    122 rdf:type schema:Person
    123 sg:pub.10.1007/978-3-030-34869-4_39 schema:sameAs https://app.dimensions.ai/details/publication/pub.1122857204
    124 https://doi.org/10.1007/978-3-030-34869-4_39
    125 rdf:type schema:CreativeWork
    126 sg:pub.10.1007/978-3-540-48765-4_16 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011141970
    127 https://doi.org/10.1007/978-3-540-48765-4_16
    128 rdf:type schema:CreativeWork
    129 sg:pub.10.1007/978-981-10-5687-1_71 schema:sameAs https://app.dimensions.ai/details/publication/pub.1092973080
    130 https://doi.org/10.1007/978-981-10-5687-1_71
    131 rdf:type schema:CreativeWork
    132 sg:pub.10.1007/s13198-017-0620-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1085081628
    133 https://doi.org/10.1007/s13198-017-0620-x
    134 rdf:type schema:CreativeWork
    135 grid-institutes:grid.412227.0 schema:alternateName Department of Information Technology, North-Eastern Hill University, Umshing Mawkynroh, 793022, Shillong, Meghalaya, India
    136 schema:name Department of Information Technology, North-Eastern Hill University, Umshing Mawkynroh, 793022, Shillong, Meghalaya, India
    137 rdf:type schema:Organization
    138 grid-institutes:grid.452520.4 schema:alternateName Department of Computer Science and Engineering, Haldia Institute of Technology, 721657, Haldia, Purba Medinipur, West Bengal, India
    139 schema:name Department of Computer Science and Engineering, Haldia Institute of Technology, 721657, Haldia, Purba Medinipur, West Bengal, India
    140 rdf:type schema:Organization
    141 grid-institutes:grid.59056.3f schema:alternateName Department of Computer Science and Engineering, University of Calcutta, JD-2, Sector-III, Salt Lake, 700106, Kolkata, West Bengal, India
    142 schema:name Department of Computer Science and Engineering, University of Calcutta, JD-2, Sector-III, Salt Lake, 700106, Kolkata, West Bengal, India
    143 rdf:type schema:Organization
     




    Preview window. Press ESC to close (or click here)


    ...