Write a C++ program that uses genetic algorithms to solve sudoku puzzles. The pr

Question

Write a C++ program that uses genetic algorithms to solve sudoku puzzles.
The program must accept input files in the following format(.txt-notepad)
when you initialize the board, you must maintain the invariant that each 3x3 subgrid (a.k.a. box, or block) contains each of the digits once and only once.
include "swap" but ignore "3-swap" and "insertion swap". Also ignore the additional condition on mutation regarding that "after the swap the numbers appear 3 times or less in their respective rows and columns

In addition to any console output, your program should write its interim results to a (log) file, every so many generations.

Explanation / Answer

import java.util.Random; //Generates a Sudoku puzzle through brute-force public class SudokuPuzzle { public int[][] puzzle = new int[9][9]; // Generated puzzle. public int[][] solved_puzzle = new int[9][9]; // The solved puzzle. private int[][] _tmp_grid = new int[9][9]; // For the solver private Random rand = new Random(); private short solution_count; // Should be 1 /** * Constructor generates a new puzzle, and its solution */ public SudokuPuzzle() { generateSolvedPuzzle(0); generatePuzzle(); } /** * Finds a solved puzzle through depth-first search */ private boolean generateSolvedPuzzle(int cur_cell) { if (cur_cell > 80) return true; int col = cur_cell % 9; int row = cur_cell / 9; // create a sequence of the integers {1,...,9} of random order int [] numbers = new int[9]; for (int i=0; i < 9; i++) numbers[i] = 1+i; shuffle_array(numbers); for (int i=0; i < 9; i++) { int n = numbers[i]; // for the next number in the array // if number is acceptable by Sudoku rules if (!existsInColumn(solved_puzzle, n, col) && !existsInRow(solved_puzzle, n, row) && !existsInSubGrid(solved_puzzle, n, row, col)) { // attempt to fill in the next cell with the current cell set to number solved_puzzle[row][col] = n; if (generateSolvedPuzzle(cur_cell + 1)) return true; solved_puzzle[row][col] = 0; // didn't work, reset cell and try the next number in sequence } } return false; // unreachable (since search is exhaustive and a solved puzzle must exist) } /** * Solves the Sudoku puzzle through depth-first, exhaustive search, and store the number of * solutions in solution_count. Currently, we want to use this only to detect if two solutions * exist. Hence, we stop the search as soon as two solutions have been found. * * */ private boolean _solvePuzzle(int cur_cell) { if (cur_cell > 80) { solution_count++; if (solution_count > 1) // two solutions detected. notify caller to abort search return true; return false; } int col = cur_cell % 9; int row = cur_cell / 9; if (_tmp_grid[row][col] == 0) // if cell is unfilled { for (int n=1; n

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.