{"id":289,"date":"2022-04-25T09:00:00","date_gmt":"2022-04-25T09:00:00","guid":{"rendered":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/danielle-notice\/?p=289"},"modified":"2024-03-10T16:44:17","modified_gmt":"2024-03-10T16:44:17","slug":"solving-sudoku-with-metaheuristics-gvns","status":"publish","type":"post","link":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/danielle-notice\/2022\/04\/25\/solving-sudoku-with-metaheuristics-gvns\/","title":{"rendered":"Solving Sudoku with Metaheuristics: GVNS"},"content":{"rendered":"Reading Time: <\/span> 5<\/span> minutes<\/span><\/span>\n

The last time I travelled, I saw a little old lady in the airport with her crossword puzzle book. My grandmother travels with her word search book. Me? In my old age, I will travel with a Sudoku book. Before I hit old age, I will take advantage of the opportunity to combine my studies with my favourite game. As it turns out, heuristic algorithms are pretty popular for solving, creating and rating Sudoku puzzles. In this post, we will look at how a metaheuristic, general variable neighbourhood search<\/strong>, has been used to solve Sudoku<\/strong> puzzle instances. <\/p>\n\n\n\n

  1. What is Sudoku?<\/li>
  2. What are metaheuristics?<\/li>
  3. General Variable Neighbourhood Search<\/li>
  4. Solving Sudoku<\/li><\/ol>\n\n\n\n

    1. What is Sudoku?<\/h2>\n\n\n\n
    \n
    \n

    Sudoku is Japanese puzzle which consists of an n2<\/sup> \u00d7 n2<\/sup><\/em> grid divided into n2<\/sup><\/em> sub-grids each of size n \u00d7 n<\/em>. The word Sudoku is a combination of two Japanese words, Su <\/em>(Number) and Duko<\/em> (Single) and loosely translates to \u201csolitary number\u201d. n<\/em> is the order of the puzzle, with n<\/em>=3 being the most popular. <\/p>\n\n\n\n

    The objective of Sudoku<\/strong> is to fill each cell in a way that every row, column and sub-square contains each integer between 1 and n2<\/sup><\/em> inclusive
    exactly once.<\/p>\n<\/div>\n\n\n\n

    \n
    \"\"<\/figure>\n<\/div>\n<\/div>\n\n\n\n

    Sudoku is an example of a combinatorial optimisation (CO) problem, which is a class of problems whose solution is in a finite or countably infinite set. Constructing or completing a Sudoku puzzle from a partially filled grid are both NP<\/em>-complete problems. This means that there is no deterministic algorithm which can solve all possible Sudoku problem instances in polynomial time. The solution space for an empty 9 \u00d7 9 Sudoku grid contains approximately 6.7 \u00d7 1021<\/sup> possible combinations. However, the pre-filled cells serve as constraints and reduce the number of possible combinations.<\/p>\n\n\n\n

    2. What are metaheuristics?<\/h2>\n\n\n\n

    When it comes to solving optimisation problems, there are 2 main types of approaches: exact methods and approximate methods. Exact methods are guaranteed to find an
    optimal solution for every finite problem instance of an CO problem. <\/p>\n\n\n\n

    Approximate methods such as heuristic algorithms can be used when there is no known exact method that can be used to solve the problem or when the known exact methods are too computationally expensive to be used practically. In the context of optimisation problems, a heuristic <\/strong>is a well-defined intelligent procedure – based on intuition, problem context and structure – designed to find an approximate solution to the problem. Unlike exact methods, the solutions found may not be optimal, but are some type of “acceptable”. The effectiveness of a heuristic depends on the quality of the approximations that it produces. <\/p>\n\n\n\n

    The performance of heuristics can be improved using metaheuristics<\/strong>, which are high-level,
    problem-independent strategies used to develop heuristic optimisation algorithms. They are designed to approximately solve a wide range of problems without needing to fundamentally change.<\/p>\n\n\n\n

    3. General Variable Neighbourhood Search<\/h2>\n\n\n\n

    Variable neighbourhood search (VNS) <\/strong>algorithms, which were originally proposed by Mladenovi\u0107 and Hansen (1997)<\/a>, are single-solution based metaheuristics. They successively explore a set of predefined neighbourhoods which are typically increasingly distant from the current candidate solution. <\/p>\n\n\n\n

    \"\"
    Illustration of the main idea of a basic VNS algorithm<\/figcaption><\/figure><\/div>\n\n\n\n

    VNS\u2019 main cycle is composed of three phases: shaking, local search and move.<\/em><\/p>\n\n\n\n

    In the shake phase, a random solution s\u2032<\/em> is selected from the k<\/em>th neighbourhood of the current solution s<\/em>. This s\u2032<\/em> is then used as the initial solution for the local search algorithm being used which produces a new candidate solution s\u2032\u2032<\/em>. In the move phase, if s\u2032\u2032<\/em> is better than the current solution s<\/em>, then it replaces s<\/em> and the cycle is restarted with this new solution; otherwise, the cycle is restarted with the same solution but a different neighbourhood.<\/p>\n\n\n\n

    \"\"<\/figure><\/div>\n\n\n\n

    Variable Neighbourhood Descent (VND) is a deterministic variant of the VNS algorithm. The VNS main cycle uses a best improvement method, choosing s\u2032\u2032<\/em> as the local optimum in neighbourhood Nk<\/sub><\/em>. <\/p>\n\n\n\n

    The General Variable Neighbourhood Search (GVNS)<\/strong> uses the VND as the local search procedure (line 7 of the algorithm).<\/p>\n\n\n\n

    4. Solving Sudoku with GVNS<\/h2>\n\n\n\n

    We will now look at the different elements from the algorithm above and how Sevkli and Hamza (2019)<\/a> used this metaheuristic to solve 9 \u00d7 9 Sudoku puzzles.<\/p>\n\n\n\n

    Solution representation:<\/strong> each sub-grid is numbered from 1 to 9, and each cell in a sub-grid is numbered from 1 to 9. So xij<\/sub><\/em> denotes the j<\/em>th cell in sub-grid i<\/em> (see grid above for example of labelled cell).<\/p>\n\n\n\n

    Solution Initialisation<\/strong>: To initialise the solution, for each cell, a random number is selected
    from a list of numbers that include all the numbers that could be assigned to the cell without violating any of the constraints with respect to the fixed cells. This is done in such a way that the sub-grid rule is satisfied. To reduce the solution space, they fixed the
    cells that only have one possible value and repeated that until there were no more such cells.<\/p>\n\n\n\n

    Cost function f(s)<\/em>: <\/strong>evaluates the violation of the row and column constraints and counts how many values are repeated in each row and in each column (illustrated in figure below). The goal is to minimise the cost function. The optimal solution will have f(s)=0<\/em>.<\/p>\n\n\n\n

    \"\"
    A candidate solution of the Sudoku puzzle with its fitness value. Repeated digits highlighted in first row and column.<\/figcaption><\/figure><\/div>\n\n\n\n

    Neighbourhood structures<\/h4>\n\n\n\n
    \n
    \n

    Only one neighbourhood structure, Invert<\/strong>, is defined for the shake phase. In this structure two cells in the sub-grid are selected and the order of the sub-sequence of cells between them is reversed.<\/p>\n\n\n\n

    There are 3 neighbourhood structures defined which are used in the VND local search:<\/p>\n\n\n\n