C# 实现数独游戏

1.数独单元

 public struct SudokuCell{public SudokuCell() : this(0, 0, 0){}public SudokuCell(int x, int y, int number){X = x; Y = y; Number = number;}public int X { get; set; }public int Y { get; set; }public int Number { get; set; }}

2.数独创建

public class SudokuGenerator{private const int BoardSize = 9;private const int EmptyCellValue = 0;private Random random;private readonly ChaosRandomEx chaosRandomEx;public SudokuGenerator(){random = new Random();chaosRandomEx = new ChaosRandomEx();}public SudokuCell[,] GenerateSudoku(DifficultyLevel difficulty){SudokuCell[,] board = new SudokuCell[BoardSize, BoardSize];// 初始化数独网格for (int row = 0; row < BoardSize; row++){for (int col = 0; col < BoardSize; col++){board[row, col] = new SudokuCell(row, col, EmptyCellValue);}}// 填充数独网格FillSudoku(board);// 根据难度要求移除部分单元格的值RemoveCells(board, difficulty);return board;}private void FillSudoku(SudokuCell[,] board){SolveSudoku(board);}private bool SolveSudoku(SudokuCell[,] board){int row = 0;int col = 0;if (!FindEmptyCell(board, ref row, ref col)){// 所有单元格都已填满，数独已解决return true;}List<int> numbers = GetRandomNumberSequence();foreach (int num in numbers){if (IsValidMove(board, row, col, num)){// 尝试填充数字board[row, col].Number = num;if (SolveSudoku(board)){// 递归解决剩余的单元格return true;}// 回溯到上一个单元格board[row, col].Number = EmptyCellValue;}}return false;}private bool FindEmptyCell(SudokuCell[,] board, ref int row, ref int col){for (row = 0; row < BoardSize; row++){for (col = 0; col < BoardSize; col++){if (board[row, col].Number == EmptyCellValue){return true;}}}return false;}public bool IsValidMove(SudokuCell[,] board, int row, int col, int num){// 检查行是否合法for (int i = 0; i < BoardSize; i++){if (board[i, col].Number == num){return false;}}// 检查列是否合法for (int i = 0; i < BoardSize; i++){if (board[row, i].Number == num){return false;}}// 检查子网格是否合法int subgridRow = (row / 3) * 3;int subgridCol = (col / 3) * 3;for (int i = 0; i < 3; i++){for (int j = 0; j < 3; j++){if (board[subgridRow + i, subgridCol + j].Number == num){return false;}}}return true;}private List<int> GetRandomNumberSequence(){List<int> numbers = new List<int> { 1, 2, 3, 4, 5, 6, 7, 8, 9 };Shuffle(numbers);return numbers;}private void Shuffle<T>(List<T> list){int n = list.Count;while (n > 1){n--;int k = random.Next(n + 1);T value = list[k];list[k] = list[n];list[n] = value;}}private void RemoveCells(SudokuCell[,] board, DifficultyLevel difficulty){int cellsToRemove = GetCellsToRemoveCount(difficulty);for (int i = 0; i < cellsToRemove; i++){int row = random.Next(BoardSize);int col = random.Next(BoardSize);if (board[row, col].Number != EmptyCellValue){board[row, col].Number = EmptyCellValue;}else{i--;}}}private int GetCellsToRemoveCount(DifficultyLevel difficulty){return difficulty switch{DifficultyLevel.Medium => 32,DifficultyLevel.Hard => 44,DifficultyLevel.VeryHard => 56,DifficultyLevel.SuperHard => 68,DifficultyLevel.Insane => 80,_ => 20};}}

3.数独难度等级

public enum DifficultyLevel{/// <summary>/// 简单/// </summary>[Remark("简单")]Easy,/// <summary>/// 中等/// </summary>[Remark("中等")]Medium,/// <summary>/// 困难/// </summary>[Remark("困难")]Hard,/// <summary>/// 极难/// </summary>[Remark("极难")]VeryHard,/// <summary>/// 超难/// </summary>[Remark("超难")]SuperHard,/// <summary>/// 疯狂/// </summary>[Remark("疯狂")]Insane}

4.递归回溯算法寻找答案

/// <summary>/// 递归回溯算法/// </summary>public class SudokuSolver{public SudokuCell[,] SolveSudoku(SudokuCell[,] board){var solution = new SudokuCell[board.GetLength(0), board.GetLength(1)];Array.Copy(board, solution, board.Length);if (BacktrackSolve(solution)){return solution;}else{// 没有找到解return null;}}private bool BacktrackSolve(SudokuCell[,] board){for (int row = 0; row < 9; row++){for (int col = 0; col < 9; col++){if (board[row, col].Number == 0){for (int num = 1; num <= 9; num++){if (IsValid(board, row, col, num)){board[row, col].Number = num;if (BacktrackSolve(board)){return true;}board[row, col].Number = 0; // 回溯}}return false; // 所有数字都尝试过，没有找到合适的解}}}return true; // 数独已经填满，找到解}private bool IsValid(SudokuCell[,] board, int row, int col, int num){// 检查同行是否有重复数字for (int i = 0; i < 9; i++){if (board[row, i].Number == num){return false;}}// 检查同列是否有重复数字for (int i = 0; i < 9; i++){if (board[i, col].Number == num){return false;}}// 检查同九宫格是否有重复数字int startRow = row - row % 3;int startCol = col - col % 3;for (int i = 0; i < 3; i++){for (int j = 0; j < 3; j++){if (board[startRow + i, startCol + j].Number == num){return false;}}}return true; // 没有重复数字}}

5.数独创建中心

public class SudokuCenter : IDisposable{public bool IsStart { get; set; } = false;private int _width;private int _height;public const int CELLSNUMBER = 9;public const int CELLSNUMBER2 = 20;private int _cellSize;private int _rowSize;public int CellSize=> _cellSize;public int RowSize => _rowSize;public int Height => _height;public int Width => _width;public int Padding => CELLSNUMBER2;private Bitmap _bitmap;public Bitmap GetBitmap{get=>(Bitmap)_bitmap?.Clone();private set => _bitmap = value;}public SudokuCell[,] Suduku { get;private set; }public SudokuCell[,] PlayerSuduku { get; private set; }/// <summary>/// 生成棋盘图/// </summary>/// <param name="w"></param>/// <param name="h"></param>public void InitCheckerBoard(int w, int h){w -= (CELLSNUMBER2 * 2 + 1);h -= (CELLSNUMBER2 * 2 + 1);_width = w;_height = h;_cellSize = _width / CELLSNUMBER;_rowSize = _height / CELLSNUMBER;Bitmap bitmap = new Bitmap(_width + CELLSNUMBER2, _height + CELLSNUMBER2);using (var g = Graphics.FromImage(bitmap)){g.SmoothingMode = SmoothingMode.AntiAlias;//g.Clear(Color.Gray);DrawCheckerBoard(g);}_bitmap?.Dispose();GetBitmap = bitmap;}public SudokuCell[,] GenerateSudoku(DifficultyLevel difficulty){SudokuGenerator sudokuGenerator = new SudokuGenerator();Suduku = sudokuGenerator.GenerateSudoku(difficulty);PlayerSuduku = new SudokuCell[Suduku.GetLength(0), Suduku.GetLength(1)];Array.Copy(Suduku, PlayerSuduku, Suduku.Length);return Suduku;}public Color SudukuColor { get; set; }= Color.Black;public Color SolutionColor { get; set; } = Color.Red;public Color TransparentColor { get; } = Color.Transparent;public Font Font { get; set; }= new Font("Arial", 20, FontStyle.Bold);public Bitmap DrawSolution(SudokuCell[,] board){using SolidBrush brush = new SolidBrush(SolutionColor);using SolidBrush brush2 = new SolidBrush(SudukuColor);var bm = GetBitmap;using var g = Graphics.FromImage(bm);for (int row = 0; row < CELLSNUMBER; row++){for (int col = 0; col < CELLSNUMBER; col++){int number = Suduku[row, col].Number;if (number != 0){DrawString(g, row, col, number.ToString(), brush2);}else{number = board[row, col].Number;DrawString(g, row, col, number.ToString(), brush);}}}return bm;}public void DrawSudoku(Graphics g, SudokuCell[,] board){using SolidBrush brush = new SolidBrush(SudukuColor);for (int row = 0; row < CELLSNUMBER; row++){for (int col = 0; col < CELLSNUMBER; col++){int num= board[row, col].Number;if((num != 0)){DrawString(g,row,col,num.ToString(), brush);}}}}public void DrawString(Graphics g,int row,int col,string number, SolidBrush brush){int x = CELLSNUMBER2 + col * _cellSize + _cellSize / 2 - 8;int y = CELLSNUMBER2 + row * _rowSize + _rowSize / 2 - 10;g.DrawString(number, Font, brush, new Point(x, y));}public Rectangle DrawTransparent(Graphics g, int row, int col){int off = 5;int off2 = 7;int x = CELLSNUMBER2 + col * _cellSize + off;int y = CELLSNUMBER2 + row * _rowSize+ off;using (SolidBrush brush = new SolidBrush(Color.White)) // 使用透明色进行擦除{var rec = new Rectangle(x, y, CellSize - off2, RowSize - off2);g.FillRectangle(brush, rec);return rec;}}public bool IsSolutionCorrect(SudokuCell[,] board, SudokuCell[,] solution){for (int row = 0; row < CELLSNUMBER; row++){for (int col = 0; col < CELLSNUMBER; col++){if (board[row, col].Number != solution[row, col].Number){return false;}}}return true;}public bool IsValidMove(SudokuCell[,] board, int row, int col, int num){// 检查行是否合法for (int i = 0; i < CELLSNUMBER; i++){if (board[i, col].Number == num){return false;}}// 检查列是否合法for (int i = 0; i < CELLSNUMBER; i++){if (board[row, i].Number == num){return false;}}// 检查子网格是否合法int subgridRow = (row / 3) * 3;int subgridCol = (col / 3) * 3;for (int i = 0; i < 3; i++){for (int j = 0; j < 3; j++){if (board[subgridRow + i, subgridCol + j].Number == num){return false;}}}return true;}private void DrawCheckerBoard(Graphics g){using Pen pen = new Pen(Color.Black, 1);using Pen pen2 = new Pen(Color.Black, 2);using Font font = new Font("Arial", 10, FontStyle.Regular);using SolidBrush brush = new SolidBrush(Color.Black);for (int i = 0; i < CELLSNUMBER + 1; i++){if (i == 0 || i % 3 == 0){g.DrawLine(pen2, new Point(CELLSNUMBER2, CELLSNUMBER2 + i * _rowSize), new Point(CELLSNUMBER2 + _cellSize * CELLSNUMBER, CELLSNUMBER2 + i * _rowSize));g.DrawLine(pen2, new Point(CELLSNUMBER2 + i * _cellSize, CELLSNUMBER2 + 0), new Point(CELLSNUMBER2 + i * _cellSize, CELLSNUMBER2 + _rowSize * CELLSNUMBER));}else{g.DrawLine(pen, new Point(CELLSNUMBER2, CELLSNUMBER2 + i * _rowSize), new Point(CELLSNUMBER2 + _cellSize * CELLSNUMBER, CELLSNUMBER2 + i * _rowSize));g.DrawLine(pen, new Point(CELLSNUMBER2 + i * _cellSize, CELLSNUMBER2 + 0), new Point(CELLSNUMBER2 + i * _cellSize, CELLSNUMBER2 + _rowSize * CELLSNUMBER));}int x = CELLSNUMBER2 + i * _cellSize + _cellSize / 2 - 5;int y = 0;g.DrawString((i + 1).ToString(), font, brush, new Point(x, y));x = 0;y = CELLSNUMBER2 + i * _rowSize + _rowSize / 2 - 5;g.DrawString((i + 1).ToString(), font, brush, new Point(x, y));}}public void Dispose(){_bitmap?.Dispose();}}

