ClusterM

Slow sudoku solver

Oct 26th, 2021
623
143 days
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. using System;
  2. using System.Collections.Generic;
  3. using System.Linq;
  4.  
  5. namespace Sudoku
  6. {
  7.     public class Solution
  8.     {
  9.         public void SolveSudoku(char[][] board)
  10.         {
  11.             var cells = Clone(board);
  12.             Print(cells);
  13.             var started = DateTime.Now;            
  14.             Console.WriteLine($"Started: {started}");
  15.             cells = SolveIteration(cells);
  16.  
  17.             if (!IsSolved(cells))
  18.             {
  19.                 // Still not solved
  20.                 throw new InvalidOperationException("Can't solve sudoku");
  21.             }
  22.  
  23.             for (var y = 0; y < 9; y++)
  24.                 for (var x = 0; x < 9; x++)
  25.                 {
  26.                     board[x][y] = ((byte)cells[x][y]).ToString()[0];
  27.                 }
  28.            
  29.             Console.WriteLine();
  30.             Print(cells);
  31.  
  32.             var finished = DateTime.Now;
  33.             Console.WriteLine($"Finished: {finished}");
  34.             Console.WriteLine($"Total time: {(int)(finished - started).TotalHours}:{(finished - started).Minutes:D2}:{(finished - started).Seconds:D2}");
  35.             Console.ReadLine();
  36.         }
  37.  
  38.         public object[][] SolveIteration(object[][] board)
  39.         {
  40.             bool changed;
  41.             do
  42.             {
  43.                 changed = false;
  44.                 for (var y = 0; y < 9; y++)
  45.                     for (var x = 0; x < 9; x++)
  46.                     {
  47.                         if (board[x][y] is List<byte>)
  48.                             changed |= CalculatePossible(board, x, y);
  49.                         if (IsFailed(board))
  50.                             return null;
  51.                     }
  52.             } while (changed);
  53.  
  54.             if (IsSolved(board))
  55.             {
  56.                 return board;
  57.             }
  58.  
  59.             for (var y = 0; y < 9; y++)
  60.                 for (var x = 0; x < 9; x++)
  61.                 {
  62.                     if (board[x][y] is List<byte>)
  63.                         for (var l = 0; l < (board[x][y] as List<byte>).Count; l++)
  64.                         {
  65.                             var cloned = Clone(board);
  66.                             cloned[x][y] = (cloned[x][y] as List<byte>)[l];
  67.                             var solved = SolveIteration(cloned);
  68.                             if (solved != null)
  69.                                 return solved;
  70.                         }
  71.                 }
  72.  
  73.             return null;
  74.         }
  75.  
  76.         object[][] Clone(char[][] board)
  77.         {
  78.             var cells = new object[9][];
  79.             for (var x = 0; x < 9; x++)
  80.                 cells[x] = new object[9];
  81.             for (var y = 0; y < 9; y++)
  82.                 for (var x = 0; x < 9; x++)
  83.                 {
  84.                     if ((char)board[x][y] != '.')
  85.                         cells[x][y] = (byte)((char)board[x][y] - '0');
  86.                     else if ((char)board[x][y] == '.')
  87.                         cells[x][y] = new List<byte>() { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
  88.                 }
  89.             return cells;
  90.         }
  91.  
  92.         object[][] Clone(object[][] board)
  93.         {
  94.             var cells = new object[9][];
  95.             for (var x = 0; x < 9; x++)
  96.                 cells[x] = new object[9];
  97.             for (var y = 0; y < 9; y++)
  98.                 for (var x = 0; x < 9; x++)
  99.                 {
  100.                     if ((board[x][y] is char) && ((char)board[x][y] != '.'))
  101.                         cells[x][y] = (byte)((char)board[x][y] - '0');
  102.                     else if ((board[x][y] is char) && ((char)board[x][y] == '.'))
  103.                         cells[x][y] = new List<byte>() { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
  104.                     else if (board[x][y] is byte)
  105.                         cells[x][y] = board[x][y];
  106.                     else if (board[x][y] is List<byte>)
  107.                         cells[x][y] = new List<byte>((board[x][y] as List<byte>).ToArray());
  108.                     else
  109.                         throw new InvalidOperationException();
  110.                 }
  111.             return cells;
  112.         }
  113.  
  114.         bool CalculatePossible(object[][] board, int x, int y)
  115.         {
  116.             var orig = (board[x][y] as List<byte>).Count;
  117.             var possibles = new List<byte>() { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
  118.             for (var ly = 0; ly < 9; ly++)
  119.             {
  120.                 if (board[x][ly] is byte) possibles.Remove((byte)board[x][ly]);
  121.             }
  122.             for (var lx = 0; lx < 9; lx++)
  123.             {
  124.                 if (board[lx][y] is byte) possibles.Remove((byte)board[lx][y]);
  125.             }
  126.             for (var ly = 0; ly < 3; ly++)
  127.                 for (var lx = 0; lx < 3; lx++)
  128.                 {
  129.                     var rx = x / 3 * 3 + lx;
  130.                     var ry = y / 3 * 3 + ly;
  131.                     if (board[rx][ry] is byte)
  132.                         possibles.Remove((byte)board[rx][ry]);
  133.                 }
  134.             board[x][y] = possibles;
  135.             if (possibles.Count > 1)
  136.             {
  137.                 return (board[x][y] as List<byte>).Count != orig;
  138.             }
  139.             else if (possibles.Count == 1)
  140.             {
  141.                 board[x][y] = possibles.Single();
  142.                 return true;
  143.             }
  144.  
  145.             return false;
  146.         }
  147.  
  148.         bool IsSolved(object[][] board) => !IsFailed(board) && !board.SelectMany(x => x).Where(c => c is List<byte>).Any();
  149.  
  150.         bool IsFailed(object[][] board) => board.SelectMany(x => x).Where(c => (c is List<byte>) && (c as List<byte>).Count == 0).Any();
  151.  
  152.         void Print(object[][] board)
  153.         {
  154.             for (var y = 0; y < 9; y++)
  155.             {
  156.                 for (var x = 0; x < 9; x++)
  157.                 {
  158.                     if (board[x][y] is byte)
  159.                         Console.Write(board[x][y]);
  160.                     else
  161.                         Console.Write('.');
  162.                     if ((x % 3) == 2)
  163.                         Console.Write(' ');
  164.                 }
  165.                 Console.WriteLine();
  166.                 if ((y % 3) == 2)
  167.                     Console.WriteLine();
  168.             }
  169.         }
  170.     }
  171.  
  172.     class Program
  173.     {
  174.         static void Main(string[] args)
  175.         {
  176.             /*
  177.             var board = new char[][] {
  178.                     new char[] { '5', '3', '.', '.', '7', '.', '.', '.', '.'},
  179.                     new char[] { '6', '.', '.', '1', '9', '5', '.', '.', '.'},
  180.                     new char[] { '.', '9', '8', '.', '.', '.', '.', '6', '.'},
  181.                     new char[] { '8', '.', '.', '.', '6', '.', '.', '.', '3'},
  182.                     new char[] { '4', '.', '.', '8', '.', '3', '.', '.', '1'},  
  183.                     new char[] { '7', '.', '.', '.', '2', '.', '.', '.', '6'},
  184.                     new char[] { '.', '6', '.', '.', '.', '.', '2', '8', '.'},
  185.                     new char[] { '.', '.', '.', '4', '1', '9', '.', '.', '5'},
  186.                     new char[] { '.', '.', '.', '.', '8', '.', '.', '7', '9'}
  187.                 };
  188.             */
  189.  
  190.             /*
  191.             var board = new char[][]
  192.             {
  193.                 new char[] {'.', '.', '9', '7', '4', '8', '.', '.', '.'},
  194.                 new char[] {'7', '.', '.', '.', '.', '.', '.', '.', '.'},
  195.                 new char[] {'.', '2', '.', '1', '.', '9', '.', '.', '.'},
  196.                 new char[] {'.', '.', '7', '.', '.', '.', '2', '4', '.'},
  197.                 new char[] {'.', '6', '4', '.', '1', '.', '5', '9', '.'},
  198.                 new char[] {'.', '9', '8', '.', '.', '.', '3', '.', '.'},
  199.                 new char[] {'.', '.', '.', '8', '.', '3', '.', '2', '.'},
  200.                 new char[] {'.', '.', '.', '.', '.', '.', '.', '.', '6'},
  201.                 new char[] {'.', '.', '.', '2', '7', '5', '9', '.', '.'}
  202.             };
  203.             */
  204.  
  205.             var board = new char[][]
  206.             {
  207.                 new char[] {'.', '.', '.', '2', '.', '.', '.', '6', '3'},
  208.                 new char[] {'3', '.', '.', '.', '.', '5', '4', '.', '1'},
  209.                 new char[] {'.', '.', '1', '.', '.', '3', '9', '8', '.'},
  210.                 new char[] {'.', '.', '.', '.', '.', '.', '.', '9', '.'},
  211.                 new char[] {'.', '.', '.', '5', '3', '8', '.', '.', '.'},
  212.                 new char[] {'.', '3', '.', '.', '.', '.', '.', '.', '.'},
  213.                 new char[] {'.', '2', '6', '3', '.', '.', '5', '.', '.'},
  214.                 new char[] {'5', '.', '3', '7', '.', '.', '.', '.', '8'},
  215.                 new char[] {'4', '7', '.', '.', '.', '1', '.', '.', '.'}
  216.             };
  217.  
  218.             var solver = new Solution();
  219.             solver.SolveSudoku(board);
  220.         }
  221.     }
  222. }
  223.  
RAW Paste Data