 6.数字键盘

 

 public partial class FrmNumber : Form{public FrmNumber(){InitializeComponent();foreach (Control item in this.Controls){item.Click += Item_Click;}}public Action<NumberArg> NumberCallback;public Point ClickPoint {  get; set; }public Point RowCell { get; set; }public Graphics Graphics { get; set; }private void Item_Click(object? sender, EventArgs e){Button btn = sender as Button;NumberArg numberArg = new NumberArg();if (btn.Name == "btnClear"){numberArg.Type = NumberType.Clear;}else if (btn.Name == "btnClose"){numberArg.Type = NumberType.Close;}else{numberArg.Type = NumberType.Number;numberArg.Value = btn.Text;}numberArg.CllickPoint = ClickPoint;numberArg.RowCell = RowCell;numberArg.Graphics = Graphics;NumberCallback?.Invoke(numberArg);this.Close();}private void FrmNumber_FormClosing(object sender, FormClosingEventArgs e){this.Dispose();}}public struct NumberArg{public NumberType Type { get; set; }public string Value { get; set; }public Point CllickPoint { get; set; }public Graphics Graphics { get; set; }public Point RowCell { get; set; }}public enum NumberType{Clear,Close,Number}

7.主窗体 

 

public partial class FrmMain : Form{private SudokuCenter _sudokuCenter;private System.Windows.Forms.Timer _timer;public FrmMain(){InitializeComponent();this.SetStyle(ControlStyles.DoubleBuffer | ControlStyles.OptimizedDoubleBuffer |ControlStyles.UserPaint |ControlStyles.AllPaintingInWmPaint,true);this.UpdateStyles();this.DoubleBuffered = true;_sudokuCenter = new SudokuCenter();_sudokuCenter.InitCheckerBoard(this.pbGameBack.Width, this.pbGameBack.Height);BindType(typeof(DifficultyLevel), this.cbDifficultyLevel, "Easy");}private void BindType(Type type, ComboBox comboBox, string defaultValue){var enumValues = Enum.GetValues(type);var list = new List<IdValues>();int index = 0, curIndex = 0;foreach (Enum value in enumValues){int hc = value.GetHashCode();list.Add(new IdValues{Id = hc.ToString(),Value = value.ToString(),Display= value.GetEnumDesc(),Standby = hc});if (value.ToString() == defaultValue)index = curIndex;curIndex++;}comboBox.ValueMember = "Id";comboBox.DisplayMember = "Display";comboBox.DataSource = list;comboBox.SelectedIndex = index;}private void pbGameBack_Paint(object sender, PaintEventArgs e){if (sudukuBitmap != null){e.Graphics.DrawImage(sudukuBitmap, 0, 0, pbGameBack.Width, pbGameBack.Height);}}public string Compute(long time){if (time < 60)return $"00:{ChangeString(time)}";long minute = time / 60;if (minute < 60)return $"{ChangeString(minute)}:{ChangeString(time % 60)}";long hour = minute / 60;return $"{ChangeString(hour)}:{Compute(time - hour * 3600)}";}private string ChangeString(long val){return val.ToString("D2");}/// <summary>/// 开始/// </summary>/// <param name="sender"></param>/// <param name="e"></param>private void btnStart_Click(object sender, EventArgs e){StartGame();}Bitmap sudukuBitmap;private void StartGame(){if (_sudokuCenter.IsStart){if (MessageBox.Show("你正在开始游戏，确认重新开始吗？", "提示", MessageBoxButtons.OKCancel, MessageBoxIcon.Question) == DialogResult.Cancel){return;}}if (_timer != null){_timer.Stop();_timer.Dispose();}time = 0;_timer = new System.Windows.Forms.Timer();_timer.Interval = 1000;_timer.Tick += timer_Tick;_timer.Start();DifficultyLevel level = (DifficultyLevel)(this.cbDifficultyLevel.Items[cbDifficultyLevel.SelectedIndex] as IdValues).Standby;var sudoku = _sudokuCenter.GenerateSudoku(level);this.pbGameBack.Image?.Dispose();sudukuBitmap?.Dispose();sudukuBitmap = null;sudukuBitmap = _sudokuCenter.GetBitmap;using var g = Graphics.FromImage(sudukuBitmap);_sudokuCenter.DrawSudoku(g, sudoku);_sudokuCenter.IsStart = true;pbGameBack.Invalidate();}long time = 0;private void timer_Tick(object? sender, EventArgs e){lblTime.ExecBeginInvoke(() =>{lblTime.Text = Compute(++time);});}/// <summary>/// 答案/// </summary>/// <param name="sender"></param>/// <param name="e"></param>private void btnSolution_Click(object sender, EventArgs e){if (!_sudokuCenter.IsStart){return;}if (MessageBox.Show("你正在开始游戏，确认显示答案吗？", "提示", MessageBoxButtons.OKCancel, MessageBoxIcon.Question) == DialogResult.Cancel){return;}SudokuSolver sudokuSolver = new SudokuSolver();var solveSudoku = sudokuSolver.SolveSudoku(_sudokuCenter.Suduku);var bm = _sudokuCenter.DrawSolution(solveSudoku);pbGameBack.Image?.Dispose();sudukuBitmap?.Dispose();sudukuBitmap = null;sudukuBitmap = bm;//pbGameBack.Image = bm;_sudokuCenter.IsStart = false;pbGameBack.Invalidate();}private void pbGameBack_MouseDown(object sender, MouseEventArgs e){if (_sudokuCenter.Suduku == null || !_sudokuCenter.IsStart)return;int row = (e.Y - _sudokuCenter.Padding * 2) / _sudokuCenter.RowSize;int col = (e.X - _sudokuCenter.Padding * 2) / _sudokuCenter.CellSize;// 检测鼠标是否在小方格内if (row >= 0 && row < 9 && col >= 0 && col < 9){var number = _sudokuCenter.Suduku[row, col].Number;if (number != 0)return;using (FrmNumber fn = new FrmNumber()){fn.NumberCallback = NumberCallback;Point p = pbGameBack.PointToScreen(Point.Empty);fn.StartPosition = FormStartPosition.Manual;fn.Location = new Point(p.X + e.X + (_sudokuCenter.CellSize >> 1), p.Y + e.Y + (_sudokuCenter.RowSize >> 1));fn.ClickPoint = new Point(e.X, e.Y);fn.RowCell = new Point(row, col);fn.ShowDialog();}}}private void NumberCallback(NumberArg arg){switch (arg.Type){case NumberType.Number:DrawString(arg.RowCell.X, arg.RowCell.Y, arg.Value);int num = Convert.ToInt32(arg.Value);if (cbPrompt.Checked){bool status = _sudokuCenter.IsValidMove(_sudokuCenter.PlayerSuduku, arg.RowCell.X, arg.RowCell.Y, num);lblPrompt.Text = status ? "你真棒！" : "重复了";}else{lblPrompt.Text = "已写入";}_sudokuCenter.PlayerSuduku[arg.RowCell.X, arg.RowCell.Y].Number = num;pbGameBack.Invalidate(new Rectangle(SudokuCenter.CELLSNUMBER2 + arg.RowCell.Y * _sudokuCenter.CellSize, SudokuCenter.CELLSNUMBER2 + arg.RowCell.X * _sudokuCenter.RowSize, SudokuCenter.CELLSNUMBER2 + _sudokuCenter.CellSize, SudokuCenter.CELLSNUMBER2 + _sudokuCenter.RowSize));break;case NumberType.Clear:using (var g = Graphics.FromImage(sudukuBitmap)){_sudokuCenter.PlayerSuduku[arg.RowCell.X, arg.RowCell.Y].Number = 0;var rec= _sudokuCenter.DrawTransparent(g, arg.RowCell.X, arg.RowCell.Y);lblPrompt.Text = "已清除";pbGameBack.Invalidate(rec);}break;}}private void DrawString(int row, int col, string num){using (var g = Graphics.FromImage(sudukuBitmap)){using SolidBrush brush = new SolidBrush(_sudokuCenter.SolutionColor);_sudokuCenter.DrawTransparent(g, row, col);_sudokuCenter.DrawString(g, row, col, num, brush);}}private void DrawString(Graphics g, int row, int col, string num){using SolidBrush brush = new SolidBrush(_sudokuCenter.SolutionColor);_sudokuCenter.DrawTransparent(g, row, col);_sudokuCenter.DrawString(g, row, col, num, brush);pbGameBack.Invalidate(new Rectangle(SudokuCenter.CELLSNUMBER2 + col * _sudokuCenter.CellSize, SudokuCenter.CELLSNUMBER2 + row * _sudokuCenter.RowSize, _sudokuCenter.CellSize, _sudokuCenter.RowSize));}/// <summary>/// 提交/// </summary>/// <param name="sender"></param>/// <param name="e"></param>private void btnSubmit_Click(object sender, EventArgs e){if (!_sudokuCenter.IsStart){return;}if (MessageBox.Show("你正在开始游戏，确认提交答案吗？", "提示", MessageBoxButtons.OKCancel, MessageBoxIcon.Question) == DialogResult.Cancel){return;}_timer.Stop();SudokuSolver sudokuSolver = new SudokuSolver();var solveSudoku = sudokuSolver.SolveSudoku(_sudokuCenter.Suduku);bool status = _sudokuCenter.IsSolutionCorrect(_sudokuCenter.PlayerSuduku, solveSudoku);if (status){lblPrompt.Text = "全对了，你真棒！";MessageBox.Show("全对了，你真棒！", "恭喜");}else{lblPrompt.Text = "很遗憾，有错误！";MessageBox.Show("很遗憾，有错误！", "失败");for (int row = 0; row < SudokuCenter.CELLSNUMBER; row++){for (int col = 0; col < SudokuCenter.CELLSNUMBER; col++){if (solveSudoku[row, col].Number != _sudokuCenter.PlayerSuduku[row, col].Number){this.DrawString(row, col, solveSudoku[row, col].Number.ToString());}}}pbGameBack.Invalidate();}_sudokuCenter.IsStart = false;}/// <summary>/// 重新开始/// </summary>/// <param name="sender"></param>/// <param name="e"></param>private void btnRestart_Click(object sender, EventArgs e){StartGame();}private void FrmMain_FormClosing(object sender, FormClosingEventArgs e){_sudokuCenter.Dispose();this.pbGameBack.Image?.Dispose();this.pbGameBack.Dispose();if (_timer != null){_timer.Stop();_timer.Dispose();}this.Dispose();}}

8.其它

 public class RemarkAttribute : Attribute{/// <summary>/// 备注/// </summary>public string Remark { get; set; }public RemarkAttribute(string remark){this.Remark = remark;}}public static class EnumEx{/// <summary>/// 根据枚举元素,获取该枚举元素的描述信息/// </summary>/// <typeparam name="T"></typeparam>/// <param name="tField"></param>/// <returns></returns>public static string GetEnumDesc<T>(this T tField) where T : Enum{var description = string.Empty; //结果var inputType = tField.GetType(); //输入的类型var descType = typeof(RemarkAttribute); //目标查找的描述类型var fieldStr = tField.ToString();                //输入的字段字符串var field = inputType.GetField(fieldStr);        //目标字段var isDefined = field?.IsDefined(descType, false);//判断描述是否在字段的特性if (isDefined ?? false){var enumAttributes = field.GetCustomAttributes(descType, false) as RemarkAttribute[];  //得到特性信息description = enumAttributes?.FirstOrDefault()?.Remark ?? string.Empty;//  description = string.Join(',', enumAttributes?.Select(t => t.Remark));}return description;}}

 

 public class IdValues{public string Id { get; set; }public string Value { get; set; }public string Value2 { get; set; }public string Value3 { get; set; }public string Value4 { get; set; }public string Value5 { get; set; }public int Standby { get; set; }public string Display { get; set; }public static bool operator ==(IdValues idValues, IdValues idValues2){return idValues.Equals(idValues2);}public static bool operator !=(IdValues idValues, IdValues idValues2){return !idValues.Equals(idValues2);}public override int GetHashCode(){var code = (Id, Value, Value2, Value3, Value4, Value5, Standby).GetHashCode();return code;}public override bool Equals(object? obj){return obj?.GetHashCode() == GetHashCode();}const int TARGET = 0x1F;/// <summary>/// 将连续字段的哈希代码左移两位或更多位来加权各个哈希代码(最佳情况下，超出位 31 的位应环绕，而不是被丢弃)/// </summary>/// <param name="value"></param>/// <param name="positions"></param>/// <returns></returns>public int ShiftAndWrap(int value, int positions = 3){positions &= TARGET;uint number = BitConverter.ToUInt32(BitConverter.GetBytes(value), 0);uint wrapped = number >> (32 - positions);return BitConverter.ToInt32(BitConverter.GetBytes((number << positions) | wrapped), 0);}}

 

 internal static class SystemEx{/// <summary>/// 跨线程操作控件/// </summary>/// <param name="con"></param>/// <param name="action"></param>public static void ExecBeginInvoke(this Control con, Action action){if (action == null) return;if (con.InvokeRequired){con.BeginInvoke(new Action(action));}else{action();}}/// <summary>/// 跨线程操作控件/// </summary>/// <param name="con"></param>/// <param name="action"></param>public static void ExecInvoke(this Control con, Action action){if (action == null) return;if (con.InvokeRequired){con.Invoke(new Action(action));}else{action();}}}